]>
Commit | Line | Data |
---|---|---|
fea681da | 1 | .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de) |
fc5911e1 MK |
2 | .\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk |
3 | .\" <mtk.manpages@gmail.com> | |
fea681da | 4 | .\" |
1dd72f9c | 5 | .\" %%%LICENSE_START(GPLv2+_DOC_FULL) |
fea681da MK |
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. | |
10 | .\" | |
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. | |
15 | .\" | |
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. | |
20 | .\" | |
21 | .\" You should have received a copy of the GNU General Public | |
c715f741 MK |
22 | .\" License along with this manual; if not, see |
23 | .\" <http://www.gnu.org/licenses/>. | |
6a8d8745 | 24 | .\" %%%LICENSE_END |
fea681da MK |
25 | .\" |
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 | |
4f5aae84 | 31 | .\" 2008-09-02, mtk: various additions and rewrites |
74f7e82a MK |
32 | .\" 2008-09-03, mtk, restructured somewhat, in part after suggestions from |
33 | .\" Timothy S. Nelson <wayland@wayland.id.au> | |
fea681da | 34 | .\" |
4b8c67d9 | 35 | .TH HSEARCH 3 2017-09-15 "GNU" "Linux Programmer's Manual" |
fea681da | 36 | .SH NAME |
ffd18676 MK |
37 | hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, |
38 | hsearch_r \- hash table management | |
fea681da | 39 | .SH SYNOPSIS |
b9f02710 | 40 | .nf |
fea681da | 41 | .B #include <search.h> |
68e4db0a | 42 | .PP |
fea681da | 43 | .BI "int hcreate(size_t " nel ); |
68e4db0a | 44 | .PP |
fea681da | 45 | .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action ); |
68e4db0a | 46 | .PP |
fea681da | 47 | .B "void hdestroy(void);" |
68e4db0a | 48 | .PP |
b80f966b | 49 | .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */" |
fea681da | 50 | .B #include <search.h> |
68e4db0a | 51 | .PP |
fc5911e1 | 52 | .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab ); |
68e4db0a | 53 | .PP |
fc5911e1 MK |
54 | .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval , |
55 | .BI " struct hsearch_data *" htab ); | |
68e4db0a | 56 | .PP |
fc5911e1 | 57 | .BI "void hdestroy_r(struct hsearch_data *" htab ); |
b9f02710 | 58 | .fi |
fea681da MK |
59 | .SH DESCRIPTION |
60 | The three functions | |
e511ffb6 MK |
61 | .BR hcreate (), |
62 | .BR hsearch (), | |
fea681da | 63 | and |
e511ffb6 | 64 | .BR hdestroy () |
0927f4c5 MK |
65 | allow the caller to create and manage a hash search table |
66 | containing entries consisting of a key (a string) and associated data. | |
fe80e23e | 67 | Using these functions, only one hash table can be used at a time. |
847e0d88 | 68 | .PP |
fc5911e1 MK |
69 | The three functions |
70 | .BR hcreate_r (), | |
71 | .BR hsearch_r (), | |
72 | .BR hdestroy_r () | |
73 | are reentrant versions that allow a program to use | |
0927f4c5 | 74 | more than one hash search table at the same time. |
fc5911e1 MK |
75 | The last argument, |
76 | .IR htab , | |
77 | points to a structure that describes the table | |
78 | on which the function is to operate. | |
79 | The programmer should treat this structure as opaque | |
80 | (i.e., do not attempt to directly access or modify | |
81 | the fields in this structure). | |
847e0d88 | 82 | .PP |
fc5911e1 | 83 | First a hash table must be created using |
60a90ecd | 84 | .BR hcreate (). |
fe80e23e | 85 | The argument \fInel\fP specifies the maximum number of entries |
fea681da | 86 | in the table. |
fe80e23e | 87 | (This maximum cannot be changed later, so choose it wisely.) |
fc5911e1 | 88 | The implementation may adjust this value upward to improve the |
fea681da | 89 | performance of the resulting hash table. |
fe80e23e | 90 | .\" e.g., in glibc it is raised to the next higher prime number |
847e0d88 | 91 | .PP |
fc5911e1 MK |
92 | The |
93 | .BR hcreate_r () | |
94 | function performs the same task as | |
95 | .BR hcreate (), | |
96 | but for the table described by the structure | |
97 | .IR *htab . | |
98 | The structure pointed to by | |
99 | .I htab | |
100 | must be zeroed before the first call to | |
101 | .BR hcreate_r (). | |
847e0d88 | 102 | .PP |
fc5911e1 | 103 | The function |
60a90ecd | 104 | .BR hdestroy () |
fc5911e1 MK |
105 | frees the memory occupied by the hash table that was created by |
106 | .BR hcreate (). | |
fe80e23e | 107 | After calling |
211c7df8 | 108 | .BR hdestroy (), |
fe80e23e MK |
109 | a new hash table can be created using |
110 | .BR hcreate (). | |
fc5911e1 MK |
111 | The |
112 | .BR hdestroy_r () | |
0927f4c5 MK |
113 | function performs the analogous task for a hash table described by |
114 | .IR *htab , | |
115 | which was previously created using | |
116 | .BR hcreate_r (). | |
847e0d88 | 117 | .PP |
fc5911e1 | 118 | The |
fe80e23e | 119 | .BR hsearch () |
fc5911e1 | 120 | function searches the hash table for an |
fe80e23e MK |
121 | item with the same key as \fIitem\fP (where "the same" is determined using |
122 | .BR strcmp (3)), | |
123 | and if successful returns a pointer to it. | |
847e0d88 | 124 | .PP |
fe80e23e MK |
125 | The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in |
126 | \fI<search.h>\fP as follows: | |
51f5698d | 127 | .PP |
207050fa MK |
128 | .in +4n |
129 | .EX | |
c13182ef | 130 | typedef struct entry { |
a08ea57c MK |
131 | char *key; |
132 | void *data; | |
7295b7ed | 133 | } ENTRY; |
b8302363 | 134 | .EE |
e646a1ba | 135 | .in |
51f5698d | 136 | .PP |
fe80e23e | 137 | The field \fIkey\fP points to a null-terminated string which is the |
fea681da | 138 | search key. |
fe80e23e | 139 | The field \fIdata\fP points to data that is associated with that key. |
847e0d88 | 140 | .PP |
60a90ecd MK |
141 | The argument \fIaction\fP determines what |
142 | .BR hsearch () | |
fe80e23e MK |
143 | does after an unsuccessful search. |
144 | This argument must either have the value | |
145 | .BR ENTER , | |
146 | meaning insert a copy of | |
fc5911e1 MK |
147 | .IR item |
148 | (and return a pointer to the new hash table entry as the function result), | |
fe80e23e MK |
149 | or the value |
150 | .BR FIND , | |
151 | meaning that NULL should be returned. | |
152 | (If | |
153 | .I action | |
154 | is | |
155 | .BR FIND , | |
156 | then | |
157 | .I data | |
158 | is ignored.) | |
847e0d88 | 159 | .PP |
fc5911e1 MK |
160 | The |
161 | .BR hsearch_r () | |
162 | function is like | |
163 | .BR hsearch () | |
164 | but operates on the hash table described by | |
165 | .IR *htab . | |
fe80e23e MK |
166 | The |
167 | .BR hsearch_r () | |
168 | function differs from | |
169 | .BR hsearch () | |
170 | in that a pointer to the found item is returned in | |
fc5911e1 | 171 | .IR *retval , |
fe80e23e | 172 | rather than as the function result. |
47297adb | 173 | .SH RETURN VALUE |
60a90ecd MK |
174 | .BR hcreate () |
175 | and | |
176 | .BR hcreate_r () | |
c7094399 | 177 | return nonzero on success. |
b4b02cc4 MK |
178 | They return 0 on error, with |
179 | .I errno | |
180 | set to indicate the cause of the error. | |
847e0d88 | 181 | .PP |
fe80e23e MK |
182 | On success, |
183 | .BR hsearch () | |
184 | returns a pointer to an entry in the hash table. | |
60a90ecd | 185 | .BR hsearch () |
fe80e23e MK |
186 | returns NULL on error, that is, |
187 | if \fIaction\fP is \fBENTER\fP and | |
fea681da MK |
188 | the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP |
189 | cannot be found in the hash table. | |
60a90ecd | 190 | .BR hsearch_r () |
c7094399 | 191 | returns nonzero on success, and 0 on error. |
b4b02cc4 MK |
192 | In the event of an error, these two functions set |
193 | .I errno | |
194 | to indicate the cause of the error. | |
fea681da | 195 | .SH ERRORS |
dd3568a1 | 196 | .PP |
fe80e23e | 197 | .BR hcreate_r () |
c658470d SL |
198 | and |
199 | .BR hdestroy_r () | |
fe80e23e MK |
200 | can fail for the following reasons: |
201 | .TP | |
202 | .B EINVAL | |
fc5911e1 | 203 | .I htab |
fe80e23e | 204 | is NULL. |
fe80e23e MK |
205 | .PP |
206 | .BR hsearch () | |
207 | and | |
208 | .BR hsearch_r () | |
209 | can fail for the following reasons: | |
210 | .TP | |
211 | .B ENOMEM | |
212 | .I action | |
213 | was | |
214 | .BR ENTER , | |
215 | .I key | |
216 | was not found in the table, | |
217 | and there was no room in the table to add a new entry. | |
218 | .TP | |
219 | .B ESRCH | |
220 | .I action | |
221 | was | |
7a4076fa | 222 | .BR FIND , |
fe80e23e MK |
223 | and |
224 | .I key | |
225 | was not found in the table. | |
226 | .PP | |
d94f4292 MK |
227 | POSIX.1 specifies only the |
228 | .\" PROX.1-2001, POSIX.1-2008 | |
fe80e23e MK |
229 | .B ENOMEM |
230 | error. | |
e92d82ff | 231 | .SH ATTRIBUTES |
dadcab37 PH |
232 | For an explanation of the terms used in this section, see |
233 | .BR attributes (7). | |
234 | .TS | |
235 | allbox; | |
b384eb70 | 236 | lbw25 lb lb |
dadcab37 PH |
237 | l l l. |
238 | Interface Attribute Value | |
239 | T{ | |
e92d82ff PH |
240 | .BR hcreate (), |
241 | .BR hsearch (), | |
b384eb70 | 242 | .br |
e92d82ff | 243 | .BR hdestroy () |
b384eb70 | 244 | T} Thread safety MT-Unsafe race:hsearch |
dadcab37 | 245 | T{ |
e92d82ff PH |
246 | .BR hcreate_r (), |
247 | .BR hsearch_r (), | |
b384eb70 | 248 | .br |
e92d82ff | 249 | .BR hdestroy_r () |
b384eb70 | 250 | T} Thread safety MT-Safe race:htab |
dadcab37 | 251 | .TE |
47297adb | 252 | .SH CONFORMING TO |
fea681da | 253 | The functions |
e511ffb6 MK |
254 | .BR hcreate (), |
255 | .BR hsearch (), | |
fea681da | 256 | and |
e511ffb6 | 257 | .BR hdestroy () |
d94f4292 | 258 | are from SVr4, and are described in POSIX.1-2001 and POSIX.1-2008. |
847e0d88 | 259 | .PP |
fea681da | 260 | The functions |
e511ffb6 MK |
261 | .BR hcreate_r (), |
262 | .BR hsearch_r (), | |
fc5911e1 | 263 | and |
e511ffb6 | 264 | .BR hdestroy_r () |
fea681da | 265 | are GNU extensions. |
fe80e23e MK |
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. | |
847e0d88 | 273 | .PP |
fe80e23e MK |
274 | The |
275 | .BR hdestroy () | |
fc5911e1 | 276 | and |
0cf28c34 | 277 | .BR hdestroy_r () |
fc5911e1 | 278 | functions do not free the buffers pointed to by the |
fe80e23e MK |
279 | .I key |
280 | and | |
281 | .I data | |
282 | elements of the hash table entries. | |
fc5911e1 MK |
283 | (It can't do this because it doesn't know |
284 | whether these buffers were allocated dynamically.) | |
fe80e23e MK |
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. | |
fea681da | 291 | .SH BUGS |
68e1685c | 292 | SVr4 and POSIX.1-2001 specify that \fIaction\fP |
d9a10d9d | 293 | is significant only for unsuccessful searches, so that an \fBENTER\fP |
c13182ef | 294 | should not do anything for a successful search. |
fc5911e1 MK |
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. | |
847e0d88 | 298 | .PP |
fea681da MK |
299 | Individual hash table entries can be added, but not deleted. |
300 | .SH EXAMPLE | |
301 | .PP | |
fe80e23e | 302 | The following program inserts 24 items into a hash table, then prints |
fea681da | 303 | some of them. |
207050fa MK |
304 | .PP |
305 | .EX | |
cf0a9ace MK |
306 | #include <stdio.h> |
307 | #include <stdlib.h> | |
308 | #include <search.h> | |
c13182ef | 309 | |
2ba8b63e | 310 | static char *data[] = { "alpha", "bravo", "charlie", "delta", |
cf0a9ace MK |
311 | "echo", "foxtrot", "golf", "hotel", "india", "juliet", |
312 | "kilo", "lima", "mike", "november", "oscar", "papa", | |
313 | "quebec", "romeo", "sierra", "tango", "uniform", | |
29059a65 | 314 | "victor", "whisky", "x\-ray", "yankee", "zulu" |
cf0a9ace | 315 | }; |
fea681da | 316 | |
c13182ef MK |
317 | int |
318 | main(void) | |
41798314 | 319 | { |
cf0a9ace MK |
320 | ENTRY e, *ep; |
321 | int i; | |
c13182ef | 322 | |
cf0a9ace | 323 | hcreate(30); |
fe80e23e | 324 | |
cf0a9ace | 325 | for (i = 0; i < 24; i++) { |
c13182ef MK |
326 | e.key = data[i]; |
327 | /* data is just an integer, instead of a | |
cf0a9ace | 328 | pointer to something */ |
0c535394 | 329 | e.data = (void *) i; |
cf0a9ace MK |
330 | ep = hsearch(e, ENTER); |
331 | /* there should be no failures */ | |
332 | if (ep == NULL) { | |
fea681da | 333 | fprintf(stderr, "entry failed\\n"); |
4c44ffe5 | 334 | exit(EXIT_FAILURE); |
cf0a9ace | 335 | } |
fea681da | 336 | } |
fe80e23e | 337 | |
cf0a9ace MK |
338 | for (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\\n", e.key, | |
29059a65 | 344 | ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0); |
cf0a9ace | 345 | } |
ed7bbec7 | 346 | hdestroy(); |
5bc8c34c | 347 | exit(EXIT_SUCCESS); |
cf0a9ace | 348 | } |
207050fa | 349 | .EE |
47297adb | 350 | .SH SEE ALSO |
fea681da MK |
351 | .BR bsearch (3), |
352 | .BR lsearch (3), | |
353 | .BR malloc (3), | |
0a4f8b7b | 354 | .BR tsearch (3) |