[src/trunk]: src/share/man/man9 Add thmap(9) man page. Reviewed by wiz@.

[rmind <rmind%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/53005d4d7c78
branches:  trunk
changeset: 459167:53005d4d7c78
user:      rmind <rmind%NetBSD.org@localhost>
date:      Wed Aug 28 20:08:11 2019 +0000

description:
Add thmap(9) man page.  Reviewed by wiz@.
Forgot to commit it half a year ago.

diffstat:

 share/man/man9/thmap.9 |  236 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 236 insertions(+), 0 deletions(-)

diffs (240 lines):

diff -r 5af0a63bd6ba -r 53005d4d7c78 share/man/man9/thmap.9
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/share/man/man9/thmap.9    Wed Aug 28 20:08:11 2019 +0000
@@ -0,0 +1,236 @@
+.\"
+.\" Copyright (c) 2018 Mindaugas Rasiukevicius <rmind at noxt eu>
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.Dd December 11, 2018
+.Dt THMAP 9
+.Os
+.Sh NAME
+.Nm thmap
+.Nd concurrent trie-hash map
+.Sh SYNOPSIS
+.In thmap.h
+.\" -----
+.Ft thmap_t *
+.Fn thmap_create "uintptr_t baseptr" "const thmap_ops_t *ops" "unsigned flags"
+.Ft void
+.Fn thmap_destroy "thmap_t *hmap"
+.Ft void *
+.Fn thmap_get "thmap_t *hmap" "const void *key" "size_t len"
+.Ft void *
+.Fn thmap_put "thmap_t *hmap" "const void *key" "size_t len" "void *val"
+.Ft void *
+.Fn thmap_del "thmap_t *hmap" "const void *key" "size_t len"
+.Ft void *
+.Fn thmap_stage_gc "thmap_t *hmap"
+.Ft void
+.Fn thmap_gc "thmap_t *hmap" "void *ref"
+.Ft void
+.Fn thmap_setroot "thmap_t *thmap" "uintptr_t root_offset"
+.Ft uintptr_t
+.Fn thmap_getroot "const thmap_t *thmap"
+.\" -----
+.Sh DESCRIPTION
+Concurrent trie-hash map \(em a general purpose associative array,
+combining the elements of hashing and radix trie.
+Highlights:
+.Pp
+.Bl -hyphen -compact
+.It
+Very competitive performance, with logarithmic time complexity on average.
+.It
+Lookups are lock-free and inserts/deletes are using fine-grained locking.
+.It
+Incremental growth of the data structure (no large resizing/rehashing).
+.It
+Optional support for use with shared memory, e.g. memory-mapped file.
+.El
+.Pp
+Delete operations (the key/data destruction) must be synchronized with
+the readers using some reclamation mechanism.
+.\" -----
+.Sh FUNCTIONS
+.Bl -tag -width thmap_create
+.It Fn thmap_create
+Construct a new trie-hash map.
+The optional
+.Fa ops
+parameter can
+used to set the custom allocate/free operations (see the description of
+.Vt thmap_ops_t
+below).
+In such case, the
+.Fa baseptr
+is the base (start) address of the address space mapping (it must be
+word-aligned).
+If
+.Fa ops
+is set to
+.Dv NULL ,
+then
+.Xr malloc 3
+and
+.Xr free 3
+will be used as the default operations and
+.Fa baseptr
+should be set to zero.
+Currently, the supported
+.Fa flags
+are:
+.Bl -tag -width THMAP_NOCOPY
+.It Dv THMAP_NOCOPY
+The keys on insert will not be copied and the given pointers to them will
+be expected to be valid and the values constant until the key is deleted;
+by default, the put operation will make a copy of the key.
+.It Dv THMAP_SETROOT
+Indicate that the root of the map will be manually set using the
+.Fn thmap_setroot
+routine;
+by default, the map is initialized and the root node is set on
+.Fn thmap_create .
+.El
+.\" ---
+.It Fn thmap_destroy
+Destroy the map, freeing the memory it uses.
+.\" ---
+.It Fn thmap_get
+Lookup the key (of a given length) and return the value associated with it.
+Return
+.Dv NULL
+if the key is not found (see the
+.Sx CAVEATS
+section).
+.\" ---
+.It Fn thmap_put
+Insert the key with an arbitrary value.
+If the key is already present, return the already existing associated value
+without changing it.
+Otherwise, on a successful insert, return the given value.
+Just compare the result against
+.Fa val
+to test whether the insert was successful.
+.\" ---
+.It Fn thmap_del
+Remove the given key.
+If the key was present, return the associated value;
+otherwise return
+.Dv NULL .
+The memory associated with the entry is not released immediately, because
+in the concurrent environment (e.g., multi-threaded application) the caller
+may need to ensure it is safe to do so.
+It is managed using the
+.Fn thmap_stage_gc
+and
+.Fn thmap_gc
+routines.
+.\" ---
+.It Fn thmap_stage_gc
+Stage the currently pending entries (the memory not yet released after
+the deletion) for reclamation (G/C).
+This operation should be called
+.Em before
+the synchronization barrier.
+.Pp
+Returns a reference which must be passed to
+.Fn thmap_gc .
+Not calling the G/C function for the returned reference would result in
+a memory leak.
+.\" ---
+.It Fn thmap_gc
+Reclaim (G/C) the staged entries i.e. release any memory associated
+with the deleted keys.
+The reference must be the value returned by the call to
+.Fn thmap_stage_gc .
+.Pp
+This function must be called
+.Em after
+the synchronization barrier which guarantees that there are no active
+readers referencing the staged entries.
+.\" ---
+.El
+.Pp
+If the map is created using the
+.Fa THMAP_SETROOT
+flag, then the following functions are applicable:
+.\" ---
+.Bl -tag -width thmap_setroot
+.It Fn thmap_setroot
+Set the root node.
+The address must be relative to the base address, as if allocated by the
+.Fn thmap_ops_t::alloc
+routine.
+Return 0 on success and \-1 on failure (if already set).
+.It Fn thmap_getroot
+Get the root node address.
+The returned address will be relative to the base address.
+.El
+.\" ---
+.Pp
+Members of
+.Vt thmap_ops_t
+are
+.Bd -literal
+        uintptr_t (*alloc)(size_t len);
+        void      (*free)(uintptr_t addr, size_t len);
+.Ed
+.\" -----
+.Sh CAVEATS
+The implementation uses pointer tagging and atomic operations.
+This requires the base address and the allocations to provide at least word
+alignment.
+.Pp
+While the
+.Dv NULL
+values may be inserted,
+.Fn thmap_get
+and
+.Fn thmap_del
+cannot indicate whether the key was not found or a key with a
+.Dv NULL
+value was found.
+If the caller needs to indicate an "empty" value, it can use a
+special pointer value, such as
+.Li (void *)(uintptr_t)0x1 .
+.\" -----
+.Sh EXAMPLES
+Simple case backed by
+.Xr malloc 3 ,
+which could be used in multi-threaded environment:
+.Bd -literal
+       thmap_t *kvmap;
+       struct obj *obj;
+
+       kvmap = thmap_create(0, NULL);
+       assert(kvmap != NULL);
+       ...
+       obj = obj_create();
+       thmap_put(kvmap, "test", sizeof("test") - 1, obj);
+       ...
+       obj = thmap_get(kvmap, "test", sizeof("test") - 1);
+       ...
+       thmap_destroy(kvmap);
+.Ed
+.\" -----
+.Sh AUTHORS
+.An Mindaugas Rasiukevicius Aq Mt rmind%noxt.eu@localhost