Copyright (c) 1999 The NetBSD Foundation, Inc.
All rights reserved.
This code is derived from software contributed to The NetBSD Foundation
by Klaus Klein.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.
.Dd September 14, 2011 .Dt HCREATE 3 .Os .Sh NAME .Nm hcreate , .Nm hcreate_r , .Nm hdestroy , .Nm hdestroy_r , .Nm hsearch , .Nm hsearch_r .Nd manage hash search table .Sh LIBRARY .Lb libc .Sh SYNOPSIS n search.h .Ft int .Fn hcreate "size_t nel" .Ft int .Fn hcreate_r "size_t nel" "struct hsearch_data *table" .Ft void .Fn hdestroy "void" .Ft void .Fn hdestroy_r "struct hsearch_data *table" .Ft ENTRY * .Fn hsearch "ENTRY item" "ACTION action" .Ft int .Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table" .Sh DESCRIPTION The .Fn hcreate , .Fn hcreate_r , .Fn hdestroy , .Fn hdestroy_r .Fn hsearch , and .Fn hsearch_r functions manage hash search tables.
p The .Fn hcreate function allocates and initializes the table. The .Fa nel argument specifies an estimate of the maximum number of entries to be held by the table. Unless further memory allocation fails, supplying an insufficient .Fa nel value will not result in functional harm, although a performance degradation may occur. Initialization using the .Fn hcreate function is mandatory prior to any access operations using .Fn hsearch .
p The .Fn hdestroy function destroys a table previously created using .Fn hcreate . After a call to .Fn hdestroy , the data can no longer be accessed.
p The .Fn hsearch function is used to search to the hash table. It returns a pointer into the hash table indicating the address of an item. The .Fa item argument is of type .Vt ENTRY , defined in the n search.h header. This is a structure type that contains two pointers:
p l -tag -compact -offset indent -width "void *data " t Fa char *key comparison key t Fa void *data pointer to data associated with .Fa key .El
p The key comparison function used by .Fn hsearch is .Xr strcmp 3 .
p The .Fa action argument is of type .Vt ACTION , an enumeration type which defines the following values: l -tag -offset indent -width ENTERXX t Dv ENTER Insert .Fa item into the hash table. If an existing item with the same key is found, it is not replaced. Note that the .Fa key and .Fa data elements of .Fa item are used directly by the new table entry. The storage for the key must not be modified during the lifetime of the hash table. t Dv FIND Search the hash table without inserting .Fa item . .El
p Note that the comparison .Fa key must be allocated using .Xr malloc 3 or .Xr calloc 3 if action is .Dv ENTER and .Fn hdestroy will be called. This is because .Fn hdestroy will call .Xr free 3 for each comparison .Fa key (but not .Fa data ) . Typically the comparison .Fa key is allocated by using .Xr strdup 3 .
p The .Fn hcreate_r , .Fn hdestroy_r , and .Fn hsearch_r functions are re-entrant versions of the above functions that can operate on a table supplied by the user. The .Fn hsearch_r function returns .Dv 0 if the action is .Dv ENTER and the element cannot be created, .Dv 1 otherwise. If the element exists or can be created, it will be placed in .Fa itemp , otherwise .Fa itemp will be set to .Dv NULL . .Sh RETURN VALUES If successful, the .Fn hcreate and .Fn hcreate_r functions return a non-zero value. Otherwise, a value of .Dv 0 is returned and .Va errno is set to indicate the error.
p The .Fn hdestroy and .Fn hdestroy_r functions return no value.
p If successful, the .Fn hsearch function returns a pointer to hash table entry matching the provided key. If the action is .Dv FIND and the item was not found, or if the action is .Dv ENTER and the insertion failed, .Dv NULL is returned and .Va errno is set to indicate the error. If the action is .Dv ENTER and an entry already existed in the table matching the given key, the existing entry is returned and is not replaced.
p The .Fn hsearch_r function returns .Dv 1 unless the table is full, when it returns .Dv 0 . If .Fn hsearch returns .Dv 0 or the element is not found, .Va errno is set to indicate the error. .Sh ERRORS The .Fn hcreate , .Fn hcreate_r , .Fn hsearch and .Fn hsearch_r functions will fail if: l -tag -width Er t Bq Er ENOMEM Insufficient memory is available. .El
p The .Fn hsearch and .Fn hsearch_r functions will also fail if the action is .Dv SEARCH and the element is not found: l -tag -width Er t Bq Er ESRCH The .Fa item given is not found. .El .Sh SEE ALSO .Xr bsearch 3 , .Xr lsearch 3 , .Xr malloc 3 , .Xr strcmp 3 .Sh STANDARDS The .Fn hcreate , .Fn hdestroy and .Fn hsearch functions conform to .St -xpg4.2 . .Sh HISTORY The .Fn hcreate , .Fn hdestroy and .Fn hsearch functions first appeared in .At V . The .Fn hcreate_r , .Fn hdestroy_r and .Fn hsearch_r functions are .Tn GNU extensions. .Sh CAVEATS At least the following limitations can be mentioned: l -bullet t The original,
f non- Tn GNU interface permits the use of only one hash table at a time. t Individual hash table entries can be added, but not deleted. t The standard is indecipherable about the internal memory usage of the functions, mentioning only that .Do .Fn hcreate and .Fn hsearch functions may use .Fn malloc to allocate space .Dc . This limits the portability of the functions, given that other implementations may not .Xr free 3 the buffer pointed by .Fa key . .El