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