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