1.\" $NetBSD: hcreate.3,v 1.13 2014/07/20 20:17:21 christos 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 July 20, 2014 31.Dt HCREATE 3 32.Os 33.Sh NAME 34.Nm hcreate , 35.Nm hcreate_r , 36.Nm hdestroy , 37.Nm hdestroy1 , 38.Nm hdestroy_r , 39.Nm hdestroy1_r , 40.Nm hsearch , 41.Nm hsearch_r 42.Nd manage hash search table 43.Sh LIBRARY 44.Lb libc 45.Sh SYNOPSIS 46.In search.h 47.Ft int 48.Fn hcreate "size_t nel" 49.Ft int 50.Fn hcreate_r "size_t nel" "struct hsearch_data *table" 51.Ft void 52.Fn hdestroy "void" 53.Ft void 54.Fn hdestroy1 "void (*freekey)(void *)" "void (*freedata)(void *)" 55.Ft void 56.Fn hdestroy_r "struct hsearch_data *table" 57.Ft void 58.Fn hdestroy1_r "struct hsearch_data *table" "void (*freekey)(void *)" "void (*freedata)(void *)" 59.Ft ENTRY * 60.Fn hsearch "ENTRY item" "ACTION action" 61.Ft int 62.Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table" 63.Sh DESCRIPTION 64The 65.Fn hcreate , 66.Fn hcreate_r , 67.Fn hdestroy , 68.Fn hdestroy_r 69.Fn hdestroy1 , 70.Fn hdestroy1_r 71.Fn hsearch , 72and 73.Fn hsearch_r 74functions manage hash search tables. 75.Pp 76The 77.Fn hcreate 78function allocates and initializes the table. 79The 80.Fa nel 81argument specifies an estimate of the maximum number of entries to be held 82by the table. 83Unless further memory allocation fails, supplying an insufficient 84.Fa nel 85value will not result in functional harm, although a performance degradation 86may occur. 87Initialization using the 88.Fn hcreate 89function is mandatory prior to any access operations using 90.Fn hsearch . 91.Pp 92The 93.Fn hdestroy 94function destroys a table previously created using 95.Fn hcreate . 96After a call to 97.Fn hdestroy , 98the data can no longer be accessed. 99.Pp 100The 101.Fn hsearch 102function is used to search to the hash table. 103It returns a pointer into the 104hash table indicating the address of an item. 105The 106.Fa item 107argument is of type 108.Vt ENTRY , 109defined in the 110.In search.h 111header. 112This is a structure type that contains two pointers: 113.Pp 114.Bl -tag -compact -offset indent -width "void *data " 115.It Fa char *key 116comparison key 117.It Fa void *data 118pointer to data associated with 119.Fa key 120.El 121.Pp 122The key comparison function used by 123.Fn hsearch 124is 125.Xr strcmp 3 . 126.Pp 127The 128.Fa action 129argument is of type 130.Vt ACTION , 131an enumeration type which defines the following values: 132.Bl -tag -offset indent -width ENTERXX 133.It Dv ENTER 134Insert 135.Fa item 136into the hash table. 137If an existing item with the same key is found, it is not replaced. 138Note that the 139.Fa key 140and 141.Fa data 142elements of 143.Fa item 144are used directly by the new table entry. 145The storage for the 146key must not be modified during the lifetime of the hash table. 147.It Dv FIND 148Search the hash table without inserting 149.Fa item . 150.El 151.Pp 152The traditional 153.Fn hdestroy 154and 155.Fn hdestroy_r 156functions don't 157.Xr free 3 158the data associated with the 159.Fa key 160and 161.Fa value 162of each entry, because they did not allocate them. 163Since there is no 164.Dq iterator 165function provided, the 166.Fn hdestroy1 167and 168.Fn hdestroy1_r 169allow controlling how the 170.Fa key 171or 172.Fa value 173will be freed using the 174provided functions in the 175.Fa freekey 176and 177.Fa freedata 178arguments. 179If they are 180.Dv NULL , 181then 182.Fa key 183and 184.Fa value 185are not freed. 186.Pp 187The 188.Fn hcreate_r , 189.Fn hdestroy_r , 190.Fn hdestroy1_r , 191and 192.Fn hsearch_r 193functions are re-entrant versions of the above functions that can 194operate on a table supplied by the user. 195The 196.Fn hsearch_r 197function returns 198.Dv 0 199if the action is 200.Dv ENTER 201and the element cannot be created, 202.Dv 1 203otherwise. 204If the element exists or can be created, it will be placed in 205.Fa itemp , 206otherwise 207.Fa itemp 208will be set to 209.Dv NULL . 210.Sh RETURN VALUES 211If successful, the 212.Fn hcreate 213and 214.Fn hcreate_r 215functions return a non-zero value. 216Otherwise, a value of 217.Dv 0 218is returned and 219.Va errno 220is set to indicate the error. 221.Pp 222The 223.Fn hdestroy 224and 225.Fn hdestroy_r 226functions return no value. 227.Pp 228If successful, the 229.Fn hsearch 230function returns a pointer to hash table entry matching 231the provided key. 232If the action is 233.Dv FIND 234and the item was not found, or if the action is 235.Dv ENTER 236and the insertion failed, 237.Dv NULL 238is returned and 239.Va errno 240is set to indicate the error. 241If the action is 242.Dv ENTER 243and an entry already existed in the table matching the given 244key, the existing entry is returned and is not replaced. 245.Pp 246The 247.Fn hsearch_r 248function returns 249.Dv 1 250unless the table is full, when it returns 251.Dv 0 . 252If 253.Fn hsearch 254returns 255.Dv 0 256or the element is not found, 257.Va errno 258is set to indicate the error. 259.Sh ERRORS 260The 261.Fn hcreate , 262.Fn hcreate_r , 263.Fn hsearch 264and 265.Fn hsearch_r 266functions will fail if: 267.Bl -tag -width Er 268.It Bq Er ENOMEM 269Insufficient memory is available. 270.El 271.Pp 272The 273.Fn hsearch 274and 275.Fn hsearch_r 276functions will also fail if the action is 277.Dv SEARCH 278and the element is not found: 279.Bl -tag -width Er 280.It Bq Er ESRCH 281The 282.Fa item 283given is not found. 284.El 285.Sh SEE ALSO 286.Xr bsearch 3 , 287.Xr free 3 , 288.Xr lsearch 3 , 289.Xr malloc 3 , 290.Xr strcmp 3 291.Sh STANDARDS 292The 293.Fn hcreate , 294.Fn hdestroy 295and 296.Fn hsearch 297functions conform to 298.St -xpg4.2 . 299.Sh HISTORY 300The 301.Fn hcreate , 302.Fn hdestroy 303and 304.Fn hsearch 305functions first appeared in 306.At V . 307The 308.Fn hcreate_r , 309.Fn hdestroy_r , 310and 311.Fn hsearch_r 312functions are 313.Tn GNU 314extensions. 315The 316.Fn hdestroy1 317and 318.Fn hdestroy1_r 319are 320.Nx 321extensions. 322.Sh CAVEATS 323At least the following limitations can be mentioned: 324.Bl -bullet 325.It 326The original, 327.Pf non- Tn GNU 328interface permits the use of only one hash table at a time. 329.It 330Individual hash table entries can be added, but not deleted. 331.It 332There is no iterator to scan for all entries in the table. 333.El 334