newlib/libc/search/hcreate.3

   1 .\" $FreeBSD: src/lib/libc/stdlib/hcreate.3,v 1.2 2001/07/09 15:54:36 ru 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 .Pp
  48 The
  49 .Fn hsearch
  50 function is a hash-table search routine.
  51 It returns a pointer into a hash table
  52 indicating the location at which an entry can be found.
  53 The
  54 .Fa item
  55 argument is a structure of type
  56 .Vt ENTRY
  57 (defined in the
  58 .Aq Pa search.h
  59 header) containing two pointers:
  60 .Fa item.key
  61 points to the comparison key (a
  62 .Vt "char *" ) ,
  63 and
  64 .Fa item.data
  65 (a
  66 .Vt "void *" )
  67 points to any other data to be associated with
  68 that key.
  69 The comparison function used by
  70 .Fn hsearch
  71 is
  72 .Xr strcmp 3 .
  73 The
  74 .Fa action
  75 argument is a
  76 member of an enumeration type
  77 .Vt ACTION
  78 indicating the disposition of the entry if it cannot be
  79 found in the table.
  80 .Dv ENTER
  81 indicates that the
  82 .Fa item
  83 should be inserted in the table at an
  84 appropriate point.
  85 .Dv FIND
  86 indicates that no entry should be made.
  87 Unsuccessful resolution is
  88 indicated by the return of a
  89 .Dv NULL
  90 pointer.
  91 .Sh RETURN VALUES
  92 The
  93 .Fn hcreate
  94 function returns 0 if it cannot allocate sufficient space for the table;
  95 otherwise, it returns non-zero.
  96 .Pp
  97 The
  98 .Fn hdestroy
  99 function does not return a value.
 100 .Pp
 101 The
 102 .Fn hsearch
 103 function returns a
 104 .Dv NULL
 105 pointer if either the
 106 .Fa action
 107 is
 108 .Dv FIND
 109 and the
 110 .Fa item
 111 could not be found or the
 112 .Fa action
 113 is
 114 .Dv ENTER
 115 and the table is full.
 116 .Sh ERRORS
 117 The
 118 .Fn hcreate
 119 and
 120 .Fn hsearch
 121 functions may fail if:
 122 .Bl -tag -width Er
 123 .It Bq Er ENOMEM
 124 Insufficient storage space is available.
 125 .El
 126 .Sh EXAMPLES
 127 The following example reads in strings followed by two numbers
 128 and stores them in a hash table, discarding duplicates.
 129 It then reads in strings and finds the matching entry in the hash
 130 table and prints it out.
 131 .Bd -literal
 132 #include <stdio.h>
 133 #include <search.h>
 134 #include <string.h>
 135
 136 struct info {                   /* This is the info stored in the table */
 137         int age, room;          /* other than the key. */
 138 };
 139
 140 #define NUM_EMPL        5000    /* # of elements in search table. */
 141
 142 int
 143 main(void)
 144 {
 145         char string_space[NUM_EMPL*20]; /* Space to store strings. */
 146         struct info info_space[NUM_EMPL]; /* Space to store employee info. */
 147         char *str_ptr = string_space; /* Next space in string_space. */
 148         struct info *info_ptr = info_space; /* Next space in info_space. */
 149         ENTRY item;
 150         ENTRY *found_item; /* Name to look for in table. */
 151         char name_to_find[30];
 152         int i = 0;
 153
 154         /* Create table; no error checking is performed. */
 155         (void) hcreate(NUM_EMPL);
 156
 157         while (scanf("%s%d%d", str_ptr, &info_ptr->age,
 158             &info_ptr->room) != EOF && i++ < NUM_EMPL) {
 159                 /* Put information in structure, and structure in item. */
 160                 item.key = str_ptr;
 161                 item.data = info_ptr;
 162                 str_ptr += strlen(str_ptr) + 1;
 163                 info_ptr++;
 164                 /* Put item into table. */
 165                 (void) hsearch(item, ENTER);
 166         }
 167
 168         /* Access table. */
 169         item.key = name_to_find;
 170         while (scanf("%s", item.key) != EOF) {
 171                 if ((found_item = hsearch(item, FIND)) != NULL) {
 172                         /* If item is in the table. */
 173                         (void)printf("found %s, age = %d, room = %d\en",
 174                             found_item->key,
 175                             ((struct info *)found_item->data)->age,
 176                             ((struct info *)found_item->data)->room);
 177                 } else
 178                         (void)printf("no such employee %s\en", name_to_find);
 179         }
 180         return 0;
 181 }
 182 .Ed
 183 .Sh SEE ALSO
 184 .Xr bsearch 3 ,
 185 .Xr lsearch 3 ,
 186 .Xr malloc 3 ,
 187 .Xr strcmp 3 ,
 188 .Xr tsearch 3
 189 .Sh STANDARDS
 190 The
 191 .Fn hcreate ,
 192 .Fn hdestroy ,
 193 and
 194 .Fn hsearch
 195 functions conform to
 196 .St -xpg4.2 .
 197 .Sh HISTORY
 198 The
 199 .Fn hcreate ,
 200 .Fn hdestroy ,
 201 and
 202 .Fn hsearch
 203 functions first appeared in
 204 .At V .
 205 .Sh BUGS
 206 The interface permits the use of only one hash table at a time.