diff options
| -rw-r--r-- | debian/patches/0011-XXX-libports-cuckoo-hashing.patch | 75 |
1 files changed, 42 insertions, 33 deletions
diff --git a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch index 8095584f..74d91a91 100644 --- a/debian/patches/0011-XXX-libports-cuckoo-hashing.patch +++ b/debian/patches/0011-XXX-libports-cuckoo-hashing.patch @@ -1,15 +1,15 @@ -From e444428e279c8b1b47c5c19abc093d6fd59c106d Mon Sep 17 00:00:00 2001 +From 86c0c31e918babde0c3e75d62a1ad1b59c494995 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/ihash.c | 200 ++++++++++++++++++++++++++++++------------------------- - libihash/ihash.h | 38 +++-------- - 2 files changed, 119 insertions(+), 119 deletions(-) + libihash/ihash.c | 208 +++++++++++++++++++++++++++++++------------------------ + libihash/ihash.h | 38 +++------- + 2 files changed, 128 insertions(+), 118 deletions(-) diff --git a/libihash/ihash.c b/libihash/ihash.c -index e74a2c5..4a0ff07 100644 +index e74a2c5..cb7d765 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -69,6 +69,18 @@ index_valid (hurd_ihash_t ht, unsigned int idx, hurd_ihash_key_t key) @@ -78,20 +78,28 @@ index e74a2c5..4a0ff07 100644 } -@@ -184,27 +181,47 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, +@@ -184,27 +181,57 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, ht->cleanup = cleanup; ht->cleanup_data = cleanup_data; } + +/* XXX */ ++static inline void ++set_item (hurd_ihash_t ht, unsigned int idx, struct _hurd_ihash_item *item) ++{ ++ ht->items[idx] = *item; ++ if (__builtin_expect (ht->locp_offset != HURD_IHASH_NO_LOCP, 1)) ++ *((hurd_ihash_locp_t *) (((char *) item->value) + ht->locp_offset)) ++ = &ht->items[idx].value; ++} + ++/* XXX */ +static inline int +add_item (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value) +{ + struct _hurd_ihash_item item, old; + unsigned int idx0, idx1; -+ item = (struct _hurd_ihash_item){ .key = key, .value = value}; - -/* Set the maximum load factor in percent to MAX_LOAD, which should be - between 1 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT. - New elements are only added to the hash table while the number of @@ -100,6 +108,15 @@ index e74a2c5..4a0ff07 100644 - expanded and reorganized. A MAX_LOAD of 100 will always fill the - whole table before enlarging it, but note that this will increase - the cost of operations significantly when the table is almost full. ++ item = (struct _hurd_ihash_item){ .key = key, .value = value}; + +- If the value is set to a smaller value than the current load +- factor, the next reorganization will happen when a new item is +- added to the hash table. */ +-void +-hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) +-{ +- ht->max_load = max_load; + /* xxx max_loop = round_up (3 * log_{1+epsilon}(n)) */ + unsigned int i; + for (i = 0; i < 3 * ht->size; i++) @@ -107,33 +124,26 @@ index e74a2c5..4a0ff07 100644 + idx0 = hash0 (ht, item.key); + if (index_empty (ht, idx0)) + { -+ ht->items[idx0] = item; ++ set_item (ht, idx0, &item); + return 1; + } + + old = ht->items[idx0]; -+ ht->items[idx0] = item; ++ set_item (ht, idx0, &item); + item = old; + + idx1 = hash1 (ht, item.key); + if (index_empty (ht, idx1)) + { -+ ht->items[idx1] = item; ++ set_item (ht, idx1, &item); + return 1; + } + -+ old = ht->items[idx0]; -+ ht->items[idx0] = item; ++ old = ht->items[idx1]; ++ set_item (ht, idx1, &item); + item = old; + } - -- If the value is set to a smaller value than the current load -- factor, the next reorganization will happen when a new item is -- added to the hash table. */ --void --hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) --{ -- ht->max_load = max_load; ++ + return 0; } @@ -142,7 +152,7 @@ index e74a2c5..4a0ff07 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. -@@ -215,53 +232,55 @@ hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load) +@@ -215,53 +242,55 @@ 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) { @@ -169,7 +179,12 @@ index e74a2c5..4a0ff07 100644 - } - while (up_idx != 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}; + - /* Remove the old entry for this key if necessary. */ + unsigned int idx = find_index (ht, key); if (index_valid (ht, idx, key)) @@ -192,7 +207,7 @@ index e74a2c5..4a0ff07 100644 - + /* Update the entry. */ + locp_remove (ht, &ht->items[idx].value); -+ ht->items[idx].value = value; ++ set_item (ht, idx, &item); return 1; } @@ -203,12 +218,6 @@ index e74a2c5..4a0ff07 100644 + + /* We failed. */ + -+ /* 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}; -+ + retry: + /* Pick different hash functions. */ + ht->salt0 = hash_int32 (ht->salt0, 32); @@ -240,7 +249,7 @@ index e74a2c5..4a0ff07 100644 } -@@ -278,8 +297,8 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +@@ -278,8 +307,8 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) if (ht->size) { @@ -251,7 +260,7 @@ index e74a2c5..4a0ff07 100644 if (add_one (ht, key, item)) return 0; } -@@ -289,10 +308,10 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +@@ -289,10 +318,10 @@ 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 @@ -264,7 +273,7 @@ index e74a2c5..4a0ff07 100644 if (ht->items == NULL) { -@@ -301,12 +320,11 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) +@@ -301,12 +330,11 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) } /* We have to rehash the old entries. */ |