1.\" $NetBSD: thmap.9,v 1.3 2020/08/28 07:03:41 riastradh Exp $ 2.\" 3.\" Copyright (c) 2018 Mindaugas Rasiukevicius <rmind at noxt eu> 4.\" All rights reserved. 5.\" 6.\" Redistribution and use in source and binary forms, with or without 7.\" modification, are permitted provided that the following conditions 8.\" are met: 9.\" 1. Redistributions of source code must retain the above copyright 10.\" notice, this list of conditions and the following disclaimer. 11.\" 2. Redistributions in binary form must reproduce the above copyright 12.\" notice, this list of conditions and the following disclaimer in the 13.\" documentation and/or other materials provided with the distribution. 14.\" 15.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25.\" SUCH DAMAGE. 26.\" 27.Dd December 11, 2018 28.Dt THMAP 9 29.Os 30.Sh NAME 31.Nm thmap 32.Nd concurrent trie-hash map 33.Sh SYNOPSIS 34.In thmap.h 35.\" ----- 36.Ft thmap_t * 37.Fn thmap_create "uintptr_t baseptr" "const thmap_ops_t *ops" "unsigned flags" 38.Ft void 39.Fn thmap_destroy "thmap_t *thmap" 40.Ft void * 41.Fn thmap_get "thmap_t *thmap" "const void *key" "size_t len" 42.Ft void * 43.Fn thmap_put "thmap_t *thmap" "const void *key" "size_t len" "void *val" 44.Ft void * 45.Fn thmap_del "thmap_t *thmap" "const void *key" "size_t len" 46.Ft void * 47.Fn thmap_stage_gc "thmap_t *thmap" 48.Ft void 49.Fn thmap_gc "thmap_t *thmap" "void *ref" 50.Ft void 51.Fn thmap_setroot "thmap_t *thmap" "uintptr_t root_offset" 52.Ft uintptr_t 53.Fn thmap_getroot "const thmap_t *thmap" 54.\" ----- 55.Sh DESCRIPTION 56Concurrent trie-hash map \(em a general purpose associative array, 57combining the elements of hashing and radix trie. 58Highlights: 59.Pp 60.Bl -hyphen -compact 61.It 62Very competitive performance, with logarithmic time complexity on average. 63.It 64Lookups are lock-free and inserts/deletes are using fine-grained locking. 65.It 66Incremental growth of the data structure (no large resizing/rehashing). 67.It 68Optional support for use with shared memory, e.g. memory-mapped file. 69.El 70.Pp 71Delete operations (the key/data destruction) must be synchronized with 72the readers using some reclamation mechanism. 73.\" ----- 74.Sh FUNCTIONS 75.Bl -tag -width abcd 76.It Fn thmap_create baseptr ops flags 77Construct a new trie-hash map. 78The optional 79.Fa ops 80parameter can 81used to set the custom allocate/free operations (see the description of 82.Vt thmap_ops_t 83below). 84In such case, the 85.Fa baseptr 86is the base (start) address of the address space mapping (it must be 87word-aligned). 88If 89.Fa ops 90is set to 91.Dv NULL , 92then 93.Xr malloc 3 94and 95.Xr free 3 96will be used as the default operations and 97.Fa baseptr 98should be set to zero. 99Currently, the supported 100.Fa flags 101are: 102.Bl -tag -width THMAP_SETROOT 103.It Dv THMAP_NOCOPY 104The keys on insert will not be copied and the given pointers to them will 105be expected to be valid and the values constant until the key is deleted; 106by default, the put operation will make a copy of the key. 107.It Dv THMAP_SETROOT 108Indicate that the root of the map will be manually set using the 109.Fn thmap_setroot 110routine; 111by default, the map is initialized and the root node is set on 112.Fn thmap_create . 113.El 114.\" --- 115.It Fn thmap_destroy thmap 116Destroy the map, freeing the memory it uses. 117.\" --- 118.It Fn thmap_get thmap key len 119Lookup the key (of a given length) and return the value associated with it. 120Return 121.Dv NULL 122if the key is not found (see the 123.Sx CAVEATS 124section). 125.\" --- 126.It Fn thmap_put thmap key len val 127Insert the key with an arbitrary value. 128If the key is already present, return the already existing associated value 129without changing it. 130Otherwise, on a successful insert, return the given value. 131Just compare the result against 132.Fa val 133to test whether the insert was successful. 134.\" --- 135.It Fn thmap_del thmap key len 136Remove the given key. 137If the key was present, return the associated value; 138otherwise return 139.Dv NULL . 140The memory associated with the entry is not released immediately, because 141in the concurrent environment (e.g., multi-threaded application) the caller 142may need to ensure it is safe to do so. 143It is managed using the 144.Fn thmap_stage_gc 145and 146.Fn thmap_gc 147routines. 148.\" --- 149.It Fn thmap_stage_gc thmap 150Stage the currently pending entries (the memory not yet released after 151the deletion) for reclamation (G/C). 152This operation should be called 153.Em before 154the synchronization barrier. 155.Pp 156Returns a reference which must be passed to 157.Fn thmap_gc . 158Not calling the G/C function for the returned reference would result in 159a memory leak. 160.\" --- 161.It Fn thmap_gc thmap ref 162Reclaim (G/C) the staged entries i.e. release any memory associated 163with the deleted keys. 164The reference must be the value returned by the call to 165.Fn thmap_stage_gc . 166.Pp 167This function must be called 168.Em after 169the synchronization barrier which guarantees that there are no active 170readers referencing the staged entries. 171.\" --- 172.El 173.Pp 174If the map is created using the 175.Fa THMAP_SETROOT 176flag, then the following functions are applicable: 177.\" --- 178.Bl -tag -width abcd 179.It Fn thmap_setroot thmap root_offset 180Set the root node. 181The address must be relative to the base address, as if allocated by the 182.Fn thmap_ops_t::alloc 183routine. 184Return 0 on success and \-1 on failure (if already set). 185.It Fn thmap_getroot thmap 186Get the root node address. 187The returned address will be relative to the base address. 188.El 189.\" --- 190.Pp 191Members of 192.Vt thmap_ops_t 193are 194.Bd -literal 195 uintptr_t (*alloc)(size_t len); 196 void (*free)(uintptr_t addr, size_t len); 197.Ed 198.\" ----- 199.Sh EXAMPLES 200Simple case backed by 201.Xr malloc 3 , 202which could be used in multi-threaded environment: 203.Bd -literal 204 thmap_t *kvmap; 205 struct obj *obj; 206 207 kvmap = thmap_create(0, NULL); 208 assert(kvmap != NULL); 209 ... 210 obj = obj_create(); 211 thmap_put(kvmap, "test", sizeof("test") - 1, obj); 212 ... 213 obj = thmap_get(kvmap, "test", sizeof("test") - 1); 214 ... 215 thmap_destroy(kvmap); 216.Ed 217.\" ----- 218.Sh AUTHORS 219.An Mindaugas Rasiukevicius Aq Mt rmind@noxt.eu 220.Sh CAVEATS 221The implementation uses pointer tagging and atomic operations. 222This requires the base address and the allocations to provide at least word 223alignment. 224.Pp 225While the 226.Dv NULL 227values may be inserted, 228.Fn thmap_get 229and 230.Fn thmap_del 231cannot indicate whether the key was not found or a key with a 232.Dv NULL 233value was found. 234If the caller needs to indicate an "empty" value, it can use a 235special pointer value, such as 236.Li (void *)(uintptr_t)0x1 . 237.\" ----- 238