1 .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de)
2 .\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk
3 .\" <mtk.manpages@gmail.com>
5 .\" %%%LICENSE_START(GPLv2+_DOC_FULL)
6 .\" This is free documentation; you can redistribute it and/or
7 .\" modify it under the terms of the GNU General Public License as
8 .\" published by the Free Software Foundation; either version 2 of
9 .\" the License, or (at your option) any later version.
11 .\" The GNU General Public License's references to "object code"
12 .\" and "executables" are to be interpreted as the output of any
13 .\" document formatting or typesetting system, including
14 .\" intermediate and printed output.
16 .\" This manual is distributed in the hope that it will be useful,
17 .\" but WITHOUT ANY WARRANTY; without even the implied warranty of
18 .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 .\" GNU General Public License for more details.
21 .\" You should have received a copy of the GNU General Public
22 .\" License along with this manual; if not, see
23 .\" <http://www.gnu.org/licenses/>.
26 .\" References consulted:
27 .\" SunOS 4.1.1 man pages
28 .\" Modified Sat Sep 30 21:52:01 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
29 .\" Remarks from dhw@gamgee.acad.emich.edu Fri Jun 19 06:46:31 1998
30 .\" Modified 2001-12-26, 2003-11-28, 2004-05-20, aeb
31 .\" 2008-09-02, mtk: various additions and rewrites
32 .\" 2008-09-03, mtk, restructured somewhat, in part after suggestions from
33 .\" Timothy S. Nelson <wayland@wayland.id.au>
35 .TH HSEARCH 3 2021-03-22 "GNU" "Linux Programmer's Manual"
37 hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r,
38 hsearch_r \- hash table management
41 .B #include <search.h>
43 .BI "int hcreate(size_t " nel );
44 .B "void hdestroy(void);"
46 .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action );
48 .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
49 .B #include <search.h>
51 .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab );
52 .BI "void hdestroy_r(struct hsearch_data *" htab );
54 .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval ,
55 .BI " struct hsearch_data *" htab );
63 allow the caller to create and manage a hash search table
64 containing entries consisting of a key (a string) and associated data.
65 Using these functions, only one hash table can be used at a time.
71 are reentrant versions that allow a program to use
72 more than one hash search table at the same time.
75 points to a structure that describes the table
76 on which the function is to operate.
77 The programmer should treat this structure as opaque
78 (i.e., do not attempt to directly access or modify
79 the fields in this structure).
81 First a hash table must be created using
83 The argument \fInel\fP specifies the maximum number of entries
85 (This maximum cannot be changed later, so choose it wisely.)
86 The implementation may adjust this value upward to improve the
87 performance of the resulting hash table.
88 .\" e.g., in glibc it is raised to the next higher prime number
92 function performs the same task as
94 but for the table described by the structure
96 The structure pointed to by
98 must be zeroed before the first call to
103 frees the memory occupied by the hash table that was created by
107 a new hash table can be created using
111 function performs the analogous task for a hash table described by
113 which was previously created using
118 function searches the hash table for an
119 item with the same key as \fIitem\fP (where "the same" is determined using
121 and if successful returns a pointer to it.
123 The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in
124 \fI<search.h>\fP as follows:
128 typedef struct entry {
135 The field \fIkey\fP points to a null-terminated string which is the
137 The field \fIdata\fP points to data that is associated with that key.
139 The argument \fIaction\fP determines what
141 does after an unsuccessful search.
142 This argument must either have the value
144 meaning insert a copy of
146 (and return a pointer to the new hash table entry as the function result),
149 meaning that NULL should be returned.
162 but operates on the hash table described by
166 function differs from
168 in that a pointer to the found item is returned in
170 rather than as the function result.
175 return nonzero on success.
176 They return 0 on error, with
178 set to indicate the error.
182 returns a pointer to an entry in the hash table.
184 returns NULL on error, that is,
185 if \fIaction\fP is \fBENTER\fP and
186 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
187 cannot be found in the hash table.
189 returns nonzero on success, and 0 on error.
190 In the event of an error, these two functions set
192 to indicate the error.
197 can fail for the following reasons:
206 can fail for the following reasons:
213 was not found in the table,
214 and there was no room in the table to add a new entry.
222 was not found in the table.
224 POSIX.1 specifies only the
225 .\" PROX.1-2001, POSIX.1-2008
229 For an explanation of the terms used in this section, see
237 Interface Attribute Value
242 T} Thread safety MT-Unsafe race:hsearch
247 T} Thread safety MT-Safe race:htab
258 are from SVr4, and are described in POSIX.1-2001 and POSIX.1-2008.
267 Hash table implementations are usually more efficient when the
268 table contains enough free space to minimize collisions.
269 Typically, this means that
271 should be at least 25% larger than the maximum number of elements
272 that the caller expects to store in the table.
278 functions do not free the buffers pointed to by the
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.
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 version 2.3), the
296 implementation violates the specification,
297 updating the \fIdata\fP for the given \fIkey\fP in this case.
299 Individual hash table entries can be added, but not deleted.
301 The following program inserts 24 items into a hash table, then prints
309 static char *data[] = { "alpha", "bravo", "charlie", "delta",
310 "echo", "foxtrot", "golf", "hotel", "india", "juliet",
311 "kilo", "lima", "mike", "november", "oscar", "papa",
312 "quebec", "romeo", "sierra", "tango", "uniform",
313 "victor", "whisky", "x\-ray", "yankee", "zulu"
324 for (int i = 0; i < 24; i++) {
326 /* data is just an integer, instead of a
327 pointer to something */
329 ep = hsearch(e, ENTER);
330 /* there should be no failures */
332 fprintf(stderr, "entry failed\en");
337 for (int i = 22; i < 26; i++) {
338 /* print two entries from the table, and
339 show that two are not in the table */
341 ep = hsearch(e, FIND);
342 printf("%9.9s \-> %9.9s:%d\en", e.key,
343 ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0);