[hurd] 29/31: libihash: keep track of free slots

[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 39031d37fd82c119b4b16af256a8ceae5d8c6ea8
Author: Justus Winter <address@hidden>
Date:   Thu Apr 28 20:11:27 2016 +0200

    libihash: keep track of free slots
    
    * libihash/ihash.c (hurd_ihash_init): Init new field 'nr_free'.
    (add_one): Decrement counter if a free slot is used.
    (hurd_ihash_locp_add): Likewise.
    (hurd_ihash_add): Reset counter on reallocation.
    * libihash/ihash.h (struct hurd_ihash): New field 'nr_free'.
    (hurd_ihash_get_effective_load): New function.
---
 libihash/ihash.c |  9 +++++++++
 libihash/ihash.h | 11 +++++++++++
 2 files changed, 20 insertions(+)

diff --git a/libihash/ihash.c b/libihash/ihash.c
index 01ba23b..800f492 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -131,6 +131,7 @@ hurd_ihash_init (hurd_ihash_t ht, intptr_t locp_offs)
   ht->cleanup = 0;
   ht->fct_hash = NULL;
   ht->fct_cmp = NULL;
+  ht->nr_free = 0;
 }
 
 
@@ -246,6 +247,11 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, 
hurd_ihash_value_t value)
   if (index_empty (ht, idx))
     {
       ht->nr_items++;
+      if (ht->items[idx].value == _HURD_IHASH_EMPTY)
+        {
+          assert (ht->nr_free > 0);
+          ht->nr_free--;
+        }
       ht->items[idx].value = value;
       ht->items[idx].key = key;
 
@@ -290,6 +296,8 @@ hurd_ihash_locp_add (hurd_ihash_t ht, hurd_ihash_locp_t 
locp,
     {
       item->key = key;
       ht->nr_items += 1;
+      assert (ht->nr_free > 0);
+      ht->nr_free -= 1;
     }
   else
     {
@@ -335,6 +343,7 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, 
hurd_ihash_value_t item)
       ht->size = HURD_IHASH_MIN_SIZE;
   else
       ht->size <<= 1;
+  ht->nr_free = ht->size;
 
   /* calloc() will initialize all values to _HURD_IHASH_EMPTY implicitly.  */
   ht->items = calloc (ht->size, sizeof (struct _hurd_ihash_item));
diff --git a/libihash/ihash.h b/libihash/ihash.h
index 356f647..80679f1 100644
--- a/libihash/ihash.h
+++ b/libihash/ihash.h
@@ -113,6 +113,9 @@ struct hurd_ihash
   /* User-supplied functions for the generalized key interface.  */
   hurd_ihash_fct_hash_t fct_hash;
   hurd_ihash_fct_cmp_t fct_cmp;
+
+  /* Number of free slots.  */
+  size_t nr_free;
 };
 typedef struct hurd_ihash *hurd_ihash_t;
 
@@ -225,6 +228,14 @@ hurd_ihash_get_load (hurd_ihash_t ht)
   return d >= 0 ? ht->nr_items >> d : ht->nr_items << -d;
 }
 
+/* Similar, but counts tombstones as well.  */
+static inline unsigned int
+hurd_ihash_get_effective_load (hurd_ihash_t ht)
+{
+  int d = __builtin_ctzl (ht->size) - 7;
+  return
+    d >= 0 ? (ht->size - ht->nr_free) >> d : (ht->size - ht->nr_free) << -d;
+}
 
 /* Add ITEM 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

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