Synced with libiberty in the gcc repository.

1 files changed, 107 insertions, 62 deletions

diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 6ae34aa..57b4041 100644
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -1,5 +1,5 @@
 /* An expandable hash tables datatype.  
-   Copyright (C) 1999 Free Software Foundation, Inc.
+   Copyright (C) 1999, 2000 Free Software Foundation, Inc.
    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
 
 This file is part of the libiberty library.
@@ -59,8 +59,20 @@ Boston, MA 02111-1307, USA.  */
 
 #define DELETED_ENTRY  ((void *) 1)
 
+static unsigned long higher_prime_number PARAMS ((unsigned long));
+static hashval_t hash_pointer PARAMS ((const void *));
+static int eq_pointer PARAMS ((const void *, const void *));
+static void htab_expand PARAMS ((htab_t));
+static void **find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
+
+/* At some point, we could make these be NULL, and modify the
+   hash-table routines to handle NULL specially; that would avoid
+   function-call overhead for the common case of hashing pointers.  */
+htab_hash htab_hash_pointer = hash_pointer;
+htab_eq htab_eq_pointer = eq_pointer;
+
 /* The following function returns the nearest prime number which is
-   greater than given source number. */
+   greater than a given source number, N. */
 
 static unsigned long
 higher_prime_number (n)
@@ -68,24 +80,47 @@ higher_prime_number (n)
 {
   unsigned long i;
 
-  n |= 0x01;  /* Force N to be odd.  */
+  /* Ensure we have a larger number and then force to odd.  */
+  n++;  
+  n |= 0x01; 
+
+  /* All odd numbers < 9 are prime.  */
   if (n < 9)
-    return n; /* All odd numbers < 9 are prime.  */
+    return n;
+
+  /* Otherwise find the next prime using a sieve.  */
 
  next:
-  n += 2;
-  i = 3;
-  do
-    {
-      if (n % i == 0)
-	goto next;
-      i += 2;
-    }
-  while ((i * i) <= n);
+
+  for (i = 3; i * i <= n; i += 2)
+    if (n % i == 0)
+      {
+	 n += 2;
+	 goto next;
+       }
 
   return n;
 }
 
+/* Returns a hash code for P.  */
+
+static hashval_t
+hash_pointer (p)
+     const void *p;
+{
+  return (hashval_t) ((long)p >> 3);
+}
+
+/* Returns non-zero if P1 and P2 are equal.  */
+
+static int
+eq_pointer (p1, p2)
+     const void *p1;
+     const void *p2;
+{
+  return p1 == p2;
+}
+
 /* This function creates table with length slightly longer than given
    source length.  Created hash table is initiated as empty (all the
    hash table entries are EMPTY_ENTRY).  The function returns the
@@ -118,13 +153,12 @@ htab_delete (htab)
      htab_t htab;
 {
   int i;
+
   if (htab->del_f)
     for (i = htab->size - 1; i >= 0; i--)
-      {
-	if (htab->entries[i] != EMPTY_ENTRY
-	    && htab->entries[i] != DELETED_ENTRY)
-	  (*htab->del_f) (htab->entries[i]);
-      }
+      if (htab->entries[i] != EMPTY_ENTRY
+	  && htab->entries[i] != DELETED_ENTRY)
+	(*htab->del_f) (htab->entries[i]);
 
   free (htab->entries);
   free (htab);
@@ -137,13 +171,12 @@ htab_empty (htab)
      htab_t htab;
 {
   int i;
+
   if (htab->del_f)
     for (i = htab->size - 1; i >= 0; i--)
-      {
-	if (htab->entries[i] != EMPTY_ENTRY
-	    && htab->entries[i] != DELETED_ENTRY)
-	  (*htab->del_f) (htab->entries[i]);
-      }
+      if (htab->entries[i] != EMPTY_ENTRY
+	  && htab->entries[i] != DELETED_ENTRY)
+	(*htab->del_f) (htab->entries[i]);
 
   memset (htab->entries, 0, htab->size * sizeof (void *));
 }
@@ -154,22 +187,23 @@ htab_empty (htab)
       hash table.
    This function also assumes there are no deleted entries in the table.
    HASH is the hash value for the element to be inserted.  */
+
 static void **
 find_empty_slot_for_expand (htab, hash)
      htab_t htab;
-     unsigned int hash;
+     hashval_t hash;
 {
   size_t size = htab->size;
-  unsigned int hash2 = 1 + hash % (size - 2);
+  hashval_t hash2 = 1 + hash % (size - 2);
   unsigned int index = hash % size;
 
   for (;;)
     {
       void **slot = htab->entries + index;
+
       if (*slot == EMPTY_ENTRY)
 	return slot;
-
-      if (*slot == DELETED_ENTRY)
+      else if (*slot == DELETED_ENTRY)
 	abort ();
 
       index += hash2;
@@ -196,7 +230,7 @@ htab_expand (htab)
   olimit = oentries + htab->size;
 
   htab->size = higher_prime_number (htab->size * 2);
-  htab->entries = xcalloc (htab->size, sizeof (void **));
+  htab->entries = (void **) xcalloc (htab->size, sizeof (void **));
 
   htab->n_elements -= htab->n_deleted;
   htab->n_deleted = 0;
@@ -205,14 +239,18 @@ htab_expand (htab)
   do
     {
       void *x = *p;
+
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 	{
 	  void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
+
 	  *q = x;
 	}
+
       p++;
     }
   while (p < olimit);
+
   free (oentries);
 }
 
@@ -223,33 +261,41 @@ void *
 htab_find_with_hash (htab, element, hash)
      htab_t htab;
      const void *element;
-     unsigned int hash;
+     hashval_t hash;
 {
-  unsigned int index, hash2;
+  unsigned int index;
+  hashval_t 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;
     }
 }
 
 /* Like htab_find_slot_with_hash, but compute the hash value from the
    element.  */
+
 void *
 htab_find (htab, element)
      htab_t htab;
@@ -268,14 +314,15 @@ void **
 htab_find_slot_with_hash (htab, element, hash, insert)
      htab_t htab;
      const void *element;
-     unsigned int hash;
-     int insert;
+     hashval_t hash;
+     enum insert_option insert;
 {
   void **first_deleted_slot;
-  unsigned int index, hash2;
+  unsigned int index;
+  hashval_t hash2;
   size_t size;
 
-  if (insert && htab->size * 3 <= htab->n_elements * 4)
+  if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4)
     htab_expand (htab);
 
   size = htab->size;
@@ -290,7 +337,7 @@ htab_find_slot_with_hash (htab, element, hash, insert)
       void *entry = htab->entries[index];
       if (entry == EMPTY_ENTRY)
 	{
-	  if (!insert)
+	  if (insert == NO_INSERT)
 	    return NULL;
 
 	  htab->n_elements++;
@@ -309,11 +356,8 @@ htab_find_slot_with_hash (htab, element, hash, insert)
 	  if (!first_deleted_slot)
 	    first_deleted_slot = &htab->entries[index];
 	}
-      else
-	{
-	  if ((*htab->eq_f) (entry, element))
-	    return &htab->entries[index];
-	}
+      else  if ((*htab->eq_f) (entry, element))
+	return &htab->entries[index];
       
       htab->collisions++;
       index += hash2;
@@ -324,11 +368,12 @@ htab_find_slot_with_hash (htab, element, hash, insert)
 
 /* Like htab_find_slot_with_hash, but compute the hash value from the
    element.  */
+
 void **
 htab_find_slot (htab, element, insert)
      htab_t htab;
      const void *element;
-     int insert;
+     enum insert_option insert;
 {
   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 				   insert);
@@ -345,7 +390,7 @@ htab_remove_elt (htab, element)
 {
   void **slot;
 
-  slot = htab_find_slot (htab, element, 0);
+  slot = htab_find_slot (htab, element, NO_INSERT);
   if (*slot == EMPTY_ENTRY)
     return;
 
@@ -368,8 +413,10 @@ htab_clear_slot (htab, slot)
   if (slot < htab->entries || slot >= htab->entries + htab->size
       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
     abort ();
+
   if (htab->del_f)
     (*htab->del_f) (*slot);
+
   *slot = DELETED_ENTRY;
   htab->n_deleted++;
 }
@@ -385,12 +432,13 @@ htab_traverse (htab, callback, info)
      htab_trav callback;
      void *info;
 {
-  void **slot, **limit;
-  slot = htab->entries;
-  limit = slot + htab->size;
+  void **slot = htab->entries;
+  void **limit = slot + htab->size;
+
   do
     {
       void *x = *slot;
+
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 	if (!(*callback) (slot, info))
 	  break;
@@ -398,7 +446,7 @@ htab_traverse (htab, callback, info)
   while (++slot < limit);
 }
 
-/* The following function returns current size of given hash table. */
+/* Return the current size of given hash table. */
 
 size_t
 htab_size (htab)
@@ -407,8 +455,7 @@ htab_size (htab)
   return htab->size;
 }
 
-/* The following function returns current number of elements in given
-   hash table. */
+/* Return the current number of elements in given hash table. */
 
 size_t
 htab_elements (htab)
@@ -417,17 +464,15 @@ htab_elements (htab)
   return htab->n_elements - htab->n_deleted;
 }
 
-/* The following function returns number of percents of fixed
-   collisions during all work with given hash table. */
+/* Return the fraction of fixed collisions during all work with given
+   hash table. */
 
 double
 htab_collisions (htab)
      htab_t htab;
 {
-  int searches;
-
-  searches = htab->searches;
-  if (searches == 0)
+  if (htab->searches == 0)
     return 0.0;
-  return (double)htab->collisions / (double)searches;
+
+  return (double) htab->collisions / (double) htab->searches;
 }