diff options
Diffstat (limited to 'man/man3/hsearch.3')
| -rw-r--r-- | man/man3/hsearch.3 | 355 |
1 files changed, 355 insertions, 0 deletions
diff --git a/man/man3/hsearch.3 b/man/man3/hsearch.3 new file mode 100644 index 0000000..7dc38ee --- /dev/null +++ b/man/man3/hsearch.3 @@ -0,0 +1,355 @@ +'\" t +.\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de) +.\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk +.\" <mtk.manpages@gmail.com> +.\" +.\" SPDX-License-Identifier: GPL-2.0-or-later +.\" +.\" References consulted: +.\" SunOS 4.1.1 man pages +.\" Modified Sat Sep 30 21:52:01 1995 by Jim Van Zandt <jrv@vanzandt.mv.com> +.\" Remarks from dhw@gamgee.acad.emich.edu Fri Jun 19 06:46:31 1998 +.\" Modified 2001-12-26, 2003-11-28, 2004-05-20, aeb +.\" 2008-09-02, mtk: various additions and rewrites +.\" 2008-09-03, mtk, restructured somewhat, in part after suggestions from +.\" Timothy S. Nelson <wayland@wayland.id.au> +.\" +.TH hsearch 3 2024-05-02 "Linux man-pages (unreleased)" +.SH NAME +hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, +hsearch_r \- hash table management +.SH LIBRARY +Standard C library +.RI ( libc ", " \-lc ) +.SH SYNOPSIS +.nf +.B #include <search.h> +.P +.BI "int hcreate(size_t " nel ); +.B "void hdestroy(void);" +.P +.BI "ENTRY *hsearch(ENTRY " item ", ACTION " action ); +.P +.BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */" +.B #include <search.h> +.P +.BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab ); +.BI "void hdestroy_r(struct hsearch_data *" htab ); +.P +.BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval , +.BI " struct hsearch_data *" htab ); +.fi +.SH DESCRIPTION +The three functions +.BR hcreate (), +.BR hsearch (), +and +.BR hdestroy () +allow the caller to create and manage a hash search table +containing entries consisting of a key (a string) and associated data. +Using these functions, only one hash table can be used at a time. +.P +The three functions +.BR hcreate_r (), +.BR hsearch_r (), +.BR hdestroy_r () +are reentrant versions that allow a program to use +more than one hash search table at the same time. +The last argument, +.IR htab , +points to a structure that describes the table +on which the function is to operate. +The programmer should treat this structure as opaque +(i.e., do not attempt to directly access or modify +the fields in this structure). +.P +First a hash table must be created using +.BR hcreate (). +The argument \fInel\fP specifies the maximum number of entries +in the table. +(This maximum cannot be changed later, so choose it wisely.) +The implementation may adjust this value upward to improve the +performance of the resulting hash table. +.\" e.g., in glibc it is raised to the next higher prime number +.P +The +.BR hcreate_r () +function performs the same task as +.BR hcreate (), +but for the table described by the structure +.IR *htab . +The structure pointed to by +.I htab +must be zeroed before the first call to +.BR hcreate_r (). +.P +The function +.BR hdestroy () +frees the memory occupied by the hash table that was created by +.BR hcreate (). +After calling +.BR hdestroy (), +a new hash table can be created using +.BR hcreate (). +The +.BR hdestroy_r () +function performs the analogous task for a hash table described by +.IR *htab , +which was previously created using +.BR hcreate_r (). +.P +The +.BR hsearch () +function searches the hash table for an +item with the same key as \fIitem\fP (where "the same" is determined using +.BR strcmp (3)), +and if successful returns a pointer to it. +.P +The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in +\fI<search.h>\fP as follows: +.P +.in +4n +.EX +typedef struct entry { + char *key; + void *data; +} ENTRY; +.EE +.in +.P +The field \fIkey\fP points to a null-terminated string which is the +search key. +The field \fIdata\fP points to data that is associated with that key. +.P +The argument \fIaction\fP determines what +.BR hsearch () +does after an unsuccessful search. +This argument must either have the value +.BR ENTER , +meaning insert a copy of +.I item +(and return a pointer to the new hash table entry as the function result), +or the value +.BR FIND , +meaning that NULL should be returned. +(If +.I action +is +.BR FIND , +then +.I data +is ignored.) +.P +The +.BR hsearch_r () +function is like +.BR hsearch () +but operates on the hash table described by +.IR *htab . +The +.BR hsearch_r () +function differs from +.BR hsearch () +in that a pointer to the found item is returned in +.IR *retval , +rather than as the function result. +.SH RETURN VALUE +.BR hcreate () +and +.BR hcreate_r () +return nonzero on success. +They return 0 on error, with +.I errno +set to indicate the error. +.P +On success, +.BR hsearch () +returns a pointer to an entry in the hash table. +.BR hsearch () +returns NULL on error, that is, +if \fIaction\fP is \fBENTER\fP and +the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP +cannot be found in the hash table. +.BR hsearch_r () +returns nonzero on success, and 0 on error. +In the event of an error, these two functions set +.I errno +to indicate the error. +.SH ERRORS +.BR hcreate_r () +and +.BR hdestroy_r () +can fail for the following reasons: +.TP +.B EINVAL +.I htab +is NULL. +.P +.BR hsearch () +and +.BR hsearch_r () +can fail for the following reasons: +.TP +.B ENOMEM +.I action +was +.BR ENTER , +.I key +was not found in the table, +and there was no room in the table to add a new entry. +.TP +.B ESRCH +.I action +was +.BR FIND , +and +.I key +was not found in the table. +.P +POSIX.1 specifies only the +.\" PROX.1-2001, POSIX.1-2008 +.B ENOMEM +error. +.SH ATTRIBUTES +For an explanation of the terms used in this section, see +.BR attributes (7). +.TS +allbox; +lbx lb lb +l l l. +Interface Attribute Value +T{ +.na +.nh +.BR hcreate (), +.BR hsearch (), +.BR hdestroy () +T} Thread safety MT-Unsafe race:hsearch +T{ +.na +.nh +.BR hcreate_r (), +.BR hsearch_r (), +.BR hdestroy_r () +T} Thread safety MT-Safe race:htab +.TE +.SH STANDARDS +.TP +.BR hcreate () +.TQ +.BR hsearch () +.TQ +.BR hdestroy () +POSIX.1-2008. +.TP +.BR hcreate_r () +.TQ +.BR hsearch_r () +.TQ +.BR hdestroy_r () +GNU. +.SH HISTORY +.TP +.BR hcreate () +.TQ +.BR hsearch () +.TQ +.BR hdestroy () +SVr4, POSIX.1-2001. +.TP +.BR hcreate_r () +.TQ +.BR hsearch_r () +.TQ +.BR hdestroy_r () +GNU. +.SH NOTES +Hash table implementations are usually more efficient when the +table contains enough free space to minimize collisions. +Typically, this means that +.I nel +should be at least 25% larger than the maximum number of elements +that the caller expects to store in the table. +.P +The +.BR hdestroy () +and +.BR hdestroy_r () +functions do not free the buffers pointed to by the +.I key +and +.I data +elements of the hash table entries. +(It can't do this because it doesn't know +whether these buffers were allocated dynamically.) +If these buffers need to be freed (perhaps because the program +is repeatedly creating and destroying hash tables, +rather than creating a single table whose lifetime +matches that of the program), +then the program must maintain bookkeeping data structures that +allow it to free them. +.SH BUGS +SVr4 and POSIX.1-2001 specify that \fIaction\fP +is significant only for unsuccessful searches, so that an \fBENTER\fP +should not do anything for a successful search. +In libc and glibc (before glibc 2.3), the +implementation violates the specification, +updating the \fIdata\fP for the given \fIkey\fP in this case. +.P +Individual hash table entries can be added, but not deleted. +.SH EXAMPLES +The following program inserts 24 items into a hash table, then prints +some of them. +.P +.\" SRC BEGIN (hsearch.c) +.EX +#include <search.h> +#include <stdio.h> +#include <stdlib.h> +\& +static char *data[] = { "alpha", "bravo", "charlie", "delta", + "echo", "foxtrot", "golf", "hotel", "india", "juliet", + "kilo", "lima", "mike", "november", "oscar", "papa", + "quebec", "romeo", "sierra", "tango", "uniform", + "victor", "whisky", "x\-ray", "yankee", "zulu" +}; +\& +int +main(void) +{ + ENTRY e; + ENTRY *ep; +\& + hcreate(30); +\& + for (size_t i = 0; i < 24; i++) { + e.key = data[i]; + /* data is just an integer, instead of a + pointer to something */ + e.data = (void *) i; + ep = hsearch(e, ENTER); + /* there should be no failures */ + if (ep == NULL) { + fprintf(stderr, "entry failed\en"); + exit(EXIT_FAILURE); + } + } +\& + for (size_t i = 22; i < 26; i++) { + /* print two entries from the table, and + show that two are not in the table */ + e.key = data[i]; + ep = hsearch(e, FIND); + printf("%9.9s \-> %9.9s:%d\en", e.key, + ep ? ep\->key : "NULL", ep ? (int)(ep\->data) : 0); + } + hdestroy(); + exit(EXIT_SUCCESS); +} +.EE +.\" SRC END +.SH SEE ALSO +.BR bsearch (3), +.BR lsearch (3), +.BR malloc (3), +.BR tsearch (3) |