[hurd] 30/31: libihash: rehash if effective load exceeds the threshold

[Samuel Thibault]

This is an automated email from the git hooks/post-receive script.

sthibault pushed a commit to branch upstream
in repository hurd.

commit 9d29cfbf9fd8a0e26a3410194d1a060114973ad2
Author: Justus Winter <address@hidden>
Date:   Thu Apr 28 21:12:58 2016 +0200

    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(-)

diff --git a/libihash/ihash.c b/libihash/ihash.c
index 800f492..ae1cf12 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;
 

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-hurd/hurd.git