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