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