hashtab.c (higher_prime_number): Use 7 as minimum.

        * hashtab.c (higher_prime_number): Use 7 as minimum.
        (find_empty_slot_for_expand): Don't compute hash2 unless needed.
        (htab_find_slot_with_hash): Likewise.

From-SVN: r52099

diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index ae06bfc051549cff13804da09b6426cba1a6ca5e..b7e03afce42c15e81c38b3cfbb3dee0a8d891c0a 100644 (file)
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,9 @@
+2002-04-09  Richard Henderson  <rth@redhat.com>
+
+       * hashtab.c (higher_prime_number): Use 7 as minimum.
+       (find_empty_slot_for_expand): Don't compute hash2 unless needed.
+       (htab_find_slot_with_hash): Likewise.
+
 2002-04-01  Phil Edwards  <pme@gcc.gnu.org>
 
        * cp-demangle.c (__cxa_demangle):  Also protect with IN_GLIBCPP_V3.

diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 36ad6e4940b6373070375a100005f5d34c983872..7477c35c3bc0b93eb65f2dca76bbd73a681d2e3d 100644 (file)
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -1,5 +1,5 @@
 /* An expandable hash tables datatype.  
-   Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
+   Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
 
 This file is part of the libiberty library.
@@ -81,7 +81,6 @@ higher_prime_number (n)
   /* These are primes that are near, but slightly smaller than, a
      power of two.  */
   static const unsigned long primes[] = {
-    (unsigned long) 2,
     (unsigned long) 7,
     (unsigned long) 13,
     (unsigned long) 31,
@@ -264,21 +263,27 @@ find_empty_slot_for_expand (htab, hash)
      hashval_t hash;
 {
   size_t size = htab->size;
-  hashval_t hash2 = 1 + hash % (size - 2);
   unsigned int index = hash % size;
+  PTR *slot = htab->entries + index;
+  hashval_t hash2;
+
+  if (*slot == EMPTY_ENTRY)
+    return slot;
+  else if (*slot == DELETED_ENTRY)
+    abort ();
 
+  hash2 = 1 + hash % (size - 2);
   for (;;)
     {
-      PTR *slot = htab->entries + index;
+      index += hash2;
+      if (index >= size)
+       index -= size;
 
+      slot = htab->entries + index;
       if (*slot == EMPTY_ENTRY)
        return slot;
       else if (*slot == DELETED_ENTRY)
        abort ();
-
-      index += hash2;
-      if (index >= size)
-       index -= size;
     }
 }
 
@@ -405,50 +410,59 @@ htab_find_slot_with_hash (htab, element, hash, insert)
   unsigned int index;
   hashval_t hash2;
   size_t size;
+  PTR entry;
 
   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
       && htab_expand (htab) == 0)
     return NULL;
 
   size = htab->size;
-  hash2 = 1 + hash % (size - 2);
   index = hash % size;
 
   htab->searches++;
   first_deleted_slot = NULL;
 
+  entry = htab->entries[index];
+  if (entry == EMPTY_ENTRY)
+    goto empty_entry;
+  else if (entry == DELETED_ENTRY)
+    first_deleted_slot = &htab->entries[index];
+  else if ((*htab->eq_f) (entry, element))
+    return &htab->entries[index];
+      
+  hash2 = 1 + hash % (size - 2);
   for (;;)
     {
-      PTR entry = htab->entries[index];
+      htab->collisions++;
+      index += hash2;
+      if (index >= size)
+       index -= size;
+      
+      entry = htab->entries[index];
       if (entry == EMPTY_ENTRY)
-       {
-         if (insert == NO_INSERT)
-           return NULL;
-
-         htab->n_elements++;
-
-         if (first_deleted_slot)
-           {
-             *first_deleted_slot = EMPTY_ENTRY;
-             return first_deleted_slot;
-           }
-
-         return &htab->entries[index];
-       }
-
-      if (entry == DELETED_ENTRY)
+       goto empty_entry;
+      else if (entry == DELETED_ENTRY)
        {
          if (!first_deleted_slot)
            first_deleted_slot = &htab->entries[index];
        }
-      else  if ((*htab->eq_f) (entry, element))
+      else if ((*htab->eq_f) (entry, element))
        return &htab->entries[index];
-      
-      htab->collisions++;
-      index += hash2;
-      if (index >= size)
-       index -= size;
     }
+
+ empty_entry:
+  if (insert == NO_INSERT)
+    return NULL;
+
+  htab->n_elements++;
+
+  if (first_deleted_slot)
+    {
+      *first_deleted_slot = EMPTY_ENTRY;
+      return first_deleted_slot;
+    }
+
+  return &htab->entries[index];
 }
 
 /* Like htab_find_slot_with_hash, but compute the hash value from the