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.\" $FreeBSD$ 30.\" 31.Dd July 21, 2014 32.Dt HCREATE 3 33.Os 34.Sh NAME 35.Nm hcreate , 36.Nm hcreate_r , 37.Nm hdestroy , 38.Nm hdestroy_r , 39.Nm hsearch , 40.Nm hsearch_r 41.Nd manage hash search table 42.Sh LIBRARY 43.Lb libc 44.Sh SYNOPSIS 45.In search.h 46.Ft int 47.Fn hcreate "size_t nel" 48.Ft int 49.Fn hcreate_r "size_t nel" "struct hsearch_data *table" 50.Ft void 51.Fn hdestroy "void" 52.Ft void 53.Fn hdestroy_r "struct hsearch_data *table" 54.Ft ENTRY * 55.Fn hsearch "ENTRY item" "ACTION action" 56.Ft int 57.Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table" 58.Sh DESCRIPTION 59The 60.Fn hcreate , 61.Fn hcreate_r , 62.Fn hdestroy , 63.Fn hdestroy_r 64.Fn hsearch , 65and 66.Fn hsearch_r 67functions manage hash search tables. 68.Pp 69The 70.Fn hcreate 71function allocates sufficient space for the table, and the application should 72ensure it is called before 73.Fn hsearch 74is used. 75The 76.Fa nel 77argument is an estimate of the maximum 78number of entries that the table should contain. 79This number may be adjusted upward by the 80algorithm in order to obtain certain mathematically favorable circumstances. 81.Pp 82The 83.Fn hdestroy 84function disposes of the search table, and may be followed by another call to 85.Fn hcreate . 86After the call to 87.Fn hdestroy , 88the data can no longer be considered accessible. 89The 90.Fn hdestroy 91function calls 92.Xr free 3 93for each comparison key in the search table 94but not the data item associated with the key. 95.Pp 96The 97.Fn hsearch 98function is a hash-table search routine. 99It returns a pointer into a hash table 100indicating the location at which an entry can be found. 101The 102.Fa item 103argument is a structure of type 104.Vt ENTRY 105(defined in the 106.In search.h 107header) that contains two pointers: 108.Fa item.key 109points to the comparison key (a 110.Vt "char *" ) , 111and 112.Fa item.data 113(a 114.Vt "void *" ) 115points to any other data to be associated with 116that key. 117The comparison function used by 118.Fn hsearch 119is 120.Xr strcmp 3 . 121The 122.Fa action 123argument is a 124member of an enumeration type 125.Vt ACTION 126indicating the disposition of the entry if it cannot be 127found in the table. 128.Dv ENTER 129indicates that the 130.Fa item 131should be inserted in the table at an 132appropriate point. 133.Dv FIND 134indicates that no entry should be made. 135Unsuccessful resolution is 136indicated by the return of a 137.Dv NULL 138pointer. 139.Pp 140The comparison key (passed to 141.Fn hsearch 142as 143.Fa item.key ) 144must be allocated using 145.Xr malloc 3 146if 147.Fa action 148is 149.Dv ENTER 150and 151.Fn hdestroy 152is called. 153.Pp 154The 155.Fn hcreate_r , 156.Fn hdestroy_r , 157and 158.Fn hsearch_r 159functions are re-entrant versions of the above functions that can 160operate on a table supplied by the user. 161The 162.Fn hsearch_r 163function returns 164.Dv 0 165if the action is 166.Dv ENTER 167and the element cannot be created, 168.Dv 1 169otherwise. 170If the element exists or can be created, it will be placed in 171.Fa itemp , 172otherwise 173.Fa itemp 174will be set to 175.Dv NULL . 176.Sh RETURN VALUES 177The 178.Fn hcreate 179and 180.Fn hcreate_r 181functions return 0 if the table creation failed and the global variable 182.Va errno 183is set to indicate the error; 184otherwise, a non-zero value is returned. 185.Pp 186The 187.Fn hdestroy 188and 189.Fn hdestroy_r 190functions return no value. 191.Pp 192The 193.Fn hsearch 194and 195.Fn hsearch_r 196functions return a 197.Dv NULL 198pointer if either the 199.Fa action 200is 201.Dv FIND 202and the 203.Fa item 204could not be found or the 205.Fa action 206is 207.Dv ENTER 208and the table is full. 209.Sh EXAMPLES 210The following example reads in strings followed by two numbers 211and stores them in a hash table, discarding duplicates. 212It then reads in strings and finds the matching entry in the hash 213table and prints it out. 214.Bd -literal 215#include <stdio.h> 216#include <search.h> 217#include <string.h> 218#include <stdlib.h> 219 220struct info { /* This is the info stored in the table */ 221 int age, room; /* other than the key. */ 222}; 223 224#define NUM_EMPL 5000 /* # of elements in search table. */ 225 226int 227main(void) 228{ 229 char str[BUFSIZ]; /* Space to read string */ 230 struct info info_space[NUM_EMPL]; /* Space to store employee info. */ 231 struct info *info_ptr = info_space; /* Next space in info_space. */ 232 ENTRY item; 233 ENTRY *found_item; /* Name to look for in table. */ 234 char name_to_find[30]; 235 int i = 0; 236 237 /* Create table; no error checking is performed. */ 238 (void) hcreate(NUM_EMPL); 239 240 while (scanf("%s%d%d", str, &info_ptr->age, 241 &info_ptr->room) != EOF && i++ < NUM_EMPL) { 242 /* Put information in structure, and structure in item. */ 243 item.key = strdup(str); 244 item.data = info_ptr; 245 info_ptr++; 246 /* Put item into table. */ 247 (void) hsearch(item, ENTER); 248 } 249 250 /* Access table. */ 251 item.key = name_to_find; 252 while (scanf("%s", item.key) != EOF) { 253 if ((found_item = hsearch(item, FIND)) != NULL) { 254 /* If item is in the table. */ 255 (void)printf("found %s, age = %d, room = %d\en", 256 found_item->key, 257 ((struct info *)found_item->data)->age, 258 ((struct info *)found_item->data)->room); 259 } else 260 (void)printf("no such employee %s\en", name_to_find); 261 } 262 hdestroy(); 263 return 0; 264} 265.Ed 266.Sh ERRORS 267The 268.Fn hcreate 269.Fn hcreate_r , 270.Fn hsearch 271and 272.Fn hsearch_r 273functions will fail if: 274.Bl -tag -width Er 275.It Bq Er ENOMEM 276Insufficient memory is available. 277.It Bq Er EINVAL 278A table already exists. 279.El 280.Pp 281The 282.Fn hsearch 283and 284.Fn hsearch_r 285functions will also fail if the action is 286.Dv SEARCH 287and the element is not found: 288.Bl -tag -width Er 289.It Bq Er ESRCH 290The 291.Fa item 292given is not found. 293.El 294.Sh SEE ALSO 295.Xr bsearch 3 , 296.Xr lsearch 3 , 297.Xr malloc 3 , 298.Xr strcmp 3 , 299.Xr tsearch 3 300.Sh STANDARDS 301The 302.Fn hcreate , 303.Fn hdestroy , 304and 305.Fn hsearch 306functions conform to 307.St -xpg4.2 . 308.Sh HISTORY 309The 310.Fn hcreate , 311.Fn hdestroy , 312and 313.Fn hsearch 314functions first appeared in 315.At V . 316The 317.Fn hcreate_r , 318.Fn hdestroy_r 319and 320.Fn hsearch_r 321functions are 322.Tn GNU 323extensions. 324.Sh BUGS 325The original, 326.Pf non- Tn GNU 327interface permits the use of only one hash table at a time. 328