lib/libc/stdlib/hcreate.3

   1 .\" $FreeBSD: src/lib/libc/stdlib/hcreate.3,v 1.2.2.2 2003/04/05 13:53:05 dwmalone Exp $
   2 .\" $DragonFly: src/lib/libc/stdlib/hcreate.3,v 1.2 2003/06/17 04:26:46 dillon Exp $
   3 .\"
   4 .Dd May 8, 2001
   5 .Os
   6 .Dt HCREATE 3
   7 .Sh NAME
   8 .Nm hcreate , hdestroy , hsearch
   9 .Nd manage hash search table
  10 .Sh LIBRARY
  11 .Lb libc
  12 .Sh SYNOPSIS
  13 .In search.h
  14 .Ft int
  15 .Fn hcreate "size_t nel"
  16 .Ft void
  17 .Fn hdestroy void
  18 .Ft ENTRY *
  19 .Fn hsearch "ENTRY item" "ACTION action"
  20 .Sh DESCRIPTION
  21 The
  22 .Fn hcreate ,
  23 .Fn hdestroy ,
  24 and
  25 .Fn hsearch
  26 functions manage hash search tables.
  27 .Pp
  28 The
  29 .Fn hcreate
  30 function allocates sufficient space for the table, and the application should
  31 ensure it is called before
  32 .Fn hsearch
  33 is used.
  34 The
  35 .Fa nel
  36 argument is an estimate of the maximum
  37 number of entries that the table should contain.
  38 This number may be adjusted upward by the
  39 algorithm in order to obtain certain mathematically favorable circumstances.
  40 .Pp
  41 The
  42 .Fn hdestroy
  43 function disposes of the search table, and may be followed by another call to
  44 .Fn hcreate .
  45 After the call to
  46 .Fn hdestroy ,
  47 the data can no longer be considered accessible.
  48 The
  49 .Fn hdestroy
  50 function calls
  51 .Xr free 3
  52 for each comparison key in the search table
  53 but not the data item associated with the key.
  54 .Pp
  55 The
  56 .Fn hsearch
  57 function is a hash-table search routine.
  58 It returns a pointer into a hash table
  59 indicating the location at which an entry can be found.
  60 The
  61 .Fa item
  62 argument is a structure of type
  63 .Vt ENTRY
  64 (defined in the
  65 .Aq Pa search.h
  66 header) containing two pointers:
  67 .Fa item.key
  68 points to the comparison key (a
  69 .Vt "char *" ) ,
  70 and
  71 .Fa item.data
  72 (a
  73 .Vt "void *" )
  74 points to any other data to be associated with
  75 that key.
  76 The comparison function used by
  77 .Fn hsearch
  78 is
  79 .Xr strcmp 3 .
  80 The
  81 .Fa action
  82 argument is a
  83 member of an enumeration type
  84 .Vt ACTION
  85 indicating the disposition of the entry if it cannot be
  86 found in the table.
  87 .Dv ENTER
  88 indicates that the
  89 .Fa item
  90 should be inserted in the table at an
  91 appropriate point.
  92 .Dv FIND
  93 indicates that no entry should be made.
  94 Unsuccessful resolution is
  95 indicated by the return of a
  96 .Dv NULL
  97 pointer.
  98 .Pp
  99 The comparison key (passed to
 100 .Fn hsearch
 101 as
 102 .Fa item.key )
 103 must be allocated using
 104 .Xr malloc 3
 105 if
 106 .Fa action
 107 is
 108 .Dv ENTER
 109 and
 110 .Fn hdestroy
 111 is called.
 112 .Sh RETURN VALUES
 113 The
 114 .Fn hcreate
 115 function returns 0 if it cannot allocate sufficient space for the table;
 116 otherwise, it returns non-zero.
 117 .Pp
 118 The
 119 .Fn hdestroy
 120 function does not return a value.
 121 .Pp
 122 The
 123 .Fn hsearch
 124 function returns a
 125 .Dv NULL
 126 pointer if either the
 127 .Fa action
 128 is
 129 .Dv FIND
 130 and the
 131 .Fa item
 132 could not be found or the
 133 .Fa action
 134 is
 135 .Dv ENTER
 136 and the table is full.
 137 .Sh ERRORS
 138 The
 139 .Fn hcreate
 140 and
 141 .Fn hsearch
 142 functions may fail if:
 143 .Bl -tag -width Er
 144 .It Bq Er ENOMEM
 145 Insufficient storage space is available.
 146 .El
 147 .Sh EXAMPLES
 148 The following example reads in strings followed by two numbers
 149 and stores them in a hash table, discarding duplicates.
 150 It then reads in strings and finds the matching entry in the hash
 151 table and prints it out.
 152 .Bd -literal
 153 #include <stdio.h>
 154 #include <search.h>
 155 #include <string.h>
 156 #include <stdlib.h>
 157
 158 struct info {                   /* This is the info stored in the table */
 159         int age, room;          /* other than the key. */
 160 };
 161
 162 #define NUM_EMPL        5000    /* # of elements in search table. */
 163
 164 int
 165 main(void)
 166 {
 167         char str[BUFSIZ]; /* Space to read string */
 168         struct info info_space[NUM_EMPL]; /* Space to store employee info. */
 169         struct info *info_ptr = info_space; /* Next space in info_space. */
 170         ENTRY item;
 171         ENTRY *found_item; /* Name to look for in table. */
 172         char name_to_find[30];
 173         int i = 0;
 174
 175         /* Create table; no error checking is performed. */
 176         (void) hcreate(NUM_EMPL);
 177
 178         while (scanf("%s%d%d", str, &info_ptr->age,
 179             &info_ptr->room) != EOF && i++ < NUM_EMPL) {
 180                 /* Put information in structure, and structure in item. */
 181                 item.key = strdup(str);
 182                 item.data = info_ptr;
 183                 info_ptr++;
 184                 /* Put item into table. */
 185                 (void) hsearch(item, ENTER);
 186         }
 187
 188         /* Access table. */
 189         item.key = name_to_find;
 190         while (scanf("%s", item.key) != EOF) {
 191                 if ((found_item = hsearch(item, FIND)) != NULL) {
 192                         /* If item is in the table. */
 193                         (void)printf("found %s, age = %d, room = %d\en",
 194                             found_item->key,
 195                             ((struct info *)found_item->data)->age,
 196                             ((struct info *)found_item->data)->room);
 197                 } else
 198                         (void)printf("no such employee %s\en", name_to_find);
 199         }
 200         hdestroy();
 201         return 0;
 202 }
 203 .Ed
 204 .Sh SEE ALSO
 205 .Xr bsearch 3 ,
 206 .Xr lsearch 3 ,
 207 .Xr malloc 3 ,
 208 .Xr strcmp 3 ,
 209 .Xr tsearch 3
 210 .Sh STANDARDS
 211 The
 212 .Fn hcreate ,
 213 .Fn hdestroy ,
 214 and
 215 .Fn hsearch
 216 functions conform to
 217 .St -xpg4.2 .
 218 .Sh HISTORY
 219 The
 220 .Fn hcreate ,
 221 .Fn hdestroy ,
 222 and
 223 .Fn hsearch
 224 functions first appeared in
 225 .At V .
 226 .Sh BUGS
 227 The interface permits the use of only one hash table at a time.