Added "bucket_iterators" to FoldingSet. Bucket iterators allow iteration

over all the nodes in a particular bucket.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46716 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 69 insertions, 1 deletions

diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index bfbf99c269..d0097613d6 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -224,6 +224,7 @@ public:
 // Convenience type to hide the implementation of the folding set.
 typedef FoldingSetImpl::Node FoldingSetNode;
 template<class T> class FoldingSetIterator;
+template<class T> class FoldingSetBucketIterator;
 
 //===----------------------------------------------------------------------===//
 /// FoldingSetTrait - This trait class is used to define behavior of how
@@ -265,6 +266,16 @@ public:
   const_iterator begin() const { return const_iterator(Buckets); }
   const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
 
+  typedef FoldingSetBucketIterator<T> bucket_iterator;  
+
+  bucket_iterator bucket_begin(unsigned hash) {
+    return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
+  }
+  
+  bucket_iterator bucket_end(unsigned hash) {
+    return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
+  }
+  
   /// GetOrInsertNode - If there is an existing simple Node exactly
   /// equal to the specified node, return it.  Otherwise, insert 'N' and
   /// return it instead.
@@ -322,6 +333,57 @@ public:
 };
   
 //===----------------------------------------------------------------------===//
+/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
+///  shared by all folding sets, which knows how to walk a particular bucket
+///  of a folding set hash table.
+  
+class FoldingSetBucketIteratorImpl {
+protected:
+  void *Ptr;
+
+  FoldingSetBucketIteratorImpl(void **Bucket);
+  
+  FoldingSetBucketIteratorImpl(void **Bucket, bool)
+    : Ptr(reinterpret_cast<void*>(Bucket)) {}
+
+  void advance() {
+    void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
+    uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
+    Ptr = reinterpret_cast<void*>(x);
+  }
+  
+public:
+  bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
+    return Ptr == RHS.Ptr;
+  }
+  bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
+    return Ptr != RHS.Ptr;
+  }
+};
+  
+  
+template<class T>
+class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
+public:
+  FoldingSetBucketIterator(void **Bucket) : 
+    FoldingSetBucketIteratorImpl(Bucket) {}
+  
+  FoldingSetBucketIterator(void **Bucket, bool) : 
+    FoldingSetBucketIteratorImpl(Bucket, true) {}
+  
+  T& operator*() const { return *static_cast<T*>(Ptr); }  
+  T* operator->() const { return static_cast<T*>(Ptr); }
+  
+  inline FoldingSetBucketIterator& operator++() { // Preincrement
+    advance();
+    return *this;
+  }          
+  FoldingSetBucketIterator operator++(int) {      // Postincrement
+    FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
+  }
+};
+  
+//===----------------------------------------------------------------------===//
 /// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
 /// types in an enclosing object so that they can be inserted into FoldingSets.
 template <typename T>
diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp
index 1e8c732a14..774fbabc28 100644
--- a/lib/Support/FoldingSet.cpp
+++ b/lib/Support/FoldingSet.cpp
@@ -148,7 +148,7 @@ static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
   return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
 }
 
-/// GetBucketPtr - Provides a casting of a bucket pointer for isNode
+
 /// testing.
 static void **GetBucketPtr(void *NextInBucketPtr) {
   intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
@@ -358,3 +358,9 @@ void FoldingSetIteratorImpl::advance() {
   }
 }
 
+//===----------------------------------------------------------------------===//
+// FoldingSetBucketIteratorImpl Implementation
+
+FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
+  Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket;
+}