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.h | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'libihash/ihash.h') 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 -- cgit v1.2.3