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