1.\" $OpenBSD: hcreate.3,v 1.8 2018/01/30 11:37:58 jmc 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: January 30 2018 $ 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 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 162If successful, the 163.Fn hsearch 164function returns a pointer to a hash table entry matching 165the provided key. 166If the action is 167.Dv FIND 168and the item was not found, or if the action is 169.Dv ENTER 170and the insertion failed, 171.Dv NULL 172is returned and 173.Va errno 174is set to indicate the error. 175If the action is 176.Dv ENTER 177and an entry already existed in the table matching the given 178key, the existing entry is returned and is not replaced. 179.Sh ERRORS 180The 181.Fn hcreate 182and 183.Fn hsearch 184functions will fail if: 185.Bl -tag -width Er 186.It Bq Er ENOMEM 187Insufficient memory is available. 188.El 189.Sh SEE ALSO 190.Xr bsearch 3 , 191.Xr lsearch 3 , 192.Xr malloc 3 , 193.Xr strcmp 3 194.Sh STANDARDS 195The 196.Fn hcreate , 197.Fn hdestroy 198and 199.Fn hsearch 200functions conform to 201.St -xpg4.2 . 202.Sh HISTORY 203The 204.Fn hcreate , 205.Fn hdestroy 206and 207.Fn hsearch 208functions first appeared in 209.At V . 210.Sh CAVEATS 211At least the following limitations can be mentioned: 212.Bl -bullet 213.It 214The interface permits the use of only one hash table at a time. 215.It 216Individual hash table entries can be added, but not deleted. 217.It 218The standard is indecipherable about the 219internal memory usage of the functions, 220mentioning only that 221.Do 222.Fn hcreate 223and 224.Fn hsearch 225functions may use 226.Fn malloc 227to allocate space 228.Dc . 229This limits the portability of the functions, 230given that other implementations may not 231.Xr free 3 232the buffer pointed by 233.Fa key . 234.El 235