hashtab.c optimizations

[Zack Weinberg <zack at wolery dot cumb dot org>]

These are purely optimization and do not affect any semantics or fix
any bugs.  htab_find is changed to avoid an expensive modulus
operation when it's not needed, at the cost of duplicating a bit of
the code.  I didn't make the analogous change to htab_find_slot
because that function is used much less often and is heavier anyway.
Instead, I split it into two functions, one which may expand the hash
table, and one which won't.  The latter can be used internally in
contexts where we know we don't have to expand the table (e.g. because
we just expanded it).

zw

	* hashtab.c (higher_prime_number): Add static prototype.
	(htab_find_slot): Split all the code after the expansion check
	out into a new, static function, htab_find_slot_noexpand.
	(htab_expand, htab_remove_elt): Call htab_find_slot_noexpand.
	(htab_find): Don't calculate hash2 unless we need it.
	Rearrange conditional for better efficiency.

===================================================================
Index: hashtab.c
--- hashtab.c	2000/03/10 00:00:24	1.7
+++ hashtab.c	2000/03/12 23:46:52
@@ -55,8 +55,11 @@ Boston, MA 02111-1307, USA.  */
 
 #define DELETED_ENTRY  ((void *) 1)
 
+static unsigned long higher_prime_number PARAMS ((unsigned long));
+static void **htab_find_slot_noexpand	 PARAMS ((htab_t, const void *, int));
+
 /* 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)
@@ -173,7 +176,7 @@ htab_expand (htab)
       void *x = *p;
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 	{
-	  void **q = htab_find_slot (htab, x, 1);
+	  void **q = htab_find_slot_noexpand (htab, x, 1);
 	  *q = x;
 	}
       p++;
@@ -192,25 +195,31 @@ htab_find (htab, element)
 {
   unsigned int index, hash, hash2;
   size_t size;
+  void *entry;
 
   htab->searches++;
   size = htab->size;
   hash = (*htab->hash_f) (element);
-  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;
     }
 }
 
@@ -226,13 +235,22 @@ htab_find_slot (htab, element, insert)
      const void *element;
      int insert;
 {
+  if (insert && htab->size * 3 <= htab->n_elements * 4)
+    htab_expand (htab);
+
+  return htab_find_slot_noexpand (htab, element, insert);
+}
+
+static void **
+htab_find_slot_noexpand (htab, element, insert)
+     htab_t htab;
+     const void *element;
+     int insert;
+{
   void **first_deleted_slot;
   unsigned int index, hash, hash2;
   size_t size;
 
-  if (insert && htab->size * 3 <= htab->n_elements * 4)
-    htab_expand (htab);
-
   size = htab->size;
   hash = (*htab->hash_f) (element);
   hash2 = 1 + hash % (size - 2);
@@ -289,7 +307,7 @@ htab_remove_elt (htab, element)
 {
   void **slot;
 
-  slot = htab_find_slot (htab, element, 0);
+  slot = htab_find_slot_noexpand (htab, element, 0);
   if (*slot == EMPTY_ENTRY)
     return;