diff options
Diffstat (limited to 'include/llvm/ADT/ImmutableSet.h')
| -rw-r--r-- | include/llvm/ADT/ImmutableSet.h | 170 |
1 files changed, 74 insertions, 96 deletions
diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index 3c6f58c..87026f0 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -142,13 +142,13 @@ public: iterator RItr = RHS.begin(), REnd = RHS.end(); while (LItr != LEnd && RItr != REnd) { - if (*LItr == *RItr) { + if (&*LItr == &*RItr) { LItr.skipSubTree(); RItr.skipSubTree(); continue; } - if (!LItr->isElementEqual(*RItr)) + if (!LItr->isElementEqual(&*RItr)) return false; ++LItr; @@ -293,8 +293,8 @@ private: height = h; } - static inline - uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { + static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R, + value_type_ref V) { uint32_t digest = 0; if (L) @@ -311,7 +311,7 @@ private: return digest; } - inline uint32_t computeDigest() { + uint32_t computeDigest() { // Check the lowest bit to determine if digest has actually been // pre-computed. if (hasCachedDigest()) @@ -429,9 +429,7 @@ protected: value_type_ref getValue(TreeTy* T) const { return T->value; } // Make sure the index is not the Tombstone or Entry key of the DenseMap. - static inline unsigned maskCacheIndex(unsigned I) { - return (I & ~0x02); - } + static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); } unsigned incrementHeight(TreeTy* L, TreeTy* R) const { unsigned hl = getHeight(L); @@ -444,7 +442,7 @@ protected: typename TreeTy::iterator& TE) { typename TreeTy::iterator I = T->begin(), E = T->end(); for ( ; I!=E ; ++I, ++TI) { - if (TI == TE || !I->isElementEqual(*TI)) + if (TI == TE || !I->isElementEqual(&*TI)) return false; } return true; @@ -647,24 +645,26 @@ public: //===----------------------------------------------------------------------===// template <typename ImutInfo> -class ImutAVLTreeGenericIterator { +class ImutAVLTreeGenericIterator + : public std::iterator<std::bidirectional_iterator_tag, + ImutAVLTree<ImutInfo>> { SmallVector<uintptr_t,20> stack; public: enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3, Flags=0x3 }; typedef ImutAVLTree<ImutInfo> TreeTy; - typedef ImutAVLTreeGenericIterator<ImutInfo> _Self; - inline ImutAVLTreeGenericIterator() {} - inline ImutAVLTreeGenericIterator(const TreeTy* Root) { + ImutAVLTreeGenericIterator() {} + ImutAVLTreeGenericIterator(const TreeTy *Root) { if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root)); } - TreeTy* operator*() const { + TreeTy &operator*() const { assert(!stack.empty()); - return reinterpret_cast<TreeTy*>(stack.back() & ~Flags); + return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags); } + TreeTy *operator->() const { return &*this; } uintptr_t getVisitState() const { assert(!stack.empty()); @@ -695,13 +695,15 @@ public: } } - inline bool operator==(const _Self& x) const { + bool operator==(const ImutAVLTreeGenericIterator &x) const { return stack == x.stack; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } + bool operator!=(const ImutAVLTreeGenericIterator &x) const { + return !(*this == x); + } - _Self& operator++() { + ImutAVLTreeGenericIterator &operator++() { assert(!stack.empty()); TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); assert(Current); @@ -727,7 +729,7 @@ public: return *this; } - _Self& operator--() { + ImutAVLTreeGenericIterator &operator--() { assert(!stack.empty()); TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); assert(Current); @@ -754,30 +756,34 @@ public: }; template <typename ImutInfo> -class ImutAVLTreeInOrderIterator { +class ImutAVLTreeInOrderIterator + : public std::iterator<std::bidirectional_iterator_tag, + ImutAVLTree<ImutInfo>> { typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy; InternalIteratorTy InternalItr; public: typedef ImutAVLTree<ImutInfo> TreeTy; - typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self; ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) { - if (Root) operator++(); // Advance to first element. + if (Root) + ++*this; // Advance to first element. } ImutAVLTreeInOrderIterator() : InternalItr() {} - inline bool operator==(const _Self& x) const { + bool operator==(const ImutAVLTreeInOrderIterator &x) const { return InternalItr == x.InternalItr; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } + bool operator!=(const ImutAVLTreeInOrderIterator &x) const { + return !(*this == x); + } - inline TreeTy* operator*() const { return *InternalItr; } - inline TreeTy* operator->() const { return *InternalItr; } + TreeTy &operator*() const { return *InternalItr; } + TreeTy *operator->() const { return &*InternalItr; } - inline _Self& operator++() { + ImutAVLTreeInOrderIterator &operator++() { do ++InternalItr; while (!InternalItr.atEnd() && InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); @@ -785,7 +791,7 @@ public: return *this; } - inline _Self& operator--() { + ImutAVLTreeInOrderIterator &operator--() { do --InternalItr; while (!InternalItr.atBeginning() && InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); @@ -793,7 +799,7 @@ public: return *this; } - inline void skipSubTree() { + void skipSubTree() { InternalItr.skipToParent(); while (!InternalItr.atEnd() && @@ -802,6 +808,24 @@ public: } }; +/// Generic iterator that wraps a T::TreeTy::iterator and exposes +/// iterator::getValue() on dereference. +template <typename T> +struct ImutAVLValueIterator + : iterator_adaptor_base< + ImutAVLValueIterator<T>, typename T::TreeTy::iterator, + typename std::iterator_traits< + typename T::TreeTy::iterator>::iterator_category, + const typename T::value_type> { + ImutAVLValueIterator() = default; + explicit ImutAVLValueIterator(typename T::TreeTy *Tree) + : ImutAVLValueIterator::iterator_adaptor_base(Tree) {} + + typename ImutAVLValueIterator::reference operator*() const { + return this->I->getValue(); + } +}; + //===----------------------------------------------------------------------===// // Trait classes for Profile information. //===----------------------------------------------------------------------===// @@ -814,7 +838,7 @@ struct ImutProfileInfo { typedef const T value_type; typedef const T& value_type_ref; - static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { FoldingSetTrait<T>::Profile(X,ID); } }; @@ -825,7 +849,7 @@ struct ImutProfileInteger { typedef const T value_type; typedef const T& value_type_ref; - static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { ID.AddInteger(X); } }; @@ -852,7 +876,7 @@ struct ImutProfileInfo<bool> { typedef const bool value_type; typedef const bool& value_type_ref; - static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { ID.AddBoolean(X); } }; @@ -865,7 +889,7 @@ struct ImutProfileInfo<T*> { typedef const T* value_type; typedef value_type value_type_ref; - static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) { + static void Profile(FoldingSetNodeID &ID, value_type_ref X) { ID.AddPointer(X); } }; @@ -890,18 +914,18 @@ struct ImutContainerInfo : public ImutProfileInfo<T> { typedef bool data_type; typedef bool data_type_ref; - static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } - static inline data_type_ref DataOfValue(value_type_ref) { return true; } + static key_type_ref KeyOfValue(value_type_ref D) { return D; } + static data_type_ref DataOfValue(value_type_ref) { return true; } - static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { + static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return std::equal_to<key_type>()(LHS,RHS); } - static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { + static bool isLess(key_type_ref LHS, key_type_ref RHS) { return std::less<key_type>()(LHS,RHS); } - static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } + static bool isDataEqual(data_type_ref, data_type_ref) { return true; } }; /// ImutContainerInfo - Specialization for pointer values to treat pointers @@ -916,18 +940,14 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { typedef bool data_type; typedef bool data_type_ref; - static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } - static inline data_type_ref DataOfValue(value_type_ref) { return true; } + static key_type_ref KeyOfValue(value_type_ref D) { return D; } + static data_type_ref DataOfValue(value_type_ref) { return true; } - static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { - return LHS == RHS; - } + static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; } - static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { - return LHS < RHS; - } + static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; } - static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } + static bool isDataEqual(data_type_ref, data_type_ref) { return true; } }; //===----------------------------------------------------------------------===// @@ -1059,31 +1079,7 @@ public: // Iterators. //===--------------------------------------------------===// - class iterator { - typename TreeTy::iterator itr; - - iterator() {} - iterator(TreeTy* t) : itr(t) {} - friend class ImmutableSet<ValT,ValInfo>; - - public: - typedef ptrdiff_t difference_type; - typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type; - typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference; - typedef typename iterator::value_type *pointer; - typedef std::bidirectional_iterator_tag iterator_category; - - typename iterator::reference operator*() const { return itr->getValue(); } - typename iterator::pointer operator->() const { return &(operator*()); } - - iterator& operator++() { ++itr; return *this; } - iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - iterator& operator--() { --itr; return *this; } - iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - - bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } - }; + typedef ImutAVLValueIterator<ImmutableSet> iterator; iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } @@ -1094,13 +1090,11 @@ public: unsigned getHeight() const { return Root ? Root->getHeight() : 0; } - static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) { + static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) { ID.AddPointer(S.Root); } - inline void Profile(FoldingSetNodeID& ID) const { - return Profile(ID,*this); - } + void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } //===--------------------------------------------------===// // For testing. @@ -1150,7 +1144,7 @@ public: if (Root) { Root->release(); } } - static inline ImmutableSetRef getEmptySet(FactoryTy *F) { + static ImmutableSetRef getEmptySet(FactoryTy *F) { return ImmutableSetRef(0, F); } @@ -1195,21 +1189,7 @@ public: // Iterators. //===--------------------------------------------------===// - class iterator { - typename TreeTy::iterator itr; - iterator(TreeTy* t) : itr(t) {} - friend class ImmutableSetRef<ValT,ValInfo>; - public: - iterator() {} - inline value_type_ref operator*() const { return itr->getValue(); } - inline iterator& operator++() { ++itr; return *this; } - inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - inline iterator& operator--() { --itr; return *this; } - inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } - inline value_type *operator->() const { return &(operator*()); } - }; + typedef ImutAVLValueIterator<ImmutableSetRef> iterator; iterator begin() const { return iterator(Root); } iterator end() const { return iterator(); } @@ -1220,13 +1200,11 @@ public: unsigned getHeight() const { return Root ? Root->getHeight() : 0; } - static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { + static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) { ID.AddPointer(S.Root); } - inline void Profile(FoldingSetNodeID& ID) const { - return Profile(ID,*this); - } + void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } //===--------------------------------------------------===// // For testing. |