lib/libc/stdlib/hcreate.3

   1 .\"-
   2 .\" Copyright (c) 1999 The NetBSD Foundation, Inc.
   3 .\" All rights reserved.
   4 .\"
   5 .\" This code is derived from software contributed to The NetBSD Foundation
   6 .\" by Klaus Klein.
   7 .\"
   8 .\" Redistribution and use in source and binary forms, with or without
   9 .\" modification, are permitted provided that the following conditions
  10 .\" are met:
  11 .\" 1. Redistributions of source code must retain the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer.
  13 .\" 2. Redistributions in binary form must reproduce the above copyright
  14 .\"    notice, this list of conditions and the following disclaimer in the
  15 .\"    documentation and/or other materials provided with the distribution.
  16 .\"
  17 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  18 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  19 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20 .\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  21 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  25 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27 .\" POSSIBILITY OF SUCH DAMAGE.
  28 .\"
  29 .\" $FreeBSD$
  30 .\"
  31 .Dd February 6, 2017
  32 .Dt HCREATE 3
  33 .Os
  34 .Sh NAME
  35 .Nm hcreate ,
  36 .Nm hcreate_r ,
  37 .Nm hdestroy ,
  38 .Nm hdestroy_r ,
  39 .Nm hsearch ,
  40 .Nm hsearch_r
  41 .Nd manage hash search table
  42 .Sh LIBRARY
  43 .Lb libc
  44 .Sh SYNOPSIS
  45 .In search.h
  46 .Ft int
  47 .Fn hcreate "size_t nel"
  48 .Ft int
  49 .Fn hcreate_r "size_t nel" "struct hsearch_data *table"
  50 .Ft void
  51 .Fn hdestroy "void"
  52 .Ft void
  53 .Fn hdestroy_r "struct hsearch_data *table"
  54 .Ft ENTRY *
  55 .Fn hsearch "ENTRY item" "ACTION action"
  56 .Ft int
  57 .Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table"
  58 .Sh DESCRIPTION
  59 The
  60 .Fn hcreate ,
  61 .Fn hcreate_r ,
  62 .Fn hdestroy ,
  63 .Fn hdestroy_r
  64 .Fn hsearch ,
  65 and
  66 .Fn hsearch_r
  67 functions manage hash search tables.
  68 .Pp
  69 The
  70 .Fn hcreate
  71 function allocates sufficient space for the table, and the application should
  72 ensure it is called before
  73 .Fn hsearch
  74 is used.
  75 The
  76 .Fa nel
  77 argument is an estimate of the maximum
  78 number of entries that the table should contain.
  79 As this implementation resizes the hash table dynamically,
  80 this argument is ignored.
  81 .Pp
  82 The
  83 .Fn hdestroy
  84 function disposes of the search table, and may be followed by another call to
  85 .Fn hcreate .
  86 After the call to
  87 .Fn hdestroy ,
  88 the data can no longer be considered accessible.
  89 The
  90 .Fn hdestroy
  91 function calls
  92 .Xr free 3
  93 for each comparison key in the search table
  94 but not the data item associated with the key.
  95 .Pp
  96 The
  97 .Fn hsearch
  98 function is a hash-table search routine.
  99 It returns a pointer into a hash table
 100 indicating the location at which an entry can be found.
 101 The
 102 .Fa item
 103 argument is a structure of type
 104 .Vt ENTRY
 105 (defined in the
 106 .In search.h
 107 header) that contains two pointers:
 108 .Fa item.key
 109 points to the comparison key (a
 110 .Vt "char *" ) ,
 111 and
 112 .Fa item.data
 113 (a
 114 .Vt "void *" )
 115 points to any other data to be associated with
 116 that key.
 117 The comparison function used by
 118 .Fn hsearch
 119 is
 120 .Xr strcmp 3 .
 121 The
 122 .Fa action
 123 argument is a
 124 member of an enumeration type
 125 .Vt ACTION
 126 indicating the disposition of the entry if it cannot be
 127 found in the table.
 128 .Dv ENTER
 129 indicates that the
 130 .Fa item
 131 should be inserted in the table at an
 132 appropriate point.
 133 .Dv FIND
 134 indicates that no entry should be made.
 135 Unsuccessful resolution is
 136 indicated by the return of a
 137 .Dv NULL
 138 pointer.
 139 .Pp
 140 The comparison key (passed to
 141 .Fn hsearch
 142 as
 143 .Fa item.key )
 144 must be allocated using
 145 .Xr malloc 3
 146 if
 147 .Fa action
 148 is
 149 .Dv ENTER
 150 and
 151 .Fn hdestroy
 152 is called.
 153 .Pp
 154 The
 155 .Fn hcreate_r ,
 156 .Fn hdestroy_r ,
 157 and
 158 .Fn hsearch_r
 159 functions are re-entrant versions of the above functions that can
 160 operate on a table supplied by the user.
 161 The
 162 .Fn hsearch_r
 163 function returns
 164 .Dv 0
 165 if the action is
 166 .Dv ENTER
 167 and the element cannot be created,
 168 .Dv 1
 169 otherwise.
 170 If the element exists or can be created, it will be placed in
 171 .Fa itemp ,
 172 otherwise
 173 .Fa itemp
 174 will be set to
 175 .Dv NULL .
 176 .Sh RETURN VALUES
 177 The
 178 .Fn hcreate
 179 and
 180 .Fn hcreate_r
 181 functions return 0 if the table creation failed and the global variable
 182 .Va errno
 183 is set to indicate the error;
 184 otherwise, a non-zero value is returned.
 185 .Pp
 186 The
 187 .Fn hdestroy
 188 and
 189 .Fn hdestroy_r
 190 functions return no value.
 191 .Pp
 192 The
 193 .Fn hsearch
 194 and
 195 .Fn hsearch_r
 196 functions return a
 197 .Dv NULL
 198 pointer if either the
 199 .Fa action
 200 is
 201 .Dv FIND
 202 and the
 203 .Fa item
 204 could not be found or the
 205 .Fa action
 206 is
 207 .Dv ENTER
 208 and the table is full.
 209 .Sh EXAMPLES
 210 The following example reads in strings followed by two numbers
 211 and stores them in a hash table, discarding duplicates.
 212 It then reads in strings and finds the matching entry in the hash
 213 table and prints it out.
 214 .Bd -literal
 215 #include <stdio.h>
 216 #include <search.h>
 217 #include <string.h>
 218 #include <stdlib.h>
 219
 220 struct info {                   /* This is the info stored in the table */
 221         int age, room;          /* other than the key. */
 222 };
 223
 224 #define NUM_EMPL        5000    /* # of elements in search table. */
 225
 226 int
 227 main(void)
 228 {
 229         char str[BUFSIZ]; /* Space to read string */
 230         struct info info_space[NUM_EMPL]; /* Space to store employee info. */
 231         struct info *info_ptr = info_space; /* Next space in info_space. */
 232         ENTRY item;
 233         ENTRY *found_item; /* Name to look for in table. */
 234         char name_to_find[30];
 235         int i = 0;
 236
 237         /* Create table; no error checking is performed. */
 238         (void) hcreate(NUM_EMPL);
 239
 240         while (scanf("%s%d%d", str, &info_ptr->age,
 241             &info_ptr->room) != EOF && i++ < NUM_EMPL) {
 242                 /* Put information in structure, and structure in item. */
 243                 item.key = strdup(str);
 244                 item.data = info_ptr;
 245                 info_ptr++;
 246                 /* Put item into table. */
 247                 (void) hsearch(item, ENTER);
 248         }
 249
 250         /* Access table. */
 251         item.key = name_to_find;
 252         while (scanf("%s", item.key) != EOF) {
 253                 if ((found_item = hsearch(item, FIND)) != NULL) {
 254                         /* If item is in the table. */
 255                         (void)printf("found %s, age = %d, room = %d\en",
 256                             found_item->key,
 257                             ((struct info *)found_item->data)->age,
 258                             ((struct info *)found_item->data)->room);
 259                 } else
 260                         (void)printf("no such employee %s\en", name_to_find);
 261         }
 262         hdestroy();
 263         return 0;
 264 }
 265 .Ed
 266 .Sh ERRORS
 267 The
 268 .Fn hcreate ,
 269 .Fn hcreate_r ,
 270 .Fn hsearch ,
 271 and
 272 .Fn hsearch_r
 273 functions will fail if:
 274 .Bl -tag -width Er
 275 .It Bq Er ENOMEM
 276 Insufficient memory is available.
 277 .El
 278 .Pp
 279 The
 280 .Fn hsearch
 281 and
 282 .Fn hsearch_r
 283 functions will also fail if the action is
 284 .Dv FIND
 285 and the element is not found:
 286 .Bl -tag -width Er
 287 .It Bq Er ESRCH
 288 The
 289 .Fa item
 290 given is not found.
 291 .El
 292 .Sh SEE ALSO
 293 .Xr bsearch 3 ,
 294 .Xr lsearch 3 ,
 295 .Xr malloc 3 ,
 296 .Xr strcmp 3 ,
 297 .Xr tsearch 3
 298 .Sh STANDARDS
 299 The
 300 .Fn hcreate ,
 301 .Fn hdestroy ,
 302 and
 303 .Fn hsearch
 304 functions conform to
 305 .St -xpg4.2 .
 306 .Sh HISTORY
 307 The
 308 .Fn hcreate ,
 309 .Fn hdestroy ,
 310 and
 311 .Fn hsearch
 312 functions first appeared in
 313 .At V .
 314 The
 315 .Fn hcreate_r ,
 316 .Fn hdestroy_r
 317 and
 318 .Fn hsearch_r
 319 functions are
 320 .Tn GNU
 321 extensions.
 322 .Sh BUGS
 323 The original,
 324 .Pf non- Tn GNU
 325 interface permits the use of only one hash table at a time.