]>
Commit | Line | Data |
---|---|---|
fea681da MK |
1 | .\" Hey Emacs! This file is -*- nroff -*- source. |
2 | .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de) | |
3 | .\" | |
4 | .\" This is free documentation; you can redistribute it and/or | |
5 | .\" modify it under the terms of the GNU General Public License as | |
6 | .\" published by the Free Software Foundation; either version 2 of | |
7 | .\" the License, or (at your option) any later version. | |
8 | .\" | |
9 | .\" The GNU General Public License's references to "object code" | |
10 | .\" and "executables" are to be interpreted as the output of any | |
11 | .\" document formatting or typesetting system, including | |
12 | .\" intermediate and printed output. | |
13 | .\" | |
14 | .\" This manual is distributed in the hope that it will be useful, | |
15 | .\" but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | .\" GNU General Public License for more details. | |
18 | .\" | |
19 | .\" You should have received a copy of the GNU General Public | |
20 | .\" License along with this manual; if not, write to the Free | |
21 | .\" Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, | |
22 | .\" USA. | |
23 | .\" | |
24 | .\" References consulted: | |
25 | .\" SunOS 4.1.1 man pages | |
26 | .\" Modified Sat Sep 30 21:52:01 1995 by Jim Van Zandt <jrv@vanzandt.mv.com> | |
27 | .\" Remarks from dhw@gamgee.acad.emich.edu Fri Jun 19 06:46:31 1998 | |
28 | .\" Modified 2001-12-26, 2003-11-28, 2004-05-20, aeb | |
29 | .\" | |
30 | .TH HSEARCH 3 2004-05-20 "GNU" "Linux Programmer's Manual" | |
31 | .SH NAME | |
ffd18676 MK |
32 | hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, |
33 | hsearch_r \- hash table management | |
fea681da | 34 | .SH SYNOPSIS |
b9f02710 | 35 | .nf |
fea681da MK |
36 | .B #include <search.h> |
37 | .sp | |
38 | .BI "int hcreate(size_t " nel ); | |
39 | .sp | |
40 | .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action ); | |
41 | .sp | |
42 | .B "void hdestroy(void);" | |
cf0a9ace | 43 | .sp |
fea681da MK |
44 | .B #define _GNU_SOURCE |
45 | .br | |
46 | .B #include <search.h> | |
47 | .sp | |
48 | .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" tab ); | |
49 | .sp | |
c13182ef | 50 | .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" ret , |
b9f02710 | 51 | .BI " struct hsearch_data *" tab ); |
fea681da MK |
52 | .sp |
53 | .BI "void hdestroy_r(struct hsearch_data *" tab ); | |
b9f02710 | 54 | .fi |
fea681da MK |
55 | .SH DESCRIPTION |
56 | The three functions | |
e511ffb6 MK |
57 | .BR hcreate (), |
58 | .BR hsearch (), | |
fea681da | 59 | and |
e511ffb6 | 60 | .BR hdestroy () |
fea681da MK |
61 | allow the user to create a hash table (only one at a time) |
62 | which associates a key with any data. | |
63 | .PP | |
60a90ecd MK |
64 | First the table must be created with the function |
65 | .BR hcreate (). | |
fea681da MK |
66 | The argument \fInel\fP is an estimate of the maximum number of entries |
67 | in the table. | |
60a90ecd MK |
68 | The function |
69 | .BR hcreate () | |
70 | may adjust this value upward to improve the | |
fea681da MK |
71 | performance of the resulting hash table. |
72 | .PP | |
60a90ecd MK |
73 | The corresponding function |
74 | .BR hdestroy () | |
75 | frees the memory occupied by | |
fea681da MK |
76 | the hash table so that a new table can be constructed. |
77 | .PP | |
78 | The argument \fIitem\fP is of type \fBENTRY\fP, which is a typedef defined in | |
79 | \fI<search.h>\fP and includes these elements: | |
bd191423 | 80 | .in +4n |
fea681da MK |
81 | .sp |
82 | .nf | |
c13182ef | 83 | typedef struct entry { |
a08ea57c MK |
84 | char *key; |
85 | void *data; | |
7295b7ed | 86 | } ENTRY; |
bd191423 | 87 | .in |
fea681da MK |
88 | .fi |
89 | .sp | |
28d88c17 | 90 | The field \fIkey\fP points to the null-terminated string which is the |
fea681da MK |
91 | search key. |
92 | The field \fIdata\fP points to the data associated with that key. | |
60a90ecd MK |
93 | The function |
94 | .BR hsearch () | |
95 | searches the hash table for an | |
fea681da MK |
96 | item with the same key as \fIitem\fP (where "the same" is determined using |
97 | .BR strcmp (3)), | |
98 | and if successful returns a pointer to it. | |
60a90ecd MK |
99 | The argument \fIaction\fP determines what |
100 | .BR hsearch () | |
101 | does | |
c13182ef MK |
102 | after an unsuccessful search. |
103 | A value of \fBENTER\fP instructs it to | |
fea681da | 104 | insert a copy of \fIitem\fP, while a value of \fBFIND\fP means to return |
35e21ba7 | 105 | NULL. |
fea681da MK |
106 | .PP |
107 | The three functions | |
e511ffb6 MK |
108 | .BR hcreate_r (), |
109 | .BR hsearch_r (), | |
110 | .BR hdestroy_r () | |
fea681da | 111 | are reentrant versions that allow the use of more than one table. |
c13182ef MK |
112 | The last argument used identifies the table. |
113 | The struct it points to | |
fea681da | 114 | must be zeroed before the first call to |
63aa9df0 | 115 | .BR hcreate_r (). |
fea681da | 116 | .SH "RETURN VALUE" |
60a90ecd MK |
117 | .BR hcreate () |
118 | and | |
119 | .BR hcreate_r () | |
120 | return 0 when allocation of the memory | |
eba72288 | 121 | for the hash table fails, non-zero otherwise. |
fea681da | 122 | .LP |
60a90ecd MK |
123 | .BR hsearch () |
124 | returns NULL if \fIaction\fP is \fBENTER\fP and | |
fea681da MK |
125 | the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP |
126 | cannot be found in the hash table. | |
127 | .LP | |
60a90ecd MK |
128 | .BR hsearch_r () |
129 | returns 0 if \fIaction\fP is \fBENTER\fP and | |
eba72288 | 130 | the hash table is full, and non-zero otherwise. |
fea681da MK |
131 | .SH ERRORS |
132 | POSIX documents | |
133 | .TP | |
134 | .B ENOMEM | |
135 | Out of memory. | |
136 | .LP | |
137 | The glibc implementation will return the following two errors. | |
138 | .TP | |
139 | .B ENOMEM | |
140 | Table full with \fIaction\fP set to \fBENTER\fP. | |
141 | .TP | |
142 | .B ESRCH | |
c4bb193f | 143 | The \fIaction\fP argument is \fBFIND\fP and no corresponding element |
fea681da | 144 | is found in the table. |
a7fadb55 | 145 | .SH "CONFORMING TO" |
fea681da | 146 | The functions |
e511ffb6 MK |
147 | .BR hcreate (), |
148 | .BR hsearch (), | |
fea681da | 149 | and |
e511ffb6 | 150 | .BR hdestroy () |
68e1685c | 151 | are from SVr4, and are described in POSIX.1-2001. |
fea681da | 152 | The functions |
e511ffb6 MK |
153 | .BR hcreate_r (), |
154 | .BR hsearch_r (), | |
155 | .BR hdestroy_r () | |
fea681da MK |
156 | are GNU extensions. |
157 | .SH BUGS | |
68e1685c | 158 | SVr4 and POSIX.1-2001 specify that \fIaction\fP |
d9a10d9d | 159 | is significant only for unsuccessful searches, so that an \fBENTER\fP |
c13182ef MK |
160 | should not do anything for a successful search. |
161 | The libc and glibc | |
fea681da MK |
162 | implementations update the \fIdata\fP for the given \fIkey\fP |
163 | in this case. | |
164 | .\" Tue Jan 29 09:27:40 2002: fixed in latest glibc snapshot | |
165 | .LP | |
166 | Individual hash table entries can be added, but not deleted. | |
167 | .SH EXAMPLE | |
168 | .PP | |
169 | The following program inserts 24 items in to a hash table, then prints | |
170 | some of them. | |
171 | .nf | |
172 | ||
cf0a9ace MK |
173 | #include <stdio.h> |
174 | #include <stdlib.h> | |
175 | #include <search.h> | |
c13182ef | 176 | |
cf0a9ace MK |
177 | char *data[] = { "alpha", "bravo", "charlie", "delta", |
178 | "echo", "foxtrot", "golf", "hotel", "india", "juliet", | |
179 | "kilo", "lima", "mike", "november", "oscar", "papa", | |
180 | "quebec", "romeo", "sierra", "tango", "uniform", | |
29059a65 | 181 | "victor", "whisky", "x\-ray", "yankee", "zulu" |
cf0a9ace | 182 | }; |
fea681da | 183 | |
c13182ef MK |
184 | int |
185 | main(void) | |
41798314 | 186 | { |
cf0a9ace MK |
187 | ENTRY e, *ep; |
188 | int i; | |
c13182ef | 189 | |
cf0a9ace MK |
190 | /* starting with small table, and letting it grow does not work */ |
191 | hcreate(30); | |
192 | for (i = 0; i < 24; i++) { | |
c13182ef MK |
193 | e.key = data[i]; |
194 | /* data is just an integer, instead of a | |
cf0a9ace | 195 | pointer to something */ |
0c535394 | 196 | e.data = (void *) i; |
cf0a9ace MK |
197 | ep = hsearch(e, ENTER); |
198 | /* there should be no failures */ | |
199 | if (ep == NULL) { | |
fea681da | 200 | fprintf(stderr, "entry failed\\n"); |
4c44ffe5 | 201 | exit(EXIT_FAILURE); |
cf0a9ace | 202 | } |
fea681da | 203 | } |
cf0a9ace MK |
204 | for (i = 22; i < 26; i++) { |
205 | /* print two entries from the table, and | |
206 | show that two are not in the table */ | |
207 | e.key = data[i]; | |
208 | ep = hsearch(e, FIND); | |
209 | printf("%9.9s \-> %9.9s:%d\\n", e.key, | |
29059a65 | 210 | ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0); |
cf0a9ace | 211 | } |
5bc8c34c | 212 | exit(EXIT_SUCCESS); |
cf0a9ace | 213 | } |
fea681da MK |
214 | .fi |
215 | .SH "SEE ALSO" | |
216 | .BR bsearch (3), | |
217 | .BR lsearch (3), | |
218 | .BR malloc (3), | |
0a90178c MK |
219 | .BR tsearch (3), |
220 | .BR feature_test_macros (7) |