wget/src/hash.c

72    retrieved by providing the key.  Fast lookup tables are typically
78      hash_table_put       -- establishes or updates key->value mapping.
79      hash_table_get       -- retrieves value of key.
80      hash_table_get_pair  -- get key/value pair for key.
81      hash_table_contains  -- test whether the table contains key.
82      hash_table_remove    -- remove key->value mapping for given key.
100    "hash" and "test".  The hash function transforms the key into an
116    The above means that all the cells (each cell containing a key and
118    of each cell is determined by the hash value of its key and the
119    size of the table: location := hash(key) % size.  If two different
149   void *key;
177    or pointers, the only key that cannot be used is the integer value
188 #define CELL_OCCUPIED(c) ((c)->key != INVALID_PTR)
191 #define CLEAR_CELL(c) ((c)->key = INVALID_PTR)
204 #define HASH_POSITION(key, hashfun, size) ((hashfun) (key) % size)
265    assumed, i.e. pointer values are used for key comparison.  (Common
316    KEY is equal to key, using linear probing.  Returns the cell
320 find_cell (const struct hash_table *ht, const void *key)
324   struct cell *c = cells + HASH_POSITION (key, ht->hash_function, size);
328     if (equals (key, c->key))
333 /* Get the value that corresponds to the key KEY in the hash table HT.
341 hash_table_get (const struct hash_table *ht, const void *key)
343   struct cell *c = find_cell (ht, key);
350 /* Like hash_table_get, but writes out the pointers to both key and
361         *(void **)orig_key = c->key;
373 hash_table_contains (const struct hash_table *ht, const void *key)
375   struct cell *c = find_cell (ht, key);
379 /* Grow hash table HT as necessary, and rehash all the key-value
413         new_c = cells + HASH_POSITION (c->key, hasher, newsize);
422 /* Put VALUE in the hash table HT under the key KEY.  This regrows the
426 hash_table_put (struct hash_table *ht, const void *key, void *value)
428   struct cell *c = find_cell (ht, key);
432       c->key   = (void *)key; /* const? */
442       c = find_cell (ht, key);
447   c->key   = (void *)key;       /* const? */
455 hash_table_remove (struct hash_table *ht, const void *key)
457   struct cell *c = find_cell (ht, key);
477           const void *key2 = c->key;
480           /* Find the new location for the key. */
483             if (key2 == c_new->key)
510    the key, the value, and ARG.  When FN returns a non-zero value, the
516    hash_table_put or hash_table_remove on that entry's key.  That is
530         void *key;
532         key = c->key;
533         if (fn (key, c->value, arg))
536         if (c->key != key && CELL_OCCUPIED (c))
546          ... do something with iter.key and iter.value ...
560    entries, the key and value pointers are stored to ITER->key and
575         iter->key = c->key;
643 hash_string (const void *key)
645   const char *p = key;
681 hash_string_nocase (const void *key)
683   const char *p = key;
721   uintptr_t key = (uintptr_t) ptr;
722   key += (key << 12);
723   key ^= (key >> 22);
724   key += (key << 4);
725   key ^= (key >> 9);
726   key += (key << 10);
727   key ^= (key >> 2);
728   key += (key << 7);
729   key ^= (key >> 12);
731   key += (key << 44);
732   key ^= (key >> 54);
733   key += (key << 36);
734   key ^= (key >> 41);
735   key += (key << 42);
736   key ^= (key >> 34);
737   key += (key << 39);
738   key ^= (key >> 44);
740   return (unsigned long) key;
763     printf ("%s: %s\n", iter.key, iter.value);