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