1 files changed, 229 insertions, 96 deletions

diff --git a/contrib/binutils/libiberty/hashtab.c b/contrib/binutils/libiberty/hashtab.c
index 16c5d3e4b12eb..122ed43e12811 100644
--- a/contrib/binutils/libiberty/hashtab.c
+++ b/contrib/binutils/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.
@@ -41,6 +41,10 @@ Boston, MA 02111-1307, USA.  */
 #include <stdlib.h>
 #endif
 
+#ifdef HAVE_STRING_H
+#include <string.h>
+#endif
+
 #include <stdio.h>
 
 #include "libiberty.h"
@@ -48,44 +52,113 @@ Boston, MA 02111-1307, USA.  */
 
 /* This macro defines reserved value for empty table entry. */
 
-#define EMPTY_ENTRY    ((void *) 0)
+#define EMPTY_ENTRY    ((PTR) 0)
 
 /* This macro defines reserved value for table entry which contained
    a deleted element. */
 
-#define DELETED_ENTRY  ((void *) 1)
+#define DELETED_ENTRY  ((PTR) 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 int htab_expand PARAMS ((htab_t));
+static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
 
-/* The following function returns the nearest prime number which is
-   greater than given source number. */
+/* 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 a nearest prime number which is
+   greater than N, and near a power of two. */
 
 static unsigned long
 higher_prime_number (n)
      unsigned long n;
 {
-  unsigned long i;
+  /* These are primes that are near, but slightly smaller than, a
+     power of two.  */
+  static unsigned long primes[] = {
+    2,
+    7,
+    13,
+    31,
+    61,
+    127,
+    251,
+    509,
+    1021,
+    2039,
+    4093,
+    8191,
+    16381,
+    32749,
+    65521,
+    131071,
+    262139,
+    524287,
+    1048573,
+    2097143,
+    4194301,
+    8388593,
+    16777213,
+    33554393,
+    67108859,
+    134217689,
+    268435399,
+    536870909,
+    1073741789,
+    2147483647,
+    4294967291
+  };
 
-  n |= 0x01;  /* Force N to be odd.  */
-  if (n < 9)
-    return n; /* All odd numbers < 9 are prime.  */
+  unsigned long* low = &primes[0];
+  unsigned long* high = &primes[sizeof(primes) / sizeof(primes[0])];
 
- next:
-  n += 2;
-  i = 3;
-  do
+  while (low != high)
     {
-      if (n % i == 0)
-	goto next;
-      i += 2;
+      unsigned long* mid = low + (high - low) / 2;
+      if (n > *mid)
+	low = mid + 1;
+      else
+	high = mid;
     }
-  while ((i * i) <= n);
 
-  return n;
+  /* If we've run out of primes, abort.  */
+  if (n > *low)
+    {
+      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
+      abort ();
+    }
+
+  return *low;
+}
+
+/* Returns a hash code for P.  */
+
+static hashval_t
+hash_pointer (p)
+     const PTR p;
+{
+  return (hashval_t) ((long)p >> 3);
+}
+
+/* Returns non-zero if P1 and P2 are equal.  */
+
+static int
+eq_pointer (p1, p2)
+     const PTR p1;
+     const PTR 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
-   created hash table. */
+   created hash table.  Memory allocation must not fail.  */
 
 htab_t
 htab_create (size, hash_f, eq_f, del_f)
@@ -98,11 +171,46 @@ htab_create (size, hash_f, eq_f, del_f)
 
   size = higher_prime_number (size);
   result = (htab_t) xcalloc (1, sizeof (struct htab));
-  result->entries = (void **) xcalloc (size, sizeof (void *));
+  result->entries = (PTR *) xcalloc (size, sizeof (PTR));
   result->size = size;
   result->hash_f = hash_f;
   result->eq_f = eq_f;
   result->del_f = del_f;
+  result->return_allocation_failure = 0;
+  return result;
+}
+
+/* This function creates table with length slightly longer than given
+   source length.  The created hash table is initiated as empty (all the
+   hash table entries are EMPTY_ENTRY).  The function returns the created
+   hash table.  Memory allocation may fail; it may return NULL.  */
+
+htab_t
+htab_try_create (size, hash_f, eq_f, del_f)
+     size_t size;
+     htab_hash hash_f;
+     htab_eq eq_f;
+     htab_del del_f;
+{
+  htab_t result;
+
+  size = higher_prime_number (size);
+  result = (htab_t) calloc (1, sizeof (struct htab));
+  if (result == NULL)
+    return NULL;
+
+  result->entries = (PTR *) calloc (size, sizeof (PTR));
+  if (result->entries == NULL)
+    {
+      free (result);
+      return NULL;
+    }
+
+  result->size = size;
+  result->hash_f = hash_f;
+  result->eq_f = eq_f;
+  result->del_f = del_f;
+  result->return_allocation_failure = 1;
   return result;
 }
 
@@ -114,13 +222,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);
@@ -133,15 +240,14 @@ 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 *));
+  memset (htab->entries, 0, htab->size * sizeof (PTR));
 }
 
 /* Similar to htab_find_slot, but without several unwanted side effects:
@@ -150,22 +256,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 **
+
+static PTR *
 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;
+      PTR *slot = htab->entries + index;
+
       if (*slot == EMPTY_ENTRY)
 	return slot;
-
-      if (*slot == DELETED_ENTRY)
+      else if (*slot == DELETED_ENTRY)
 	abort ();
 
       index += hash2;
@@ -178,21 +285,32 @@ find_empty_slot_for_expand (htab, hash)
    entries and repeatedly inserts the table elements.  The occupancy
    of the table after the call will be about 50%.  Naturally the hash
    table must already exist.  Remember also that the place of the
-   table entries is changed. */
+   table entries is changed.  If memory allocation failures are allowed,
+   this function will return zero, indicating that the table could not be
+   expanded.  If all goes well, it will return a non-zero value.  */
 
-static void
+static int
 htab_expand (htab)
      htab_t htab;
 {
-  void **oentries;
-  void **olimit;
-  void **p;
+  PTR *oentries;
+  PTR *olimit;
+  PTR *p;
 
   oentries = htab->entries;
   olimit = oentries + htab->size;
 
   htab->size = higher_prime_number (htab->size * 2);
-  htab->entries = xcalloc (htab->size, sizeof (void **));
+
+  if (htab->return_allocation_failure)
+    {
+      PTR *nentries = (PTR *) calloc (htab->size, sizeof (PTR *));
+      if (nentries == NULL)
+	return 0;
+      htab->entries = nentries;
+    }
+  else
+    htab->entries = (PTR *) xcalloc (htab->size, sizeof (PTR *));
 
   htab->n_elements -= htab->n_deleted;
   htab->n_deleted = 0;
@@ -200,56 +318,69 @@ htab_expand (htab)
   p = oentries;
   do
     {
-      void *x = *p;
+      PTR x = *p;
+
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 	{
-	  void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
+	  PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
+
 	  *q = x;
 	}
+
       p++;
     }
   while (p < olimit);
+
   free (oentries);
+  return 1;
 }
 
 /* This function searches for a hash table entry equal to the given
    element.  It cannot be used to insert or delete an element.  */
 
-void *
+PTR
 htab_find_with_hash (htab, element, hash)
      htab_t htab;
-     const void *element;
-     unsigned int hash;
+     const PTR element;
+     hashval_t hash;
 {
-  unsigned int index, hash2;
+  unsigned int index;
+  hashval_t hash2;
   size_t size;
+  PTR 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 *
+
+PTR
 htab_find (htab, element)
      htab_t htab;
-     const void *element;
+     const PTR element;
 {
   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
 }
@@ -258,21 +389,25 @@ htab_find (htab, element)
    equal to the given element.  To delete an entry, call this with
    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
    after doing some checks).  To insert an entry, call this with
-   INSERT = 1, then write the value you want into the returned slot.  */
+   INSERT = 1, then write the value you want into the returned slot.
+   When inserting an entry, NULL may be returned if memory allocation
+   fails.  */
 
-void **
+PTR *
 htab_find_slot_with_hash (htab, element, hash, insert)
      htab_t htab;
-     const void *element;
-     unsigned int hash;
-     int insert;
+     const PTR element;
+     hashval_t hash;
+     enum insert_option insert;
 {
-  void **first_deleted_slot;
-  unsigned int index, hash2;
+  PTR *first_deleted_slot;
+  unsigned int index;
+  hashval_t hash2;
   size_t size;
 
-  if (insert && htab->size * 3 <= htab->n_elements * 4)
-    htab_expand (htab);
+  if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
+      && htab_expand (htab) == 0)
+    return NULL;
 
   size = htab->size;
   hash2 = 1 + hash % (size - 2);
@@ -283,10 +418,10 @@ htab_find_slot_with_hash (htab, element, hash, insert)
 
   for (;;)
     {
-      void *entry = htab->entries[index];
+      PTR entry = htab->entries[index];
       if (entry == EMPTY_ENTRY)
 	{
-	  if (!insert)
+	  if (insert == NO_INSERT)
 	    return NULL;
 
 	  htab->n_elements++;
@@ -305,11 +440,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;
@@ -320,11 +452,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 **
+
+PTR *
 htab_find_slot (htab, element, insert)
      htab_t htab;
-     const void *element;
-     int insert;
+     const PTR element;
+     enum insert_option insert;
 {
   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
 				   insert);
@@ -337,11 +470,11 @@ htab_find_slot (htab, element, insert)
 void
 htab_remove_elt (htab, element)
      htab_t htab;
-     void *element;
+     PTR element;
 {
-  void **slot;
+  PTR *slot;
 
-  slot = htab_find_slot (htab, element, 0);
+  slot = htab_find_slot (htab, element, NO_INSERT);
   if (*slot == EMPTY_ENTRY)
     return;
 
@@ -359,13 +492,15 @@ htab_remove_elt (htab, element)
 void
 htab_clear_slot (htab, slot)
      htab_t htab;
-     void **slot;
+     PTR *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++;
 }
@@ -379,14 +514,15 @@ void
 htab_traverse (htab, callback, info)
      htab_t htab;
      htab_trav callback;
-     void *info;
+     PTR info;
 {
-  void **slot, **limit;
-  slot = htab->entries;
-  limit = slot + htab->size;
+  PTR *slot = htab->entries;
+  PTR *limit = slot + htab->size;
+
   do
     {
-      void *x = *slot;
+      PTR x = *slot;
+
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
 	if (!(*callback) (slot, info))
 	  break;
@@ -394,7 +530,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)
@@ -403,8 +539,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)
@@ -413,17 +548,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;
 }