1.\" $NetBSD: hcreate.3,v 1.8 2010/05/01 06:18:03 jruoho 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 May 1, 2010 31.Dt HCREATE 3 32.Os 33.Sh NAME 34.Nm hcreate , 35.Nm hdestroy , 36.Nm hsearch 37.Nd manage hash search table 38.Sh LIBRARY 39.Lb libc 40.Sh SYNOPSIS 41.In search.h 42.Ft int 43.Fn hcreate "size_t nel" 44.Ft void 45.Fn hdestroy "void" 46.Ft ENTRY * 47.Fn hsearch "ENTRY item" "ACTION action" 48.Sh DESCRIPTION 49The 50.Fn hcreate , 51.Fn hdestroy 52and 53.Fn hsearch 54functions manage hash search tables. 55.Pp 56The 57.Fn hcreate 58function allocates and initializes the table. 59The 60.Fa nel 61argument specifies an estimate of the maximum number of entries to be held 62by the table. 63Unless further memory allocation fails, supplying an insufficient 64.Fa nel 65value will not result in functional harm, although a performance degradation 66may occur. 67Initialization using the 68.Fn hcreate 69function is mandatory prior to any access operations using 70.Fn hsearch . 71.Pp 72The 73.Fn hdestroy 74function destroys a table previously created using 75.Fn hcreate . 76After a call to 77.Fn hdestroy , 78the data can no longer be accessed. 79.Pp 80The 81.Fn hsearch 82function is used to search to the hash table. 83It returns a pointer into the 84hash table indicating the address of an item. 85The 86.Fa item 87argument is of type 88.Vt ENTRY , 89defined in the 90.In search.h 91header. 92This is a structure type that contains two pointers: 93.Pp 94.Bl -tag -compact -offset indent -width "void *data " 95.It Fa char *key 96comparison key 97.It Fa void *data 98pointer to data associated with 99.Fa key 100.El 101.Pp 102The key comparison function used by 103.Fn hsearch 104is 105.Xr strcmp 3 . 106.Pp 107The 108.Fa action 109argument is of type 110.Vt ACTION , 111an enumeration type which defines the following values: 112.Bl -tag -offset indent -width ENTERXX 113.It Dv ENTER 114Insert 115.Fa item 116into the hash table. 117If an existing item with the same key is found, it is not replaced. 118Note that the 119.Fa key 120and 121.Fa data 122elements of 123.Fa item 124are used directly by the new table entry. 125The storage for the 126key must not be modified during the lifetime of the hash table. 127.It Dv FIND 128Search the hash table without inserting 129.Fa item . 130.El 131.Pp 132Note that the comparison 133.Fa key 134must be allocated using 135.Xr malloc 3 136or 137.Xr calloc 3 138if action is 139.Dv ENTER 140and 141.Fn hdestroy 142will be called. 143This is because 144.Fn hdestroy 145will call 146.Xr free 3 147for each comparison 148.Fa key 149(but not 150.Fa data ) . 151Typically the comparison 152.Fa key 153is allocated by using 154.Xr strdup 3 . 155.Sh RETURN VALUES 156If successful, the 157.Fn hcreate 158function returns a non-zero value. 159Otherwise, a value of 0 is returned and 160.Va errno 161is set to indicate the error. 162.Pp 163The 164.Fn hdestroy 165functions 166returns no value. 167.Pp 168If successful, the 169.Fn hsearch 170function returns a pointer to hash table entry matching 171the provided key. 172If the action is 173.Dv FIND 174and the item was not found, or if the action is 175.Dv ENTER 176and the insertion failed, 177.Dv NULL 178is returned and 179.Va errno 180is set to indicate the error. 181If the action is 182.Dv ENTER 183and an entry already existed in the table matching the given 184key, the existing entry is returned and is not replaced. 185.Sh ERRORS 186The 187.Fn hcreate 188and 189.Fn hsearch 190functions will fail if: 191.Bl -tag -width Er 192.It Bq Er ENOMEM 193Insufficient memory is available. 194.El 195.Sh SEE ALSO 196.Xr bsearch 3 , 197.Xr lsearch 3 , 198.Xr malloc 3 , 199.Xr strcmp 3 200.Sh STANDARDS 201The 202.Fn hcreate , 203.Fn hdestroy 204and 205.Fn hsearch 206functions conform to 207.St -xpg4.2 . 208.Sh HISTORY 209The 210.Fn hcreate , 211.Fn hdestroy 212and 213.Fn hsearch 214functions first appeared in 215.At V . 216.Sh CAVEATS 217At least the following limitations can be mentioned: 218.Bl -bullet 219.It 220The interface permits the use of only one hash table at a time. 221.It 222Individual hash table entries can be added, but not deleted. 223.It 224The standard is indecipherable about the 225internal memory usage of the functions, 226mentioning only that 227.Do 228.Fn hcreate 229and 230.Fn hsearch 231functions may use 232.Fn malloc 233to allocate space 234.Dc . 235This limits the portability of the functions, 236given that other implementations may not 237.Xr free 3 238the buffer pointed by 239.Fa key . 240.El 241