2 Copyright (C) 2000-2005 Free Software Foundation, Inc.
4 This file is part of GNU Wget.
6 GNU Wget is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or (at
9 your option) any later version.
11 GNU Wget 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.
16 You should have received a copy of the GNU General Public License
17 along with Wget; if not, write to the Free Software Foundation, Inc.,
18 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 In addition, as a special exception, the Free Software Foundation
21 gives permission to link the code of its release of Wget with the
22 OpenSSL project's "OpenSSL" library (or with modified versions of it
23 that use the same license as the "OpenSSL" library), and distribute
24 the linked executables. You must obey the GNU General Public License
25 in all respects for all of the code used other than "OpenSSL". If you
26 modify this file, you may extend this exception to your version of the
27 file, but you are not obligated to do so. If you do not wish to do
28 so, delete this exception statement from your version. */
30 /* With -DSTANDALONE, this file can be compiled outside Wget source
31 tree. To test, also use -DTEST. */
44 /* Get Wget's utility headers. */
48 /* Make do without them. */
49 # define xnew(x) xmalloc (sizeof (x))
50 # define xnew_array(type, x) xmalloc (sizeof (type) * (x))
51 # define xmalloc malloc
53 # define countof(x) (sizeof (x) / sizeof ((x)[0]))
54 # define TOLOWER(x) ('A' <= (x) && (x) <= 'Z' ? (x) - 32 : (x))
61 Hash tables are a technique used to implement mapping between
62 objects with near-constant-time access and storage. The table
63 associates keys to values, and a value can be very quickly
64 retrieved by providing the key. Fast lookup tables are typically
65 implemented as hash tables.
68 hash_table_new -- creates the table.
69 hash_table_destroy -- destroys the table.
70 hash_table_put -- establishes or updates key->value mapping.
71 hash_table_get -- retrieves value of key.
72 hash_table_get_pair -- get key/value pair for key.
73 hash_table_contains -- test whether the table contains key.
74 hash_table_remove -- remove key->value mapping for given key.
75 hash_table_for_each -- call function for each table entry.
76 hash_table_iterate -- iterate over entries in hash table.
77 hash_table_iter_next -- return next element during iteration.
78 hash_table_clear -- clear hash table contents.
79 hash_table_count -- return the number of entries in the table.
81 The hash table grows internally as new entries are added and is not
82 limited in size, except by available memory. The table doubles
83 with each resize, which ensures that the amortized time per
84 operation remains constant.
86 If not instructed otherwise, tables created by hash_table_new
87 consider the keys to be equal if their pointer values are the same.
88 You can use make_string_hash_table to create tables whose keys are
89 considered equal if their string contents are the same. In the
90 general case, the criterion of equality used to compare keys is
91 specified at table creation time with two callback functions,
92 "hash" and "test". The hash function transforms the key into an
93 arbitrary number that must be the same for two equal keys. The
94 test function accepts two keys and returns non-zero if they are to
97 Note that neither keys nor values are copied when inserted into the
98 hash table, so they must exist for the lifetime of the table. This
99 means that e.g. the use of static strings is OK, but objects with a
100 shorter life-time probably need to be copied (with strdup() or the
101 like in the case of strings) before being inserted. */
105 The hash table is implemented as an open-addressed table with
106 linear probing collision resolution.
108 The above means that all the cells (each cell containing a key and
109 a value pointer) are stored in a contiguous array. Array position
110 of each cell is determined by the hash value of its key and the
111 size of the table: location := hash(key) % size. If two different
112 keys end up on the same position (collide), the one that came
113 second is stored in the first unoccupied cell that follows it.
114 This collision resolution technique is called "linear probing".
116 There are more advanced collision resolution methods (quadratic
117 probing, double hashing), but we don't use them because they incur
118 more non-sequential access to the array, which results in worse CPU
119 cache behavior. Linear probing works well as long as the
120 count/size ratio (fullness) is kept below 75%. We make sure to
121 grow and rehash the table whenever this threshold is exceeded.
123 Collisions complicate deletion because simply clearing a cell
124 followed by previously collided entries would cause those neighbors
125 to not be picked up by find_cell later. One solution is to leave a
126 "tombstone" marker instead of clearing the cell, and another is to
127 recalculate the positions of adjacent cells. We take the latter
128 approach because it results in less bookkeeping garbage and faster
129 retrieval at the (slight) expense of deletion. */
131 /* Maximum allowed fullness: when hash table's fullness exceeds this
132 value, the table is resized. */
133 #define HASH_MAX_FULLNESS 0.75
135 /* The hash table size is multiplied by this factor (and then rounded
136 to the next prime) with each resize. This guarantees infrequent
138 #define HASH_RESIZE_FACTOR 2
145 typedef unsigned long (*hashfun_t) (const void *);
146 typedef int (*testfun_t) (const void *, const void *);
149 hashfun_t hash_function;
150 testfun_t test_function;
152 struct cell *cells; /* contiguous array of cells. */
153 int size; /* size of the array. */
155 int count; /* number of occupied entries. */
156 int resize_threshold; /* after size exceeds this number of
157 entries, resize the table. */
158 int prime_offset; /* the offset of the current prime in
162 /* We use the all-bits-set constant (INVALID_PTR) marker to mean that
163 a cell is empty. It is unaligned and therefore illegal as a
164 pointer. INVALID_PTR_CHAR (0xff) is the single-character constant
165 used to initialize the entire cells array as empty.
167 The all-bits-set value is a better choice than NULL because it
168 allows the use of NULL/0 keys. Since the keys are either integers
169 or pointers, the only key that cannot be used is the integer value
170 -1. This is acceptable because it still allows the use of
171 nonnegative integer keys. */
173 #define INVALID_PTR ((void *) ~0UL)
175 # define UCHAR_MAX 0xff
177 #define INVALID_PTR_CHAR UCHAR_MAX
179 /* Whether the cell C is occupied (non-empty). */
180 #define CELL_OCCUPIED(c) ((c)->key != INVALID_PTR)
182 /* Clear the cell C, i.e. mark it as empty (unoccupied). */
183 #define CLEAR_CELL(c) ((c)->key = INVALID_PTR)
185 /* "Next" cell is the cell following C, but wrapping back to CELLS
186 when C would reach CELLS+SIZE. */
187 #define NEXT_CELL(c, cells, size) (c != cells + (size - 1) ? c + 1 : cells)
189 /* Loop over occupied cells starting at C, terminating the loop when
190 an empty cell is encountered. */
191 #define FOREACH_OCCUPIED_ADJACENT(c, cells, size) \
192 for (; CELL_OCCUPIED (c); c = NEXT_CELL (c, cells, size))
194 /* Return the position of KEY in hash table SIZE large, hash function
196 #define HASH_POSITION(key, hashfun, size) ((hashfun) (key) % size)
198 /* Find a prime near, but greather than or equal to SIZE. The primes
199 are looked up from a table with a selection of primes convenient
202 PRIME_OFFSET is a minor optimization: it specifies start position
203 for the search for the large enough prime. The final offset is
204 stored in the same variable. That way the list of primes does not
205 have to be scanned from the beginning each time around. */
208 prime_size (int size, int *prime_offset)
210 static const int primes[] = {
211 13, 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
212 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
213 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
214 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
215 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
216 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
217 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
218 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
219 1174703521, 1527114613, 1837299131, 2147483647
223 for (i = *prime_offset; i < countof (primes); i++)
224 if (primes[i] >= size)
226 /* Set the offset to the next prime. That is safe because,
227 next time we are called, it will be with a larger SIZE,
228 which means we could never return the same prime anyway.
229 (If that is not the case, the caller can simply reset
231 *prime_offset = i + 1;
238 static int cmp_pointer (const void *, const void *);
240 /* Create a hash table with hash function HASH_FUNCTION and test
241 function TEST_FUNCTION. The table is empty (its count is 0), but
242 pre-allocated to store at least ITEMS items.
244 ITEMS is the number of items that the table can accept without
245 needing to resize. It is useful when creating a table that is to
246 be immediately filled with a known number of items. In that case,
247 the regrows are a waste of time, and specifying ITEMS correctly
248 will avoid them altogether.
250 Note that hash tables grow dynamically regardless of ITEMS. The
251 only use of ITEMS is to preallocate the table and avoid unnecessary
252 dynamic regrows. Don't bother making ITEMS prime because it's not
253 used as size unchanged. To start with a small table that grows as
254 needed, simply specify zero ITEMS.
256 If hash and test callbacks are not specified, identity mapping is
257 assumed, i.e. pointer values are used for key comparison. (Common
258 Lisp calls such tables EQ hash tables, and Java calls them
259 IdentityHashMaps.) If your keys require different comparison,
260 specify hash and test functions. For easy use of C strings as hash
261 keys, you can use the convenience functions make_string_hash_table
262 and make_nocase_string_hash_table. */
265 hash_table_new (int items,
266 unsigned long (*hash_function) (const void *),
267 int (*test_function) (const void *, const void *))
270 struct hash_table *ht = xnew (struct hash_table);
272 ht->hash_function = hash_function ? hash_function : hash_pointer;
273 ht->test_function = test_function ? test_function : cmp_pointer;
275 /* If the size of struct hash_table ever becomes a concern, this
276 field can go. (Wget doesn't create many hashes.) */
277 ht->prime_offset = 0;
279 /* Calculate the size that ensures that the table will store at
280 least ITEMS keys without the need to resize. */
281 size = 1 + items / HASH_MAX_FULLNESS;
282 size = prime_size (size, &ht->prime_offset);
284 ht->resize_threshold = size * HASH_MAX_FULLNESS;
285 /*assert (ht->resize_threshold >= items);*/
287 ht->cells = xnew_array (struct cell, ht->size);
289 /* Mark cells as empty. We use 0xff rather than 0 to mark empty
290 keys because it allows us to use NULL/0 as keys. */
291 memset (ht->cells, INVALID_PTR_CHAR, size * sizeof (struct cell));
298 /* Free the data associated with hash table HT. */
301 hash_table_destroy (struct hash_table *ht)
307 /* The heart of most functions in this file -- find the cell whose
308 KEY is equal to key, using linear probing. Returns the cell
309 that matches KEY, or the first empty cell if none matches. */
311 static inline struct cell *
312 find_cell (const struct hash_table *ht, const void *key)
314 struct cell *cells = ht->cells;
316 struct cell *c = cells + HASH_POSITION (key, ht->hash_function, size);
317 testfun_t equals = ht->test_function;
319 FOREACH_OCCUPIED_ADJACENT (c, cells, size)
320 if (equals (key, c->key))
325 /* Get the value that corresponds to the key KEY in the hash table HT.
326 If no value is found, return NULL. Note that NULL is a legal value
327 for value; if you are storing NULLs in your hash table, you can use
328 hash_table_contains to be sure that a (possibly NULL) value exists
329 in the table. Or, you can use hash_table_get_pair instead of this
333 hash_table_get (const struct hash_table *ht, const void *key)
335 struct cell *c = find_cell (ht, key);
336 if (CELL_OCCUPIED (c))
342 /* Like hash_table_get, but writes out the pointers to both key and
343 value. Returns non-zero on success. */
346 hash_table_get_pair (const struct hash_table *ht, const void *lookup_key,
347 void *orig_key, void *value)
349 struct cell *c = find_cell (ht, lookup_key);
350 if (CELL_OCCUPIED (c))
353 *(void **)orig_key = c->key;
355 *(void **)value = c->value;
362 /* Return 1 if HT contains KEY, 0 otherwise. */
365 hash_table_contains (const struct hash_table *ht, const void *key)
367 struct cell *c = find_cell (ht, key);
368 return CELL_OCCUPIED (c);
371 /* Grow hash table HT as necessary, and rehash all the key-value
375 grow_hash_table (struct hash_table *ht)
377 hashfun_t hasher = ht->hash_function;
378 struct cell *old_cells = ht->cells;
379 struct cell *old_end = ht->cells + ht->size;
380 struct cell *c, *cells;
383 newsize = prime_size (ht->size * HASH_RESIZE_FACTOR, &ht->prime_offset);
385 printf ("growing from %d to %d; fullness %.2f%% to %.2f%%\n",
387 100.0 * ht->count / ht->size,
388 100.0 * ht->count / newsize);
392 ht->resize_threshold = newsize * HASH_MAX_FULLNESS;
394 cells = xnew_array (struct cell, newsize);
395 memset (cells, INVALID_PTR_CHAR, newsize * sizeof (struct cell));
398 for (c = old_cells; c < old_end; c++)
399 if (CELL_OCCUPIED (c))
402 /* We don't need to test for uniqueness of keys because they
403 come from the hash table and are therefore known to be
405 new_c = cells + HASH_POSITION (c->key, hasher, newsize);
406 FOREACH_OCCUPIED_ADJACENT (new_c, cells, newsize)
414 /* Put VALUE in the hash table HT under the key KEY. This regrows the
415 table if necessary. */
418 hash_table_put (struct hash_table *ht, const void *key, void *value)
420 struct cell *c = find_cell (ht, key);
421 if (CELL_OCCUPIED (c))
423 /* update existing item */
424 c->key = (void *)key; /* const? */
429 /* If adding the item would make the table exceed max. fullness,
430 grow the table first. */
431 if (ht->count >= ht->resize_threshold)
433 grow_hash_table (ht);
434 c = find_cell (ht, key);
439 c->key = (void *)key; /* const? */
443 /* Remove KEY->value mapping from HT. Return 0 if there was no such
444 entry; return 1 if an entry was removed. */
447 hash_table_remove (struct hash_table *ht, const void *key)
449 struct cell *c = find_cell (ht, key);
450 if (!CELL_OCCUPIED (c))
455 struct cell *cells = ht->cells;
456 hashfun_t hasher = ht->hash_function;
461 /* Rehash all the entries following C. The alternative
462 approach is to mark the entry as deleted, i.e. create a
463 "tombstone". That speeds up removal, but leaves a lot of
464 garbage and slows down hash_table_get and hash_table_put. */
466 c = NEXT_CELL (c, cells, size);
467 FOREACH_OCCUPIED_ADJACENT (c, cells, size)
469 const void *key2 = c->key;
472 /* Find the new location for the key. */
473 c_new = cells + HASH_POSITION (key2, hasher, size);
474 FOREACH_OCCUPIED_ADJACENT (c_new, cells, size)
475 if (key2 == c_new->key)
476 /* The cell C (key2) is already where we want it (in
477 C_NEW's "chain" of keys.) */
490 /* Clear HT of all entries. After calling this function, the count
491 and the fullness of the hash table will be zero. The size will
495 hash_table_clear (struct hash_table *ht)
497 memset (ht->cells, INVALID_PTR_CHAR, ht->size * sizeof (struct cell));
501 /* Call FN for each entry in HT. FN is called with three arguments:
502 the key, the value, and ARG. When FN returns a non-zero value, the
505 It is undefined what happens if you add or remove entries in the
506 hash table while hash_table_for_each is running. The exception is
507 the entry you're currently mapping over; you may call
508 hash_table_put or hash_table_remove on that entry's key. That is
509 also the reason why this function cannot be implemented in terms of
510 hash_table_iterate. */
513 hash_table_for_each (struct hash_table *ht,
514 int (*fn) (void *, void *, void *), void *arg)
516 struct cell *c = ht->cells;
517 struct cell *end = ht->cells + ht->size;
520 if (CELL_OCCUPIED (c))
525 if (fn (key, c->value, arg))
527 /* hash_table_remove might have moved the adjacent cells. */
528 if (c->key != key && CELL_OCCUPIED (c))
533 /* Initiate iteration over HT. Entries are obtained with
534 hash_table_iter_next, a typical iteration loop looking like this:
536 hash_table_iterator iter;
537 for (hash_table_iterate (ht, &iter); hash_table_iter_next (&iter); )
538 ... do something with iter.key and iter.value ...
540 The iterator does not need to be deallocated after use. The hash
541 table must not be modified while being iterated over. */
544 hash_table_iterate (struct hash_table *ht, hash_table_iterator *iter)
546 iter->pos = ht->cells;
547 iter->end = ht->cells + ht->size;
550 /* Get the next hash table entry. ITER is an iterator object
551 initialized using hash_table_iterate. While there are more
552 entries, the key and value pointers are stored to ITER->key and
553 ITER->value respectively and 1 is returned. When there are no more
554 entries, 0 is returned.
556 If the hash table is modified between calls to this function, the
557 result is undefined. */
560 hash_table_iter_next (hash_table_iterator *iter)
562 struct cell *c = iter->pos;
563 struct cell *end = iter->end;
565 if (CELL_OCCUPIED (c))
568 iter->value = c->value;
575 /* Return the number of elements in the hash table. This is not the
576 same as the physical size of the hash table, which is always
577 greater than the number of elements. */
580 hash_table_count (const struct hash_table *ht)
585 /* Functions from this point onward are meant for convenience and
586 don't strictly belong to this file. However, this is as good a
587 place for them as any. */
589 /* Guidelines for creating custom hash and test functions:
591 - The test function returns non-zero for keys that are considered
592 "equal", zero otherwise.
594 - The hash function returns a number that represents the
595 "distinctness" of the object. In more precise terms, it means
596 that for any two objects that test "equal" under the test
597 function, the hash function MUST produce the same result.
599 This does not mean that all different objects must produce
600 different values (that would be "perfect" hashing), only that
601 non-distinct objects must produce the same values! For instance,
602 a hash function that returns 0 for any given object is a
603 perfectly valid (albeit extremely bad) hash function. A hash
604 function that hashes a string by adding up all its characters is
605 another example of a valid (but still quite bad) hash function.
607 It is not hard to make hash and test functions agree about
608 equality. For example, if the test function compares strings
609 case-insensitively, the hash function can lower-case the
610 characters when calculating the hash value. That ensures that
611 two strings differing only in case will hash the same.
613 - To prevent performance degradation, choose a hash function with
614 as good "spreading" as possible. A good hash function will use
615 all the bits of the input when calculating the hash, and will
616 react to even small changes in input with a completely different
617 output. But don't make the hash function itself overly slow,
618 because you'll be incurring a non-negligible overhead to all hash
622 * Support for hash tables whose keys are strings.
626 /* Base 31 hash function. Taken from Gnome's glib, modified to use
629 We used to use the popular hash function from the Dragon Book, but
630 this one seems to perform much better, both by being faster and by
631 generating less collisions. */
634 hash_string (const void *key)
640 for (p += 1; *p != '\0'; p++)
641 h = (h << 5) - h + *p;
646 /* Frontend for strcmp usable for hash tables. */
649 cmp_string (const void *s1, const void *s2)
651 return !strcmp ((const char *)s1, (const char *)s2);
654 /* Return a hash table of preallocated to store at least ITEMS items
655 suitable to use strings as keys. */
658 make_string_hash_table (int items)
660 return hash_table_new (items, hash_string, cmp_string);
664 * Support for hash tables whose keys are strings, but which are
665 * compared case-insensitively.
669 /* Like hash_string, but produce the same hash regardless of the case. */
672 hash_string_nocase (const void *key)
675 unsigned int h = TOLOWER (*p);
678 for (p += 1; *p != '\0'; p++)
679 h = (h << 5) - h + TOLOWER (*p);
684 /* Like string_cmp, but doing case-insensitive compareison. */
687 string_cmp_nocase (const void *s1, const void *s2)
689 return !strcasecmp ((const char *)s1, (const char *)s2);
692 /* Like make_string_hash_table, but uses string_hash_nocase and
693 string_cmp_nocase. */
696 make_nocase_string_hash_table (int items)
698 return hash_table_new (items, hash_string_nocase, string_cmp_nocase);
701 /* Hashing of numeric values, such as pointers and integers.
703 This implementation is the Robert Jenkins' 32 bit Mix Function,
704 with a simple adaptation for 64-bit values. According to Jenkins
705 it should offer excellent spreading of values. Unlike the popular
706 Knuth's multiplication hash, this function doesn't need to know the
707 hash table size to work. */
710 hash_pointer (const void *ptr)
712 unsigned long key = (unsigned long) ptr;
735 cmp_pointer (const void *ptr1, const void *ptr2)
746 print_hash (struct hash_table *sht)
748 hash_table_iterator iter;
751 for (hash_table_iterate (sht, &iter); hash_table_iter_next (&iter);
753 printf ("%s: %s\n", iter.key, iter.value);
754 assert (count == sht->count);
760 struct hash_table *ht = make_string_hash_table (0);
762 while ((fgets (line, sizeof (line), stdin)))
764 int len = strlen (line);
768 if (!hash_table_contains (ht, line))
769 hash_table_put (ht, strdup (line), "here I am!");
774 if (hash_table_get_pair (ht, line, &line_copy, NULL))
776 hash_table_remove (ht, line);
786 printf ("%d %d\n", ht->count, ht->size);