Import of Binutils from the FSF 2.13 branch (just pre-.1 release).

These bits are taken from the FSF anoncvs repo on 11-Oct-2002 22:39:35 PDT.

1 files changed, 87 insertions, 73 deletions

diff --git a/contrib/binutils/libiberty/hashtab.c b/contrib/binutils/libiberty/hashtab.c
index 36ad6e4..6bf59ff 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, 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,
@@ -159,60 +158,60 @@ eq_pointer (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.  Memory allocation must not fail.  */
+   created hash table, or NULL if memory allocation fails.  */
 
 htab_t
-htab_create (size, hash_f, eq_f, del_f)
+htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
      size_t size;
      htab_hash hash_f;
      htab_eq eq_f;
      htab_del del_f;
+     htab_alloc alloc_f;
+     htab_free free_f;
 {
   htab_t result;
 
   size = higher_prime_number (size);
-  result = (htab_t) xcalloc (1, sizeof (struct htab));
-  result->entries = (PTR *) xcalloc (size, sizeof (PTR));
+  result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
+  if (result == NULL)
+    return NULL;
+  result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
+  if (result->entries == NULL)
+    {
+      if (free_f != NULL)
+	(*free_f) (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 = 0;
+  result->alloc_f = alloc_f;
+  result->free_f = free_f;
   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.  */
+/* These functions exist solely for backward compatibility.  */
 
+#undef htab_create
 htab_t
-htab_try_create (size, hash_f, eq_f, del_f)
+htab_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;
-    }
+  return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
+}
 
-  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;
+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;
+{
+  return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
 }
 
 /* This function frees all memory allocated for given hash table.
@@ -230,8 +229,11 @@ htab_delete (htab)
 	  && htab->entries[i] != DELETED_ENTRY)
 	(*htab->del_f) (htab->entries[i]);
 
-  free (htab->entries);
-  free (htab);
+  if (htab->free_f != NULL)
+    {
+      (*htab->free_f) (htab->entries);
+      (*htab->free_f) (htab);
+    }
 }
 
 /* This function clears all entries in the given hash table.  */
@@ -264,21 +266,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;
     }
 }
 
@@ -297,21 +305,17 @@ htab_expand (htab)
   PTR *oentries;
   PTR *olimit;
   PTR *p;
+  PTR *nentries;
 
   oentries = htab->entries;
   olimit = oentries + htab->size;
 
   htab->size = higher_prime_number (htab->size * 2);
 
-  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 *));
+  nentries = (PTR *) (*htab->alloc_f) (htab->size, sizeof (PTR *));
+  if (nentries == NULL)
+    return 0;
+  htab->entries = nentries;
 
   htab->n_elements -= htab->n_deleted;
   htab->n_deleted = 0;
@@ -332,7 +336,8 @@ htab_expand (htab)
     }
   while (p < olimit);
 
-  free (oentries);
+  if (htab->free_f != NULL)
+    (*htab->free_f) (oentries);
   return 1;
 }
 
@@ -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