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
diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h
index bfbf99c..d009761 100644
--- a/include/llvm/ADT/FoldingSet.h
+++ b/include/llvm/ADT/FoldingSet.h
@@ -224,6 +224,7 @@
// 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 @@
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 @@
};
//===----------------------------------------------------------------------===//
+/// 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 1e8c732..774fbab 100644
--- a/lib/Support/FoldingSet.cpp
+++ b/lib/Support/FoldingSet.cpp
@@ -148,7 +148,7 @@
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 @@
}
}
+//===----------------------------------------------------------------------===//
+// FoldingSetBucketIteratorImpl Implementation
+
+FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
+ Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket;
+}