man3/hsearch.3

   1 .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de)
   2 .\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk
   3 .\"     <mtk.manpages@gmail.com>
   4 .\"
   5 .\" This is free documentation; you can redistribute it and/or
   6 .\" modify it under the terms of the GNU General Public License as
   7 .\" published by the Free Software Foundation; either version 2 of
   8 .\" the License, or (at your option) any later version.
   9 .\"
  10 .\" The GNU General Public License's references to "object code"
  11 .\" and "executables" are to be interpreted as the output of any
  12 .\" document formatting or typesetting system, including
  13 .\" intermediate and printed output.
  14 .\"
  15 .\" This manual is distributed in the hope that it will be useful,
  16 .\" but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 .\" GNU General Public License for more details.
  19 .\"
  20 .\" You should have received a copy of the GNU General Public
  21 .\" License along with this manual; if not, see
  22 .\" <http://www.gnu.org/licenses/>.
  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 .\" 2008-09-02, mtk: various additions and rewrites
  30 .\" 2008-09-03, mtk, restructured somewhat, in part after suggestions from
  31 .\"     Timothy S. Nelson <wayland@wayland.id.au>
  32 .\"
  33 .TH HSEARCH 3 2011-09-10 "GNU" "Linux Programmer's Manual"
  34 .SH NAME
  35 hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r,
  36 hsearch_r \- hash table management
  37 .SH SYNOPSIS
  38 .nf
  39 .B #include <search.h>
  40 .sp
  41 .BI "int hcreate(size_t " nel );
  42 .sp
  43 .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action );
  44 .sp
  45 .B "void hdestroy(void);"
  46 .sp
  47 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  48 .br
  49 .B #include <search.h>
  50 .sp
  51 .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab );
  52 .sp
  53 .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval ,
  54 .BI "              struct hsearch_data *" htab );
  55 .sp
  56 .BI "void hdestroy_r(struct hsearch_data *" htab );
  57 .fi
  58 .SH DESCRIPTION
  59 The three functions
  60 .BR hcreate (),
  61 .BR hsearch (),
  62 and
  63 .BR hdestroy ()
  64 allow the caller to create and manage a hash search table
  65 containing entries consisting of a key (a string) and associated data.
  66 Using these functions, only one hash table can be used at a time.
  67
  68 The three functions
  69 .BR hcreate_r (),
  70 .BR hsearch_r (),
  71 .BR hdestroy_r ()
  72 are reentrant versions that allow a program to use
  73 more than one hash search table at the same time.
  74 The last argument,
  75 .IR htab ,
  76 points to a structure that describes the table
  77 on which the function is to operate.
  78 The programmer should treat this structure as opaque
  79 (i.e., do not attempt to directly access or modify
  80 the fields in this structure).
  81
  82 First a hash table must be created using
  83 .BR hcreate ().
  84 The argument \fInel\fP specifies the maximum number of entries
  85 in the table.
  86 (This maximum cannot be changed later, so choose it wisely.)
  87 The implementation may adjust this value upward to improve the
  88 performance of the resulting hash table.
  89 .\" e.g., in glibc it is raised to the next higher prime number
  90
  91 The
  92 .BR hcreate_r ()
  93 function performs the same task as
  94 .BR hcreate (),
  95 but for the table described by the structure
  96 .IR *htab .
  97 The structure pointed to by
  98 .I htab
  99 must be zeroed before the first call to
 100 .BR hcreate_r ().
 101
 102 The function
 103 .BR hdestroy ()
 104 frees the memory occupied by the hash table that was created by
 105 .BR hcreate ().
 106 After calling
 107 .BR hdestroy ()
 108 a new hash table can be created using
 109 .BR hcreate ().
 110 The
 111 .BR hdestroy_r ()
 112 function performs the analogous task for a hash table described by
 113 .IR *htab ,
 114 which was previously created using
 115 .BR hcreate_r ().
 116
 117 The
 118 .BR hsearch ()
 119 function searches the hash table for an
 120 item with the same key as \fIitem\fP (where "the same" is determined using
 121 .BR strcmp (3)),
 122 and if successful returns a pointer to it.
 123
 124 The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in
 125 \fI<search.h>\fP as follows:
 126 .in +4n
 127 .sp
 128 .nf
 129 typedef struct entry {
 130     char *key;
 131     void *data;
 132 } ENTRY;
 133 .in
 134 .fi
 135 .sp
 136 The field \fIkey\fP points to a null-terminated string which is the
 137 search key.
 138 The field \fIdata\fP points to data that is associated with that key.
 139
 140 The argument \fIaction\fP determines what
 141 .BR hsearch ()
 142 does after an unsuccessful search.
 143 This argument must either have the value
 144 .BR ENTER ,
 145 meaning insert a copy of
 146 .IR item
 147 (and return a pointer to the new hash table entry as the function result),
 148 or the value
 149 .BR FIND ,
 150 meaning that NULL should be returned.
 151 (If
 152 .I action
 153 is
 154 .BR FIND ,
 155 then
 156 .I data
 157 is ignored.)
 158
 159 The
 160 .BR hsearch_r ()
 161 function is like
 162 .BR hsearch ()
 163 but operates on the hash table described by
 164 .IR *htab .
 165 The
 166 .BR hsearch_r ()
 167 function differs from
 168 .BR hsearch ()
 169 in that a pointer to the found item is returned in
 170 .IR *retval ,
 171 rather than as the function result.
 172 .SH RETURN VALUE
 173 .BR hcreate ()
 174 and
 175 .BR hcreate_r ()
 176 return nonzero on success.
 177 They return 0 on error.
 178
 179 On success,
 180 .BR hsearch ()
 181 returns a pointer to an entry in the hash table.
 182 .BR hsearch ()
 183 returns NULL on error, that is,
 184 if \fIaction\fP is \fBENTER\fP and
 185 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
 186 cannot be found in the hash table.
 187 .BR hsearch_r ()
 188 returns nonzero on success, and 0 on error.
 189 .SH ERRORS
 190 .LP
 191 .BR hcreate_r ()
 192 and
 193 .BR hdestroy_r ()
 194 can fail for the following reasons:
 195 .TP
 196 .B EINVAL
 197 .I htab
 198 is NULL.
 199 .PP
 200 .BR hsearch ()
 201 and
 202 .BR hsearch_r ()
 203 can fail for the following reasons:
 204 .TP
 205 .B ENOMEM
 206 .I action
 207 was
 208 .BR ENTER ,
 209 .I key
 210 was not found in the table,
 211 and there was no room in the table to add a new entry.
 212 .TP
 213 .B ESRCH
 214 .I action
 215 was
 216 .BR FIND ,
 217 and
 218 .I key
 219 was not found in the table.
 220 .PP
 221 POSIX.1-2001 only specifies the
 222 .B ENOMEM
 223 error.
 224 .SH CONFORMING TO
 225 The functions
 226 .BR hcreate (),
 227 .BR hsearch (),
 228 and
 229 .BR hdestroy ()
 230 are from SVr4, and are described in POSIX.1-2001.
 231 The functions
 232 .BR hcreate_r (),
 233 .BR hsearch_r (),
 234 and
 235 .BR hdestroy_r ()
 236 are GNU extensions.
 237 .SH NOTES
 238 Hash table implementations are usually more efficient when the
 239 table contains enough free space to minimize collisions.
 240 Typically, this means that
 241 .I nel
 242 should be at least 25% larger than the maximum number of elements
 243 that the caller expects to store in the table.
 244
 245 The
 246 .BR hdestroy ()
 247 and
 248 .BR hdestroy_r ()
 249 functions do not free the buffers pointed to by the
 250 .I key
 251 and
 252 .I data
 253 elements of the hash table entries.
 254 (It can't do this because it doesn't know
 255 whether these buffers were allocated dynamically.)
 256 If these buffers need to be freed (perhaps because the program
 257 is repeatedly creating and destroying hash tables,
 258 rather than creating a single table whose lifetime
 259 matches that of the program),
 260 then the program must maintain bookkeeping data structures that
 261 allow it to free them.
 262 .SH BUGS
 263 SVr4 and POSIX.1-2001 specify that \fIaction\fP
 264 is significant only for unsuccessful searches, so that an \fBENTER\fP
 265 should not do anything for a successful search.
 266 In libc and glibc (before version 2.3), the
 267 implementation violates the specification,
 268 updating the \fIdata\fP for the given \fIkey\fP in this case.
 269
 270 Individual hash table entries can be added, but not deleted.
 271 .SH EXAMPLE
 272 .PP
 273 The following program inserts 24 items into a hash table, then prints
 274 some of them.
 275 .nf
 276
 277 #include <stdio.h>
 278 #include <stdlib.h>
 279 #include <search.h>
 280
 281 char *data[] = { "alpha", "bravo", "charlie", "delta",
 282      "echo", "foxtrot", "golf", "hotel", "india", "juliet",
 283      "kilo", "lima", "mike", "november", "oscar", "papa",
 284      "quebec", "romeo", "sierra", "tango", "uniform",
 285      "victor", "whisky", "x\-ray", "yankee", "zulu"
 286 };
 287
 288 int
 289 main(void)
 290 {
 291     ENTRY e, *ep;
 292     int i;
 293
 294     hcreate(30);
 295
 296     for (i = 0; i < 24; i++) {
 297         e.key = data[i];
 298         /* data is just an integer, instead of a
 299            pointer to something */
 300         e.data = (void *) i;
 301         ep = hsearch(e, ENTER);
 302         /* there should be no failures */
 303         if (ep == NULL) {
 304             fprintf(stderr, "entry failed\\n");
 305             exit(EXIT_FAILURE);
 306         }
 307     }
 308
 309     for (i = 22; i < 26; i++) {
 310         /* print two entries from the table, and
 311            show that two are not in the table */
 312         e.key = data[i];
 313         ep = hsearch(e, FIND);
 314         printf("%9.9s \-> %9.9s:%d\\n", e.key,
 315                ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0);
 316     }
 317     hdestroy();
 318     exit(EXIT_SUCCESS);
 319 }
 320 .fi
 321 .SH SEE ALSO
 322 .BR bsearch (3),
 323 .BR lsearch (3),
 324 .BR malloc (3),
 325 .BR tsearch (3)