2 .\" Copyright (c) 1999 The NetBSD Foundation, Inc.
3 .\" All rights reserved.
5 .\" This code is derived from software contributed to The NetBSD Foundation
8 .\" Redistribution and use in source and binary forms, with or without
9 .\" modification, are permitted provided that the following conditions
11 .\" 1. Redistributions of source code must retain the above copyright
12 .\" notice, this list of conditions and the following disclaimer.
13 .\" 2. Redistributions in binary form must reproduce the above copyright
14 .\" notice, this list of conditions and the following disclaimer in the
15 .\" documentation and/or other materials provided with the distribution.
17 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
18 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 .\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
21 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 .\" POSSIBILITY OF SUCH DAMAGE.
39 .Nd manage hash search table
45 .Fn hcreate "size_t nel"
47 .Fn hcreate_r "size_t nel" "struct hsearch_data *table"
51 .Fn hdestroy_r "struct hsearch_data *table"
53 .Fn hsearch "ENTRY item" "ACTION action"
55 .Fn hsearch_r "ENTRY item" "ACTION action" "ENTRY ** itemp" "struct hsearch_data *table"
65 functions manage hash search tables.
69 function allocates sufficient space for the table, and the application should
70 ensure it is called before
75 argument is an estimate of the maximum
76 number of entries that the table should contain.
77 As this implementation resizes the hash table dynamically,
78 this argument is ignored.
82 function disposes of the search table, and may be followed by another call to
86 the data can no longer be considered accessible.
91 for each comparison key in the search table
92 but not the data item associated with the key.
96 function is a hash-table search routine.
97 It returns a pointer into a hash table
98 indicating the location at which an entry can be found.
101 argument is a structure of type
105 header) that contains two pointers:
107 points to the comparison key (a
113 points to any other data to be associated with
115 The comparison function used by
122 member of an enumeration type
124 indicating the disposition of the entry if it cannot be
129 should be inserted in the table at an
132 indicates that no entry should be made.
133 Unsuccessful resolution is
134 indicated by the return of a
138 The comparison key (passed to
142 must be allocated using
157 functions are re-entrant versions of the above functions that can
158 operate on a table supplied by the user.
165 and the element cannot be created,
168 If the element exists or can be created, it will be placed in
179 functions return 0 if the table creation failed and the global variable
181 is set to indicate the error;
182 otherwise, a non-zero value is returned.
188 functions return no value.
196 pointer if either the
202 could not be found or the
206 and the table is full.
208 The following example reads in strings followed by two numbers
209 and stores them in a hash table, discarding duplicates.
210 It then reads in strings and finds the matching entry in the hash
211 table and prints it out.
218 struct info { /* This is the info stored in the table */
219 int age, room; /* other than the key. */
222 #define NUM_EMPL 5000 /* # of elements in search table. */
227 char str[BUFSIZ]; /* Space to read string */
228 struct info info_space[NUM_EMPL]; /* Space to store employee info. */
229 struct info *info_ptr = info_space; /* Next space in info_space. */
231 ENTRY *found_item; /* Name to look for in table. */
232 char name_to_find[30];
235 /* Create table; no error checking is performed. */
236 (void) hcreate(NUM_EMPL);
238 while (scanf("%s%d%d", str, &info_ptr->age,
239 &info_ptr->room) != EOF && i++ < NUM_EMPL) {
240 /* Put information in structure, and structure in item. */
241 item.key = strdup(str);
242 item.data = info_ptr;
244 /* Put item into table. */
245 (void) hsearch(item, ENTER);
249 item.key = name_to_find;
250 while (scanf("%s", item.key) != EOF) {
251 if ((found_item = hsearch(item, FIND)) != NULL) {
252 /* If item is in the table. */
253 (void)printf("found %s, age = %d, room = %d\en",
255 ((struct info *)found_item->data)->age,
256 ((struct info *)found_item->data)->room);
258 (void)printf("no such employee %s\en", name_to_find);
271 functions will fail if:
274 Insufficient memory is available.
281 functions will also fail if the action is
283 and the element is not found:
310 functions first appeared in
323 interface permits the use of only one hash table at a time.