1.\" $NetBSD: hcreate.3,v 1.10 2011/09/15 09:14:54 wiz Exp $ 2.\" 3.\" Copyright (c) 1999 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Klaus Klein. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd September 14, 2011 31.Dt HCREATE 3 32.Os 33.Sh NAME 34.Nm hcreate , 35.Nm hcreate_r , 36.Nm hdestroy , 37.Nm hdestroy_r , 38.Nm hsearch , 39.Nm hsearch_r 40.Nd manage hash search table 41.Sh LIBRARY 42.Lb libc 43.Sh SYNOPSIS 44.In search.h 45.Ft int 46.Fn hcreate "size_t nel" 47.Ft int 48.Fn hcreate_r "size_t nel" "struct hsearch_data *table" 49.Ft void 50.Fn hdestroy "void" 51.Ft void 52.Fn hdestroy_r "struct hsearch_data *table" 53.Ft ENTRY * 54.Fn hsearch "ENTRY item" "ACTION action" 55.Ft int 56.Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table" 57.Sh DESCRIPTION 58The 59.Fn hcreate , 60.Fn hcreate_r , 61.Fn hdestroy , 62.Fn hdestroy_r 63.Fn hsearch , 64and 65.Fn hsearch_r 66functions manage hash search tables. 67.Pp 68The 69.Fn hcreate 70function allocates and initializes the table. 71The 72.Fa nel 73argument specifies an estimate of the maximum number of entries to be held 74by the table. 75Unless further memory allocation fails, supplying an insufficient 76.Fa nel 77value will not result in functional harm, although a performance degradation 78may occur. 79Initialization using the 80.Fn hcreate 81function is mandatory prior to any access operations using 82.Fn hsearch . 83.Pp 84The 85.Fn hdestroy 86function destroys a table previously created using 87.Fn hcreate . 88After a call to 89.Fn hdestroy , 90the data can no longer be accessed. 91.Pp 92The 93.Fn hsearch 94function is used to search to the hash table. 95It returns a pointer into the 96hash table indicating the address of an item. 97The 98.Fa item 99argument is of type 100.Vt ENTRY , 101defined in the 102.In search.h 103header. 104This is a structure type that contains two pointers: 105.Pp 106.Bl -tag -compact -offset indent -width "void *data " 107.It Fa char *key 108comparison key 109.It Fa void *data 110pointer to data associated with 111.Fa key 112.El 113.Pp 114The key comparison function used by 115.Fn hsearch 116is 117.Xr strcmp 3 . 118.Pp 119The 120.Fa action 121argument is of type 122.Vt ACTION , 123an enumeration type which defines the following values: 124.Bl -tag -offset indent -width ENTERXX 125.It Dv ENTER 126Insert 127.Fa item 128into the hash table. 129If an existing item with the same key is found, it is not replaced. 130Note that the 131.Fa key 132and 133.Fa data 134elements of 135.Fa item 136are used directly by the new table entry. 137The storage for the 138key must not be modified during the lifetime of the hash table. 139.It Dv FIND 140Search the hash table without inserting 141.Fa item . 142.El 143.Pp 144Note that the comparison 145.Fa key 146must be allocated using 147.Xr malloc 3 148or 149.Xr calloc 3 150if action is 151.Dv ENTER 152and 153.Fn hdestroy 154will be called. 155This is because 156.Fn hdestroy 157will call 158.Xr free 3 159for each comparison 160.Fa key 161(but not 162.Fa data ) . 163Typically the comparison 164.Fa key 165is allocated by using 166.Xr strdup 3 . 167.Pp 168The 169.Fn hcreate_r , 170.Fn hdestroy_r , 171and 172.Fn hsearch_r 173functions are re-entrant versions of the above functions that can 174operate on a table supplied by the user. 175The 176.Fn hsearch_r 177function returns 178.Dv 0 179if the action is 180.Dv ENTER 181and the element cannot be created, 182.Dv 1 183otherwise. 184If the element exists or can be created, it will be placed in 185.Fa itemp , 186otherwise 187.Fa itemp 188will be set to 189.Dv NULL . 190.Sh RETURN VALUES 191If successful, the 192.Fn hcreate 193and 194.Fn hcreate_r 195functions return a non-zero value. 196Otherwise, a value of 197.Dv 0 198is returned and 199.Va errno 200is set to indicate the error. 201.Pp 202The 203.Fn hdestroy 204and 205.Fn hdestroy_r 206functions return no value. 207.Pp 208If successful, the 209.Fn hsearch 210function returns a pointer to hash table entry matching 211the provided key. 212If the action is 213.Dv FIND 214and the item was not found, or if the action is 215.Dv ENTER 216and the insertion failed, 217.Dv NULL 218is returned and 219.Va errno 220is set to indicate the error. 221If the action is 222.Dv ENTER 223and an entry already existed in the table matching the given 224key, the existing entry is returned and is not replaced. 225.Pp 226The 227.Fn hsearch_r 228function returns 229.Dv 1 230unless the table is full, when it returns 231.Dv 0 . 232If 233.Fn hsearch 234returns 235.Dv 0 236or the element is not found, 237.Va errno 238is set to indicate the error. 239.Sh ERRORS 240The 241.Fn hcreate , 242.Fn hcreate_r , 243.Fn hsearch 244and 245.Fn hsearch_r 246functions will fail if: 247.Bl -tag -width Er 248.It Bq Er ENOMEM 249Insufficient memory is available. 250.El 251.Pp 252The 253.Fn hsearch 254and 255.Fn hsearch_r 256functions will also fail if the action is 257.Dv SEARCH 258and the element is not found: 259.Bl -tag -width Er 260.It Bq Er ESRCH 261The 262.Fa item 263given is not found. 264.El 265.Sh SEE ALSO 266.Xr bsearch 3 , 267.Xr lsearch 3 , 268.Xr malloc 3 , 269.Xr strcmp 3 270.Sh STANDARDS 271The 272.Fn hcreate , 273.Fn hdestroy 274and 275.Fn hsearch 276functions conform to 277.St -xpg4.2 . 278.Sh HISTORY 279The 280.Fn hcreate , 281.Fn hdestroy 282and 283.Fn hsearch 284functions first appeared in 285.At V . 286The 287.Fn hcreate_r , 288.Fn hdestroy_r 289and 290.Fn hsearch_r 291functions are 292.Tn GNU 293extensions. 294.Sh CAVEATS 295At least the following limitations can be mentioned: 296.Bl -bullet 297.It 298The original, 299.Pf non- Tn GNU 300interface permits the use of only one hash table at a time. 301.It 302Individual hash table entries can be added, but not deleted. 303.It 304The standard is indecipherable about the 305internal memory usage of the functions, 306mentioning only that 307.Do 308.Fn hcreate 309and 310.Fn hsearch 311functions may use 312.Fn malloc 313to allocate space 314.Dc . 315This limits the portability of the functions, 316given that other implementations may not 317.Xr free 3 318the buffer pointed by 319.Fa key . 320.El 321