xref: /netbsd-src/share/man/man9/thmap.9 (revision 5307371bf319d730adf0a7f2fa91eacd949f1fdd)
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