Module Name: src Committed By: rmind Date: Wed Aug 28 20:08:11 UTC 2019
Added Files: src/share/man/man9: thmap.9 Log Message: Add thmap(9) man page. Reviewed by wiz@. Forgot to commit it half a year ago. To generate a diff of this commit: cvs rdiff -u -r0 -r1.1 src/share/man/man9/thmap.9 Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Added files: Index: src/share/man/man9/thmap.9 diff -u /dev/null src/share/man/man9/thmap.9:1.1 --- /dev/null Wed Aug 28 20:08:11 2019 +++ src/share/man/man9/thmap.9 Wed Aug 28 20:08:11 2019 @@ -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 rm...@noxt.eu