libihash: use fast binary scaling to determine the load

Expressing the maximum load in binary percent (where 128b% corresponds
to 100%) allows us to use fast binary scaling to determine if the
maximum load has been reached without losing precision.

Furthermore, the previously used expression 'ht->nr_items * 100'
overflows int at 2^25 (unsigned int at 2^26).  When a hash table
reached that limit, it would fail to resize and fill up the table.
This change fixes that.

* libihash/ihash.c (hurd_ihash_set_max_load): Update the comment.
(hurd_ihash_add): Use fast binary scaling to determine the current
load.
* libihash/ihash.h (struct hurd_ihash): Update comment for max_load.
(hurd_ihash_set_max_load): Update the comment.

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