* gimplify.c (gimplify_cond_expr): Use THEN_ and ELSE_ local variables.

[pf3gnuchains/gcc-fork.git] / libiberty / hashtab.c

diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 5557e0a..8c89bfc 100644 (file)
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -1,5 +1,5 @@
 /* An expandable hash tables datatype.  
-   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
+   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009
    Free Software Foundation, Inc.
    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
 
@@ -50,6 +50,9 @@ Boston, MA 02110-1301, USA.  */
 #ifdef HAVE_LIMITS_H
 #include <limits.h>
 #endif
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>
+#endif
 #ifdef HAVE_STDINT_H
 #include <stdint.h>
 #endif
@@ -64,15 +67,6 @@ Boston, MA 02110-1301, USA.  */
 #define CHAR_BIT 8
 #endif
 
-/* This macro defines reserved value for empty table entry. */
-
-#define EMPTY_ENTRY    ((PTR) 0)
-
-/* This macro defines reserved value for table entry which contained
-   a deleted element. */
-
-#define DELETED_ENTRY  ((PTR) 1)
-
 static unsigned int higher_prime_index (unsigned long);
 static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int);
 static hashval_t htab_mod (hashval_t, htab_t);
@@ -205,7 +199,7 @@ higher_prime_index (unsigned long n)
 static hashval_t
 hash_pointer (const PTR p)
 {
-  return (hashval_t) ((long)p >> 3);
+  return (hashval_t) ((intptr_t)p >> 3);
 }
 
 /* Returns non-zero if P1 and P2 are equal.  */
@@ -290,7 +284,7 @@ htab_mod_m2 (hashval_t hash, htab_t htab)
 
 /* 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
+   hash table entries are HTAB_EMPTY_ENTRY).  The function returns the
    created hash table, or NULL if memory allocation fails.  */
 
 htab_t
@@ -401,7 +395,7 @@ htab_delete (htab_t htab)
 
   if (htab->del_f)
     for (i = size - 1; i >= 0; i--)
-      if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
+      if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
        (*htab->del_f) (entries[i]);
 
   if (htab->free_f != NULL)
@@ -427,10 +421,31 @@ htab_empty (htab_t htab)
 
   if (htab->del_f)
     for (i = size - 1; i >= 0; i--)
-      if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY)
+      if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
        (*htab->del_f) (entries[i]);
 
-  memset (entries, 0, size * sizeof (PTR));
+  /* Instead of clearing megabyte, downsize the table.  */
+  if (size > 1024*1024 / sizeof (PTR))
+    {
+      int nindex = higher_prime_index (1024 / sizeof (PTR));
+      int nsize = prime_tab[nindex].prime;
+
+      if (htab->free_f != NULL)
+       (*htab->free_f) (htab->entries);
+      else if (htab->free_with_arg_f != NULL)
+       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
+      if (htab->alloc_with_arg_f != NULL)
+       htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
+                                                          sizeof (PTR *));
+      else
+       htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
+     htab->size = nsize;
+     htab->size_prime_index = nindex;
+    }
+  else
+    memset (entries, 0, size * sizeof (PTR));
+  htab->n_deleted = 0;
+  htab->n_elements = 0;
 }
 
 /* Similar to htab_find_slot, but without several unwanted side effects:
@@ -448,9 +463,9 @@ find_empty_slot_for_expand (htab_t htab, hashval_t hash)
   PTR *slot = htab->entries + index;
   hashval_t hash2;
 
-  if (*slot == EMPTY_ENTRY)
+  if (*slot == HTAB_EMPTY_ENTRY)
     return slot;
-  else if (*slot == DELETED_ENTRY)
+  else if (*slot == HTAB_DELETED_ENTRY)
     abort ();
 
   hash2 = htab_mod_m2 (hash, htab);
@@ -461,9 +476,9 @@ find_empty_slot_for_expand (htab_t htab, hashval_t hash)
        index -= size;
 
       slot = htab->entries + index;
-      if (*slot == EMPTY_ENTRY)
+      if (*slot == HTAB_EMPTY_ENTRY)
        return slot;
-      else if (*slot == DELETED_ENTRY)
+      else if (*slot == HTAB_DELETED_ENTRY)
        abort ();
     }
 }
@@ -523,7 +538,7 @@ htab_expand (htab_t htab)
     {
       PTR x = *p;
 
-      if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
        {
          PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
 
@@ -556,8 +571,8 @@ htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
   index = htab_mod (hash, htab);
 
   entry = htab->entries[index];
-  if (entry == EMPTY_ENTRY
-      || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+  if (entry == HTAB_EMPTY_ENTRY
+      || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
     return entry;
 
   hash2 = htab_mod_m2 (hash, htab);
@@ -569,8 +584,8 @@ htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
        index -= size;
 
       entry = htab->entries[index];
-      if (entry == EMPTY_ENTRY
-         || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+      if (entry == HTAB_EMPTY_ENTRY
+         || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
        return entry;
     }
 }
@@ -615,9 +630,9 @@ htab_find_slot_with_hash (htab_t htab, const PTR element,
   first_deleted_slot = NULL;
 
   entry = htab->entries[index];
-  if (entry == EMPTY_ENTRY)
+  if (entry == HTAB_EMPTY_ENTRY)
     goto empty_entry;
-  else if (entry == DELETED_ENTRY)
+  else if (entry == HTAB_DELETED_ENTRY)
     first_deleted_slot = &htab->entries[index];
   else if ((*htab->eq_f) (entry, element))
     return &htab->entries[index];
@@ -631,9 +646,9 @@ htab_find_slot_with_hash (htab_t htab, const PTR element,
        index -= size;
       
       entry = htab->entries[index];
-      if (entry == EMPTY_ENTRY)
+      if (entry == HTAB_EMPTY_ENTRY)
        goto empty_entry;
-      else if (entry == DELETED_ENTRY)
+      else if (entry == HTAB_DELETED_ENTRY)
        {
          if (!first_deleted_slot)
            first_deleted_slot = &htab->entries[index];
@@ -649,7 +664,7 @@ htab_find_slot_with_hash (htab_t htab, const PTR element,
   if (first_deleted_slot)
     {
       htab->n_deleted--;
-      *first_deleted_slot = EMPTY_ENTRY;
+      *first_deleted_slot = HTAB_EMPTY_ENTRY;
       return first_deleted_slot;
     }
 
@@ -688,13 +703,13 @@ htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
   PTR *slot;
 
   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
-  if (*slot == EMPTY_ENTRY)
+  if (*slot == HTAB_EMPTY_ENTRY)
     return;
 
   if (htab->del_f)
     (*htab->del_f) (*slot);
 
-  *slot = DELETED_ENTRY;
+  *slot = HTAB_DELETED_ENTRY;
   htab->n_deleted++;
 }
 
@@ -706,13 +721,13 @@ void
 htab_clear_slot (htab_t htab, PTR *slot)
 {
   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
-      || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
+      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
     abort ();
 
   if (htab->del_f)
     (*htab->del_f) (*slot);
 
-  *slot = DELETED_ENTRY;
+  *slot = HTAB_DELETED_ENTRY;
   htab->n_deleted++;
 }
 
@@ -726,7 +741,7 @@ htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
 {
   PTR *slot;
   PTR *limit;
-
+  
   slot = htab->entries;
   limit = slot + htab_size (htab);
 
@@ -734,7 +749,7 @@ htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
     {
       PTR x = *slot;
 
-      if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
        if (!(*callback) (slot, info))
          break;
     }
@@ -747,7 +762,8 @@ htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
 void
 htab_traverse (htab_t htab, htab_trav callback, PTR info)
 {
-  if (htab_elements (htab) * 8 < htab_size (htab))
+  size_t size = htab_size (htab);
+  if (htab_elements (htab) * 8 < size && size > 32)
     htab_expand (htab);
 
   htab_traverse_noresize (htab, callback, info);