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 2019-03-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 .PP
  43 .BI "int hcreate(size_t " nel );
  44 .PP
  45 .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action );
  46 .PP
  47 .B "void hdestroy(void);"
  48 .PP
  49 .BR "#define _GNU_SOURCE" "         /* See feature_test_macros(7) */"
  50 .B #include <search.h>
  51 .PP
  52 .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab );
  53 .PP
  54 .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval ,
  55 .BI "              struct hsearch_data *" htab );
  56 .PP
  57 .BI "void hdestroy_r(struct hsearch_data *" htab );
  58 .fi
  59 .SH DESCRIPTION
  60 The three functions
  61 .BR hcreate (),
  62 .BR hsearch (),
  63 and
  64 .BR hdestroy ()
  65 allow the caller to create and manage a hash search table
  66 containing entries consisting of a key (a string) and associated data.
  67 Using these functions, only one hash table can be used at a time.
  68 .PP
  69 The three functions
  70 .BR hcreate_r (),
  71 .BR hsearch_r (),
  72 .BR hdestroy_r ()
  73 are reentrant versions that allow a program to use
  74 more than one hash search table at the same time.
  75 The last argument,
  76 .IR htab ,
  77 points to a structure that describes the table
  78 on which the function is to operate.
  79 The programmer should treat this structure as opaque
  80 (i.e., do not attempt to directly access or modify
  81 the fields in this structure).
  82 .PP
  83 First a hash table must be created using
  84 .BR hcreate ().
  85 The argument \fInel\fP specifies the maximum number of entries
  86 in the table.
  87 (This maximum cannot be changed later, so choose it wisely.)
  88 The implementation may adjust this value upward to improve the
  89 performance of the resulting hash table.
  90 .\" e.g., in glibc it is raised to the next higher prime number
  91 .PP
  92 The
  93 .BR hcreate_r ()
  94 function performs the same task as
  95 .BR hcreate (),
  96 but for the table described by the structure
  97 .IR *htab .
  98 The structure pointed to by
  99 .I htab
 100 must be zeroed before the first call to
 101 .BR hcreate_r ().
 102 .PP
 103 The function
 104 .BR hdestroy ()
 105 frees the memory occupied by the hash table that was created by
 106 .BR hcreate ().
 107 After calling
 108 .BR hdestroy (),
 109 a new hash table can be created using
 110 .BR hcreate ().
 111 The
 112 .BR hdestroy_r ()
 113 function performs the analogous task for a hash table described by
 114 .IR *htab ,
 115 which was previously created using
 116 .BR hcreate_r ().
 117 .PP
 118 The
 119 .BR hsearch ()
 120 function searches the hash table for an
 121 item with the same key as \fIitem\fP (where "the same" is determined using
 122 .BR strcmp (3)),
 123 and if successful returns a pointer to it.
 124 .PP
 125 The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in
 126 \fI<search.h>\fP as follows:
 127 .PP
 128 .in +4n
 129 .EX
 130 typedef struct entry {
 131     char *key;
 132     void *data;
 133 } ENTRY;
 134 .EE
 135 .in
 136 .PP
 137 The field \fIkey\fP points to a null-terminated string which is the
 138 search key.
 139 The field \fIdata\fP points to data that is associated with that key.
 140 .PP
 141 The argument \fIaction\fP determines what
 142 .BR hsearch ()
 143 does after an unsuccessful search.
 144 This argument must either have the value
 145 .BR ENTER ,
 146 meaning insert a copy of
 147 .IR item
 148 (and return a pointer to the new hash table entry as the function result),
 149 or the value
 150 .BR FIND ,
 151 meaning that NULL should be returned.
 152 (If
 153 .I action
 154 is
 155 .BR FIND ,
 156 then
 157 .I data
 158 is ignored.)
 159 .PP
 160 The
 161 .BR hsearch_r ()
 162 function is like
 163 .BR hsearch ()
 164 but operates on the hash table described by
 165 .IR *htab .
 166 The
 167 .BR hsearch_r ()
 168 function differs from
 169 .BR hsearch ()
 170 in that a pointer to the found item is returned in
 171 .IR *retval ,
 172 rather than as the function result.
 173 .SH RETURN VALUE
 174 .BR hcreate ()
 175 and
 176 .BR hcreate_r ()
 177 return nonzero on success.
 178 They return 0 on error, with
 179 .I errno
 180 set to indicate the cause of the error.
 181 .PP
 182 On success,
 183 .BR hsearch ()
 184 returns a pointer to an entry in the hash table.
 185 .BR hsearch ()
 186 returns NULL on error, that is,
 187 if \fIaction\fP is \fBENTER\fP and
 188 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
 189 cannot be found in the hash table.
 190 .BR hsearch_r ()
 191 returns nonzero on success, and 0 on error.
 192 In the event of an error, these two functions set
 193 .I errno
 194 to indicate the cause of the error.
 195 .SH ERRORS
 196 .PP
 197 .BR hcreate_r ()
 198 and
 199 .BR hdestroy_r ()
 200 can fail for the following reasons:
 201 .TP
 202 .B EINVAL
 203 .I htab
 204 is NULL.
 205 .PP
 206 .BR hsearch ()
 207 and
 208 .BR hsearch_r ()
 209 can fail for the following reasons:
 210 .TP
 211 .B ENOMEM
 212 .I action
 213 was
 214 .BR ENTER ,
 215 .I key
 216 was not found in the table,
 217 and there was no room in the table to add a new entry.
 218 .TP
 219 .B ESRCH
 220 .I action
 221 was
 222 .BR FIND ,
 223 and
 224 .I key
 225 was not found in the table.
 226 .PP
 227 POSIX.1 specifies only the
 228 .\" PROX.1-2001, POSIX.1-2008
 229 .B ENOMEM
 230 error.
 231 .SH ATTRIBUTES
 232 For an explanation of the terms used in this section, see
 233 .BR attributes (7).
 234 .TS
 235 allbox;
 236 lbw25 lb lb
 237 l l l.
 238 Interface       Attribute       Value
 239 T{
 240 .BR hcreate (),
 241 .BR hsearch (),
 242 .br
 243 .BR hdestroy ()
 244 T}      Thread safety   MT-Unsafe race:hsearch
 245 T{
 246 .BR hcreate_r (),
 247 .BR hsearch_r (),
 248 .br
 249 .BR hdestroy_r ()
 250 T}      Thread safety   MT-Safe race:htab
 251 .TE
 252 .SH CONFORMING TO
 253 The functions
 254 .BR hcreate (),
 255 .BR hsearch (),
 256 and
 257 .BR hdestroy ()
 258 are from SVr4, and are described in POSIX.1-2001 and POSIX.1-2008.
 259 .PP
 260 The functions
 261 .BR hcreate_r (),
 262 .BR hsearch_r (),
 263 and
 264 .BR hdestroy_r ()
 265 are GNU extensions.
 266 .SH NOTES
 267 Hash table implementations are usually more efficient when the
 268 table contains enough free space to minimize collisions.
 269 Typically, this means that
 270 .I nel
 271 should be at least 25% larger than the maximum number of elements
 272 that the caller expects to store in the table.
 273 .PP
 274 The
 275 .BR hdestroy ()
 276 and
 277 .BR hdestroy_r ()
 278 functions do not free the buffers pointed to by the
 279 .I key
 280 and
 281 .I data
 282 elements of the hash table entries.
 283 (It can't do this because it doesn't know
 284 whether these buffers were allocated dynamically.)
 285 If these buffers need to be freed (perhaps because the program
 286 is repeatedly creating and destroying hash tables,
 287 rather than creating a single table whose lifetime
 288 matches that of the program),
 289 then the program must maintain bookkeeping data structures that
 290 allow it to free them.
 291 .SH BUGS
 292 SVr4 and POSIX.1-2001 specify that \fIaction\fP
 293 is significant only for unsuccessful searches, so that an \fBENTER\fP
 294 should not do anything for a successful search.
 295 In libc and glibc (before version 2.3), the
 296 implementation violates the specification,
 297 updating the \fIdata\fP for the given \fIkey\fP in this case.
 298 .PP
 299 Individual hash table entries can be added, but not deleted.
 300 .SH EXAMPLES
 301 .PP
 302 The following program inserts 24 items into a hash table, then prints
 303 some of them.
 304 .PP
 305 .EX
 306 #include <stdio.h>
 307 #include <stdlib.h>
 308 #include <search.h>
 309
 310 static char *data[] = { "alpha", "bravo", "charlie", "delta",
 311      "echo", "foxtrot", "golf", "hotel", "india", "juliet",
 312      "kilo", "lima", "mike", "november", "oscar", "papa",
 313      "quebec", "romeo", "sierra", "tango", "uniform",
 314      "victor", "whisky", "x\-ray", "yankee", "zulu"
 315 };
 316
 317 int
 318 main(void)
 319 {
 320     ENTRY e, *ep;
 321     int i;
 322
 323     hcreate(30);
 324
 325     for (i = 0; i < 24; i++) {
 326         e.key = data[i];
 327         /* data is just an integer, instead of a
 328            pointer to something */
 329         e.data = (void *) i;
 330         ep = hsearch(e, ENTER);
 331         /* there should be no failures */
 332         if (ep == NULL) {
 333             fprintf(stderr, "entry failed\en");
 334             exit(EXIT_FAILURE);
 335         }
 336     }
 337
 338     for (i = 22; i < 26; i++) {
 339         /* print two entries from the table, and
 340            show that two are not in the table */
 341         e.key = data[i];
 342         ep = hsearch(e, FIND);
 343         printf("%9.9s \-> %9.9s:%d\en", e.key,
 344                ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0);
 345     }
 346     hdestroy();
 347     exit(EXIT_SUCCESS);
 348 }
 349 .EE
 350 .SH SEE ALSO
 351 .BR bsearch (3),
 352 .BR lsearch (3),
 353 .BR malloc (3),
 354 .BR tsearch (3)