original/man3/hsearch.3

   1 .\" Hey Emacs! This file is -*- nroff -*- source.
   2 .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de)
   3 .\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk
   4 .\"     <mtk.manpages@gmail.com>
   5 .\"
   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, write to the Free
  23 .\" Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111,
  24 .\" USA.
  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 2008-10-06 "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.
 180
 181 On success,
 182 .BR hsearch ()
 183 returns a pointer to an entry in the hash table.
 184 .BR hsearch ()
 185 returns NULL on error, that is,
 186 if \fIaction\fP is \fBENTER\fP and
 187 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
 188 cannot be found in the hash table.
 189 .BR hsearch_r ()
 190 returns nonzero on success, and 0 on error.
 191 .SH ERRORS
 192 .LP
 193 .BR hcreate ()
 194 and
 195 .BR hcreate_r ()
 196 can fail for the following reasons:
 197 .TP
 198 .B EINVAL
 199 .RB ( hcreate_r ())
 200 .I htab
 201 is NULL.
 202 .TP
 203 .B ENOMEM
 204 Table full with \fIaction\fP set to \fBENTER\fP.
 205 .TP
 206 .B ESRCH
 207 The \fIaction\fP argument is \fBFIND\fP and no corresponding element
 208 is found in the table.
 209 .\" hdestroy_r() can set errno to EINVAL if 'tab' is NULL.
 210 .PP
 211 .BR hsearch ()
 212 and
 213 .BR hsearch_r ()
 214 can fail for the following reasons:
 215 .TP
 216 .B ENOMEM
 217 .I action
 218 was
 219 .BR ENTER ,
 220 .I key
 221 was not found in the table,
 222 and there was no room in the table to add a new entry.
 223 .TP
 224 .B ESRCH
 225 .I action
 226 was
 227 .BR FIND ,
 228 and
 229 .I key
 230 was not found in the table.
 231 .PP
 232 POSIX.1-2001 only specifies the
 233 .B ENOMEM
 234 error.
 235 .SH "CONFORMING TO"
 236 The functions
 237 .BR hcreate (),
 238 .BR hsearch (),
 239 and
 240 .BR hdestroy ()
 241 are from SVr4, and are described in POSIX.1-2001.
 242 The functions
 243 .BR hcreate_r (),
 244 .BR hsearch_r (),
 245 and
 246 .BR hdestroy_r ()
 247 are GNU extensions.
 248 .SH NOTES
 249 Hash table implementations are usually more efficient when the
 250 table contains enough free space to minimize collisions.
 251 Typically, this means that
 252 .I nel
 253 should be at least 25% larger than the maximum number of elements
 254 that the caller expects to store in the table.
 255
 256 The
 257 .BR hdestroy ()
 258 and
 259 .BR hdestroy _r()
 260 functions do not free the buffers pointed to by the
 261 .I key
 262 and
 263 .I data
 264 elements of the hash table entries.
 265 (It can't do this because it doesn't know
 266 whether these buffers were allocated dynamically.)
 267 If these buffers need to be freed (perhaps because the program
 268 is repeatedly creating and destroying hash tables,
 269 rather than creating a single table whose lifetime
 270 matches that of the program),
 271 then the program must maintain bookkeeping data structures that
 272 allow it to free them.
 273 .SH BUGS
 274 SVr4 and POSIX.1-2001 specify that \fIaction\fP
 275 is significant only for unsuccessful searches, so that an \fBENTER\fP
 276 should not do anything for a successful search.
 277 In libc and glibc (before version 2.3), the
 278 implementation violates the specification,
 279 updating the \fIdata\fP for the given \fIkey\fP in this case.
 280
 281 Individual hash table entries can be added, but not deleted.
 282 .SH EXAMPLE
 283 .PP
 284 The following program inserts 24 items into a hash table, then prints
 285 some of them.
 286 .nf
 287
 288 #include <stdio.h>
 289 #include <stdlib.h>
 290 #include <search.h>
 291
 292 char *data[] = { "alpha", "bravo", "charlie", "delta",
 293      "echo", "foxtrot", "golf", "hotel", "india", "juliet",
 294      "kilo", "lima", "mike", "november", "oscar", "papa",
 295      "quebec", "romeo", "sierra", "tango", "uniform",
 296      "victor", "whisky", "x\-ray", "yankee", "zulu"
 297 };
 298
 299 int
 300 main(void)
 301 {
 302     ENTRY e, *ep;
 303     int i;
 304
 305     hcreate(30);
 306
 307     for (i = 0; i < 24; i++) {
 308         e.key = data[i];
 309         /* data is just an integer, instead of a
 310            pointer to something */
 311         e.data = (void *) i;
 312         ep = hsearch(e, ENTER);
 313         /* there should be no failures */
 314         if (ep == NULL) {
 315             fprintf(stderr, "entry failed\\n");
 316             exit(EXIT_FAILURE);
 317         }
 318     }
 319
 320     for (i = 22; i < 26; i++) {
 321         /* print two entries from the table, and
 322            show that two are not in the table */
 323         e.key = data[i];
 324         ep = hsearch(e, FIND);
 325         printf("%9.9s \-> %9.9s:%d\\n", e.key,
 326                ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0);
 327     }
 328     hdestroy();
 329     exit(EXIT_SUCCESS);
 330 }
 331 .fi
 332 .SH "SEE ALSO"
 333 .BR bsearch (3),
 334 .BR lsearch (3),
 335 .BR malloc (3),
 336 .BR tsearch (3)