m4: Sync with FreeBSD.
[dragonfly.git] / usr.bin / m4 / lib / ohash_init.3
1 .\"     $OpenBSD: ohash_init.3,v 1.14 2007/05/31 19:19:30 jmc Exp $
2 .\" Copyright (c) 1999 Marc Espie <espie@openbsd.org>
3 .\"
4 .\" Permission to use, copy, modify, and distribute this software for any
5 .\" purpose with or without fee is hereby granted, provided that the above
6 .\" copyright notice and this permission notice appear in all copies.
7 .\"
8 .\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 .\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 .\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 .\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 .\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 .\"
16 .\" $FreeBSD: src/usr.bin/m4/lib/ohash_init.3,v 1.3 2012/11/17 01:54:24 svnexp Exp $
17 .\"
18 .Dd $Mdocdate: May 31 2007 $
19 .Dt OPEN_HASH 3
20 .Os
21 .Sh NAME
22 .Nm ohash_init ,
23 .Nm ohash_delete ,
24 .Nm ohash_lookup_interval ,
25 .Nm ohash_lookup_memory ,
26 .Nm ohash_find ,
27 .Nm ohash_remove ,
28 .Nm ohash_insert ,
29 .Nm ohash_first ,
30 .Nm ohash_next ,
31 .Nm ohash_entries
32 .Nd light-weight open hashing
33 .Sh SYNOPSIS
34 .Fd #include <stdint.h>
35 .Fd #include <stddef.h>
36 .Fd #include <ohash.h>
37 .Ft void
38 .Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
39 .Ft void
40 .Fn ohash_delete "struct ohash *h"
41 .Ft "unsigned int"
42 .Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "uint32_t hv"
43 .Ft "unsigned int"
44 .Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "uint32_t hv"
45 .Ft void *
46 .Fn ohash_find "struct ohash *h" "unsigned int i"
47 .Ft void *
48 .Fn ohash_remove "struct ohash *h" "unsigned int i"
49 .Ft void *
50 .Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p"
51 .Ft void *
52 .Fn ohash_first "struct ohash *h" "unsigned int *i"
53 .Ft void *
54 .Fn ohash_next "struct ohash *h" "unsigned int *i"
55 .Ft "unsigned int"
56 .Fn ohash_entries "struct ohash *h"
57 .Sh DESCRIPTION
58 These functions have been designed as a fast, extensible alternative to
59 the usual hash table functions.
60 They provide storage and retrieval of records indexed by keys,
61 where a key is a contiguous sequence of bytes at a fixed position in
62 each record.
63 Keys can either be NUL-terminated strings or fixed-size memory areas.
64 All functions take a pointer to an ohash structure as the
65 .Fa h
66 function argument.
67 Storage for this structure should be provided by user code.
68 .Pp
69 .Fn ohash_init
70 initializes the table to store roughly 2 to the power
71 .Fa size
72 elements.
73 .Fa info
74 holds the position of the key in each record, and two pointers to
75 .Xr calloc 3
76 and
77 .Xr free 3 Ns -like
78 functions, to use for managing the table internal storage.
79 .Pp
80 .Fn ohash_delete
81 frees storage internal to
82 .Fa h .
83 Elements themselves should be freed by the user first, using for instance
84 .Fn ohash_first
85 and
86 .Fn ohash_next .
87 .Pp
88 .Fn ohash_lookup_interval
89 and
90 .Fn ohash_lookup_memory
91 are the basic look-up element functions.
92 The hashing function result is provided by the user as
93 .Fa hv .
94 These return a
95 .Qq slot
96 in the ohash table
97 .Fa h ,
98 to be used with
99 .Fn ohash_find ,
100 .Fn ohash_insert ,
101 or
102 .Fn ohash_remove .
103 This slot is only valid up to the next call to
104 .Fn ohash_insert
105 or
106 .Fn ohash_remove .
107 .Pp
108 .Fn ohash_lookup_interval
109 handles string-like keys.
110 .Fn ohash_lookup_interval
111 assumes the key is the interval between
112 .Fa start
113 and
114 .Fa end ,
115 exclusive,
116 though the actual elements stored in the table should only contain
117 NUL-terminated keys.
118 .Pp
119 .Fn ohash_lookup_memory
120 assumes the key is the memory area starting at
121 .Fa k
122 of size
123 .Fa s .
124 All bytes are significant in key comparison.
125 .Pp
126 .Fn ohash_find
127 retrieves an element from a slot
128 .Fa i
129 returned by the
130 .Fn ohash_lookup*
131 functions.
132 It returns
133 .Dv NULL
134 if the slot is empty.
135 .Pp
136 .Fn ohash_insert
137 inserts a new element
138 .Fa p
139 at slot
140 .Fa i .
141 Slot
142 .Fa i
143 must be empty and element
144 .Fa p
145 must have a key corresponding to the
146 .Fn ohash_lookup*
147 call.
148 .Pp
149 .Fn ohash_remove
150 removes the element at slot
151 .Fa i .
152 It returns the removed element, for user code to dispose of, or
153 .Dv NULL
154 if the slot was empty.
155 .Pp
156 .Fn ohash_first
157 and
158 .Fn ohash_next
159 can be used to access all elements in an ohash table, like this:
160 .Bd -literal -offset indent
161 for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
162         do_something_with(n);
163 .Ed
164 .Pp
165 .Fa i
166 points to an auxiliary unsigned integer used to record the current position
167 in the ohash table.
168 Those functions are safe to use even while entries are added to/removed
169 from the table, but in such a case they do not guarantee that new entries
170 will be returned.
171 As a special case, they can safely be used to free elements in the table.
172 .Pp
173 .Fn ohash_entries
174 returns the number of elements in the hash table.
175 .Sh STORAGE HANDLING
176 Only
177 .Fn ohash_init ,
178 .Fn ohash_insert ,
179 .Fn ohash_remove ,
180 and
181 .Fn ohash_delete
182 may call the user-supplied memory functions.
183 It is the responsibility of the user memory allocation code to verify
184 that those calls did not fail.
185 .Pp
186 If memory allocation fails,
187 .Fn ohash_init
188 returns a useless hash table.
189 .Fn ohash_insert
190 and
191 .Fn ohash_remove
192 still perform the requested operation, but the returned table should be
193 considered read-only.
194 It can still be accessed by
195 .Fn ohash_lookup* ,
196 .Fn ohash_find ,
197 .Fn ohash_first ,
198 and
199 .Fn ohash_next
200 to dump relevant information to disk before aborting.
201 .Sh THREAD SAFETY
202 The open hashing functions are not thread-safe by design.
203 In particular, in a threaded environment, there is no guarantee that a
204 .Qq slot
205 will not move between a
206 .Fn ohash_lookup*
207 and a
208 .Fn ohash_find ,
209 .Fn ohash_insert ,
210 or
211 .Fn ohash_remove
212 call.
213 .Pp
214 Multi-threaded applications should explicitly protect ohash table access.
215 .Sh SEE ALSO
216 .Xr ohash_interval 3
217 .Rs
218 .%A Donald E. Knuth
219 .%B The Art of Computer Programming
220 .%V Vol. 3
221 .%P pp 506-550
222 .%D 1973
223 .Re
224 .Sh STANDARDS
225 Those functions are completely non-standard and should be avoided in
226 portable programs.
227 .Sh HISTORY
228 Those functions were designed and written for
229 .Ox
230 .Xr make 1
231 by Marc Espie in 1999.