diff options
| author | Eric Anholt <eric@anholt.net> | 2009-11-25 06:59:16 -0800 |
|---|---|---|
| committer | Eric Anholt <eric@anholt.net> | 2009-11-25 07:27:56 -0800 |
| commit | 376148c6daccb7ddd6e48b0b70d8ec65c4775502 (patch) | |
| tree | 4451793b3e75b9145739e2ec356106128bf3f9cf | |
| parent | 5997320dcae4d48c98f403b158b7f7be2d3022fd (diff) | |
Fix the double hashing to be double hashing instead of linear probing.
| -rw-r--r-- | hash_table.c | 15 |
1 files changed, 13 insertions, 2 deletions
diff --git a/hash_table.c b/hash_table.c index af17336..8f763d7 100644 --- a/hash_table.c +++ b/hash_table.c @@ -169,6 +169,8 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) hash_address = hash % ht->size; do { + uint32_t double_hash; + struct hash_entry *entry = ht->table + hash_address; if (entry_is_free(entry)) { @@ -179,7 +181,11 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) } } - hash_address = (hash_address + ht->rehash) % ht->size; + double_hash = hash % ht->rehash; + if (double_hash == 0) + double_hash = 1; + + hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != hash % ht->size); return NULL; @@ -241,6 +247,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, hash_address = hash % ht->size; do { struct hash_entry *entry = ht->table + hash_address; + uint32_t double_hash; if (!entry_is_present(entry)) { if (entry_is_deleted(entry)) @@ -252,7 +259,11 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, return entry; } - hash_address = (hash_address + ht->rehash) % ht->size; + double_hash = hash % ht->rehash; + if (double_hash == 0) + double_hash = 1; + + hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != hash % ht->size); /* We could hit here if a required resize failed. An unchecked-malloc |