[444] | 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. |
---|