diff options
| -rw-r--r-- | libihash/ihash.c | 37 | ||||
| -rw-r--r-- | libihash/ihash.h | 24 |
2 files changed, 40 insertions, 21 deletions
diff --git a/libihash/ihash.c b/libihash/ihash.c index 249f4884..151c1a79 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -180,14 +180,15 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, } -/* Set the maximum load factor in percent to MAX_LOAD, which should be - between 1 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT. - New elements are only added to the hash table while the number of - hashed elements is that much percent of the total size of the hash - table. If more elements are added, the hash table is first - expanded and reorganized. A MAX_LOAD of 100 will always fill the - whole table before enlarging it, but note that this will increase - the cost of operations significantly when the table is almost full. +/* Set the maximum load factor in binary percent to MAX_LOAD, which + should be between 64 and 128. The default is + HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the + hash table while the number of hashed elements is that much binary + percent of the total size of the hash table. If more elements are + added, the hash table is first expanded and reorganized. A + MAX_LOAD of 128 will always fill the whole table before enlarging + it, but note that this will increase the cost of operations + significantly when the table is almost full. If the value is set to a smaller value than the current load factor, the next reorganization will happen when a new item is @@ -272,8 +273,24 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t item) if (ht->size) { - /* Only fill the hash table up to its maximum load factor. */ - if ((ht->nr_items * 100) >> __builtin_ctzl (ht->size) <= ht->max_load) + /* Only fill the hash table up to its maximum load factor given + as "binary percent", where 128b% corresponds to 100%. As the + size is always a power of two, and 128 is also, the quotient + of both is also a power of two. Therefore, we can use bit + shifts to scale the number of items. + + load = nr_items * 128 / size + = nr_items * 2^{log2 (128) - log2 (size)} + = nr_items >> (log2 (size) - log2 (128)) + -- if size >= 128 + = nr_items << (log2 (128) - log2 (size)) + -- otherwise + */ + int d = __builtin_ctzl (ht->size) - 7; + unsigned int load = d >= 0 + ? ht->nr_items >> d + : ht->nr_items << -d; + if (load <= ht->max_load) if (add_one (ht, key, item)) return 0; } diff --git a/libihash/ihash.h b/libihash/ihash.h index 8829e51e..809166f2 100644 --- a/libihash/ihash.h +++ b/libihash/ihash.h @@ -79,7 +79,7 @@ struct hurd_ihash /* The offset of the location pointer from the hash value. */ intptr_t locp_offset; - /* The maximum load factor in percent. */ + /* The maximum load factor in binary percent. */ unsigned int max_load; /* When freeing or overwriting an element, this function is called @@ -97,8 +97,9 @@ typedef struct hurd_ihash *hurd_ihash_t; be a power of two. */ #define HURD_IHASH_MIN_SIZE 32 -/* The default value for the maximum load factor in percent. */ -#define HURD_IHASH_MAX_LOAD_DEFAULT 75 +/* The default value for the maximum load factor in binary percent. + 96b% is equivalent to 75%, 128b% to 100%. */ +#define HURD_IHASH_MAX_LOAD_DEFAULT 96 /* The LOCP_OFFS to use if no location pointer is available. */ #define HURD_IHASH_NO_LOCP INTPTR_MIN @@ -143,14 +144,15 @@ void hurd_ihash_free (hurd_ihash_t ht); void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup, void *cleanup_data); -/* Set the maximum load factor in percent to MAX_LOAD, which should be - between 50 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT. - New elements are only added to the hash table while the number of - hashed elements is that much percent of the total size of the hash - table. If more elements are added, the hash table is first - expanded and reorganized. A MAX_LOAD of 100 will always fill the - whole table before enlarging it, but note that this will increase - the cost of operations significantly when the table is almost full. +/* Set the maximum load factor in binary percent to MAX_LOAD, which + should be between 64 and 128. The default is + HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the + hash table while the number of hashed elements is that much binary + percent of the total size of the hash table. If more elements are + added, the hash table is first expanded and reorganized. A + MAX_LOAD of 128 will always fill the whole table before enlarging + it, but note that this will increase the cost of operations + significantly when the table is almost full. If the value is set to a smaller value than the current load factor, the next reorganization will happen when a new item is |