Fri Aug 28 07:03:41 2020 UTC ()
thmap(9): Minor readability and style tweaks.

- Fix typo: hmap -> thmap

- Reduce excessive indentation.

- Specify largest entry width for flag name table.

- Include parameter names in function descriptions for easier
  reference.


(riastradh)
diff -r1.2 -r1.3 src/share/man/man9/thmap.9
cvs diff -r1.2 -r1.3 src/share/man/man9/thmap.9 (expand / switch to unified diff)

--- src/share/man/man9/thmap.9 2019/08/28 22:11:25 1.2
+++ src/share/man/man9/thmap.9 2020/08/28 07:03:41 1.3
@@ -1,14 +1,14 @@ @@ -1,14 +1,14 @@
1.\" $NetBSD: thmap.9,v 1.2 2019/08/28 22:11:25 wiz Exp $ 1.\" $NetBSD: thmap.9,v 1.3 2020/08/28 07:03:41 riastradh Exp $
2.\" 2.\"
3.\" Copyright (c) 2018 Mindaugas Rasiukevicius <rmind at noxt eu> 3.\" Copyright (c) 2018 Mindaugas Rasiukevicius <rmind at noxt eu>
4.\" All rights reserved. 4.\" All rights reserved.
5.\" 5.\"
6.\" Redistribution and use in source and binary forms, with or without 6.\" Redistribution and use in source and binary forms, with or without
7.\" modification, are permitted provided that the following conditions 7.\" modification, are permitted provided that the following conditions
8.\" are met: 8.\" are met:
9.\" 1. Redistributions of source code must retain the above copyright 9.\" 1. Redistributions of source code must retain the above copyright
10.\" notice, this list of conditions and the following disclaimer. 10.\" notice, this list of conditions and the following disclaimer.
11.\" 2. Redistributions in binary form must reproduce the above copyright 11.\" 2. Redistributions in binary form must reproduce the above copyright
12.\" notice, this list of conditions and the following disclaimer in the 12.\" notice, this list of conditions and the following disclaimer in the
13.\" documentation and/or other materials provided with the distribution. 13.\" documentation and/or other materials provided with the distribution.
14.\" 14.\"
@@ -26,173 +26,173 @@ @@ -26,173 +26,173 @@
26.\" 26.\"
27.Dd December 11, 2018 27.Dd December 11, 2018
28.Dt THMAP 9 28.Dt THMAP 9
29.Os 29.Os
30.Sh NAME 30.Sh NAME
31.Nm thmap 31.Nm thmap
32.Nd concurrent trie-hash map 32.Nd concurrent trie-hash map
33.Sh SYNOPSIS 33.Sh SYNOPSIS
34.In thmap.h 34.In thmap.h
35.\" ----- 35.\" -----
36.Ft thmap_t * 36.Ft thmap_t *
37.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"
38.Ft void 38.Ft void
39.Fn thmap_destroy "thmap_t *hmap" 39.Fn thmap_destroy "thmap_t *thmap"
40.Ft void * 40.Ft void *
41.Fn thmap_get "thmap_t *hmap" "const void *key" "size_t len" 41.Fn thmap_get "thmap_t *thmap" "const void *key" "size_t len"
42.Ft void * 42.Ft void *
43.Fn thmap_put "thmap_t *hmap" "const void *key" "size_t len" "void *val" 43.Fn thmap_put "thmap_t *thmap" "const void *key" "size_t len" "void *val"
44.Ft void * 44.Ft void *
45.Fn thmap_del "thmap_t *hmap" "const void *key" "size_t len" 45.Fn thmap_del "thmap_t *thmap" "const void *key" "size_t len"
46.Ft void * 46.Ft void *
47.Fn thmap_stage_gc "thmap_t *hmap" 47.Fn thmap_stage_gc "thmap_t *thmap"
48.Ft void 48.Ft void
49.Fn thmap_gc "thmap_t *hmap" "void *ref" 49.Fn thmap_gc "thmap_t *thmap" "void *ref"
50.Ft void 50.Ft void
51.Fn thmap_setroot "thmap_t *thmap" "uintptr_t root_offset" 51.Fn thmap_setroot "thmap_t *thmap" "uintptr_t root_offset"
52.Ft uintptr_t 52.Ft uintptr_t
53.Fn thmap_getroot "const thmap_t *thmap" 53.Fn thmap_getroot "const thmap_t *thmap"
54.\" ----- 54.\" -----
55.Sh DESCRIPTION 55.Sh DESCRIPTION
56Concurrent trie-hash map \(em a general purpose associative array, 56Concurrent trie-hash map \(em a general purpose associative array,
57combining the elements of hashing and radix trie. 57combining the elements of hashing and radix trie.
58Highlights: 58Highlights:
59.Pp 59.Pp
60.Bl -hyphen -compact 60.Bl -hyphen -compact
61.It 61.It
62Very competitive performance, with logarithmic time complexity on average. 62Very competitive performance, with logarithmic time complexity on average.
63.It 63.It
64Lookups are lock-free and inserts/deletes are using fine-grained locking. 64Lookups are lock-free and inserts/deletes are using fine-grained locking.
65.It 65.It
66Incremental growth of the data structure (no large resizing/rehashing). 66Incremental growth of the data structure (no large resizing/rehashing).
67.It 67.It
68Optional support for use with shared memory, e.g. memory-mapped file. 68Optional support for use with shared memory, e.g. memory-mapped file.
69.El 69.El
70.Pp 70.Pp
71Delete operations (the key/data destruction) must be synchronized with 71Delete operations (the key/data destruction) must be synchronized with
72the readers using some reclamation mechanism. 72the readers using some reclamation mechanism.
73.\" ----- 73.\" -----
74.Sh FUNCTIONS 74.Sh FUNCTIONS
75.Bl -tag -width thmap_create 75.Bl -tag -width abcd
76.It Fn thmap_create 76.It Fn thmap_create baseptr ops flags
77Construct a new trie-hash map. 77Construct a new trie-hash map.
78The optional 78The optional
79.Fa ops 79.Fa ops
80parameter can 80parameter can
81used to set the custom allocate/free operations (see the description of 81used to set the custom allocate/free operations (see the description of
82.Vt thmap_ops_t 82.Vt thmap_ops_t
83below). 83below).
84In such case, the 84In such case, the
85.Fa baseptr 85.Fa baseptr
86is the base (start) address of the address space mapping (it must be 86is the base (start) address of the address space mapping (it must be
87word-aligned). 87word-aligned).
88If 88If
89.Fa ops 89.Fa ops
90is set to 90is set to
91.Dv NULL , 91.Dv NULL ,
92then 92then
93.Xr malloc 3 93.Xr malloc 3
94and 94and
95.Xr free 3 95.Xr free 3
96will be used as the default operations and 96will be used as the default operations and
97.Fa baseptr 97.Fa baseptr
98should be set to zero. 98should be set to zero.
99Currently, the supported 99Currently, the supported
100.Fa flags 100.Fa flags
101are: 101are:
102.Bl -tag -width THMAP_NOCOPY 102.Bl -tag -width THMAP_SETROOT
103.It Dv THMAP_NOCOPY 103.It Dv THMAP_NOCOPY
104The keys on insert will not be copied and the given pointers to them will 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; 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. 106by default, the put operation will make a copy of the key.
107.It Dv THMAP_SETROOT 107.It Dv THMAP_SETROOT
108Indicate that the root of the map will be manually set using the 108Indicate that the root of the map will be manually set using the
109.Fn thmap_setroot 109.Fn thmap_setroot
110routine; 110routine;
111by default, the map is initialized and the root node is set on 111by default, the map is initialized and the root node is set on
112.Fn thmap_create . 112.Fn thmap_create .
113.El 113.El
114.\" --- 114.\" ---
115.It Fn thmap_destroy 115.It Fn thmap_destroy thmap
116Destroy the map, freeing the memory it uses. 116Destroy the map, freeing the memory it uses.
117.\" --- 117.\" ---
118.It Fn thmap_get 118.It Fn thmap_get thmap key len
119Lookup the key (of a given length) and return the value associated with it. 119Lookup the key (of a given length) and return the value associated with it.
120Return 120Return
121.Dv NULL 121.Dv NULL
122if the key is not found (see the 122if the key is not found (see the
123.Sx CAVEATS 123.Sx CAVEATS
124section). 124section).
125.\" --- 125.\" ---
126.It Fn thmap_put 126.It Fn thmap_put thmap key len val
127Insert the key with an arbitrary value. 127Insert the key with an arbitrary value.
128If the key is already present, return the already existing associated value 128If the key is already present, return the already existing associated value
129without changing it. 129without changing it.
130Otherwise, on a successful insert, return the given value. 130Otherwise, on a successful insert, return the given value.
131Just compare the result against 131Just compare the result against
132.Fa val 132.Fa val
133to test whether the insert was successful. 133to test whether the insert was successful.
134.\" --- 134.\" ---
135.It Fn thmap_del 135.It Fn thmap_del thmap key len
136Remove the given key. 136Remove the given key.
137If the key was present, return the associated value; 137If the key was present, return the associated value;
138otherwise return 138otherwise return
139.Dv NULL . 139.Dv NULL .
140The memory associated with the entry is not released immediately, because 140The memory associated with the entry is not released immediately, because
141in the concurrent environment (e.g., multi-threaded application) the caller 141in the concurrent environment (e.g., multi-threaded application) the caller
142may need to ensure it is safe to do so. 142may need to ensure it is safe to do so.
143It is managed using the 143It is managed using the
144.Fn thmap_stage_gc 144.Fn thmap_stage_gc
145and 145and
146.Fn thmap_gc 146.Fn thmap_gc
147routines. 147routines.
148.\" --- 148.\" ---
149.It Fn thmap_stage_gc 149.It Fn thmap_stage_gc thmap
150Stage the currently pending entries (the memory not yet released after 150Stage the currently pending entries (the memory not yet released after
151the deletion) for reclamation (G/C). 151the deletion) for reclamation (G/C).
152This operation should be called 152This operation should be called
153.Em before 153.Em before
154the synchronization barrier. 154the synchronization barrier.
155.Pp 155.Pp
156Returns a reference which must be passed to 156Returns a reference which must be passed to
157.Fn thmap_gc . 157.Fn thmap_gc .
158Not calling the G/C function for the returned reference would result in 158Not calling the G/C function for the returned reference would result in
159a memory leak. 159a memory leak.
160.\" --- 160.\" ---
161.It Fn thmap_gc 161.It Fn thmap_gc thmap ref
162Reclaim (G/C) the staged entries i.e. release any memory associated 162Reclaim (G/C) the staged entries i.e. release any memory associated
163with the deleted keys. 163with the deleted keys.
164The reference must be the value returned by the call to 164The reference must be the value returned by the call to
165.Fn thmap_stage_gc . 165.Fn thmap_stage_gc .
166.Pp 166.Pp
167This function must be called 167This function must be called
168.Em after 168.Em after
169the synchronization barrier which guarantees that there are no active 169the synchronization barrier which guarantees that there are no active
170readers referencing the staged entries. 170readers referencing the staged entries.
171.\" --- 171.\" ---
172.El 172.El
173.Pp 173.Pp
174If the map is created using the 174If the map is created using the
175.Fa THMAP_SETROOT 175.Fa THMAP_SETROOT
176flag, then the following functions are applicable: 176flag, then the following functions are applicable:
177.\" --- 177.\" ---
178.Bl -tag -width thmap_setroot 178.Bl -tag -width abcd
179.It Fn thmap_setroot 179.It Fn thmap_setroot thmap root_offset
180Set the root node. 180Set the root node.
181The address must be relative to the base address, as if allocated by the 181The address must be relative to the base address, as if allocated by the
182.Fn thmap_ops_t::alloc 182.Fn thmap_ops_t::alloc
183routine. 183routine.
184Return 0 on success and \-1 on failure (if already set). 184Return 0 on success and \-1 on failure (if already set).
185.It Fn thmap_getroot 185.It Fn thmap_getroot thmap
186Get the root node address. 186Get the root node address.
187The returned address will be relative to the base address. 187The returned address will be relative to the base address.
188.El 188.El
189.\" --- 189.\" ---
190.Pp 190.Pp
191Members of 191Members of
192.Vt thmap_ops_t 192.Vt thmap_ops_t
193are 193are
194.Bd -literal 194.Bd -literal
195 uintptr_t (*alloc)(size_t len); 195 uintptr_t (*alloc)(size_t len);
196 void (*free)(uintptr_t addr, size_t len); 196 void (*free)(uintptr_t addr, size_t len);
197.Ed 197.Ed
198.\" ----- 198.\" -----