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