| blob | 1234228c0822abf169957d04768b189833f917f7 |
1 '\" t
2 .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de)
3 .\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk
4 .\" <mtk.manpages@gmail.com>
5 .\"
6 .\" SPDX-License-Identifier: GPL-2.0-or-later
7 .\"
8 .\" References consulted:
9 .\" SunOS 4.1.1 man pages
10 .\" Modified Sat Sep 30 21:52:01 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
11 .\" Remarks from dhw@gamgee.acad.emich.edu Fri Jun 19 06:46:31 1998
12 .\" Modified 2001-12-26, 2003-11-28, 2004-05-20, aeb
13 .\" 2008-09-02, mtk: various additions and rewrites
14 .\" 2008-09-03, mtk, restructured somewhat, in part after suggestions from
15 .\" Timothy S. Nelson <wayland@wayland.id.au>
16 .\"
17 .TH hsearch 3 (date) "Linux man-pages (unreleased)"
18 .SH NAME
19 hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r,
20 hsearch_r \- hash table management
21 .SH LIBRARY
22 Standard C library
23 .RI ( libc ", " \-lc )
24 .SH SYNOPSIS
25 .nf
26 .B #include <search.h>
27 .P
28 .BI "int hcreate(size_t " nel );
29 .B "void hdestroy(void);"
30 .P
31 .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action );
32 .P
33 .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
34 .B #include <search.h>
35 .P
36 .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab );
37 .BI "void hdestroy_r(struct hsearch_data *" htab );
38 .P
39 .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval ,
40 .BI " struct hsearch_data *" htab );
41 .fi
42 .SH DESCRIPTION
43 The three functions
44 .BR hcreate (),
45 .BR hsearch (),
46 and
47 .BR hdestroy ()
48 allow the caller to create and manage a hash search table
49 containing entries consisting of a key (a string) and associated data.
50 Using these functions, only one hash table can be used at a time.
51 .P
52 The three functions
53 .BR hcreate_r (),
54 .BR hsearch_r (),
55 .BR hdestroy_r ()
56 are reentrant versions that allow a program to use
57 more than one hash search table at the same time.
58 The last argument,
59 .IR htab ,
60 points to a structure that describes the table
61 on which the function is to operate.
62 The programmer should treat this structure as opaque
63 (i.e., do not attempt to directly access or modify
64 the fields in this structure).
65 .P
66 First a hash table must be created using
67 .BR hcreate ().
68 The argument \fInel\fP specifies the maximum number of entries
69 in the table.
70 (This maximum cannot be changed later, so choose it wisely.)
71 The implementation may adjust this value upward to improve the
72 performance of the resulting hash table.
73 .\" e.g., in glibc it is raised to the next higher prime number
74 .P
75 The
76 .BR hcreate_r ()
77 function performs the same task as
78 .BR hcreate (),
79 but for the table described by the structure
80 .IR *htab .
81 The structure pointed to by
82 .I htab
83 must be zeroed before the first call to
84 .BR hcreate_r ().
85 .P
86 The function
87 .BR hdestroy ()
88 frees the memory occupied by the hash table that was created by
89 .BR hcreate ().
90 After calling
91 .BR hdestroy (),
92 a new hash table can be created using
93 .BR hcreate ().
94 The
95 .BR hdestroy_r ()
96 function performs the analogous task for a hash table described by
97 .IR *htab ,
98 which was previously created using
99 .BR hcreate_r ().
100 .P
101 The
102 .BR hsearch ()
103 function searches the hash table for an
104 item with the same key as \fIitem\fP (where "the same" is determined using
105 .BR strcmp (3)),
106 and if successful returns a pointer to it.
107 .P
108 The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in
109 \fI<search.h>\fP as follows:
110 .P
111 .in +4n
112 .EX
113 typedef struct entry {
114 char *key;
115 void *data;
116 } ENTRY;
117 .EE
118 .in
119 .P
120 The field \fIkey\fP points to a null-terminated string which is the
121 search key.
122 The field \fIdata\fP points to data that is associated with that key.
123 .P
124 The argument \fIaction\fP determines what
125 .BR hsearch ()
126 does after an unsuccessful search.
127 This argument must either have the value
128 .BR ENTER ,
129 meaning insert a copy of
130 .I item
131 (and return a pointer to the new hash table entry as the function result),
132 or the value
133 .BR FIND ,
134 meaning that NULL should be returned.
135 (If
136 .I action
137 is
138 .BR FIND ,
139 then
140 .I data
141 is ignored.)
142 .P
143 The
144 .BR hsearch_r ()
145 function is like
146 .BR hsearch ()
147 but operates on the hash table described by
148 .IR *htab .
149 The
150 .BR hsearch_r ()
151 function differs from
152 .BR hsearch ()
153 in that a pointer to the found item is returned in
154 .IR *retval ,
155 rather than as the function result.
156 .SH RETURN VALUE
157 .BR hcreate ()
158 and
159 .BR hcreate_r ()
160 return nonzero on success.
161 They return 0 on error, with
162 .I errno
163 set to indicate the error.
164 .P
165 On success,
166 .BR hsearch ()
167 returns a pointer to an entry in the hash table.
168 .BR hsearch ()
169 returns NULL on error, that is,
170 if \fIaction\fP is \fBENTER\fP and
171 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
172 cannot be found in the hash table.
173 .BR hsearch_r ()
174 returns nonzero on success, and 0 on error.
175 In the event of an error, these two functions set
176 .I errno
177 to indicate the error.
178 .SH ERRORS
179 .BR hcreate_r ()
180 and
181 .BR hdestroy_r ()
182 can fail for the following reasons:
183 .TP
184 .B EINVAL
185 .I htab
186 is NULL.
187 .P
188 .BR hsearch ()
189 and
190 .BR hsearch_r ()
191 can fail for the following reasons:
192 .TP
193 .B ENOMEM
194 .I action
195 was
196 .BR ENTER ,
197 .I key
198 was not found in the table,
199 and there was no room in the table to add a new entry.
200 .TP
201 .B ESRCH
202 .I action
203 was
204 .BR FIND ,
205 and
206 .I key
207 was not found in the table.
208 .P
209 POSIX.1 specifies only the
210 .\" PROX.1-2001, POSIX.1-2008
211 .B ENOMEM
212 error.
213 .SH ATTRIBUTES
214 For an explanation of the terms used in this section, see
215 .BR attributes (7).
216 .TS
217 allbox;
218 lbx lb lb
219 l l l.
220 Interface Attribute Value
221 T{
222 .na
223 .nh
224 .BR hcreate (),
225 .BR hsearch (),
226 .BR hdestroy ()
227 T} Thread safety MT-Unsafe race:hsearch
228 T{
229 .na
230 .nh
231 .BR hcreate_r (),
232 .BR hsearch_r (),
233 .BR hdestroy_r ()
234 T} Thread safety MT-Safe race:htab
235 .TE
236 .SH STANDARDS
237 .TP
238 .BR hcreate ()
239 .TQ
240 .BR hsearch ()
241 .TQ
242 .BR hdestroy ()
243 POSIX.1-2008.
244 .TP
245 .BR hcreate_r ()
246 .TQ
247 .BR hsearch_r ()
248 .TQ
249 .BR hdestroy_r ()
250 GNU.
251 .SH HISTORY
252 .TP
253 .BR hcreate ()
254 .TQ
255 .BR hsearch ()
256 .TQ
257 .BR hdestroy ()
258 SVr4, POSIX.1-2001.
259 .TP
260 .BR hcreate_r ()
261 .TQ
262 .BR hsearch_r ()
263 .TQ
264 .BR hdestroy_r ()
265 GNU.
266 .SH NOTES
267 Hash table implementations are usually more efficient when the
268 table contains enough free space to minimize collisions.
269 Typically, this means that
270 .I nel
271 should be at least 25% larger than the maximum number of elements
272 that the caller expects to store in the table.
273 .P
274 The
275 .BR hdestroy ()
276 and
277 .BR hdestroy_r ()
278 functions do not free the buffers pointed to by the
279 .I key
280 and
281 .I data
282 elements of the hash table entries.
283 (It can't do this because it doesn't know
284 whether these buffers were allocated dynamically.)
285 If these buffers need to be freed (perhaps because the program
286 is repeatedly creating and destroying hash tables,
287 rather than creating a single table whose lifetime
288 matches that of the program),
289 then the program must maintain bookkeeping data structures that
290 allow it to free them.
291 .SH BUGS
292 SVr4 and POSIX.1-2001 specify that \fIaction\fP
293 is significant only for unsuccessful searches, so that an \fBENTER\fP
294 should not do anything for a successful search.
295 In libc and glibc (before glibc 2.3), the
296 implementation violates the specification,
297 updating the \fIdata\fP for the given \fIkey\fP in this case.
298 .P
299 Individual hash table entries can be added, but not deleted.
300 .SH EXAMPLES
301 The following program inserts 24 items into a hash table, then prints
302 some of them.
303 .P
304 .\" SRC BEGIN (hsearch.c)
305 .EX
306 #include <search.h>
307 #include <stdio.h>
308 #include <stdlib.h>
309 \&
310 static char *data[] = { "alpha", "bravo", "charlie", "delta",
311 "echo", "foxtrot", "golf", "hotel", "india", "juliet",
312 "kilo", "lima", "mike", "november", "oscar", "papa",
313 "quebec", "romeo", "sierra", "tango", "uniform",
314 "victor", "whisky", "x\-ray", "yankee", "zulu"
315 };
316 \&
317 int
318 main(void)
319 {
320 ENTRY e;
321 ENTRY *ep;
322 \&
323 hcreate(30);
324 \&
325 for (size_t i = 0; i < 24; i++) {
326 e.key = data[i];
327 /* data is just an integer, instead of a
328 pointer to something */
329 e.data = (void *) i;
330 ep = hsearch(e, ENTER);
331 /* there should be no failures */
332 if (ep == NULL) {
333 fprintf(stderr, "entry failed\en");
334 exit(EXIT_FAILURE);
335 }
336 }
337 \&
338 for (size_t i = 22; i < 26; i++) {
339 /* print two entries from the table, and
340 show that two are not in the table */
341 e.key = data[i];
342 ep = hsearch(e, FIND);
343 printf("%9.9s \-> %9.9s:%d\en", e.key,
344 ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0);
345 }
346 hdestroy();
347 exit(EXIT_SUCCESS);
348 }
349 .EE
350 .\" SRC END
351 .SH SEE ALSO
352 .BR bsearch (3),
353 .BR lsearch (3),
354 .BR malloc (3),
355 .BR tsearch (3)