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