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