1 /* Copyright (C) 1993, 1995, 1996, 1997, 2002 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <http://www.gnu.org/licenses/>. */
18
19 #include <errno.h>
20 #include <stdlib.h>
21 #include <string.h>
22
23 #include <search.h>
24
25
26 /* [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
27 [Knuth] The Art of Computer Programming, part 3 (6.4) */
28
29
30 /* The reentrant version has no static variables to maintain the state.
31 Instead the interface of all functions is extended to take an argument
32 which describes the current status. */
33 typedef struct _ENTRY
34 {
35 unsigned int used;
36 ENTRY entry;
37 }
38 _ENTRY;
39
40
41 #ifdef L_hcreate_r
42
43 /* For the used double hash method the table size has to be a prime. To
44 correct the user given table size we need a prime test. This trivial
45 algorithm is adequate because
46 a) the code is (most probably) called a few times per program run and
47 b) the number is small because the table must fit in the core */
isprime(unsigned int number)48 static int isprime (unsigned int number)
49 {
50 /* no even number will be passed */
51 unsigned int divisor = 3;
52
53 while (divisor * divisor < number && number % divisor != 0)
54 divisor += 2;
55
56 return number % divisor != 0;
57 }
58
59
60 /* Before using the hash table we must allocate memory for it.
61 Test for an existing table are done. We allocate one element
62 more as the found prime number says. This is done for more effective
63 indexing as explained in the comment for the hsearch function.
64 The contents of the table is zeroed, especially the field used
65 becomes zero. */
hcreate_r(size_t nel,struct hsearch_data * htab)66 int hcreate_r (size_t nel, struct hsearch_data *htab)
67 {
68 /* Test for correct arguments. */
69 if (htab == NULL)
70 {
71 __set_errno (EINVAL);
72 return 0;
73 }
74
75 /* There is still another table active. Return with error. */
76 if (htab->table != NULL)
77 return 0;
78
79 /* Change nel to the first prime number not smaller as nel. */
80 nel |= 1; /* make odd */
81 while (!isprime (nel))
82 nel += 2;
83
84 htab->size = nel;
85 htab->filled = 0;
86
87 /* allocate memory and zero out */
88 htab->table = (_ENTRY *) calloc (htab->size + 1, sizeof (_ENTRY));
89 if (htab->table == NULL)
90 return 0;
91
92 /* everything went alright */
93 return 1;
94 }
libc_hidden_def(hcreate_r)95 libc_hidden_def(hcreate_r)
96 #endif
97
98 #ifdef L_hdestroy_r
99 /* After using the hash table it has to be destroyed. The used memory can
100 be freed and the local static variable can be marked as not used. */
101 void hdestroy_r (struct hsearch_data *htab)
102 {
103 /* Test for correct arguments. */
104 if (htab == NULL)
105 {
106 __set_errno (EINVAL);
107 return;
108 }
109
110 /* free used memory */
111 free (htab->table);
112
113 /* the sign for an existing table is an value != NULL in htable */
114 htab->table = NULL;
115 }
libc_hidden_def(hdestroy_r)116 libc_hidden_def(hdestroy_r)
117 #endif
118
119 #ifdef L_hsearch_r
120 /* This is the search function. It uses double hashing with open addressing.
121 The argument item.key has to be a pointer to an zero terminated, most
122 probably strings of chars. The function for generating a number of the
123 strings is simple but fast. It can be replaced by a more complex function
124 like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
125
126 We use an trick to speed up the lookup. The table is created by hcreate
127 with one more element available. This enables us to use the index zero
128 special. This index will never be used because we store the first hash
129 index in the field used where zero means not used. Every other value
130 means used. The used field can be used as a first fast comparison for
131 equality of the stored and the parameter value. This helps to prevent
132 unnecessary expensive calls of strcmp. */
133
134
135 int hsearch_r (ENTRY item, ACTION action, ENTRY **retval,
136 struct hsearch_data *htab)
137 {
138 unsigned int hval;
139 unsigned int count;
140 unsigned int len = strlen (item.key);
141 unsigned int idx;
142
143 /* Compute an value for the given string. Perhaps use a better method. */
144 hval = len;
145 count = len;
146 while (count-- > 0)
147 {
148 hval <<= 4;
149 hval += item.key[count];
150 }
151
152 /* First hash function: simply take the modul but prevent zero. */
153 hval %= htab->size;
154 if (hval == 0)
155 ++hval;
156
157 /* The first index tried. */
158 idx = hval;
159
160 if (htab->table[idx].used)
161 {
162 /* Further action might be required according to the action value. */
163 unsigned hval2;
164
165 if (htab->table[idx].used == hval
166 && strcmp (item.key, htab->table[idx].entry.key) == 0)
167 {
168 *retval = &htab->table[idx].entry;
169 return 1;
170 }
171
172 /* Second hash function, as suggested in [Knuth] */
173 hval2 = 1 + hval % (htab->size - 2);
174
175 do
176 {
177 /* Because SIZE is prime this guarantees to step through all
178 available indeces. */
179 if (idx <= hval2)
180 idx = htab->size + idx - hval2;
181 else
182 idx -= hval2;
183
184 /* If we visited all entries leave the loop unsuccessfully. */
185 if (idx == hval)
186 break;
187
188 /* If entry is found use it. */
189 if (htab->table[idx].used == hval
190 && strcmp (item.key, htab->table[idx].entry.key) == 0)
191 {
192 *retval = &htab->table[idx].entry;
193 return 1;
194 }
195 }
196 while (htab->table[idx].used);
197 }
198
199 /* An empty bucket has been found. */
200 if (action == ENTER)
201 {
202 /* If table is full and another entry should be entered return
203 with error. */
204 if (htab->filled == htab->size)
205 {
206 __set_errno (ENOMEM);
207 *retval = NULL;
208 return 0;
209 }
210
211 htab->table[idx].used = hval;
212 htab->table[idx].entry = item;
213
214 ++htab->filled;
215
216 *retval = &htab->table[idx].entry;
217 return 1;
218 }
219
220 __set_errno (ESRCH);
221 *retval = NULL;
222 return 0;
223 }
224 libc_hidden_def(hsearch_r)
225 #endif
226