| .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de) |
| .\" and Copyright 2008, Linux Foundation, written by Michael Kerrisk |
| .\" <mtk.manpages@gmail.com> |
| .\" |
| .\" %%%LICENSE_START(GPLv2+_DOC_FULL) |
| .\" This is free documentation; you can redistribute it and/or |
| .\" modify it under the terms of the GNU General Public License as |
| .\" published by the Free Software Foundation; either version 2 of |
| .\" the License, or (at your option) any later version. |
| .\" |
| .\" The GNU General Public License's references to "object code" |
| .\" and "executables" are to be interpreted as the output of any |
| .\" document formatting or typesetting system, including |
| .\" intermediate and printed output. |
| .\" |
| .\" This manual is distributed in the hope that it will be useful, |
| .\" but WITHOUT ANY WARRANTY; without even the implied warranty of |
| .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| .\" GNU General Public License for more details. |
| .\" |
| .\" You should have received a copy of the GNU General Public |
| .\" License along with this manual; if not, see |
| .\" <http://www.gnu.org/licenses/>. |
| .\" %%%LICENSE_END |
| .\" |
| .\" 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 2020-06-09 "GNU" "Linux Programmer's Manual" |
| .SH NAME |
| hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, |
| hsearch_r \- hash table management |
| .SH SYNOPSIS |
| .nf |
| .B #include <search.h> |
| .PP |
| .BI "int hcreate(size_t " nel ); |
| .PP |
| .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action ); |
| .PP |
| .B "void hdestroy(void);" |
| .PP |
| .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */" |
| .B #include <search.h> |
| .PP |
| .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" htab ); |
| .PP |
| .BI "int hsearch_r(ENTRY " item ", ACTION " action ", ENTRY **" retval , |
| .BI " struct hsearch_data *" htab ); |
| .PP |
| .BI "void hdestroy_r(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. |
| .PP |
| 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). |
| .PP |
| 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 |
| .PP |
| 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 (). |
| .PP |
| 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 (). |
| .PP |
| 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. |
| .PP |
| The argument \fIitem\fP is of type \fIENTRY\fP, which is defined in |
| \fI<search.h>\fP as follows: |
| .PP |
| .in +4n |
| .EX |
| typedef struct entry { |
| char *key; |
| void *data; |
| } ENTRY; |
| .EE |
| .in |
| .PP |
| 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. |
| .PP |
| 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 |
| .IR 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.) |
| .PP |
| 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 cause of the error. |
| .PP |
| 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 cause of the error. |
| .SH ERRORS |
| .BR hcreate_r () |
| and |
| .BR hdestroy_r () |
| can fail for the following reasons: |
| .TP |
| .B EINVAL |
| .I htab |
| is NULL. |
| .PP |
| .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. |
| .PP |
| 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; |
| lbw25 lb lb |
| l l l. |
| Interface Attribute Value |
| T{ |
| .BR hcreate (), |
| .BR hsearch (), |
| .br |
| .BR hdestroy () |
| T} Thread safety MT-Unsafe race:hsearch |
| T{ |
| .BR hcreate_r (), |
| .BR hsearch_r (), |
| .br |
| .BR hdestroy_r () |
| T} Thread safety MT-Safe race:htab |
| .TE |
| .SH CONFORMING TO |
| The functions |
| .BR hcreate (), |
| .BR hsearch (), |
| and |
| .BR hdestroy () |
| are from SVr4, and are described in POSIX.1-2001 and POSIX.1-2008. |
| .PP |
| The functions |
| .BR hcreate_r (), |
| .BR hsearch_r (), |
| and |
| .BR hdestroy_r () |
| are GNU extensions. |
| .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. |
| .PP |
| 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 version 2.3), the |
| implementation violates the specification, |
| updating the \fIdata\fP for the given \fIkey\fP in this case. |
| .PP |
| 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. |
| .PP |
| .EX |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <search.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, *ep; |
| int i; |
| |
| hcreate(30); |
| |
| for (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 (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 |
| .SH SEE ALSO |
| .BR bsearch (3), |
| .BR lsearch (3), |
| .BR malloc (3), |
| .BR tsearch (3) |