From 9d29cfbf9fd8a0e26a3410194d1a060114973ad2 Mon Sep 17 00:00:00 2001 From: Justus Winter Date: Thu, 28 Apr 2016 21:12:58 +0200 Subject: libihash: rehash if effective load exceeds the threshold Previously, if a hash table was not growing anymore but entries were regularly replaced, the tombstones would accumulate slowing down lookups and insertions. A possible solution is to rehash the table if the effective load exceeds the configured threshold. The effective load also takes tombstones into account. * libihash/ihash.c (hurd_ihash_locp_add): Use the effective load. (hurd_ihash_add): Likewise. Use the load to decide whether we want to enlarge the table, otherwise we merely rehash. --- libihash/ihash.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'libihash') diff --git a/libihash/ihash.c b/libihash/ihash.c index 800f4923..ae1cf12a 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -289,7 +289,7 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t locp, || item == NULL || item->value == _HURD_IHASH_DELETED || ! compare (ht, item->key, key) - || hurd_ihash_get_load (ht) > ht->max_load) + || hurd_ihash_get_effective_load (ht) > ht->max_load) return hurd_ihash_add (ht, key, value); if (item->value == _HURD_IHASH_EMPTY) @@ -331,17 +331,19 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) if (ht->size) { /* Only fill the hash table up to its maximum load factor. */ - if (hurd_ihash_get_load (ht) <= ht->max_load) + if (hurd_ihash_get_effective_load (ht) <= ht->max_load) add_one: if (add_one (ht, key, item)) return 0; } - /* The hash table is too small, and we have to increase it. */ + /* If the load exceeds the configured maximal load, then the hash + table is too small, and we have to increase it. Otherwise we + merely rehash the table to get rid of the tombstones. */ ht->nr_items = 0; if (ht->size == 0) ht->size = HURD_IHASH_MIN_SIZE; - else + else if (hurd_ihash_get_load (&old_ht) > ht->max_load) ht->size <<= 1; ht->nr_free = ht->size; -- cgit v1.2.3