| blob | a108c7eb6bbccd717f607ef41fa3f84e2ed20108 |
1 .\" $NetBSD: hcreate.3,v 1.10 2011/09/15 09:14:54 wiz 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 September 14, 2011
31 .Dt HCREATE 3
32 .Os
33 .Sh NAME
34 .Nm hcreate ,
35 .Nm hcreate_r ,
36 .Nm hdestroy ,
37 .Nm hdestroy_r ,
38 .Nm hsearch ,
39 .Nm hsearch_r
40 .Nd manage hash search table
41 .Sh LIBRARY
42 .Lb libc
43 .Sh SYNOPSIS
44 .In search.h
45 .Ft int
46 .Fn hcreate "size_t nel"
47 .Ft int
48 .Fn hcreate_r "size_t nel" "struct hsearch_data *table"
49 .Ft void
50 .Fn hdestroy "void"
51 .Ft void
52 .Fn hdestroy_r "struct hsearch_data *table"
53 .Ft ENTRY *
54 .Fn hsearch "ENTRY item" "ACTION action"
55 .Ft int
56 .Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table"
57 .Sh DESCRIPTION
58 The
59 .Fn hcreate ,
60 .Fn hcreate_r ,
61 .Fn hdestroy ,
62 .Fn hdestroy_r
63 .Fn hsearch ,
64 and
65 .Fn hsearch_r
66 functions manage hash search tables.
67 .Pp
68 The
69 .Fn hcreate
70 function allocates and initializes the table.
71 The
72 .Fa nel
73 argument specifies an estimate of the maximum number of entries to be held
74 by the table.
75 Unless further memory allocation fails, supplying an insufficient
76 .Fa nel
77 value will not result in functional harm, although a performance degradation
78 may occur.
79 Initialization using the
80 .Fn hcreate
81 function is mandatory prior to any access operations using
82 .Fn hsearch .
83 .Pp
84 The
85 .Fn hdestroy
86 function destroys a table previously created using
87 .Fn hcreate .
88 After a call to
89 .Fn hdestroy ,
90 the data can no longer be accessed.
91 .Pp
92 The
93 .Fn hsearch
94 function is used to search to the hash table.
95 It returns a pointer into the
96 hash table indicating the address of an item.
97 The
98 .Fa item
99 argument is of type
100 .Vt ENTRY ,
101 defined in the
102 .In search.h
103 header.
104 This is a structure type that contains two pointers:
105 .Pp
106 .Bl -tag -compact -offset indent -width "void *data "
107 .It Fa char *key
108 comparison key
109 .It Fa void *data
110 pointer to data associated with
111 .Fa key
112 .El
113 .Pp
114 The key comparison function used by
115 .Fn hsearch
116 is
117 .Xr strcmp 3 .
118 .Pp
119 The
120 .Fa action
121 argument is of type
122 .Vt ACTION ,
123 an enumeration type which defines the following values:
124 .Bl -tag -offset indent -width ENTERXX
125 .It Dv ENTER
126 Insert
127 .Fa item
128 into the hash table.
129 If an existing item with the same key is found, it is not replaced.
130 Note that the
131 .Fa key
132 and
133 .Fa data
134 elements of
135 .Fa item
136 are used directly by the new table entry.
137 The storage for the
138 key must not be modified during the lifetime of the hash table.
139 .It Dv FIND
140 Search the hash table without inserting
141 .Fa item .
142 .El
143 .Pp
144 Note that the comparison
145 .Fa key
146 must be allocated using
147 .Xr malloc 3
148 or
149 .Xr calloc 3
150 if action is
151 .Dv ENTER
152 and
153 .Fn hdestroy
154 will be called.
155 This is because
156 .Fn hdestroy
157 will call
158 .Xr free 3
159 for each comparison
160 .Fa key
161 (but not
162 .Fa data ) .
163 Typically the comparison
164 .Fa key
165 is allocated by using
166 .Xr strdup 3 .
167 .Pp
168 The
169 .Fn hcreate_r ,
170 .Fn hdestroy_r ,
171 and
172 .Fn hsearch_r
173 functions are re-entrant versions of the above functions that can
174 operate on a table supplied by the user.
175 The
176 .Fn hsearch_r
177 function returns
178 .Dv 0
179 if the action is
180 .Dv ENTER
181 and the element cannot be created,
182 .Dv 1
183 otherwise.
184 If the element exists or can be created, it will be placed in
185 .Fa itemp ,
186 otherwise
187 .Fa itemp
188 will be set to
189 .Dv NULL .
190 .Sh RETURN VALUES
191 If successful, the
192 .Fn hcreate
193 and
194 .Fn hcreate_r
195 functions return a non-zero value.
196 Otherwise, a value of
197 .Dv 0
198 is returned and
199 .Va errno
200 is set to indicate the error.
201 .Pp
202 The
203 .Fn hdestroy
204 and
205 .Fn hdestroy_r
206 functions return no value.
207 .Pp
208 If successful, the
209 .Fn hsearch
210 function returns a pointer to hash table entry matching
211 the provided key.
212 If the action is
213 .Dv FIND
214 and the item was not found, or if the action is
215 .Dv ENTER
216 and the insertion failed,
217 .Dv NULL
218 is returned and
219 .Va errno
220 is set to indicate the error.
221 If the action is
222 .Dv ENTER
223 and an entry already existed in the table matching the given
224 key, the existing entry is returned and is not replaced.
225 .Pp
226 The
227 .Fn hsearch_r
228 function returns
229 .Dv 1
230 unless the table is full, when it returns
231 .Dv 0 .
232 If
233 .Fn hsearch
234 returns
235 .Dv 0
236 or the element is not found,
237 .Va errno
238 is set to indicate the error.
239 .Sh ERRORS
240 The
241 .Fn hcreate ,
242 .Fn hcreate_r ,
243 .Fn hsearch
244 and
245 .Fn hsearch_r
246 functions will fail if:
247 .Bl -tag -width Er
248 .It Bq Er ENOMEM
249 Insufficient memory is available.
250 .El
251 .Pp
252 The
253 .Fn hsearch
254 and
255 .Fn hsearch_r
256 functions will also fail if the action is
257 .Dv SEARCH
258 and the element is not found:
259 .Bl -tag -width Er
260 .It Bq Er ESRCH
261 The
262 .Fa item
263 given is not found.
264 .El
265 .Sh SEE ALSO
266 .Xr bsearch 3 ,
267 .Xr lsearch 3 ,
268 .Xr malloc 3 ,
269 .Xr strcmp 3
270 .Sh STANDARDS
271 The
272 .Fn hcreate ,
273 .Fn hdestroy
274 and
275 .Fn hsearch
276 functions conform to
277 .St -xpg4.2 .
278 .Sh HISTORY
279 The
280 .Fn hcreate ,
281 .Fn hdestroy
282 and
283 .Fn hsearch
284 functions first appeared in
285 .At V .
286 The
287 .Fn hcreate_r ,
288 .Fn hdestroy_r
289 and
290 .Fn hsearch_r
291 functions are
292 .Tn GNU
293 extensions.
294 .Sh CAVEATS
295 At least the following limitations can be mentioned:
296 .Bl -bullet
297 .It
298 The original,
299 .Pf non- Tn GNU
300 interface permits the use of only one hash table at a time.
301 .It
302 Individual hash table entries can be added, but not deleted.
303 .It
304 The standard is indecipherable about the
305 internal memory usage of the functions,
306 mentioning only that
307 .Do
308 .Fn hcreate
309 and
310 .Fn hsearch
311 functions may use
312 .Fn malloc
313 to allocate space
314 .Dc .
315 This limits the portability of the functions,
316 given that other implementations may not
317 .Xr free 3
318 the buffer pointed by
319 .Fa key .
320 .El