Debian Codegraph @

upstream/debian-unstable/man3/hsearch.3

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