| blob | 129a282b63d1c3493243a2021fb7995a458ef139 |
1 .\" $NetBSD: hcreate.3,v 1.13 2014/07/20 20:17:21 christos Exp $
2 .\"
3 .\" Copyright (c) 1999 The NetBSD Foundation, Inc.
4 .\" All rights reserved.
5 .\"
6 .\" This code is derived from software contributed to The NetBSD Foundation
7 .\" by Klaus Klein.
8 .\"
9 .\" Redistribution and use in source and binary forms, with or without
10 .\" modification, are permitted provided that the following conditions
11 .\" are met:
12 .\" 1. Redistributions of source code must retain the above copyright
13 .\" notice, this list of conditions and the following disclaimer.
14 .\" 2. Redistributions in binary form must reproduce the above copyright
15 .\" notice, this list of conditions and the following disclaimer in the
16 .\" documentation and/or other materials provided with the distribution.
17 .\"
18 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
19 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
20 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
22 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 .\" POSSIBILITY OF SUCH DAMAGE.
29 .\"
30 .Dd July 20, 2014
31 .Dt HCREATE 3
32 .Os
33 .Sh NAME
34 .Nm hcreate ,
35 .Nm hcreate_r ,
36 .Nm hdestroy ,
37 .Nm hdestroy1 ,
38 .Nm hdestroy_r ,
39 .Nm hdestroy1_r ,
40 .Nm hsearch ,
41 .Nm hsearch_r
42 .Nd manage hash search table
43 .Sh LIBRARY
44 .Lb libc
45 .Sh SYNOPSIS
46 .In search.h
47 .Ft int
48 .Fn hcreate "size_t nel"
49 .Ft int
50 .Fn hcreate_r "size_t nel" "struct hsearch_data *table"
51 .Ft void
52 .Fn hdestroy "void"
53 .Ft void
54 .Fn hdestroy1 "void (*freekey)(void *)" "void (*freedata)(void *)"
55 .Ft void
56 .Fn hdestroy_r "struct hsearch_data *table"
57 .Ft void
58 .Fn hdestroy1_r "struct hsearch_data *table" "void (*freekey)(void *)" "void (*freedata)(void *)"
59 .Ft ENTRY *
60 .Fn hsearch "ENTRY item" "ACTION action"
61 .Ft int
62 .Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table"
63 .Sh DESCRIPTION
64 The
65 .Fn hcreate ,
66 .Fn hcreate_r ,
67 .Fn hdestroy ,
68 .Fn hdestroy_r
69 .Fn hdestroy1 ,
70 .Fn hdestroy1_r
71 .Fn hsearch ,
72 and
73 .Fn hsearch_r
74 functions manage hash search tables.
75 .Pp
76 The
77 .Fn hcreate
78 function allocates and initializes the table.
79 The
80 .Fa nel
81 argument specifies an estimate of the maximum number of entries to be held
82 by the table.
83 Unless further memory allocation fails, supplying an insufficient
84 .Fa nel
85 value will not result in functional harm, although a performance degradation
86 may occur.
87 Initialization using the
88 .Fn hcreate
89 function is mandatory prior to any access operations using
90 .Fn hsearch .
91 .Pp
92 The
93 .Fn hdestroy
94 function destroys a table previously created using
95 .Fn hcreate .
96 After a call to
97 .Fn hdestroy ,
98 the data can no longer be accessed.
99 .Pp
100 The
101 .Fn hsearch
102 function is used to search to the hash table.
103 It returns a pointer into the
104 hash table indicating the address of an item.
105 The
106 .Fa item
107 argument is of type
108 .Vt ENTRY ,
109 defined in the
110 .In search.h
111 header.
112 This is a structure type that contains two pointers:
113 .Pp
114 .Bl -tag -compact -offset indent -width "void *data "
115 .It Fa char *key
116 comparison key
117 .It Fa void *data
118 pointer to data associated with
119 .Fa key
120 .El
121 .Pp
122 The key comparison function used by
123 .Fn hsearch
124 is
125 .Xr strcmp 3 .
126 .Pp
127 The
128 .Fa action
129 argument is of type
130 .Vt ACTION ,
131 an enumeration type which defines the following values:
132 .Bl -tag -offset indent -width ENTERXX
133 .It Dv ENTER
134 Insert
135 .Fa item
136 into the hash table.
137 If an existing item with the same key is found, it is not replaced.
138 Note that the
139 .Fa key
140 and
141 .Fa data
142 elements of
143 .Fa item
144 are used directly by the new table entry.
145 The storage for the
146 key must not be modified during the lifetime of the hash table.
147 .It Dv FIND
148 Search the hash table without inserting
149 .Fa item .
150 .El
151 .Pp
152 The traditional
153 .Fn hdestroy
154 and
155 .Fn hdestroy_r
156 functions don't
157 .Xr free 3
158 the data associated with the
159 .Fa key
160 and
161 .Fa value
162 of each entry, because they did not allocate them.
163 Since there is no
164 .Dq iterator
165 function provided, the
166 .Fn hdestroy1
167 and
168 .Fn hdestroy1_r
169 allow controlling how the
170 .Fa key
171 or
172 .Fa value
173 will be freed using the
174 provided functions in the
175 .Fa freekey
176 and
177 .Fa freedata
178 arguments.
179 If they are
180 .Dv NULL ,
181 then
182 .Fa key
183 and
184 .Fa value
185 are not freed.
186 .Pp
187 The
188 .Fn hcreate_r ,
189 .Fn hdestroy_r ,
190 .Fn hdestroy1_r ,
191 and
192 .Fn hsearch_r
193 functions are re-entrant versions of the above functions that can
194 operate on a table supplied by the user.
195 The
196 .Fn hsearch_r
197 function returns
198 .Dv 0
199 if the action is
200 .Dv ENTER
201 and the element cannot be created,
202 .Dv 1
203 otherwise.
204 If the element exists or can be created, it will be placed in
205 .Fa itemp ,
206 otherwise
207 .Fa itemp
208 will be set to
209 .Dv NULL .
210 .Sh RETURN VALUES
211 If successful, the
212 .Fn hcreate
213 and
214 .Fn hcreate_r
215 functions return a non-zero value.
216 Otherwise, a value of
217 .Dv 0
218 is returned and
219 .Va errno
220 is set to indicate the error.
221 .Pp
222 The
223 .Fn hdestroy
224 and
225 .Fn hdestroy_r
226 functions return no value.
227 .Pp
228 If successful, the
229 .Fn hsearch
230 function returns a pointer to hash table entry matching
231 the provided key.
232 If the action is
233 .Dv FIND
234 and the item was not found, or if the action is
235 .Dv ENTER
236 and the insertion failed,
237 .Dv NULL
238 is returned and
239 .Va errno
240 is set to indicate the error.
241 If the action is
242 .Dv ENTER
243 and an entry already existed in the table matching the given
244 key, the existing entry is returned and is not replaced.
245 .Pp
246 The
247 .Fn hsearch_r
248 function returns
249 .Dv 1
250 unless the table is full, when it returns
251 .Dv 0 .
252 If
253 .Fn hsearch
254 returns
255 .Dv 0
256 or the element is not found,
257 .Va errno
258 is set to indicate the error.
259 .Sh ERRORS
260 The
261 .Fn hcreate ,
262 .Fn hcreate_r ,
263 .Fn hsearch
264 and
265 .Fn hsearch_r
266 functions will fail if:
267 .Bl -tag -width Er
268 .It Bq Er ENOMEM
269 Insufficient memory is available.
270 .El
271 .Pp
272 The
273 .Fn hsearch
274 and
275 .Fn hsearch_r
276 functions will also fail if the action is
277 .Dv SEARCH
278 and the element is not found:
279 .Bl -tag -width Er
280 .It Bq Er ESRCH
281 The
282 .Fa item
283 given is not found.
284 .El
285 .Sh SEE ALSO
286 .Xr bsearch 3 ,
287 .Xr free 3 ,
288 .Xr lsearch 3 ,
289 .Xr malloc 3 ,
290 .Xr strcmp 3
291 .Sh STANDARDS
292 The
293 .Fn hcreate ,
294 .Fn hdestroy
295 and
296 .Fn hsearch
297 functions conform to
298 .St -xpg4.2 .
299 .Sh HISTORY
300 The
301 .Fn hcreate ,
302 .Fn hdestroy
303 and
304 .Fn hsearch
305 functions first appeared in
306 .At V .
307 The
308 .Fn hcreate_r ,
309 .Fn hdestroy_r ,
310 and
311 .Fn hsearch_r
312 functions are
313 .Tn GNU
314 extensions.
315 The
316 .Fn hdestroy1
317 and
318 .Fn hdestroy1_r
319 are
320 .Nx
321 extensions.
322 .Sh CAVEATS
323 At least the following limitations can be mentioned:
324 .Bl -bullet
325 .It
326 The original,
327 .Pf non- Tn GNU
328 interface permits the use of only one hash table at a time.
329 .It
330 Individual hash table entries can be added, but not deleted.
331 .It
332 There is no iterator to scan for all entries in the table.
333 .El