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.5 2006/05/26 19:39:37 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 .In 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 EXAMPLES
 140 The following example reads in strings followed by two numbers
 141 and stores them in a hash table, discarding duplicates.
 142 It then reads in strings and finds the matching entry in the hash
 143 table and prints it out.
 144 .Bd -literal
 145 #include <stdio.h>
 146 #include <search.h>
 147 #include <string.h>
 148 #include <stdlib.h>
 149
 150 struct info {                   /* This is the info stored in the table */
 151         int age, room;          /* other than the key. */
 152 };
 153
 154 #define NUM_EMPL        5000    /* # of elements in search table. */
 155
 156 int
 157 main(void)
 158 {
 159         char str[BUFSIZ]; /* Space to read string */
 160         struct info info_space[NUM_EMPL]; /* Space to store employee info. */
 161         struct info *info_ptr = info_space; /* Next space in info_space. */
 162         ENTRY item;
 163         ENTRY *found_item; /* Name to look for in table. */
 164         char name_to_find[30];
 165         int i = 0;
 166
 167         /* Create table; no error checking is performed. */
 168         (void) hcreate(NUM_EMPL);
 169
 170         while (scanf("%s%d%d", str, &info_ptr->age,
 171             &info_ptr->room) != EOF && i++ < NUM_EMPL) {
 172                 /* Put information in structure, and structure in item. */
 173                 item.key = strdup(str);
 174                 item.data = info_ptr;
 175                 info_ptr++;
 176                 /* Put item into table. */
 177                 (void) hsearch(item, ENTER);
 178         }
 179
 180         /* Access table. */
 181         item.key = name_to_find;
 182         while (scanf("%s", item.key) != EOF) {
 183                 if ((found_item = hsearch(item, FIND)) != NULL) {
 184                         /* If item is in the table. */
 185                         (void)printf("found %s, age = %d, room = %d\en",
 186                             found_item->key,
 187                             ((struct info *)found_item->data)->age,
 188                             ((struct info *)found_item->data)->room);
 189                 } else
 190                         (void)printf("no such employee %s\en", name_to_find);
 191         }
 192         hdestroy();
 193         return 0;
 194 }
 195 .Ed
 196 .Sh ERRORS
 197 The
 198 .Fn hcreate
 199 and
 200 .Fn hsearch
 201 functions may fail if:
 202 .Bl -tag -width Er
 203 .It Bq Er ENOMEM
 204 Insufficient storage space is available.
 205 .El
 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.