[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[hurd] 36/61: libihash: use an integer hash function on the keys
From: |
Samuel Thibault |
Subject: |
[hurd] 36/61: libihash: use an integer hash function on the keys |
Date: |
Tue, 27 May 2014 08:32:12 +0000 |
This is an automated email from the git hooks/post-receive script.
sthibault pushed a commit to branch upstream
in repository hurd.
commit 2d898893815a980f1b821fcec267eb8e7ded678e
Author: Justus Winter <address@hidden>
Date: Thu May 8 15:45:00 2014 +0200
libihash: use an integer hash function on the keys
Use an integer hash function to derive the index from the key. This
should reduce the number of collisions.
* libihash/ihash.c (hash_int32): New function.
(find_index): Use hash_int32 on the key to derive the index.
(add_one): Likewise.
---
libihash/ihash.c | 17 +++++++++++++++--
1 file changed, 15 insertions(+), 2 deletions(-)
diff --git a/libihash/ihash.c b/libihash/ihash.c
index d670fee..71ddc26 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -81,6 +81,19 @@ static const unsigned int ihash_nsizes = (sizeof ihash_sizes
/ sizeof ihash_sizes[0]);
+/* This is the integer finalizer from MurmurHash3. */
+static inline uint32_t
+murmur3_mix32 (uint32_t h, unsigned int bits)
+{
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ return h >> (32 - bits);
+}
+
/* Return 1 if the slot with the index IDX in the hash table HT is
empty, and 0 otherwise. */
static inline int
@@ -111,7 +124,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
unsigned int up_idx;
unsigned int down_idx;
- idx = key % ht->size;
+ idx = murmur3_mix32 (key, 32) % ht->size;
if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
return idx;
@@ -264,7 +277,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key,
hurd_ihash_value_t value)
unsigned int idx;
unsigned int first_free;
- idx = key % ht->size;
+ idx = murmur3_mix32 (key, 32) % ht->size;
first_free = idx;
if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-hurd/hurd.git
- [hurd] 26/61: fatfs: simplify expression, (continued)
- [hurd] 26/61: fatfs: simplify expression, Samuel Thibault, 2014/05/27
- [hurd] 29/61: tmpfs: improve diskfs_node_iterate, Samuel Thibault, 2014/05/27
- [hurd] 07/61: libports: fix notify_port_t receiver lookups, Samuel Thibault, 2014/05/27
- [hurd] 14/61: libpager: fix notify_port_t receiver lookups, Samuel Thibault, 2014/05/27
- [hurd] 34/61: libihash: reduce the default maximum load factor to 75%, Samuel Thibault, 2014/05/27
- [hurd] 17/61: Add TODO about fork() making rpctrace emit an error, Samuel Thibault, 2014/05/27
- [hurd] 33/61: ext2fs: cache the superblock, Samuel Thibault, 2014/05/27
- [hurd] 35/61: libihash: fix type of max_load, Samuel Thibault, 2014/05/27
- [hurd] 27/61: ext2fs: improve diskfs_node_iterate, Samuel Thibault, 2014/05/27
- [hurd] 39/61: trans/fakeroot: remove spurious semicolon, Samuel Thibault, 2014/05/27
- [hurd] 36/61: libihash: use an integer hash function on the keys,
Samuel Thibault <=
- [hurd] 41/61: trans/fakeroot: use C99-style struct initialization, Samuel Thibault, 2014/05/27
- [hurd] 40/61: trans/fakeroot: fix comparison between signed and unsigned, Samuel Thibault, 2014/05/27
- [hurd] 32/61: fatfs: use two distinct pager buckets for the disk and file pager, Samuel Thibault, 2014/05/27
- [hurd] 24/61: ext2fs: simplify expression, Samuel Thibault, 2014/05/27
- [hurd] 47/61: include: install refcount.h, Samuel Thibault, 2014/05/27
- [hurd] 50/61: exec: add missing includes, Samuel Thibault, 2014/05/27
- [hurd] 23/61: ext2fs: fix type of inum, Samuel Thibault, 2014/05/27
- [hurd] 22/61: exec: abbreviate the task name if necessary, Samuel Thibault, 2014/05/27
- [hurd] 46/61: trans/fakeroot: override fshelp_isowner, Samuel Thibault, 2014/05/27
- [hurd] 37/61: libihash: use linear probing and fast modulo operation, Samuel Thibault, 2014/05/27