Some cleanups/additions for hashtables

From-SVN: r32536

diff --git a/include/ChangeLog b/include/ChangeLog
index be7061c63942362d89cd0c492ca7b1860bd3b33b..e36ba7070a36675882298b466ba0e3282b3ad286 100644 (file)
--- a/include/ChangeLog
+++ b/include/ChangeLog
@@ -1,3 +1,10 @@
+2000-03-14  Bernd Schmidt  <bernds@cygnus.co.uk>
+
+       * hashtab.h (htab_trav): Modify type so that first arg is of type
+       void **.
+       (htab_find_with_hash, htab_find_slot_with_hash): Declare new
+       functions.
+
 2000-03-09  Alex Samuel  <samuel@codesourcery.com>
 
        * partition.h: New file.

diff --git a/include/hashtab.h b/include/hashtab.h
index e6e38e4d0589df9ae6e1a07424d55a428087a491..5fe239391ffb284f3d4efc966799bd834b5f87c3 100644 (file)
--- a/include/hashtab.h
+++ b/include/hashtab.h
@@ -44,7 +44,10 @@ extern "C" {
 typedef unsigned int (*htab_hash) PARAMS ((const void *));
 
 /* Compare a table entry with a possible entry.  The entry already in
-   the table always comes first.  */
+   the table always comes first, so the second element can be of a
+   different type (but in this case htab_find and htab_find_slot
+   cannot be used; instead the variants that accept a hash value
+   must be used).  */
 typedef int (*htab_eq) PARAMS ((const void *, const void *));
 
 /* Cleanup function called whenever a live element is removed from
@@ -52,9 +55,10 @@ typedef int (*htab_eq) PARAMS ((const void *, const void *));
 typedef void (*htab_del) PARAMS ((void *));
   
 /* Function called by htab_traverse for each live element.  The first
-   arg is the element, the second arg is the auxiliary pointer handed
-   to htab_traverse.  Return 1 to continue scan, 0 to stop.  */
-typedef int (*htab_trav) PARAMS ((void *, void *));
+   arg is the slot of the element (which can be passed to htab_clear_slot
+   if desired), the second arg is the auxiliary pointer handed to
+   htab_traverse.  Return 1 to continue scan, 0 to stop.  */
+typedef int (*htab_trav) PARAMS ((void **, void *));
 
 /* Hash tables are of the following type.  The structure
    (implementation) of this type is not needed for using the hash
@@ -104,6 +108,10 @@ extern void        htab_empty      PARAMS ((htab_t));
 
 extern void    *htab_find      PARAMS ((htab_t, const void *));
 extern void   **htab_find_slot PARAMS ((htab_t, const void *, int));
+extern void    *htab_find_with_hash            PARAMS ((htab_t, const void *,
+                                                        unsigned int));
+extern void   **htab_find_slot_with_hash       PARAMS ((htab_t, const void *,
+                                                        unsigned int, int));
 extern void    htab_clear_slot PARAMS ((htab_t, void **));
 extern void    htab_remove_elt PARAMS ((htab_t, void *));
 

diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index de8ed944ad074f32d1ccab6488337d1aec5f13b1..7557f62ef27a484fbe43d0d0e32300cc1438318a 100644 (file)
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,14 @@
+2000-03-14  Bernd Schmidt  <bernds@cygnus.co.uk>
+
+       * hashtab.c (find_empty_slot_for_expand): New function.
+       (htab_expand): Use it instead of htab_find_slot.
+       (htab_find_with_hash): Renamed from htab_find; now accepts extra
+       argument HASH.
+       (htab_find_slot_with_hash): Likewise for htab_find_slot.
+       (htab_find): New wrapper function.
+       (htab_find_slot): Likewise.
+       (htab_traverse): Pass slot, not entry, to called function.
+
 2000-03-09  Alex Samuel  <samuel@codesourcery.com>
 
        * Makefile.in (CFILES): Add partition.c.

diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 0bc9e485ef0eb3092e3b42d04693b2b4d52ec4bc..16c5d3e4b12eb08569ad745f20cfaba701db8ba3 100644 (file)
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -144,6 +144,36 @@ htab_empty (htab)
   memset (htab->entries, 0, htab->size * sizeof (void *));
 }
 
+/* Similar to htab_find_slot, but without several unwanted side effects:
+    - Does not call htab->eq_f when it finds an existing entry.
+    - Does not change the count of elements/searches/collisions in the
+      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;
+{
+  size_t size = htab->size;
+  unsigned int 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)
+       abort ();
+
+      index += hash2;
+      if (index >= size)
+       index -= size;
+    }
+}
+
 /* The following function changes size of memory allocated for the
    entries and repeatedly inserts the table elements.  The occupancy
    of the table after the call will be about 50%.  Naturally the hash
@@ -173,7 +203,7 @@ htab_expand (htab)
       void *x = *p;
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
        {
-         void **q = htab_find_slot (htab, x, 1);
+         void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
          *q = x;
        }
       p++;
@@ -186,16 +216,16 @@ htab_expand (htab)
    element.  It cannot be used to insert or delete an element.  */
 
 void *
-htab_find (htab, element)
+htab_find_with_hash (htab, element, hash)
      htab_t htab;
      const void *element;
+     unsigned int hash;
 {
-  unsigned int index, hash, hash2;
+  unsigned int index, hash2;
   size_t size;
 
   htab->searches++;
   size = htab->size;
-  hash = (*htab->hash_f) (element);
   hash2 = 1 + hash % (size - 2);
   index = hash % size;
 
@@ -214,6 +244,16 @@ htab_find (htab, element)
     }
 }
 
+/* Like htab_find_slot_with_hash, but compute the hash value from the
+   element.  */
+void *
+htab_find (htab, element)
+     htab_t htab;
+     const void *element;
+{
+  return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
+}
+
 /* This function searches for a hash table slot containing an entry
    equal to the given element.  To delete an entry, call this with
    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
@@ -221,20 +261,20 @@ htab_find (htab, element)
    INSERT = 1, then write the value you want into the returned slot.  */
 
 void **
-htab_find_slot (htab, element, insert)
+htab_find_slot_with_hash (htab, element, hash, insert)
      htab_t htab;
      const void *element;
+     unsigned int hash;
      int insert;
 {
   void **first_deleted_slot;
-  unsigned int index, hash, hash2;
+  unsigned int index, hash2;
   size_t size;
 
   if (insert && htab->size * 3 <= htab->n_elements * 4)
     htab_expand (htab);
 
   size = htab->size;
-  hash = (*htab->hash_f) (element);
   hash2 = 1 + hash % (size - 2);
   index = hash % size;
 
@@ -278,6 +318,18 @@ htab_find_slot (htab, element, 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;
+{
+  return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
+                                  insert);
+}
+
 /* This function deletes an element with the given value from hash
    table.  If there is no matching element in the hash table, this
    function does nothing.  */
@@ -336,7 +388,7 @@ htab_traverse (htab, callback, info)
     {
       void *x = *slot;
       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
-       if (!(*callback) (x, info))
+       if (!(*callback) (slot, info))
          break;
     }
   while (++slot < limit);