From 39031d37fd82c119b4b16af256a8ceae5d8c6ea8 Mon Sep 17 00:00:00 2001
From: Justus Winter <justus@gnupg.org>
Date: Thu, 28 Apr 2016 20:11:27 +0200
Subject: 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 +++++++++
1 file changed, 9 insertions(+)
(limited to 'libihash/ihash.c')
diff --git a/libihash/ihash.c b/libihash/ihash.c
index 01ba23bd..800f4923 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));
--
cgit v1.2.3