Debian Codegraph @

src/hash.c

raw
1 /* Hash tables.
2 Copyright (C) 2000-2011, 2015, 2018-2024 Free Software Foundation,
3 Inc.
4
5 This file is part of GNU Wget.
6
7 GNU Wget is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or (at
10 your option) any later version.
11
12 GNU Wget is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Wget. If not, see <http://www.gnu.org/licenses/>.
19
20 Additional permission under GNU GPL version 3 section 7
21
22 If you modify this program, or any covered work, by linking or
23 combining it with the OpenSSL project's OpenSSL library (or a
24 modified version of that library), containing parts covered by the
25 terms of the OpenSSL or SSLeay licenses, the Free Software Foundation
26 grants you additional permission to convey the resulting work.
27 Corresponding Source for a non-source form of such a combination
28 shall include the source code for the parts of OpenSSL used as well
29 as that of the covered work. */
30
31 /* With -DSTANDALONE, this file can be compiled outside Wget source
32 tree. To test, also use -DTEST. */
33
34 #ifndef STANDALONE
35 # include "wget.h"
36 #else
37 # include "config.h"
38 #endif
39
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <assert.h>
43 #include <string.h>
44 #include <limits.h>
45
46 #ifndef STANDALONE
47 /* Get Wget's utility headers. */
48 # include "utils.h"
49 #else
50 /* Make do without them. */
51 # define xnew(type) (xmalloc (sizeof (type)))
52 # define xnew0(type) (xcalloc (1, sizeof (type)))
53 # define xnew_array(type, len) (xmalloc ((len) * sizeof (type)))
54 # define xfree(p) do { free ((void *) (p)); p = NULL; } while (0)
55
56 # ifndef countof
57 # define countof(x) (sizeof (x) / sizeof ((x)[0]))
58 # endif
59 # include <ctype.h>
60 # define c_tolower(x) tolower ((unsigned char) (x))
61 # include <stdint.h>
62 #endif
63
64 #include "hash.h"
65
66 /* INTERFACE:
67
68 Hash tables are a technique used to implement mapping between
69 objects with near-constant-time access and storage. The table
70 associates keys to values, and a value can be very quickly
71 retrieved by providing the key. Fast lookup tables are typically
72 implemented as hash tables.
73
74 The entry points are
75 hash_table_new -- creates the table.
76 hash_table_destroy -- destroys the table.
77 hash_table_put -- establishes or updates key->value mapping.
78 hash_table_get -- retrieves value of key.
79 hash_table_get_pair -- get key/value pair for key.
80 hash_table_contains -- test whether the table contains key.
81 hash_table_remove -- remove key->value mapping for given key.
82 hash_table_for_each -- call function for each table entry.
83 hash_table_iterate -- iterate over entries in hash table.
84 hash_table_iter_next -- return next element during iteration.
85 hash_table_clear -- clear hash table contents.
86 hash_table_count -- return the number of entries in the table.
87
88 The hash table grows internally as new entries are added and is not
89 limited in size, except by available memory. The table doubles
90 with each resize, which ensures that the amortized time per
91 operation remains constant.
92
93 If not instructed otherwise, tables created by hash_table_new
94 consider the keys to be equal if their pointer values are the same.
95 You can use make_string_hash_table to create tables whose keys are
96 considered equal if their string contents are the same. In the
97 general case, the criterion of equality used to compare keys is
98 specified at table creation time with two callback functions,
99 "hash" and "test". The hash function transforms the key into an
100 arbitrary number that must be the same for two equal keys. The
101 test function accepts two keys and returns non-zero if they are to
102 be considered equal.
103
104 Note that neither keys nor values are copied when inserted into the
105 hash table, so they must exist for the lifetime of the table. This
106 means that e.g. the use of static strings is OK, but objects with a
107 shorter life-time probably need to be copied (with strdup() or the
108 like in the case of strings) before being inserted. */
109
110 /* IMPLEMENTATION:
111
112 The hash table is implemented as an open-addressed table with
113 linear probing collision resolution.
114
115 The above means that all the cells (each cell containing a key and
116 a value pointer) are stored in a contiguous array. Array position
117 of each cell is determined by the hash value of its key and the
118 size of the table: location := hash(key) % size. If two different
119 keys end up on the same position (collide), the one that came
120 second is stored in the first unoccupied cell that follows it.
121 This collision resolution technique is called "linear probing".
122
123 There are more advanced collision resolution methods (quadratic
124 probing, double hashing), but we don't use them because they incur
125 more non-sequential access to the array, which results in worse CPU
126 cache behavior. Linear probing works well as long as the
127 count/size ratio (fullness) is kept below 75%. We make sure to
128 grow and rehash the table whenever this threshold is exceeded.
129
130 Collisions complicate deletion because simply clearing a cell
131 followed by previously collided entries would cause those neighbors
132 to not be picked up by find_cell later. One solution is to leave a
133 "tombstone" marker instead of clearing the cell, and another is to
134 recalculate the positions of adjacent cells. We take the latter
135 approach because it results in less bookkeeping garbage and faster
136 retrieval at the (slight) expense of deletion. */
137
138 /* Maximum allowed fullness: when hash table's fullness exceeds this
139 value, the table is resized. */
140 #define HASH_MAX_FULLNESS 0.75
141
142 /* The hash table size is multiplied by this factor (and then rounded
143 to the next prime) with each resize. This guarantees infrequent
144 resizes. */
145 #define HASH_RESIZE_FACTOR 2
146
147 struct cell {
148 void *key;
149 void *value;
150 };
151
152 typedef unsigned long (*hashfun_t) (const void *);
153 typedef int (*testfun_t) (const void *, const void *);
154
155 struct hash_table {
156 hashfun_t hash_function;
157 testfun_t test_function;
158
159 struct cell *cells; /* contiguous array of cells. */
160 int size; /* size of the array. */
161
162 int count; /* number of occupied entries. */
163 int resize_threshold; /* after size exceeds this number of
164 entries, resize the table. */
165 int prime_offset; /* the offset of the current prime in
166 the prime table. */
167 };
168
169 /* We use the all-bits-set constant (INVALID_PTR) marker to mean that
170 a cell is empty. It is unaligned and therefore illegal as a
171 pointer. INVALID_PTR_CHAR (0xff) is the single-character constant
172 used to initialize the entire cells array as empty.
173
174 The all-bits-set value is a better choice than NULL because it
175 allows the use of NULL/0 keys. Since the keys are either integers
176 or pointers, the only key that cannot be used is the integer value
177 -1. This is acceptable because it still allows the use of
178 nonnegative integer keys. */
179
180 #define INVALID_PTR ((void *) ~(uintptr_t) 0)
181 #ifndef UCHAR_MAX
182 # define UCHAR_MAX 0xff
183 #endif
184 #define INVALID_PTR_CHAR UCHAR_MAX
185
186 /* Whether the cell C is occupied (non-empty). */
187 #define CELL_OCCUPIED(c) ((c)->key != INVALID_PTR)
188
189 /* Clear the cell C, i.e. mark it as empty (unoccupied). */
190 #define CLEAR_CELL(c) ((c)->key = INVALID_PTR)
191
192 /* "Next" cell is the cell following C, but wrapping back to CELLS
193 when C would reach CELLS+SIZE. */
194 #define NEXT_CELL(c, cells, size) (c != cells + (size - 1) ? c + 1 : cells)
195
196 /* Loop over occupied cells starting at C, terminating the loop when
197 an empty cell is encountered. */
198 #define FOREACH_OCCUPIED_ADJACENT(c, cells, size) \
199 for (; CELL_OCCUPIED (c); c = NEXT_CELL (c, cells, size))
200
201 /* Return the position of KEY in hash table SIZE large, hash function
202 being HASHFUN. */
203 #define HASH_POSITION(key, hashfun, size) ((hashfun) (key) % size)
204
205 /* Find a prime near, but greater than or equal to SIZE. The primes
206 are looked up from a table with a selection of primes convenient
207 for this purpose.
208
209 PRIME_OFFSET is a minor optimization: it specifies start position
210 for the search for the large enough prime. The final offset is
211 stored in the same variable. That way the list of primes does not
212 have to be scanned from the beginning each time around. */
213
214 static int
215 prime_size (int size, int *prime_offset)
216 {
217 static const int primes[] = {
218 13, 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
219 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
220 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
221 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
222 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
223 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
224 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
225 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
226 1174703521, 1527114613, 1837299131, 2147483647
227 };
228 size_t i;
229
230 for (i = *prime_offset; i < countof (primes); i++)
231 if (primes[i] >= size)
232 {
233 /* Set the offset to the next prime. That is safe because,
234 next time we are called, it will be with a larger SIZE,
235 which means we could never return the same prime anyway.
236 (If that is not the case, the caller can simply reset
237 *prime_offset.) */
238 *prime_offset = i + 1;
239 return primes[i];
240 }
241
242 abort ();
243 }
244
245 static int cmp_pointer (const void *, const void *);
246
247 /* Create a hash table with hash function HASH_FUNCTION and test
248 function TEST_FUNCTION. The table is empty (its count is 0), but
249 pre-allocated to store at least ITEMS items.
250
251 ITEMS is the number of items that the table can accept without
252 needing to resize. It is useful when creating a table that is to
253 be immediately filled with a known number of items. In that case,
254 the regrows are a waste of time, and specifying ITEMS correctly
255 will avoid them altogether.
256
257 Note that hash tables grow dynamically regardless of ITEMS. The
258 only use of ITEMS is to preallocate the table and avoid unnecessary
259 dynamic regrows. Don't bother making ITEMS prime because it's not
260 used as size unchanged. To start with a small table that grows as
261 needed, simply specify zero ITEMS.
262
263 If hash and test callbacks are not specified, identity mapping is
264 assumed, i.e. pointer values are used for key comparison. (Common
265 Lisp calls such tables EQ hash tables, and Java calls them
266 IdentityHashMaps.) If your keys require different comparison,
267 specify hash and test functions. For easy use of C strings as hash
268 keys, you can use the convenience functions make_string_hash_table
269 and make_nocase_string_hash_table. */
270
271 struct hash_table *
272 hash_table_new (int items,
273 unsigned long (*hash_function) (const void *),
274 int (*test_function) (const void *, const void *))
275 {
276 int size;
277 struct hash_table *ht = xnew (struct hash_table);
278
279 ht->hash_function = hash_function ? hash_function : hash_pointer;
280 ht->test_function = test_function ? test_function : cmp_pointer;
281
282 /* If the size of struct hash_table ever becomes a concern, this
283 field can go. (Wget doesn't create many hashes.) */
284 ht->prime_offset = 0;
285
286 /* Calculate the size that ensures that the table will store at
287 least ITEMS keys without the need to resize. */
288 size = (int) (1 + items / HASH_MAX_FULLNESS);
289 size = prime_size (size, &ht->prime_offset);
290 ht->size = size;
291 ht->resize_threshold = (int) (size * HASH_MAX_FULLNESS);
292 /*assert (ht->resize_threshold >= items);*/
293
294 ht->cells = xnew_array (struct cell, ht->size);
295
296 /* Mark cells as empty. We use 0xff rather than 0 to mark empty
297 keys because it allows us to use NULL/0 as keys. */
298 memset (ht->cells, INVALID_PTR_CHAR, size * sizeof (struct cell));
299
300 ht->count = 0;
301
302 return ht;
303 }
304
305 /* Free the data associated with hash table HT. */
306
307 void
308 hash_table_destroy (struct hash_table *ht)
309 {
310 xfree (ht->cells);
311 xfree (ht);
312 }
313
314 /* The heart of most functions in this file -- find the cell whose
315 KEY is equal to key, using linear probing. Returns the cell
316 that matches KEY, or the first empty cell if none matches. */
317
318 static inline struct cell *
319 find_cell (const struct hash_table *ht, const void *key)
320 {
321 struct cell *cells = ht->cells;
322 int size = ht->size;
323 struct cell *c = cells + HASH_POSITION (key, ht->hash_function, size);
324 testfun_t equals = ht->test_function;
325
326 FOREACH_OCCUPIED_ADJACENT (c, cells, size)
327 if (equals (key, c->key))
328 break;
329 return c;
330 }
331
332 /* Get the value that corresponds to the key KEY in the hash table HT.
333 If no value is found, return NULL. Note that NULL is a legal value
334 for value; if you are storing NULLs in your hash table, you can use
335 hash_table_contains to be sure that a (possibly NULL) value exists
336 in the table. Or, you can use hash_table_get_pair instead of this
337 function. */
338
339 void *
340 hash_table_get (const struct hash_table *ht, const void *key)
341 {
342 struct cell *c = find_cell (ht, key);
343 if (CELL_OCCUPIED (c))
344 return c->value;
345 else
346 return NULL;
347 }
348
349 /* Like hash_table_get, but writes out the pointers to both key and
350 value. Returns non-zero on success. */
351
352 int
353 hash_table_get_pair (const struct hash_table *ht, const void *lookup_key,
354 void *orig_key, void *value)
355 {
356 struct cell *c = find_cell (ht, lookup_key);
357 if (CELL_OCCUPIED (c))
358 {
359 if (orig_key)
360 *(void **)orig_key = c->key;
361 if (value)
362 *(void **)value = c->value;
363 return 1;
364 }
365 else
366 return 0;
367 }
368
369 /* Return 1 if HT contains KEY, 0 otherwise. */
370
371 int
372 hash_table_contains (const struct hash_table *ht, const void *key)
373 {
374 struct cell *c = find_cell (ht, key);
375 return CELL_OCCUPIED (c);
376 }
377
378 /* Grow hash table HT as necessary, and rehash all the key-value
379 mappings. */
380
381 static void
382 grow_hash_table (struct hash_table *ht)
383 {
384 hashfun_t hasher = ht->hash_function;
385 struct cell *old_cells = ht->cells;
386 struct cell *old_end = ht->cells + ht->size;
387 struct cell *c, *cells;
388 int newsize;
389
390 newsize = prime_size (ht->size * HASH_RESIZE_FACTOR, &ht->prime_offset);
391 #if 0
392 printf ("growing from %d to %d; fullness %.2f%% to %.2f%%\n",
393 ht->size, newsize,
394 100.0 * ht->count / ht->size,
395 100.0 * ht->count / newsize);
396 #endif
397
398 ht->size = newsize;
399 ht->resize_threshold = (int) (newsize * HASH_MAX_FULLNESS);
400
401 cells = xnew_array (struct cell, newsize);
402 memset (cells, INVALID_PTR_CHAR, newsize * sizeof (struct cell));
403 ht->cells = cells;
404
405 for (c = old_cells; c < old_end; c++)
406 if (CELL_OCCUPIED (c))
407 {
408 struct cell *new_c;
409 /* We don't need to test for uniqueness of keys because they
410 come from the hash table and are therefore known to be
411 unique. */
412 new_c = cells + HASH_POSITION (c->key, hasher, newsize);
413 FOREACH_OCCUPIED_ADJACENT (new_c, cells, newsize)
414 ;
415 *new_c = *c;
416 }
417
418 xfree (old_cells);
419 }
420
421 /* Put VALUE in the hash table HT under the key KEY. This regrows the
422 table if necessary. */
423
424 void
425 hash_table_put (struct hash_table *ht, const void *key, const void *value)
426 {
427 struct cell *c = find_cell (ht, key);
428 if (CELL_OCCUPIED (c))
429 {
430 /* update existing item */
431 c->key = (void *)key; /* const? */
432 c->value = (void *)value;
433 return;
434 }
435
436 /* If adding the item would make the table exceed max. fullness,
437 grow the table first. */
438 if (ht->count >= ht->resize_threshold)
439 {
440 grow_hash_table (ht);
441 c = find_cell (ht, key);
442 }
443
444 /* add new item */
445 ++ht->count;
446 c->key = (void *)key; /* const? */
447 c->value = (void *)value;
448 }
449
450 /* Remove KEY->value mapping from HT. Return 0 if there was no such
451 entry; return 1 if an entry was removed. */
452
453 int
454 hash_table_remove (struct hash_table *ht, const void *key)
455 {
456 struct cell *c = find_cell (ht, key);
457 if (!CELL_OCCUPIED (c))
458 return 0;
459 else
460 {
461 int size = ht->size;
462 struct cell *cells = ht->cells;
463 hashfun_t hasher = ht->hash_function;
464
465 CLEAR_CELL (c);
466 --ht->count;
467
468 /* Rehash all the entries following C. The alternative
469 approach is to mark the entry as deleted, i.e. create a
470 "tombstone". That speeds up removal, but leaves a lot of
471 garbage and slows down hash_table_get and hash_table_put. */
472
473 c = NEXT_CELL (c, cells, size);
474 FOREACH_OCCUPIED_ADJACENT (c, cells, size)
475 {
476 const void *key2 = c->key;
477 struct cell *c_new;
478
479 /* Find the new location for the key. */
480 c_new = cells + HASH_POSITION (key2, hasher, size);
481 FOREACH_OCCUPIED_ADJACENT (c_new, cells, size)
482 if (key2 == c_new->key)
483 /* The cell C (key2) is already where we want it (in
484 C_NEW's "chain" of keys.) */
485 goto next_rehash;
486
487 *c_new = *c;
488 CLEAR_CELL (c);
489
490 next_rehash:
491 ;
492 }
493 return 1;
494 }
495 }
496
497 /* Clear HT of all entries. After calling this function, the count
498 and the fullness of the hash table will be zero. The size will
499 remain unchanged. */
500
501 void
502 hash_table_clear (struct hash_table *ht)
503 {
504 memset (ht->cells, INVALID_PTR_CHAR, ht->size * sizeof (struct cell));
505 ht->count = 0;
506 }
507
508 /* Call FN for each entry in HT. FN is called with three arguments:
509 the key, the value, and ARG. When FN returns a non-zero value, the
510 mapping stops.
511
512 It is undefined what happens if you add or remove entries in the
513 hash table while hash_table_for_each is running. The exception is
514 the entry you're currently mapping over; you may call
515 hash_table_put or hash_table_remove on that entry's key. That is
516 also the reason why this function cannot be implemented in terms of
517 hash_table_iterate. */
518
519 void
520 hash_table_for_each (struct hash_table *ht,
521 int (*fn) (void *, void *, void *), void *arg)
522 {
523 struct cell *c = ht->cells;
524 struct cell *end = ht->cells + ht->size;
525
526 for (; c < end; c++)
527 if (CELL_OCCUPIED (c))
528 {
529 void *key;
530 repeat:
531 key = c->key;
532 if (fn (key, c->value, arg))
533 return;
534 /* hash_table_remove might have moved the adjacent cells. */
535 if (c->key != key && CELL_OCCUPIED (c))
536 goto repeat;
537 }
538 }
539
540 /* Initiate iteration over HT. Entries are obtained with
541 hash_table_iter_next, a typical iteration loop looking like this:
542
543 hash_table_iterator iter;
544 for (hash_table_iterate (ht, &iter); hash_table_iter_next (&iter); )
545 ... do something with iter.key and iter.value ...
546
547 The iterator does not need to be deallocated after use. The hash
548 table must not be modified while being iterated over. */
549
550 void
551 hash_table_iterate (struct hash_table *ht, hash_table_iterator *iter)
552 {
553 iter->pos = ht->cells;
554 iter->end = ht->cells + ht->size;
555 }
556
557 /* Get the next hash table entry. ITER is an iterator object
558 initialized using hash_table_iterate. While there are more
559 entries, the key and value pointers are stored to ITER->key and
560 ITER->value respectively and 1 is returned. When there are no more
561 entries, 0 is returned.
562
563 If the hash table is modified between calls to this function, the
564 result is undefined. */
565
566 int
567 hash_table_iter_next (hash_table_iterator *iter)
568 {
569 struct cell *c = iter->pos;
570 struct cell *end = iter->end;
571 for (; c < end; c++)
572 if (CELL_OCCUPIED (c))
573 {
574 iter->key = c->key;
575 iter->value = c->value;
576 iter->pos = c + 1;
577 return 1;
578 }
579 return 0;
580 }
581
582 /* Return the number of elements in the hash table. This is not the
583 same as the physical size of the hash table, which is always
584 greater than the number of elements. */
585
586 int
587 hash_table_count (const struct hash_table *ht)
588 {
589 return ht->count;
590 }
591
592 /* Functions from this point onward are meant for convenience and
593 don't strictly belong to this file. However, this is as good a
594 place for them as any. */
595
596 /* Guidelines for creating custom hash and test functions:
597
598 - The test function returns non-zero for keys that are considered
599 "equal", zero otherwise.
600
601 - The hash function returns a number that represents the
602 "distinctness" of the object. In more precise terms, it means
603 that for any two objects that test "equal" under the test
604 function, the hash function MUST produce the same result.
605
606 This does not mean that all different objects must produce
607 different values (that would be "perfect" hashing), only that
608 non-distinct objects must produce the same values! For instance,
609 a hash function that returns 0 for any given object is a
610 perfectly valid (albeit extremely bad) hash function. A hash
611 function that hashes a string by adding up all its characters is
612 another example of a valid (but still quite bad) hash function.
613
614 It is not hard to make hash and test functions agree about
615 equality. For example, if the test function compares strings
616 case-insensitively, the hash function can lower-case the
617 characters when calculating the hash value. That ensures that
618 two strings differing only in case will hash the same.
619
620 - To prevent performance degradation, choose a hash function with
621 as good "spreading" as possible. A good hash function will use
622 all the bits of the input when calculating the hash, and will
623 react to even small changes in input with a completely different
624 output. But don't make the hash function itself overly slow,
625 because you'll be incurring a non-negligible overhead to all hash
626 table operations. */
627
628 /*
629 * Support for hash tables whose keys are strings.
630 *
631 */
632
633 /* Base 31 hash function. Taken from Gnome's glib, modified to use
634 standard C types.
635
636 We used to use the popular hash function from the Dragon Book, but
637 this one seems to perform much better, both by being faster and by
638 generating less collisions. */
639
640 #ifdef __clang__
641 __attribute__((no_sanitize("integer")))
642 #endif
643 static unsigned long
644 hash_string (const void *key)
645 {
646 const char *p = key;
647 unsigned int h = *p;
648
649 if (h)
650 for (p += 1; *p != '\0'; p++)
651 h = (h << 5) - h + *p;
652
653 return h;
654 }
655
656 /* Frontend for strcmp usable for hash tables. */
657
658 static int
659 cmp_string (const void *s1, const void *s2)
660 {
661 return !strcmp ((const char *)s1, (const char *)s2);
662 }
663
664 /* Return a hash table of preallocated to store at least ITEMS items
665 suitable to use strings as keys. */
666
667 struct hash_table *
668 make_string_hash_table (int items)
669 {
670 return hash_table_new (items, hash_string, cmp_string);
671 }
672
673 /*
674 * Support for hash tables whose keys are strings, but which are
675 * compared case-insensitively.
676 *
677 */
678
679 /* Like hash_string, but produce the same hash regardless of the case. */
680
681 #ifdef __clang__
682 __attribute__((no_sanitize("integer")))
683 #endif
684 static unsigned long
685 hash_string_nocase (const void *key)
686 {
687 const char *p = key;
688 unsigned int h = c_tolower (*p);
689
690 if (h)
691 for (p += 1; *p != '\0'; p++)
692 h = (h << 5) - h + c_tolower (*p);
693
694 return h;
695 }
696
697 /* Like string_cmp, but doing case-insensitive comparison. */
698
699 static int
700 string_cmp_nocase (const void *s1, const void *s2)
701 {
702 return !strcasecmp ((const char *)s1, (const char *)s2);
703 }
704
705 /* Like make_string_hash_table, but uses string_hash_nocase and
706 string_cmp_nocase. */
707
708 struct hash_table *
709 make_nocase_string_hash_table (int items)
710 {
711 return hash_table_new (items, hash_string_nocase, string_cmp_nocase);
712 }
713
714 /* Hashing of numeric values, such as pointers and integers.
715
716 This implementation is the Robert Jenkins' 32 bit Mix Function,
717 with a simple adaptation for 64-bit values. According to Jenkins
718 it should offer excellent spreading of values. Unlike the popular
719 Knuth's multiplication hash, this function doesn't need to know the
720 hash table size to work. */
721
722 #ifdef __clang__
723 __attribute__((no_sanitize("integer")))
724 #endif
725 unsigned long
726 hash_pointer (const void *ptr)
727 {
728 uintptr_t key = (uintptr_t) ptr;
729 key += (key << 12);
730 key ^= (key >> 22);
731 key += (key << 4);
732 key ^= (key >> 9);
733 key += (key << 10);
734 key ^= (key >> 2);
735 key += (key << 7);
736 key ^= (key >> 12);
737 #if SIZEOF_VOID_P > 4
738 key += (key << 44);
739 key ^= (key >> 54);
740 key += (key << 36);
741 key ^= (key >> 41);
742 key += (key << 42);
743 key ^= (key >> 34);
744 key += (key << 39);
745 key ^= (key >> 44);
746 #endif
747 return (unsigned long) key;
748 }
749
750 static int
751 cmp_pointer (const void *ptr1, const void *ptr2)
752 {
753 return ptr1 == ptr2;
754 }
755
756 #ifdef TEST
757
758 #include <stdio.h>
759 #include <string.h>
760
761 void
762 print_hash (struct hash_table *sht)
763 {
764 hash_table_iterator iter;
765 int count = 0;
766
767 for (hash_table_iterate (sht, &iter); hash_table_iter_next (&iter);
768 ++count)
769 printf ("%s: %s\n", iter.key, iter.value);
770 assert (count == sht->count);
771 }
772
773 int
774 main (void)
775 {
776 struct hash_table *ht = make_string_hash_table (0);
777 char line[80];
778
779 #ifdef ENABLE_NLS
780 /* Set the current locale. */
781 setlocale (LC_ALL, "");
782 /* Set the text message domain. */
783 bindtextdomain ("wget", LOCALEDIR);
784 textdomain ("wget");
785 #endif /* ENABLE_NLS */
786
787 while ((fgets (line, sizeof (line), stdin)))
788 {
789 int len = strlen (line);
790 if (len <= 1)
791 continue;
792 line[--len] = '\0';
793 if (!hash_table_contains (ht, line))
794 hash_table_put (ht, strdup (line), "here I am!");
795 #if 1
796 if (len % 5 == 0)
797 {
798 char *line_copy;
799 if (hash_table_get_pair (ht, line, &line_copy, NULL))
800 {
801 hash_table_remove (ht, line);
802 xfree (line_copy);
803 }
804 }
805 #endif
806 }
807 #if 0
808 print_hash (ht);
809 #endif
810 #if 1
811 printf ("%d %d\n", ht->count, ht->size);
812 #endif
813 return 0;
814 }
815 #endif /* TEST */