Author: lattner Date: Wed Oct 3 16:12:09 2007 New Revision: 42589 URL: http://llvm.org/viewvc/llvm-project?rev=42589&view=rev Log: Add initial iterator support for folding set.
Modified: llvm/trunk/include/llvm/ADT/FoldingSet.h llvm/trunk/lib/Support/FoldingSet.cpp Modified: llvm/trunk/include/llvm/ADT/FoldingSet.h URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ADT/FoldingSet.h?rev=42589&r1=42588&r2=42589&view=diff ============================================================================== --- llvm/trunk/include/llvm/ADT/FoldingSet.h (original) +++ llvm/trunk/include/llvm/ADT/FoldingSet.h Wed Oct 3 16:12:09 2007 @@ -220,6 +220,8 @@ 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 @@ 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 @@ } }; +//===----------------------------------------------------------------------===// +/// 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. Modified: llvm/trunk/lib/Support/FoldingSet.cpp URL: http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Support/FoldingSet.cpp?rev=42589&r1=42588&r2=42589&view=diff ============================================================================== --- llvm/trunk/lib/Support/FoldingSet.cpp (original) +++ llvm/trunk/lib/Support/FoldingSet.cpp Wed Oct 3 16:12:09 2007 @@ -151,6 +151,7 @@ /// 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 @@ 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); + } +} + _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits