blob: a4412f97872f20ea4ae8192e2139a27dea04b999 [file] [log] [blame]
lh9ed821d2023-04-07 01:36:19 -07001/* Implement simple hashing table with string based keys.
2 Copyright (C) 1994-2015 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published
8 by the Free Software Foundation; version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, see <http://www.gnu.org/licenses/>. */
18
19#ifdef HAVE_CONFIG_H
20# include <config.h>
21#endif
22
23#include <inttypes.h>
24#include <stdio.h>
25#include <stdlib.h>
26#include <string.h>
27#include <stdint.h>
28#include <sys/types.h>
29
30#include <obstack.h>
31
32#ifdef HAVE_VALUES_H
33# include <values.h>
34#endif
35
36#include "simple-hash.h"
37
38#define obstack_chunk_alloc malloc
39#define obstack_chunk_free free
40
41#ifndef BITSPERBYTE
42# define BITSPERBYTE 8
43#endif
44
45#define hashval_t uint32_t
46#include "hashval.h"
47
48#include <programs/xmalloc.h>
49
50typedef struct hash_entry
51{
52 unsigned long used;
53 const void *key;
54 size_t keylen;
55 void *data;
56 struct hash_entry *next;
57}
58hash_entry;
59
60/* Prototypes for local functions. */
61static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
62 unsigned long hval, size_t idx, void *data);
63static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
64 unsigned long int hval);
65static int is_prime (unsigned long int candidate);
66
67
68int
69init_hash (htab, init_size)
70 hash_table *htab;
71 unsigned long int init_size;
72{
73 /* We need the size to be a prime. */
74 init_size = next_prime (init_size);
75
76 /* Initialize the data structure. */
77 htab->size = init_size;
78 htab->filled = 0;
79 htab->first = NULL;
80 htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
81 if (htab->table == NULL)
82 return -1;
83
84 obstack_init (&htab->mem_pool);
85
86 return 0;
87}
88
89
90int
91delete_hash (htab)
92 hash_table *htab;
93{
94 free (htab->table);
95 obstack_free (&htab->mem_pool, NULL);
96 return 0;
97}
98
99
100int
101insert_entry (htab, key, keylen, data)
102 hash_table *htab;
103 const void *key;
104 size_t keylen;
105 void *data;
106{
107 unsigned long int hval = compute_hashval (key, keylen);
108 hash_entry *table = (hash_entry *) htab->table;
109 size_t idx = lookup (htab, key, keylen, hval);
110
111 if (table[idx].used)
112 /* We don't want to overwrite the old value. */
113 return -1;
114 else
115 {
116 /* An empty bucket has been found. */
117 insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
118 keylen, hval, idx, data);
119 return 0;
120 }
121}
122
123static void
124insert_entry_2 (htab, key, keylen, hval, idx, data)
125 hash_table *htab;
126 const void *key;
127 size_t keylen;
128 unsigned long int hval;
129 size_t idx;
130 void *data;
131{
132 hash_entry *table = (hash_entry *) htab->table;
133
134 table[idx].used = hval;
135 table[idx].key = key;
136 table[idx].keylen = keylen;
137 table[idx].data = data;
138
139 /* List the new value in the list. */
140 if ((hash_entry *) htab->first == NULL)
141 {
142 table[idx].next = &table[idx];
143 htab->first = &table[idx];
144 }
145 else
146 {
147 table[idx].next = ((hash_entry *) htab->first)->next;
148 ((hash_entry *) htab->first)->next = &table[idx];
149 htab->first = &table[idx];
150 }
151
152 ++htab->filled;
153 if (100 * htab->filled > 75 * htab->size)
154 {
155 /* Table is filled more than 75%. Resize the table.
156 Experiments have shown that for best performance, this threshold
157 must lie between 40% and 85%. */
158 unsigned long int old_size = htab->size;
159
160 htab->size = next_prime (htab->size * 2);
161 htab->filled = 0;
162 htab->first = NULL;
163 htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
164
165 for (idx = 1; idx <= old_size; ++idx)
166 if (table[idx].used)
167 insert_entry_2 (htab, table[idx].key, table[idx].keylen,
168 table[idx].used,
169 lookup (htab, table[idx].key, table[idx].keylen,
170 table[idx].used),
171 table[idx].data);
172
173 free (table);
174 }
175}
176
177
178int
179find_entry (htab, key, keylen, result)
180 const hash_table *htab;
181 const void *key;
182 size_t keylen;
183 void **result;
184{
185 hash_entry *table = (hash_entry *) htab->table;
186 size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
187
188 if (table[idx].used == 0)
189 return -1;
190
191 *result = table[idx].data;
192 return 0;
193}
194
195
196int
197set_entry (htab, key, keylen, newval)
198 hash_table *htab;
199 const void *key;
200 size_t keylen;
201 void *newval;
202{
203 hash_entry *table = (hash_entry *) htab->table;
204 size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
205
206 if (table[idx].used == 0)
207 return -1;
208
209 table[idx].data = newval;
210 return 0;
211}
212
213
214int
215iterate_table (htab, ptr, key, keylen, data)
216 const hash_table *htab;
217 void **ptr;
218 const void **key;
219 size_t *keylen;
220 void **data;
221{
222 if (*ptr == NULL)
223 {
224 if (htab->first == NULL)
225 return -1;
226 *ptr = (void *) ((hash_entry *) htab->first)->next;
227 }
228 else
229 {
230 if (*ptr == htab->first)
231 return -1;
232 *ptr = (void *) (((hash_entry *) *ptr)->next);
233 }
234
235 *key = ((hash_entry *) *ptr)->key;
236 *keylen = ((hash_entry *) *ptr)->keylen;
237 *data = ((hash_entry *) *ptr)->data;
238 return 0;
239}
240
241
242/* References:
243 [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
244 [Knuth] The Art of Computer Programming, part3 (6.4) */
245
246static size_t
247lookup (htab, key, keylen, hval)
248 const hash_table *htab;
249 const void *key;
250 size_t keylen;
251 unsigned long int hval;
252{
253 unsigned long int hash;
254 size_t idx;
255 hash_entry *table = (hash_entry *) htab->table;
256
257 /* First hash function: simply take the modul but prevent zero. */
258 hash = 1 + hval % htab->size;
259
260 idx = hash;
261
262 if (table[idx].used)
263 {
264 if (table[idx].used == hval && table[idx].keylen == keylen
265 && memcmp (table[idx].key, key, keylen) == 0)
266 return idx;
267
268 /* Second hash function as suggested in [Knuth]. */
269 hash = 1 + hval % (htab->size - 2);
270
271 do
272 {
273 if (idx <= hash)
274 idx = htab->size + idx - hash;
275 else
276 idx -= hash;
277
278 /* If entry is found use it. */
279 if (table[idx].used == hval && table[idx].keylen == keylen
280 && memcmp (table[idx].key, key, keylen) == 0)
281 return idx;
282 }
283 while (table[idx].used);
284 }
285 return idx;
286}
287
288
289unsigned long int
290next_prime (seed)
291 unsigned long int seed;
292{
293 /* Make it definitely odd. */
294 seed |= 1;
295
296 while (!is_prime (seed))
297 seed += 2;
298
299 return seed;
300}
301
302
303static int
304is_prime (candidate)
305 unsigned long int candidate;
306{
307 /* No even number and none less than 10 will be passed here. */
308 unsigned long int divn = 3;
309 unsigned long int sq = divn * divn;
310
311 while (sq < candidate && candidate % divn != 0)
312 {
313 ++divn;
314 sq += 4 * divn;
315 ++divn;
316 }
317
318 return candidate % divn != 0;
319}