From 39031d37fd82c119b4b16af256a8ceae5d8c6ea8 Mon Sep 17 00:00:00 2001 From: Justus Winter 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