1.\" $OpenBSD: hcreate.3,v 1.6 2010/07/28 09:00:20 ray Exp $ 2.\" $NetBSD: hcreate.3,v 1.8 2010/05/01 06:18:03 jruoho Exp $ 3.\" 4.\" Copyright (c) 1999 The NetBSD Foundation, Inc. 5.\" All rights reserved. 6.\" 7.\" This code is derived from software contributed to The NetBSD Foundation 8.\" by Klaus Klein. 9.\" 10.\" Redistribution and use in source and binary forms, with or without 11.\" modification, are permitted provided that the following conditions 12.\" are met: 13.\" 1. Redistributions of source code must retain the above copyright 14.\" notice, this list of conditions and the following disclaimer. 15.\" 2. Redistributions in binary form must reproduce the above copyright 16.\" notice, this list of conditions and the following disclaimer in the 17.\" documentation and/or other materials provided with the distribution. 18.\" 19.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29.\" POSSIBILITY OF SUCH DAMAGE. 30.\" 31.Dd $Mdocdate: July 28 2010 $ 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 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 and initializes the table. 58The 59.Fa nel 60argument specifies an estimate of the maximum number of entries to be held 61by the table. 62Unless further memory allocation fails, supplying an insufficient 63.Fa nel 64value will not result in functional harm, although a performance degradation 65may occur. 66Initialization using the 67.Fn hcreate 68function is mandatory prior to any access operations using 69.Fn hsearch . 70.Pp 71The 72.Fn hdestroy 73function destroys a table previously created using 74.Fn hcreate . 75After a call to 76.Fn hdestroy , 77the data can no longer be accessed. 78.Pp 79The 80.Fn hsearch 81function is used to search to the hash table. 82It returns a pointer into the 83hash table indicating the address of an item. 84The 85.Fa item 86argument is of type 87.Vt ENTRY , 88defined in the 89.In search.h 90header. 91This is a structure type that contains two pointers: 92.Pp 93.Bl -tag -compact -offset indent -width "void *data " 94.It Fa char *key 95comparison key 96.It Fa void *data 97pointer to data associated with 98.Fa key 99.El 100.Pp 101The key comparison function used by 102.Fn hsearch 103is 104.Xr strcmp 3 . 105.Pp 106The 107.Fa action 108argument is of type 109.Vt ACTION , 110an enumeration type which defines the following values: 111.Bl -tag -offset indent -width ENTERXX 112.It Dv ENTER 113Insert 114.Fa item 115into the hash table. 116If an existing item with the same key is found, it is not replaced. 117Note that the 118.Fa key 119and 120.Fa data 121elements of 122.Fa item 123are used directly by the new table entry. 124The storage for the 125key must not be modified during the lifetime of the hash table. 126.It Dv FIND 127Search the hash table without inserting 128.Fa item . 129.El 130.Pp 131Note that the comparison 132.Fa key 133must be allocated using 134.Xr malloc 3 135or 136.Xr calloc 3 137if action is 138.Dv ENTER 139and 140.Fn hdestroy 141will be called. 142This is because 143.Fn hdestroy 144will call 145.Xr free 3 146for each comparison 147.Fa key 148(but not 149.Fa data ) . 150Typically the comparison 151.Fa key 152is allocated by using 153.Xr strdup 3 . 154.Sh RETURN VALUES 155If successful, the 156.Fn hcreate 157function returns a non-zero value. 158Otherwise, a value of 0 is returned and 159.Va errno 160is set to indicate the error. 161.Pp 162The 163.Fn hdestroy 164functions 165returns no value. 166.Pp 167If successful, the 168.Fn hsearch 169function returns a pointer to a hash table entry matching 170the provided key. 171If the action is 172.Dv FIND 173and the item was not found, or if the action is 174.Dv ENTER 175and the insertion failed, 176.Dv NULL 177is returned and 178.Va errno 179is set to indicate the error. 180If the action is 181.Dv ENTER 182and an entry already existed in the table matching the given 183key, the existing entry is returned and is not replaced. 184.Sh ERRORS 185The 186.Fn hcreate 187and 188.Fn hsearch 189functions will fail if: 190.Bl -tag -width Er 191.It Bq Er ENOMEM 192Insufficient memory is available. 193.El 194.Sh SEE ALSO 195.Xr bsearch 3 , 196.Xr lsearch 3 , 197.Xr malloc 3 , 198.Xr strcmp 3 199.Sh STANDARDS 200The 201.Fn hcreate , 202.Fn hdestroy 203and 204.Fn hsearch 205functions conform to 206.St -xpg4.2 . 207.Sh HISTORY 208The 209.Fn hcreate , 210.Fn hdestroy 211and 212.Fn hsearch 213functions first appeared in 214.At V . 215.Sh CAVEATS 216At least the following limitations can be mentioned: 217.Bl -bullet 218.It 219The interface permits the use of only one hash table at a time. 220.It 221Individual hash table entries can be added, but not deleted. 222.It 223The standard is indecipherable about the 224internal memory usage of the functions, 225mentioning only that 226.Do 227.Fn hcreate 228and 229.Fn hsearch 230functions may use 231.Fn malloc 232to allocate space 233.Dc . 234This limits the portability of the functions, 235given that other implementations may not 236.Xr free 3 237the buffer pointed by 238.Fa key . 239.El 240