diff options
| -rw-r--r-- | debian/patches/0011-XXX-libports-cuckoo-hashing.patch | 187 |
1 files changed, 106 insertions, 81 deletions
diff --git a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch index 36d1701f..dd11c0e7 100644 --- a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch +++ b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch @@ -1,13 +1,13 @@ -From bf346ba2f07adc70baebeb6f63f91170ece91b3d Mon Sep 17 00:00:00 2001 +From a1f9b63d2068df17f6a4bcc221c808b49dccaee0 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 --- libihash/Makefile | 1 + - libihash/ihash.c | 228 +++++++++++++++++++++++++++++++++++------------------- - libihash/ihash.h | 37 +++++---- - 3 files changed, 173 insertions(+), 93 deletions(-) + libihash/ihash.c | 248 +++++++++++++++++++++++++++++++++++------------------- + libihash/ihash.h | 37 +++++--- + 3 files changed, 186 insertions(+), 100 deletions(-) diff --git a/libihash/Makefile b/libihash/Makefile index 09bb136..ca528f7 100644 @@ -21,7 +21,7 @@ index 09bb136..ca528f7 100644 include ../Makeconf diff --git a/libihash/ihash.c b/libihash/ihash.c -index e74a2c5..7f58bfe 100644 +index e74a2c5..6068894 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -26,6 +26,7 @@ @@ -60,13 +60,13 @@ index e74a2c5..7f58bfe 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 @@ -118,7 +118,7 @@ index e74a2c5..7f58bfe 100644 If the value is set to a smaller value than the current load factor, the next reorganization will happen when a new item is -@@ -201,10 +202,67 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, +@@ -201,86 +202,157 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, void hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) { @@ -128,6 +128,9 @@ index e74a2c5..7f58bfe 100644 } +-/* Helper function for hurd_ihash_add. Return 1 if the item was +- added, and 0 if it could not be added because no empty slot was +- found. The arguments are identical to hurd_ihash_add. +/* Fill the IDXth slot of HT with ITEM. Updates the location pointer + if necessary. */ +static inline void @@ -142,73 +145,38 @@ index e74a2c5..7f58bfe 100644 +/* Insert ITEM into HT at its preferred location. If this location is + currently occupied, move that item to it's alternate location. + This process is repeated until no item has to be moved. -+ + +- We are using open address hashing. As the hash function we use the +- division method with quadratic probe. This is guaranteed to try +- all slots in the hash table if the prime number is 3 mod 4. */ + If this succeeds within MAX_LOOP steps, return 1. Otherwise return + 0. On failure, ITEM contains an item (not the same as the one + supplied by the caller). It is the responsibility of the callee to + add this item to HT. */ -+static inline int + static inline int +-add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) +add_item (hurd_ihash_t ht, struct _hurd_ihash_item *item, + unsigned int max_loop) -+{ -+ unsigned int i; -+ struct _hurd_ihash_item old; -+ unsigned int idx0, idx1; -+ -+ for (i = 0; i < max_loop; i++) -+ { -+ idx0 = hash0 (ht, item->key); -+ if (index_empty (ht, idx0)) -+ { -+ set_item (ht, idx0, item); -+ return 1; -+ } -+ -+ old = ht->items[idx0]; -+ set_item (ht, idx0, item); -+ *item = old; -+ -+ idx1 = hash1 (ht, item->key); -+ if (index_empty (ht, idx1)) -+ { -+ set_item (ht, idx1, item); -+ return 1; -+ } -+ -+ old = ht->items[idx1]; -+ set_item (ht, idx1, item); -+ *item = old; -+ } -+ -+ return 0; -+} -+ -+ - /* Helper function for hurd_ihash_add. Return 1 if the item was - added, and 0 if it could not be added because no empty slot was - found. The arguments are identical to hurd_ihash_add. -@@ -215,53 +273,62 @@ hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) - static inline int - add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) { - unsigned int idx; - unsigned int first_free; - unsigned int mask = ht->size - 1; -+ /* 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; -- ++ unsigned int i; ++ struct _hurd_ihash_item old; ++ unsigned int idx0, idx1; + - if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key) -- { ++ for (i = 0; i < max_loop; i++) + { - unsigned int up_idx = idx; - - do -- { ++ idx0 = hash0 (ht, item->key); ++ if (index_empty (ht, idx0)) + { - up_idx = (up_idx + 1) & mask; - if (ht->items[up_idx].value == _HURD_IHASH_EMPTY - || ht->items[up_idx].key == key) @@ -216,33 +184,62 @@ index e74a2c5..7f58bfe 100644 - idx = up_idx; - break; - } -- } ++ set_item (ht, idx0, item); ++ return 1; + } - while (up_idx != idx); - } -- + - /* Remove the old entry for this key if necessary. */ -+ unsigned int idx = find_index (ht, key); - if (index_valid (ht, idx, key)) +- if (index_valid (ht, idx, key)) - locp_remove (ht, &ht->items[idx].value); -- ++ old = ht->items[idx0]; ++ set_item (ht, idx0, item); ++ *item = old; + - /* If we have not found an empty slot, maybe the last one we - looked at was empty (or just got deleted). */ - if (!index_empty (ht, first_free)) - first_free = idx; - - if (index_empty (ht, first_free)) - { +- { - ht->nr_items++; - ht->items[first_free].value = value; - ht->items[first_free].key = key; -- ++ idx1 = hash1 (ht, item->key); ++ if (index_empty (ht, idx1)) ++ { ++ set_item (ht, idx1, item); ++ return 1; ++ } ++ ++ old = ht->items[idx1]; ++ set_item (ht, idx1, item); ++ *item = old; ++ } ++ ++ return 0; ++} + - if (ht->locp_offset != HURD_IHASH_NO_LOCP) - *((hurd_ihash_locp_t *) (((char *) value) + ht->locp_offset)) - = &ht->items[first_free].value; -- + ++/* Helper function for hurd_ihash_add. Return 1 if the item was ++ added, and 0 if it could not be added because no empty slot was ++ found. On failure, ITEM contains an item (not the same as the one ++ supplied by the caller). It is the responsibility of the callee to ++ add this item to HT. */ ++static inline int ++add_one (hurd_ihash_t ht, struct _hurd_ihash_item *item) ++{ ++ unsigned int idx = find_index (ht, item->key); ++ if (index_valid (ht, idx, item->key)) ++ { + /* Update the entry. */ + locp_remove (ht, &ht->items[idx].value); -+ set_item (ht, idx, &item); ++ set_item (ht, idx, item); + ht->nr_items += 1; return 1; } @@ -251,14 +248,22 @@ index e74a2c5..7f58bfe 100644 + /* No matter what, we will insert this item. */ + ht->nr_items += 1; + -+ int added = add_item (ht, &item, ht->max_loop); ++ int added = add_item (ht, item, ht->max_loop); + if (added) + return 1; + + /* We failed. */ + size_t size = 1U << ht->size; ++ int tries = 3; + + retry: ++ if (tries == 0) ++ /* Give up. The callee will resize the table and incorporate ++ *item. */ ++ return 0; ++ ++ tries -= 1; ++ + /* Pick different hash functions. */ + ht->salt0 = hash_int32 (ht->salt0, 32); + ht->salt1 = hash_int32 (ht->salt1, 32); @@ -267,7 +272,7 @@ index e74a2c5..7f58bfe 100644 + ht, ht->salt0, ht->salt1); + + /* Try to insert the new or stashed item. */ -+ added = add_item (ht, &item, size); ++ added = add_item (ht, item, size); + if (! added) + goto retry; + @@ -280,9 +285,9 @@ index e74a2c5..7f58bfe 100644 + ? hash0 (ht, ht->items[idx].key) != idx + : hash1 (ht, ht->items[idx].key) != idx)) + { -+ item = ht->items[idx]; ++ *item = ht->items[idx]; + ht->items[idx].value = _HURD_IHASH_EMPTY; -+ added = add_item (ht, &item, size); ++ added = add_item (ht, item, size); + if (! added) + goto retry; + } @@ -290,22 +295,38 @@ index e74a2c5..7f58bfe 100644 + return 1; } - -@@ -274,12 +341,11 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +- +-/* Add ITEM to the hash table HT under the key KEY. If there already ++ ++/* Add VALUE to the hash table HT under the key KEY. If there already + is an item under this key, call the cleanup function (if any) for + it before overriding the value. If a memory allocation error + occurs, ENOMEM is returned, otherwise 0. */ + error_t +-hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) ++hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) { struct hurd_ihash old_ht = *ht; int was_added; - unsigned int i; ++ ++ /* 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}; if (ht->size) { /* Only fill the hash table up to its maximum load factor. */ - if (ht->nr_items * 100 / ht->size <= ht->max_load) +- if (add_one (ht, key, item)) + if ((ht->nr_items * 100) >> ht->size <= ht->max_load) - if (add_one (ht, key, item)) ++ if (add_one (ht, &item)) return 0; } -@@ -289,10 +355,15 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) + +@@ -289,10 +361,15 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) if (ht->size == 0) ht->size = HURD_IHASH_MIN_SIZE; else @@ -323,7 +344,7 @@ index e74a2c5..7f58bfe 100644 if (ht->items == NULL) { -@@ -301,12 +372,11 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +@@ -301,15 +378,14 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) } /* We have to rehash the old entries. */ @@ -333,14 +354,18 @@ index e74a2c5..7f58bfe 100644 - was_added = add_one (ht, old_ht.items[i].key, old_ht.items[i].value); - assert (was_added); - } -+ HURD_IHASH_ITERATE_ITEMS (&old_ht, item) ++ HURD_IHASH_ITERATE_ITEMS (&old_ht, i) + { -+ was_added = add_one (ht, item->key, item->value); ++ was_added = add_one (ht, i); + assert (was_added); + } /* Finally add the new element! */ - was_added = add_one (ht, key, item); +- was_added = add_one (ht, key, item); ++ was_added = add_one (ht, &item); + assert (was_added); + + if (old_ht.size > 0) diff --git a/libihash/ihash.h b/libihash/ihash.h index 057babc..4077234 100644 --- a/libihash/ihash.h |