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.

1 files changed, 11 insertions, 0 deletions

diff --git a/libihash/ihash.h b/libihash/ihash.h
index 356f6473..80679f14 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