From 116c3219df347f169b1bd24acca2d53ab0ae26ec Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 3 Oct 2007 21:12:09 +0000
Subject: [PATCH] Add initial iterator support for folding set.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42589 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/FoldingSet.h | 51 +++++++++++++++++++++++++++++++++++++++++++
 lib/Support/FoldingSet.cpp    | 32 +++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)

diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index 7fca63867ba..6f486512e54 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -220,6 +220,8 @@ protected:
 typedef FoldingSetImpl::Node FoldingSetNode;
 typedef FoldingSetImpl::NodeID FoldingSetNodeID;
 
+template<class T> class FoldingSetIterator;
+
 //===----------------------------------------------------------------------===//
 /// FoldingSet - This template class is used to instantiate a specialized
 /// implementation of the folding set to the node class T.  T must be a 
@@ -238,6 +240,14 @@ public:
   explicit FoldingSet(unsigned Log2InitSize = 6)
   : FoldingSetImpl(Log2InitSize)
   {}
+  
+  typedef FoldingSetIterator<T> iterator;
+  iterator begin() { return iterator(Buckets); }
+  iterator end() { return iterator(Buckets+NumBuckets); }
+
+  typedef FoldingSetIterator<const T> const_iterator;
+  const_iterator begin() const { return const_iterator(Buckets); }
+  const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
 
   /// GetOrInsertNode - If there is an existing simple Node exactly
   /// equal to the specified node, return it.  Otherwise, insert 'N' and
@@ -254,6 +264,47 @@ public:
   }
 };
 
+//===----------------------------------------------------------------------===//
+/// FoldingSetIteratorImpl - This is the common iterator support shared by all
+/// folding sets, which knows how to walk the folding set hash table.
+class FoldingSetIteratorImpl {
+protected:
+  FoldingSetNode *NodePtr;
+  FoldingSetIteratorImpl(void **Bucket);
+  void advance();
+  
+public:
+  bool operator==(const FoldingSetIteratorImpl &RHS) const {
+    return NodePtr == RHS.NodePtr;
+  }
+  bool operator!=(const FoldingSetIteratorImpl &RHS) const {
+    return NodePtr != RHS.NodePtr;
+  }
+};
+
+
+template<class T>
+class FoldingSetIterator : public FoldingSetIteratorImpl {
+public:
+  FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
+  
+  T &operator*() const {
+    return *static_cast<T*>(NodePtr);
+  }
+  
+  T *operator->() const {
+    return static_cast<T*>(NodePtr);
+  }
+  
+  inline FoldingSetIterator& operator++() {          // Preincrement
+    advance();
+    return *this;
+  }
+  FoldingSetIterator operator++(int) {        // Postincrement
+    FoldingSetIterator tmp = *this; ++*this; return tmp;
+  }
+};
+
 } // End of namespace llvm.
 
 
diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp
index 424dff18bd8..d099d90fe24 100644
--- a/lib/Support/FoldingSet.cpp
+++ b/lib/Support/FoldingSet.cpp
@@ -151,6 +151,7 @@ static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
 /// testing.
 static void **GetBucketPtr(void *NextInBucketPtr) {
   intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
+  assert((Ptr & 1) && "Not a bucket pointer");
   return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
 }
 
@@ -323,3 +324,34 @@ FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) {
   InsertNode(N, IP);
   return N;
 }
+
+//===----------------------------------------------------------------------===//
+// FoldingSetIteratorImpl Implementation
+
+FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
+  // Skip to the first non-null non-self-cycle bucket.
+  while (*Bucket == 0 || GetNextPtr(*Bucket) == 0)
+    ++Bucket;
+  
+  NodePtr = static_cast<FoldingSetNode*>(*Bucket);
+}
+
+void FoldingSetIteratorImpl::advance() {
+  // If there is another link within this bucket, go to it.
+  void *Probe = NodePtr->getNextInBucket();
+
+  if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
+    NodePtr = NextNodeInBucket;
+  else {
+    // Otherwise, this is the last link in this bucket.  
+    void **Bucket = GetBucketPtr(Probe);
+
+    // Skip to the next non-null non-self-cycle bucket.
+    do {
+      ++Bucket;
+    } while (*Bucket == 0 || GetNextPtr(*Bucket) == 0);
+    
+    NodePtr = static_cast<FoldingSetNode*>(*Bucket);
+  }
+}
+
-- 
2.11.0