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