# hashtab.c: minor optimization [resend]

Zack Weinberg zack@wolery.cumb.org
Tue Mar 28 13:53:00 GMT 2000

```About half of my previous patch was superseded by Bernd's changes.
This just changes htab_find_with_hash so it doesn't calculate the
secondary hash unless it needs it, and tunes the loop a bit.  Good for

Also adds a static prototype for higher_prime_number.

zw

* hashtab.c (htab_find_with_hash): Avoid calculating hash2
unless it will be used.  Rearrange loop for better
optimization.

===================================================================
Index: libiberty/hashtab.c
--- libiberty/hashtab.c	2000/03/14 18:28:45	1.8
+++ libiberty/hashtab.c	2000/03/28 21:50:28
@@ -55,8 +55,10 @@ Boston, MA 02111-1307, USA.  */

#define DELETED_ENTRY  ((void *) 1)

+static unsigned long higher_prime_number PARAMS ((unsigned long));
+
/* The following function returns the nearest prime number which is
-   greater than given source number. */
+   greater than a given source number. */

static unsigned long
higher_prime_number (n)
@@ -223,24 +225,30 @@ htab_find_with_hash (htab, element, hash
{
unsigned int index, hash2;
size_t size;
+  void *entry;

htab->searches++;
size = htab->size;
-  hash2 = 1 + hash % (size - 2);
index = hash % size;

+  entry = htab->entries[index];
+  if (entry == EMPTY_ENTRY
+      || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+    return entry;
+
+  hash2 = 1 + hash % (size - 2);
+
for (;;)
{
-      void *entry = htab->entries[index];
-      if (entry == EMPTY_ENTRY)
-	return NULL;
-      else if (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))
-	return entry;
-
htab->collisions++;
index += hash2;
if (index >= size)
index -= size;
+
+      entry = htab->entries[index];
+      if (entry == EMPTY_ENTRY
+	  || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+	return entry;
}
}

```