1 files changed, 193 insertions, 14 deletions

diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index 206423dc58b..00637789923 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -155,6 +155,47 @@ along with GCC; see the file COPYING3.  If not see
 
       hash_table <pointer_hash <whatever_type>> whatever_type_hash_table;
 
+
+   HASH TABLE ITERATORS
+
+   The hash table provides standard C++ iterators.  For example, consider a
+   hash table of some_info.  We wish to consume each element of the table:
+
+      extern void consume (some_info *);
+
+   We define a convenience typedef and the hash table:
+
+      typedef hash_table <some_info_hasher> info_table_type;
+      info_table_type info_table;
+
+   Then we write the loop in typical C++ style:
+
+      for (info_table_type::iterator iter = info_table.begin ();
+           iter != info_table.end ();
+           ++iter)
+        if ((*iter).status == INFO_READY)
+          consume (&*iter);
+
+   Or with common sub-expression elimination:
+
+      for (info_table_type::iterator iter = info_table.begin ();
+           iter != info_table.end ();
+           ++iter)
+        {
+          some_info &elem = *iter;
+          if (elem.status == INFO_READY)
+            consume (&elem);
+        }
+
+   One can also use a more typical GCC style:
+
+      typedef some_info *some_info_p;
+      some_info *elem_ptr;
+      info_table_type::iterator iter;
+      FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter)
+        if (elem_ptr->status == INFO_READY)
+          consume (elem_ptr);
+
 */
 
 
@@ -368,6 +409,20 @@ public:
   typedef typename Descriptor::value_type value_type;
   typedef typename Descriptor::compare_type compare_type;
 
+  class iterator
+  {
+  public:
+    inline iterator ();
+    inline iterator (value_type **, value_type **);
+    inline value_type &operator * ();
+    void slide ();
+    inline iterator &operator ++ ();
+    inline bool operator != (const iterator &) const;
+  private:
+    value_type **slot_;
+    value_type **limit_;
+  };
+
 private:
   hash_table_control <value_type> *htab;
 
@@ -379,19 +434,19 @@ public:
   void create (size_t initial_slots);
   bool is_created ();
   void dispose ();
-  value_type *find (const compare_type *comparable);
+  value_type *find (const value_type *value);
   value_type *find_with_hash (const compare_type *comparable, hashval_t hash);
-  value_type **find_slot (const compare_type *comparable,
-			  enum insert_option insert);
+  value_type **find_slot (const value_type *value, enum insert_option insert);
   value_type **find_slot_with_hash (const compare_type *comparable,
 				    hashval_t hash, enum insert_option insert);
   void empty ();
   void clear_slot (value_type **slot);
-  void remove_elt (const compare_type *comparable);
+  void remove_elt (const value_type *value);
   void remove_elt_with_hash (const compare_type *comparable, hashval_t hash);
-  size_t size();
-  size_t elements();
-  double collisions();
+  size_t size ();
+  size_t elements ();
+  size_t elements_with_deleted ();
+  double collisions ();
 
   template <typename Argument,
 	    int (*Callback) (value_type **slot, Argument argument)>
@@ -400,6 +455,9 @@ public:
   template <typename Argument,
 	    int (*Callback) (value_type **slot, Argument argument)>
   void traverse (Argument argument);
+
+  iterator begin();
+  iterator end();
 };
 
 
@@ -430,9 +488,9 @@ hash_table <Descriptor, Allocator>::is_created ()
 template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline typename Descriptor::value_type *
-hash_table <Descriptor, Allocator>::find (const compare_type *comparable)
+hash_table <Descriptor, Allocator>::find (const value_type *value)
 {
-  return find_with_hash (comparable, Descriptor::hash (comparable));
+  return find_with_hash (value, Descriptor::hash (value));
 }
 
 
@@ -442,9 +500,9 @@ template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline typename Descriptor::value_type **
 hash_table <Descriptor, Allocator>
-::find_slot (const compare_type *comparable, enum insert_option insert)
+::find_slot (const value_type *value, enum insert_option insert)
 {
-  return find_slot_with_hash (comparable, Descriptor::hash (comparable), insert);
+  return find_slot_with_hash (value, Descriptor::hash (value), insert);
 }
 
 
@@ -453,9 +511,9 @@ hash_table <Descriptor, Allocator>
 template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline void
-hash_table <Descriptor, Allocator>::remove_elt (const compare_type *comparable)
+hash_table <Descriptor, Allocator>::remove_elt (const value_type *value)
 {
-  remove_elt_with_hash (comparable, Descriptor::hash (comparable));
+  remove_elt_with_hash (value, Descriptor::hash (value));
 }
 
 
@@ -475,12 +533,23 @@ hash_table <Descriptor, Allocator>::size()
 template <typename Descriptor,
 	  template <typename Type> class Allocator>
 inline size_t
-hash_table <Descriptor, Allocator>::elements()
+hash_table <Descriptor, Allocator>::elements ()
 {
   return htab->n_elements - htab->n_deleted;
 }
 
 
+/* Return the current number of elements in this hash table. */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline size_t
+hash_table <Descriptor, Allocator>::elements_with_deleted ()
+{
+  return htab->n_elements;
+}
+
+
   /* Return the fraction of fixed collisions during all work with given
      hash table. */
 
@@ -881,4 +950,114 @@ hash_table <Descriptor, Allocator>::traverse (Argument argument)
   traverse_noresize <Argument, Callback> (argument);
 }
 
+
+/* Iterator definitions.  */
+
+/* The default constructor produces the end value.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline
+hash_table <Descriptor, Allocator>::iterator::iterator ()
+: slot_ (NULL), limit_ (NULL)
+{
+}
+
+/* The parameterized constructor produces the begin value.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline
+hash_table <Descriptor, Allocator>::iterator::iterator
+   (value_type **slot, value_type **limit)
+: slot_ (slot), limit_ (limit)
+{
+}
+
+/* Obtain the element.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::value_type &
+hash_table <Descriptor, Allocator>::iterator::operator * ()
+{
+  return **slot_;
+}
+
+/* Slide down the iterator slots until an active entry is found.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+void
+hash_table <Descriptor, Allocator>::iterator::slide ()
+{
+  for ( ; slot_ < limit_; ++slot_ )
+    {
+      value_type *x = *slot_;
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
+        return;
+    }
+  slot_ = NULL;
+  limit_ = NULL;
+}
+
+/* Bump the iterator.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::iterator &
+hash_table <Descriptor, Allocator>::iterator::operator ++ ()
+{
+  ++slot_;
+  slide ();
+  return *this;
+}
+
+/* Compare iterators.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline bool
+hash_table <Descriptor, Allocator>::iterator::
+  operator != (const iterator &other) const
+{
+  return slot_ != other.slot_ || limit_ != other.limit_;
+}
+
+/* Hash table iterator producers.  */
+
+/* The beginning of a hash table iteration.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::iterator
+hash_table <Descriptor, Allocator>::begin ()
+{
+  iterator hti (htab->entries, htab->entries + htab->size);
+  hti.slide ();
+  return hti;
+}
+
+/* The end of a hash table iteration.  */
+
+template <typename Descriptor,
+	  template <typename Type> class Allocator>
+inline typename hash_table <Descriptor, Allocator>::iterator
+hash_table <Descriptor, Allocator>::end ()
+{
+  return iterator ();
+}
+
+/* Iterate through the elements of hash_table HTAB,
+   using hash_table <....>::iterator ITER,
+   storing each element in RESULT, which is of type TYPE.
+
+   This macro has this form for compatibility with the
+   FOR_EACH_HTAB_ELEMENT currently defined in tree-flow.h.  */
+
+#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \
+  for ((ITER) = (HTAB).begin (); \
+       (ITER) != (HTAB).end () ? (RESULT = &*(ITER) , true) : false; \
+       ++(ITER))
+
 #endif /* TYPED_HASHTAB_H */