From 26e3c445fc844b2f241dfdde9ce7e0602ba13cc4 Mon Sep 17 00:00:00 2001
From: Ted Kremenek <kremenek@apple.com>
Date: Mon, 4 Feb 2008 21:11:17 +0000
Subject: [PATCH] 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
---
 include/llvm/ADT/FoldingSet.h | 62 +++++++++++++++++++++++++++++++++++
 lib/Support/FoldingSet.cpp    |  8 ++++-
 2 files changed, 69 insertions(+), 1 deletion(-)

diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index bfbf99c269b..d0097613d68 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.
@@ -321,6 +332,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.
diff --git a/lib/Support/FoldingSet.cpp b/lib/Support/FoldingSet.cpp
index 1e8c732a148..774fbabc28e 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;
+}
-- 
2.34.1