1HSEARCH(3)                 Linux Programmer's Manual                HSEARCH(3)
2
3
4

NAME

6       hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - hash ta‐
7       ble management
8

SYNOPSIS

10       #include <search.h>
11
12       int hcreate(size_t nel);
13
14       ENTRY *hsearch(ENTRY item, ACTION action);
15
16       void hdestroy(void);
17
18       #define _GNU_SOURCE         /* See feature_test_macros(7) */
19       #include <search.h>
20
21       int hcreate_r(size_t nel, struct hsearch_data *htab);
22
23       int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
24                     struct hsearch_data *htab);
25
26       void hdestroy_r(struct hsearch_data *htab);
27

DESCRIPTION

29       The three functions hcreate(),  hsearch(),  and  hdestroy()  allow  the
30       caller to create and manage a hash search table containing entries con‐
31       sisting of a key (a string) and associated  data.   Using  these  func‐
32       tions, only one hash table can be used at a time.
33
34       The  three  functions  hcreate_r(), hsearch_r(), hdestroy_r() are reen‐
35       trant versions that allow a program to use more than  one  hash  search
36       table at the same time.  The last argument, htab, points to a structure
37       that describes the table on which the function is to operate.  The pro‐
38       grammer  should treat this structure as opaque (i.e., do not attempt to
39       directly access or modify the fields in this structure).
40
41       First a hash table must be created using hcreate().  The  argument  nel
42       specifies  the  maximum  number of entries in the table.  (This maximum
43       cannot be changed later, so choose it wisely.)  The implementation  may
44       adjust  this  value  upward to improve the performance of the resulting
45       hash table.
46
47       The hcreate_r() function performs the same task as hcreate(),  but  for
48       the  table  described by the structure *htab.  The structure pointed to
49       by htab must be zeroed before the first call to hcreate_r().
50
51       The function hdestroy() frees the memory occupied  by  the  hash  table
52       that  was  created  by hcreate().  After calling hdestroy(), a new hash
53       table can be created using hcreate().  The hdestroy_r()  function  per‐
54       forms the analogous task for a hash table described by *htab, which was
55       previously created using hcreate_r().
56
57       The hsearch() function searches the hash table for  an  item  with  the
58       same  key as item (where "the same" is determined using strcmp(3)), and
59       if successful returns a pointer to it.
60
61       The argument item is of type ENTRY, which is defined in  <search.h>  as
62       follows:
63
64           typedef struct entry {
65               char *key;
66               void *data;
67           } ENTRY;
68
69       The  field  key  points to a null-terminated string which is the search
70       key.  The field data points to data that is associated with that key.
71
72       The argument action determines what hsearch() does after an  unsuccess‐
73       ful  search.   This  argument must either have the value ENTER, meaning
74       insert a copy of item (and return a pointer to the new hash table entry
75       as the function result), or the value FIND, meaning that NULL should be
76       returned.  (If action is FIND, then data is ignored.)
77
78       The hsearch_r() function is like hsearch() but operates on the hash ta‐
79       ble   described  by  *htab.   The  hsearch_r()  function  differs  from
80       hsearch() in that a pointer to the found item is returned  in  *retval,
81       rather than as the function result.
82

RETURN VALUE

84       hcreate()  and hcreate_r() return nonzero on success.  They return 0 on
85       error, with errno set to indicate the cause of the error.
86
87       On success, hsearch() returns a pointer to an entry in the hash  table.
88       hsearch()  returns  NULL  on error, that is, if action is ENTER and the
89       hash table is full, or action is FIND and item cannot be found  in  the
90       hash  table.   hsearch_r()  returns nonzero on success, and 0 on error.
91       In the event of an error, these two functions set errno to indicate the
92       cause of the error.
93

ERRORS

95       hcreate_r() and hdestroy_r() can fail for the following reasons:
96
97       EINVAL htab is NULL.
98
99       hsearch() and hsearch_r() can fail for the following reasons:
100
101       ENOMEM action  was ENTER, key was not found in the table, and there was
102              no room in the table to add a new entry.
103
104       ESRCH  action was FIND, and key was not found in the table.
105
106       POSIX.1 specifies only the ENOMEM error.
107

ATTRIBUTES

109       For  an  explanation  of  the  terms  used   in   this   section,   see
110       attributes(7).
111
112       ┌──────────────────────────┬───────────────┬────────────────────────┐
113Interface                 Attribute     Value                  
114       ├──────────────────────────┼───────────────┼────────────────────────┤
115hcreate(), hsearch(),     │ Thread safety │ MT-Unsafe race:hsearch │
116hdestroy()                │               │                        │
117       ├──────────────────────────┼───────────────┼────────────────────────┤
118hcreate_r(), hsearch_r(), │ Thread safety │ MT-Safe race:htab      │
119hdestroy_r()              │               │                        │
120       └──────────────────────────┴───────────────┴────────────────────────┘

CONFORMING TO

122       The  functions  hcreate(), hsearch(), and hdestroy() are from SVr4, and
123       are described in POSIX.1-2001 and POSIX.1-2008.
124
125       The functions hcreate_r(), hsearch_r(), and hdestroy_r() are GNU exten‐
126       sions.
127

NOTES

129       Hash  table  implementations  are usually more efficient when the table
130       contains enough free space to  minimize  collisions.   Typically,  this
131       means that nel should be at least 25% larger than the maximum number of
132       elements that the caller expects to store in the table.
133
134       The hdestroy() and hdestroy_r()  functions  do  not  free  the  buffers
135       pointed to by the key and data elements of the hash table entries.  (It
136       can't do this because it doesn't know whether these buffers were  allo‐
137       cated dynamically.)  If these buffers need to be freed (perhaps because
138       the program is repeatedly creating and destroying hash  tables,  rather
139       than  creating  a  single table whose lifetime matches that of the pro‐
140       gram), then the program must maintain bookkeeping data structures  that
141       allow it to free them.
142

BUGS

144       SVr4  and  POSIX.1-2001  specify  that  action  is significant only for
145       unsuccessful searches, so that an ENTER should not do  anything  for  a
146       successful  search.  In libc and glibc (before version 2.3), the imple‐
147       mentation violates the specification, updating the data for  the  given
148       key in this case.
149
150       Individual hash table entries can be added, but not deleted.
151

EXAMPLE

153       The  following  program inserts 24 items into a hash table, then prints
154       some of them.
155
156       #include <stdio.h>
157       #include <stdlib.h>
158       #include <search.h>
159
160       static char *data[] = { "alpha", "bravo", "charlie", "delta",
161            "echo", "foxtrot", "golf", "hotel", "india", "juliet",
162            "kilo", "lima", "mike", "november", "oscar", "papa",
163            "quebec", "romeo", "sierra", "tango", "uniform",
164            "victor", "whisky", "x-ray", "yankee", "zulu"
165       };
166
167       int
168       main(void)
169       {
170           ENTRY e, *ep;
171           int i;
172
173           hcreate(30);
174
175           for (i = 0; i < 24; i++) {
176               e.key = data[i];
177               /* data is just an integer, instead of a
178                  pointer to something */
179               e.data = (void *) i;
180               ep = hsearch(e, ENTER);
181               /* there should be no failures */
182               if (ep == NULL) {
183                   fprintf(stderr, "entry failed\n");
184                   exit(EXIT_FAILURE);
185               }
186           }
187
188           for (i = 22; i < 26; i++) {
189               /* print two entries from the table, and
190                  show that two are not in the table */
191               e.key = data[i];
192               ep = hsearch(e, FIND);
193               printf("%9.9s -> %9.9s:%d\n", e.key,
194                      ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);
195           }
196           hdestroy();
197           exit(EXIT_SUCCESS);
198       }
199

SEE ALSO

201       bsearch(3), lsearch(3), malloc(3), tsearch(3)
202

COLOPHON

204       This page is part of release 4.15 of the Linux  man-pages  project.   A
205       description  of  the project, information about reporting bugs, and the
206       latest    version    of    this    page,    can     be     found     at
207       https://www.kernel.org/doc/man-pages/.
208
209
210
211GNU                               2017-09-15                        HSEARCH(3)
Impressum