diff options
| -rw-r--r-- | debian/patches/0011-XXX-libports-cuckoo-hashing.patch | 64 |
1 files changed, 32 insertions, 32 deletions
diff --git a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch index 28c1f53e..36d1701f 100644 --- a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch +++ b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch @@ -1,4 +1,4 @@ -From b02b304f483a1e0fe489f1c88cffba0a22d2f27b Mon Sep 17 00:00:00 2001 +From bf346ba2f07adc70baebeb6f63f91170ece91b3d Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Sat, 10 May 2014 10:05:07 +0200 Subject: [PATCH 11/11] XXX libports: cuckoo hashing @@ -21,7 +21,7 @@ index 09bb136..ca528f7 100644 include ../Makeconf diff --git a/libihash/ihash.c b/libihash/ihash.c -index e74a2c5..38b809b 100644 +index e74a2c5..7f58bfe 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -26,6 +26,7 @@ @@ -60,13 +60,13 @@ index e74a2c5..38b809b 100644 - unsigned int mask = ht->size - 1; - - idx = hash_int32 (key, 32) & mask; +- +- if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key) +- return idx; + unsigned int idx0, idx1; + idx0 = hash0 (ht, key); + idx1 = hash1 (ht, key); -- if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key) -- return idx; -- - up_idx = idx; - - do @@ -149,7 +149,7 @@ index e74a2c5..38b809b 100644 + add this item to HT. */ +static inline int +add_item (hurd_ihash_t ht, struct _hurd_ihash_item *item, -+ unsigned int max_loop) ++ unsigned int max_loop) +{ + unsigned int i; + struct _hurd_ihash_item old; @@ -159,10 +159,10 @@ index e74a2c5..38b809b 100644 + { + idx0 = hash0 (ht, item->key); + if (index_empty (ht, idx0)) -+ { -+ set_item (ht, idx0, item); -+ return 1; -+ } ++ { ++ set_item (ht, idx0, item); ++ return 1; ++ } + + old = ht->items[idx0]; + set_item (ht, idx0, item); @@ -170,10 +170,10 @@ index e74a2c5..38b809b 100644 + + idx1 = hash1 (ht, item->key); + if (index_empty (ht, idx1)) -+ { -+ set_item (ht, idx1, item); -+ return 1; -+ } ++ { ++ set_item (ht, idx1, item); ++ return 1; ++ } + + old = ht->items[idx1]; + set_item (ht, idx1, item); @@ -194,15 +194,15 @@ index e74a2c5..38b809b 100644 - unsigned int idx; - unsigned int first_free; - unsigned int mask = ht->size - 1; -- -- idx = hash_int32 (key, 32) & mask; -- first_free = idx; + /* The item that needs to be added. Also, if we remove an item from + the table, we store it here. If we fail to insert it again, we + start over. */ + struct _hurd_ihash_item item = + (struct _hurd_ihash_item){ .key = key, .value = value}; +- idx = hash_int32 (key, 32) & mask; +- first_free = idx; +- - if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key) - { - unsigned int up_idx = idx; @@ -263,8 +263,8 @@ index e74a2c5..38b809b 100644 + ht->salt0 = hash_int32 (ht->salt0, 32); + ht->salt1 = hash_int32 (ht->salt1, 32); + -+ error (0, 0, "XXXXXXXXXXXXXXXXx We failed! salts %x %x", -+ ht->salt0, ht->salt1); ++ error (0, 0, "Rehashing table %p with salts %x %x.", ++ ht, ht->salt0, ht->salt1); + + /* Try to insert the new or stashed item. */ + added = add_item (ht, &item, size); @@ -274,17 +274,17 @@ index e74a2c5..38b809b 100644 + /* Rehash the table. */ + for (idx = 0; idx < size; idx++) + if (! index_empty (ht, idx) -+ /* For each non-empty slot, check if the item there is not at -+ the correct (new) index. */ -+ && (idx < (size >> 1) /* select the appropriate function */ -+ ? hash0 (ht, ht->items[idx].key) != idx -+ : hash1 (ht, ht->items[idx].key) != idx)) ++ /* For each non-empty slot, check if the item there is not at ++ the correct (new) index. */ ++ && (idx < (size >> 1) /* select the appropriate function */ ++ ? hash0 (ht, ht->items[idx].key) != idx ++ : hash1 (ht, ht->items[idx].key) != idx)) + { -+ item = ht->items[idx]; -+ ht->items[idx].value = _HURD_IHASH_EMPTY; -+ added = add_item (ht, &item, size); -+ if (! added) -+ goto retry; ++ item = ht->items[idx]; ++ ht->items[idx].value = _HURD_IHASH_EMPTY; ++ added = add_item (ht, &item, size); ++ if (! added) ++ goto retry; + } + + return 1; @@ -342,7 +342,7 @@ index e74a2c5..38b809b 100644 /* Finally add the new element! */ was_added = add_one (ht, key, item); diff --git a/libihash/ihash.h b/libihash/ihash.h -index 057babc..5327442 100644 +index 057babc..4077234 100644 --- a/libihash/ihash.h +++ b/libihash/ihash.h @@ -73,7 +73,7 @@ struct hurd_ihash @@ -374,13 +374,13 @@ index 057babc..5327442 100644 - be a power of two. */ -#define HURD_IHASH_MIN_SIZE 32 +/* Log2 of the size of the initial allocation in number of items. */ -+#define HURD_IHASH_MIN_SIZE 5 ++#define HURD_IHASH_MIN_SIZE 6 -/* The default value for the maximum load factor in percent. */ -#define HURD_IHASH_MAX_LOAD_DEFAULT 75 +/* The default value for the maximum load factor in percent. Must be + below 50. */ -+#define HURD_IHASH_MAX_LOAD_DEFAULT 40 ++#define HURD_IHASH_MAX_LOAD_DEFAULT 42 /* The LOCP_OFFS to use if no location pointer is available. */ #define HURD_IHASH_NO_LOCP INTPTR_MIN |