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