1.\"- 2.\" Copyright (c) 1999 The NetBSD Foundation, Inc. 3.\" All rights reserved. 4.\" 5.\" This code is derived from software contributed to The NetBSD Foundation 6.\" by Klaus Klein. 7.\" 8.\" Redistribution and use in source and binary forms, with or without 9.\" modification, are permitted provided that the following conditions 10.\" are met: 11.\" 1. Redistributions of source code must retain the above copyright 12.\" notice, this list of conditions and the following disclaimer. 13.\" 2. Redistributions in binary form must reproduce the above copyright 14.\" notice, this list of conditions and the following disclaimer in the 15.\" documentation and/or other materials provided with the distribution. 16.\" 17.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 18.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 19.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 20.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 21.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27.\" POSSIBILITY OF SUCH DAMAGE. 28.\" 29.Dd February 6, 2017 30.Dt HCREATE 3 31.Os 32.Sh NAME 33.Nm hcreate , 34.Nm hcreate_r , 35.Nm hdestroy , 36.Nm hdestroy_r , 37.Nm hsearch , 38.Nm hsearch_r 39.Nd manage hash search table 40.Sh LIBRARY 41.Lb libc 42.Sh SYNOPSIS 43.In search.h 44.Ft int 45.Fn hcreate "size_t nel" 46.Ft int 47.Fn hcreate_r "size_t nel" "struct hsearch_data *table" 48.Ft void 49.Fn hdestroy "void" 50.Ft void 51.Fn hdestroy_r "struct hsearch_data *table" 52.Ft ENTRY * 53.Fn hsearch "ENTRY item" "ACTION action" 54.Ft int 55.Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table" 56.Sh DESCRIPTION 57The 58.Fn hcreate , 59.Fn hcreate_r , 60.Fn hdestroy , 61.Fn hdestroy_r 62.Fn hsearch , 63and 64.Fn hsearch_r 65functions manage hash search tables. 66.Pp 67The 68.Fn hcreate 69function allocates sufficient space for the table, and the application should 70ensure it is called before 71.Fn hsearch 72is used. 73The 74.Fa nel 75argument is an estimate of the maximum 76number of entries that the table should contain. 77As this implementation resizes the hash table dynamically, 78this argument is ignored. 79.Pp 80The 81.Fn hdestroy 82function disposes of the search table, and may be followed by another call to 83.Fn hcreate . 84After the call to 85.Fn hdestroy , 86the data can no longer be considered accessible. 87The 88.Fn hdestroy 89function calls 90.Xr free 3 91for each comparison key in the search table 92but not the data item associated with the key. 93.Pp 94The 95.Fn hsearch 96function is a hash-table search routine. 97It returns a pointer into a hash table 98indicating the location at which an entry can be found. 99The 100.Fa item 101argument is a structure of type 102.Vt ENTRY 103(defined in the 104.In search.h 105header) that contains two pointers: 106.Fa item.key 107points to the comparison key (a 108.Vt "char *" ) , 109and 110.Fa item.data 111(a 112.Vt "void *" ) 113points to any other data to be associated with 114that key. 115The comparison function used by 116.Fn hsearch 117is 118.Xr strcmp 3 . 119The 120.Fa action 121argument is a 122member of an enumeration type 123.Vt ACTION 124indicating the disposition of the entry if it cannot be 125found in the table. 126.Dv ENTER 127indicates that the 128.Fa item 129should be inserted in the table at an 130appropriate point. 131.Dv FIND 132indicates that no entry should be made. 133Unsuccessful resolution is 134indicated by the return of a 135.Dv NULL 136pointer. 137.Pp 138The comparison key (passed to 139.Fn hsearch 140as 141.Fa item.key ) 142must be allocated using 143.Xr malloc 3 144if 145.Fa action 146is 147.Dv ENTER 148and 149.Fn hdestroy 150is called. 151.Pp 152The 153.Fn hcreate_r , 154.Fn hdestroy_r , 155and 156.Fn hsearch_r 157functions are re-entrant versions of the above functions that can 158operate on a table supplied by the user. 159The 160.Fn hsearch_r 161function returns 162.Dv 0 163if the action is 164.Dv ENTER 165and the element cannot be created, 166.Dv 1 167otherwise. 168If the element exists or can be created, it will be placed in 169.Fa itemp , 170otherwise 171.Fa itemp 172will be set to 173.Dv NULL . 174.Sh RETURN VALUES 175The 176.Fn hcreate 177and 178.Fn hcreate_r 179functions return 0 if the table creation failed and the global variable 180.Va errno 181is set to indicate the error; 182otherwise, a non-zero value is returned. 183.Pp 184The 185.Fn hdestroy 186and 187.Fn hdestroy_r 188functions return no value. 189.Pp 190The 191.Fn hsearch 192and 193.Fn hsearch_r 194functions return a 195.Dv NULL 196pointer if either the 197.Fa action 198is 199.Dv FIND 200and the 201.Fa item 202could not be found or the 203.Fa action 204is 205.Dv ENTER 206and the table is full. 207.Sh EXAMPLES 208The following example reads in strings followed by two numbers 209and stores them in a hash table, discarding duplicates. 210It then reads in strings and finds the matching entry in the hash 211table and prints it out. 212.Bd -literal 213#include <stdio.h> 214#include <search.h> 215#include <string.h> 216#include <stdlib.h> 217 218struct info { /* This is the info stored in the table */ 219 int age, room; /* other than the key. */ 220}; 221 222#define NUM_EMPL 5000 /* # of elements in search table. */ 223 224int 225main(void) 226{ 227 char str[BUFSIZ]; /* Space to read string */ 228 struct info info_space[NUM_EMPL]; /* Space to store employee info. */ 229 struct info *info_ptr = info_space; /* Next space in info_space. */ 230 ENTRY item; 231 ENTRY *found_item; /* Name to look for in table. */ 232 char name_to_find[30]; 233 int i = 0; 234 235 /* Create table; no error checking is performed. */ 236 (void) hcreate(NUM_EMPL); 237 238 while (scanf("%s%d%d", str, &info_ptr->age, 239 &info_ptr->room) != EOF && i++ < NUM_EMPL) { 240 /* Put information in structure, and structure in item. */ 241 item.key = strdup(str); 242 item.data = info_ptr; 243 info_ptr++; 244 /* Put item into table. */ 245 (void) hsearch(item, ENTER); 246 } 247 248 /* Access table. */ 249 item.key = name_to_find; 250 while (scanf("%s", item.key) != EOF) { 251 if ((found_item = hsearch(item, FIND)) != NULL) { 252 /* If item is in the table. */ 253 (void)printf("found %s, age = %d, room = %d\en", 254 found_item->key, 255 ((struct info *)found_item->data)->age, 256 ((struct info *)found_item->data)->room); 257 } else 258 (void)printf("no such employee %s\en", name_to_find); 259 } 260 hdestroy(); 261 return 0; 262} 263.Ed 264.Sh ERRORS 265The 266.Fn hcreate , 267.Fn hcreate_r , 268.Fn hsearch , 269and 270.Fn hsearch_r 271functions will fail if: 272.Bl -tag -width Er 273.It Bq Er ENOMEM 274Insufficient memory is available. 275.El 276.Pp 277The 278.Fn hsearch 279and 280.Fn hsearch_r 281functions will also fail if the action is 282.Dv FIND 283and the element is not found: 284.Bl -tag -width Er 285.It Bq Er ESRCH 286The 287.Fa item 288given is not found. 289.El 290.Sh SEE ALSO 291.Xr bsearch 3 , 292.Xr lsearch 3 , 293.Xr malloc 3 , 294.Xr strcmp 3 , 295.Xr tsearch 3 296.Sh STANDARDS 297The 298.Fn hcreate , 299.Fn hdestroy , 300and 301.Fn hsearch 302functions conform to 303.St -xpg4.2 . 304.Sh HISTORY 305The 306.Fn hcreate , 307.Fn hdestroy , 308and 309.Fn hsearch 310functions first appeared in 311.At V . 312The 313.Fn hcreate_r , 314.Fn hdestroy_r 315and 316.Fn hsearch_r 317functions are 318.Tn GNU 319extensions. 320.Sh BUGS 321The original, 322.Pf non- Tn GNU 323interface permits the use of only one hash table at a time. 324