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 .\" %%%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.
  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
  22 .\" License along with this manual; if not, see
  23 .\" <http://www.gnu.org/licenses/>.
  24 .\" %%%LICENSE_END
  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
  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>
  34 .\"
  35 .TH HSEARCH 3 2014-01-05 "GNU" "Linux Programmer's Manual"
  36 .SH NAME
  37 hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r,
  38 hsearch_r \- hash table management
  39 .SH SYNOPSIS
  40 .nf
  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);"
  48 .sp
  49 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  50 .br
  51 .B #include <search.h>
  52 .sp
  53 .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab );
  54 .sp
  55 .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval ,
  56 .BI "              struct hsearch_data *" htab );
  57 .sp
  58 .BI "void hdestroy_r(struct hsearch_data *" htab );
  59 .fi
  60 .SH DESCRIPTION
  61 The three functions
  62 .BR hcreate (),
  63 .BR hsearch (),
  64 and
  65 .BR hdestroy ()
  66 allow the caller to create and manage a hash search table
  67 containing entries consisting of a key (a string) and associated data.
  68 Using these functions, only one hash table can be used at a time.
  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
  75 more than one hash search table at the same time.
  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
  85 .BR hcreate ().
  86 The argument \fInel\fP specifies the maximum number of entries
  87 in the table.
  88 (This maximum cannot be changed later, so choose it wisely.)
  89 The implementation may adjust this value upward to improve the
  90 performance of the resulting hash table.
  91 .\" e.g., in glibc it is raised to the next higher prime number
  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
 105 .BR hdestroy ()
 106 frees the memory occupied by the hash table that was created by
 107 .BR hcreate ().
 108 After calling
 109 .BR hdestroy ()
 110 a new hash table can be created using
 111 .BR hcreate ().
 112 The
 113 .BR hdestroy_r ()
 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 ().
 118
 119 The
 120 .BR hsearch ()
 121 function searches the hash table for an
 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:
 128 .in +4n
 129 .sp
 130 .nf
 131 typedef struct entry {
 132     char *key;
 133     void *data;
 134 } ENTRY;
 135 .in
 136 .fi
 137 .sp
 138 The field \fIkey\fP points to a null-terminated string which is the
 139 search key.
 140 The field \fIdata\fP points to data that is associated with that key.
 141
 142 The argument \fIaction\fP determines what
 143 .BR hsearch ()
 144 does after an unsuccessful search.
 145 This argument must either have the value
 146 .BR ENTER ,
 147 meaning insert a copy of
 148 .IR item
 149 (and return a pointer to the new hash table entry as the function result),
 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.)
 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 .
 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
 172 .IR *retval ,
 173 rather than as the function result.
 174 .SH RETURN VALUE
 175 .BR hcreate ()
 176 and
 177 .BR hcreate_r ()
 178 return nonzero on success.
 179 They return 0 on error, with
 180 .I errno
 181 set to indicate the cause of the error.
 182
 183 On success,
 184 .BR hsearch ()
 185 returns a pointer to an entry in the hash table.
 186 .BR hsearch ()
 187 returns NULL on error, that is,
 188 if \fIaction\fP is \fBENTER\fP and
 189 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
 190 cannot be found in the hash table.
 191 .BR hsearch_r ()
 192 returns nonzero on success, and 0 on error.
 193 In the event of an error, these two functions set
 194 .I errno
 195 to indicate the cause of the error.
 196 .SH ERRORS
 197 .LP
 198 .BR hcreate_r ()
 199 and
 200 .BR hdestroy_r ()
 201 can fail for the following reasons:
 202 .TP
 203 .B EINVAL
 204 .I htab
 205 is NULL.
 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
 223 .BR FIND ,
 224 and
 225 .I key
 226 was not found in the table.
 227 .PP
 228 POSIX.1-2001 specifies only the
 229 .B ENOMEM
 230 error.
 231 .SH ATTRIBUTES
 232 .SS Multithreading (see pthreads(7))
 233 The
 234 .BR hcreate (),
 235 .BR hsearch (),
 236 and
 237 .BR hdestroy ()
 238 functions use a global space for storing the table, so they are not thread-safe.
 239 .LP
 240 The
 241 .BR hcreate_r (),
 242 .BR hsearch_r (),
 243 and
 244 .BR hdestroy_r ()
 245 functions are thread-safe.
 246 .SH CONFORMING TO
 247 The functions
 248 .BR hcreate (),
 249 .BR hsearch (),
 250 and
 251 .BR hdestroy ()
 252 are from SVr4, and are described in POSIX.1-2001.
 253 The functions
 254 .BR hcreate_r (),
 255 .BR hsearch_r (),
 256 and
 257 .BR hdestroy_r ()
 258 are GNU extensions.
 259 .SH NOTES
 260 Hash table implementations are usually more efficient when the
 261 table contains enough free space to minimize collisions.
 262 Typically, this means that
 263 .I nel
 264 should be at least 25% larger than the maximum number of elements
 265 that the caller expects to store in the table.
 266
 267 The
 268 .BR hdestroy ()
 269 and
 270 .BR hdestroy_r ()
 271 functions do not free the buffers pointed to by the
 272 .I key
 273 and
 274 .I data
 275 elements of the hash table entries.
 276 (It can't do this because it doesn't know
 277 whether these buffers were allocated dynamically.)
 278 If these buffers need to be freed (perhaps because the program
 279 is repeatedly creating and destroying hash tables,
 280 rather than creating a single table whose lifetime
 281 matches that of the program),
 282 then the program must maintain bookkeeping data structures that
 283 allow it to free them.
 284 .SH BUGS
 285 SVr4 and POSIX.1-2001 specify that \fIaction\fP
 286 is significant only for unsuccessful searches, so that an \fBENTER\fP
 287 should not do anything for a successful search.
 288 In libc and glibc (before version 2.3), the
 289 implementation violates the specification,
 290 updating the \fIdata\fP for the given \fIkey\fP in this case.
 291
 292 Individual hash table entries can be added, but not deleted.
 293 .SH EXAMPLE
 294 .PP
 295 The following program inserts 24 items into a hash table, then prints
 296 some of them.
 297 .nf
 298
 299 #include <stdio.h>
 300 #include <stdlib.h>
 301 #include <search.h>
 302
 303 static char *data[] = { "alpha", "bravo", "charlie", "delta",
 304      "echo", "foxtrot", "golf", "hotel", "india", "juliet",
 305      "kilo", "lima", "mike", "november", "oscar", "papa",
 306      "quebec", "romeo", "sierra", "tango", "uniform",
 307      "victor", "whisky", "x\-ray", "yankee", "zulu"
 308 };
 309
 310 int
 311 main(void)
 312 {
 313     ENTRY e, *ep;
 314     int i;
 315
 316     hcreate(30);
 317
 318     for (i = 0; i < 24; i++) {
 319         e.key = data[i];
 320         /* data is just an integer, instead of a
 321            pointer to something */
 322         e.data = (void *) i;
 323         ep = hsearch(e, ENTER);
 324         /* there should be no failures */
 325         if (ep == NULL) {
 326             fprintf(stderr, "entry failed\\n");
 327             exit(EXIT_FAILURE);
 328         }
 329     }
 330
 331     for (i = 22; i < 26; i++) {
 332         /* print two entries from the table, and
 333            show that two are not in the table */
 334         e.key = data[i];
 335         ep = hsearch(e, FIND);
 336         printf("%9.9s \-> %9.9s:%d\\n", e.key,
 337                ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0);
 338     }
 339     hdestroy();
 340     exit(EXIT_SUCCESS);
 341 }
 342 .fi
 343 .SH SEE ALSO
 344 .BR bsearch (3),
 345 .BR lsearch (3),
 346 .BR malloc (3),
 347 .BR tsearch (3)