1 //===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Ted Kremenek and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the ImutAVLTree and ImmutableSet classes.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_IMSET_H
15 #define LLVM_ADT_IMSET_H
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/ADT/FoldingSet.h"
23 //===----------------------------------------------------------------------===//
24 // Immutable AVL-Tree Definition.
25 //===----------------------------------------------------------------------===//
27 template <typename ImutInfo> class ImutAVLFactory;
29 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
31 template <typename ImutInfo >
32 class ImutAVLTree : public FoldingSetNode {
34 typedef typename ImutInfo::key_type_ref key_type_ref;
35 typedef typename ImutInfo::value_type value_type;
36 typedef typename ImutInfo::value_type_ref value_type_ref;
38 typedef ImutAVLFactory<ImutInfo> Factory;
39 friend class ImutAVLFactory<ImutInfo>;
41 typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator;
43 //===----------------------------------------------------===//
45 //===----------------------------------------------------===//
47 /// getLeft - Returns a pointer to the left subtree. This value
48 /// is NULL if there is no left subtree.
49 ImutAVLTree* getLeft() const {
50 assert (!isMutable() && "Node is incorrectly marked mutable.");
52 return reinterpret_cast<ImutAVLTree*>(Left);
55 /// getRight - Returns a pointer to the right subtree. This value is
56 /// NULL if there is no right subtree.
57 ImutAVLTree* getRight() const { return Right; }
60 /// getHeight - Returns the height of the tree. A tree with no subtrees
61 /// has a height of 1.
62 unsigned getHeight() const { return Height; }
64 /// getValue - Returns the data value associated with the tree node.
65 const value_type& getValue() const { return Value; }
67 /// find - Finds the subtree associated with the specified key value.
68 /// This method returns NULL if no matching subtree is found.
69 ImutAVLTree* find(key_type_ref K) {
70 ImutAVLTree *T = this;
73 key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
75 if (ImutInfo::isEqual(K,CurrentKey))
77 else if (ImutInfo::isLess(K,CurrentKey))
86 /// size - Returns the number of nodes in the tree, which includes
87 /// both leaves and non-leaf nodes.
88 unsigned size() const {
91 if (const ImutAVLTree* L = getLeft()) n += L->size();
92 if (const ImutAVLTree* R = getRight()) n += R->size();
97 /// begin - Returns an iterator that iterates over the nodes of the tree
98 /// in an inorder traversal. The returned iterator thus refers to the
99 /// the tree node with the minimum data element.
100 iterator begin() const { return iterator(this); }
102 /// end - Returns an iterator for the tree that denotes the end of an
103 /// inorder traversal.
104 iterator end() const { return iterator(); }
106 /// isEqual - Compares two trees for structural equality and returns true
107 /// if they are equal. This worst case performance of this operation is
108 // linear in the sizes of the trees.
109 bool isEqual(const ImutAVLTree& RHS) const {
113 iterator LItr = begin(), LEnd = end();
114 iterator RItr = RHS.begin(), REnd = RHS.end();
116 while (LItr != LEnd && RItr != REnd) {
117 if (*LItr == *RItr) {
123 // FIXME: need to compare data values, not key values, but our
124 // traits don't support this yet.
125 if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(LItr->getValue()),
126 ImutInfo::KeyOfValue(RItr->getValue())))
133 return LItr == LEnd && RItr == REnd;
136 /// isNotEqual - Compares two trees for structural inequality. Performance
137 /// is the same is isEqual.
138 bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
140 /// contains - Returns true if this tree contains a subtree (node) that
141 /// has an data element that matches the specified key. Complexity
142 /// is logarithmic in the size of the tree.
143 bool contains(const key_type_ref K) { return (bool) find(K); }
145 /// foreach - A member template the accepts invokes operator() on a functor
146 /// object (specifed by Callback) for every node/subtree in the tree.
147 /// Nodes are visited using an inorder traversal.
148 template <typename Callback>
149 void foreach(Callback& C) {
150 if (ImutAVLTree* L = getLeft()) L->foreach(C);
154 if (ImutAVLTree* R = getRight()) R->foreach(C);
157 /// verify - A utility method that checks that the balancing and
158 /// ordering invariants of the tree are satisifed. It is a recursive
159 /// method that returns the height of the tree, which is then consumed
160 /// by the enclosing verify call. External callers should ignore the
161 /// return value. An invalid tree will cause an assertion to fire in
163 unsigned verify() const {
164 unsigned HL = getLeft() ? getLeft()->verify() : 0;
165 unsigned HR = getRight() ? getRight()->verify() : 0;
167 assert (getHeight() == ( HL > HR ? HL : HR ) + 1
168 && "Height calculation wrong.");
170 assert ((HL > HR ? HL-HR : HR-HL) <= 2
171 && "Balancing invariant violated.");
175 || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
176 ImutInfo::KeyOfValue(getValue()))
177 && "Value in left child is not less that current value.");
181 || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
182 ImutInfo::KeyOfValue(getRight()->getValue()))
183 && "Current value is not less that value of right child.");
188 //===----------------------------------------------------===//
190 //===----------------------------------------------------===//
198 //===----------------------------------------------------===//
199 // Profiling or FoldingSet.
200 //===----------------------------------------------------===//
203 void Profile(FoldingSetNodeID& ID, ImutAVLTree* L, ImutAVLTree* R,
207 ImutInfo::Profile(ID,V);
212 void Profile(FoldingSetNodeID& ID) {
213 Profile(ID,getSafeLeft(),getRight(),getValue());
216 //===----------------------------------------------------===//
217 // Internal methods (node manipulation; used by Factory).
218 //===----------------------------------------------------===//
222 ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
223 : Left(reinterpret_cast<uintptr_t>(l) | 0x1),
224 Right(r), Height(height), Value(v) {}
226 bool isMutable() const { return Left & 0x1; }
228 ImutAVLTree* getSafeLeft() const {
229 return reinterpret_cast<ImutAVLTree*>(Left & ~0x1);
232 // Mutating operations. A tree root can be manipulated as long as
233 // its reference has not "escaped" from internal methods of a
234 // factory object (see below). When a tree pointer is externally
235 // viewable by client code, the internal "mutable bit" is cleared
236 // to mark the tree immutable. Note that a tree that still has
237 // its mutable bit set may have children (subtrees) that are themselves
240 void RemoveMutableFlag() {
241 assert (Left & 0x1 && "Mutable flag already removed.");
245 void setLeft(ImutAVLTree* NewLeft) {
246 assert (isMutable());
247 Left = reinterpret_cast<uintptr_t>(NewLeft) | 0x1;
250 void setRight(ImutAVLTree* NewRight) {
251 assert (isMutable());
255 void setHeight(unsigned h) {
256 assert (isMutable());
261 //===----------------------------------------------------------------------===//
262 // Immutable AVL-Tree Factory class.
263 //===----------------------------------------------------------------------===//
265 template <typename ImutInfo >
266 class ImutAVLFactory {
267 typedef ImutAVLTree<ImutInfo> TreeTy;
268 typedef typename TreeTy::value_type_ref value_type_ref;
269 typedef typename TreeTy::key_type_ref key_type_ref;
271 typedef FoldingSet<TreeTy> CacheTy;
274 BumpPtrAllocator Allocator;
276 //===--------------------------------------------------===//
278 //===--------------------------------------------------===//
283 TreeTy* Add(TreeTy* T, value_type_ref V) {
284 T = Add_internal(V,T);
289 TreeTy* Remove(TreeTy* T, key_type_ref V) {
290 T = Remove_internal(V,T);
295 TreeTy* GetEmptyTree() const { return NULL; }
297 BumpPtrAllocator& getAllocator() { return Allocator; }
299 //===--------------------------------------------------===//
300 // A bunch of quick helper functions used for reasoning
301 // about the properties of trees and their children.
302 // These have succinct names so that the balancing code
303 // is as terse (and readable) as possible.
304 //===--------------------------------------------------===//
307 bool isEmpty(TreeTy* T) const { return !T; }
308 unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
309 TreeTy* Left(TreeTy* T) const { return T->getSafeLeft(); }
310 TreeTy* Right(TreeTy* T) const { return T->getRight(); }
311 value_type_ref Value(TreeTy* T) const { return T->Value; }
313 unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {
314 unsigned hl = Height(L);
315 unsigned hr = Height(R);
316 return ( hl > hr ? hl : hr ) + 1;
319 //===--------------------------------------------------===//
320 // "CreateNode" is used to generate new tree roots that link
321 // to other trees. The functon may also simply move links
322 // in an existing root if that root is still marked mutable.
323 // This is necessary because otherwise our balancing code
324 // would leak memory as it would create nodes that are
325 // then discarded later before the finished tree is
326 // returned to the caller.
327 //===--------------------------------------------------===//
329 TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
331 TreeTy::Profile(ID,L,R,V);
334 if (TreeTy* T = Cache.FindNodeOrInsertPos(ID,InsertPos))
337 assert (InsertPos != NULL);
339 // FIXME: more intelligent calculation of alignment.
340 TreeTy* T = (TreeTy*) Allocator.Allocate(sizeof(*T),16);
342 new (T) TreeTy(L,R,V,IncrementHeight(L,R));
344 Cache.InsertNode(T,InsertPos);
348 TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
349 assert (!isEmpty(OldTree));
351 if (OldTree->isMutable()) {
353 OldTree->setRight(R);
354 OldTree->setHeight(IncrementHeight(L,R));
357 else return CreateNode(L, Value(OldTree), R);
360 /// Balance - Used by Add_internal and Remove_internal to
361 /// balance a newly created tree.
362 TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) {
364 unsigned hl = Height(L);
365 unsigned hr = Height(R);
368 assert (!isEmpty(L) &&
369 "Left tree cannot be empty to have a height >= 2.");
371 TreeTy* LL = Left(L);
372 TreeTy* LR = Right(L);
374 if (Height(LL) >= Height(LR))
375 return CreateNode(LL, L, CreateNode(LR,V,R));
377 assert (!isEmpty(LR) &&
378 "LR cannot be empty because it has a height >= 1.");
380 TreeTy* LRL = Left(LR);
381 TreeTy* LRR = Right(LR);
383 return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
385 else if (hr > hl + 2) {
386 assert (!isEmpty(R) &&
387 "Right tree cannot be empty to have a height >= 2.");
389 TreeTy* RL = Left(R);
390 TreeTy* RR = Right(R);
392 if (Height(RR) >= Height(RL))
393 return CreateNode(CreateNode(L,V,RL), R, RR);
395 assert (!isEmpty(RL) &&
396 "RL cannot be empty because it has a height >= 1.");
398 TreeTy* RLL = Left(RL);
399 TreeTy* RLR = Right(RL);
401 return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR));
404 return CreateNode(L,V,R);
407 /// Add_internal - Creates a new tree that includes the specified
408 /// data and the data from the original tree. If the original tree
409 /// already contained the data item, the original tree is returned.
410 TreeTy* Add_internal(value_type_ref V, TreeTy* T) {
412 return CreateNode(T, V, T);
414 assert (!T->isMutable());
416 key_type_ref K = ImutInfo::KeyOfValue(V);
417 key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
419 if (ImutInfo::isEqual(K,KCurrent))
420 return CreateNode(Left(T), V, Right(T));
421 else if (ImutInfo::isLess(K,KCurrent))
422 return Balance(Add_internal(V,Left(T)), Value(T), Right(T));
424 return Balance(Left(T), Value(T), Add_internal(V,Right(T)));
427 /// Remove_interal - Creates a new tree that includes all the data
428 /// from the original tree except the specified data. If the
429 /// specified data did not exist in the original tree, the original
430 /// tree is returned.
431 TreeTy* Remove_internal(key_type_ref K, TreeTy* T) {
435 assert (!T->isMutable());
437 key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
439 if (ImutInfo::isEqual(K,KCurrent))
440 return CombineLeftRightTrees(Left(T),Right(T));
441 else if (ImutInfo::isLess(K,KCurrent))
442 return Balance(Remove_internal(K,Left(T)), Value(T), Right(T));
444 return Balance(Left(T), Value(T), Remove_internal(K,Right(T)));
447 TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) {
448 if (isEmpty(L)) return R;
449 if (isEmpty(R)) return L;
452 TreeTy* NewRight = RemoveMinBinding(R,OldNode);
453 return Balance(L,Value(OldNode),NewRight);
456 TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
457 assert (!isEmpty(T));
459 if (isEmpty(Left(T))) {
464 return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T));
467 /// MarkImmutable - Clears the mutable bits of a root and all of its
469 void MarkImmutable(TreeTy* T) {
470 if (!T || !T->isMutable())
473 T->RemoveMutableFlag();
474 MarkImmutable(Left(T));
475 MarkImmutable(Right(T));
480 //===----------------------------------------------------------------------===//
481 // Immutable AVL-Tree Iterators.
482 //===----------------------------------------------------------------------===//
484 template <typename ImutInfo>
485 class ImutAVLTreeGenericIterator {
486 SmallVector<uintptr_t,20> stack;
488 enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
491 typedef ImutAVLTree<ImutInfo> TreeTy;
492 typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
494 inline ImutAVLTreeGenericIterator() {}
495 inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
496 if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
499 TreeTy* operator*() const {
500 assert (!stack.empty());
501 return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
504 uintptr_t getVisitState() {
505 assert (!stack.empty());
506 return stack.back() & Flags;
510 bool AtEnd() const { return stack.empty(); }
512 bool AtBeginning() const {
513 return stack.size() == 1 && getVisitState() == VisitedNone;
516 void SkipToParent() {
517 assert (!stack.empty());
523 switch (getVisitState()) {
525 stack.back() |= VisitedLeft;
528 stack.back() |= VisitedRight;
531 assert (false && "Unreachable.");
535 inline bool operator==(const _Self& x) const {
536 if (stack.size() != x.stack.size())
539 for (unsigned i = 0 ; i < stack.size(); i++)
540 if (stack[i] != x.stack[i])
546 inline bool operator!=(const _Self& x) const { return !operator==(x); }
548 _Self& operator++() {
549 assert (!stack.empty());
551 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
554 switch (getVisitState()) {
556 if (TreeTy* L = Current->getLeft())
557 stack.push_back(reinterpret_cast<uintptr_t>(L));
559 stack.back() |= VisitedLeft;
564 if (TreeTy* R = Current->getRight())
565 stack.push_back(reinterpret_cast<uintptr_t>(R));
567 stack.back() |= VisitedRight;
576 assert (false && "Unreachable.");
582 _Self& operator--() {
583 assert (!stack.empty());
585 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
588 switch (getVisitState()) {
594 stack.back() &= ~Flags; // Set state to "VisitedNone."
596 if (TreeTy* L = Current->getLeft())
597 stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
602 stack.back() &= ~Flags;
603 stack.back() |= VisitedLeft;
605 if (TreeTy* R = Current->getRight())
606 stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
611 assert (false && "Unreachable.");
618 template <typename ImutInfo>
619 class ImutAVLTreeInOrderIterator {
620 typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
621 InternalIteratorTy InternalItr;
624 typedef ImutAVLTree<ImutInfo> TreeTy;
625 typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
627 ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
628 if (Root) operator++(); // Advance to first element.
631 ImutAVLTreeInOrderIterator() : InternalItr() {}
633 inline bool operator==(const _Self& x) const {
634 return InternalItr == x.InternalItr;
637 inline bool operator!=(const _Self& x) const { return !operator==(x); }
639 inline TreeTy* operator*() const { return *InternalItr; }
640 inline TreeTy* operator->() const { return *InternalItr; }
642 inline _Self& operator++() {
644 while (!InternalItr.AtEnd() &&
645 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
650 inline _Self& operator--() {
652 while (!InternalItr.AtBeginning() &&
653 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
658 inline void SkipSubTree() {
659 InternalItr.SkipToParent();
661 while (!InternalItr.AtEnd() &&
662 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
667 //===----------------------------------------------------------------------===//
668 // Trait classes for Profile information.
669 //===----------------------------------------------------------------------===//
671 /// Generic profile template. The default behavior is to invoke the
672 /// profile method of an object. Specializations for primitive integers
673 /// and generic handling of pointers is done below.
674 template <typename T>
675 struct ImutProfileInfo {
676 typedef const T value_type;
677 typedef const T& value_type_ref;
679 static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
684 /// Profile traits for integers.
685 template <typename T>
686 struct ImutProfileInteger {
687 typedef const T value_type;
688 typedef const T& value_type_ref;
690 static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
695 #define PROFILE_INTEGER_INFO(X)\
696 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
698 PROFILE_INTEGER_INFO(char)
699 PROFILE_INTEGER_INFO(unsigned char)
700 PROFILE_INTEGER_INFO(short)
701 PROFILE_INTEGER_INFO(unsigned short)
702 PROFILE_INTEGER_INFO(unsigned)
703 PROFILE_INTEGER_INFO(signed)
704 PROFILE_INTEGER_INFO(long)
705 PROFILE_INTEGER_INFO(unsigned long)
706 PROFILE_INTEGER_INFO(long long)
707 PROFILE_INTEGER_INFO(unsigned long long)
709 #undef PROFILE_INTEGER_INFO
711 /// Generic profile trait for pointer types. We treat pointers as
712 /// references to unique objects.
713 template <typename T>
714 struct ImutProfileInfo<T*> {
715 typedef const T* value_type;
716 typedef value_type value_type_ref;
718 static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
723 //===----------------------------------------------------------------------===//
724 // Trait classes that contain element comparison operators and type
725 // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
726 // inherit from the profile traits (ImutProfileInfo) to include operations
727 // for element profiling.
728 //===----------------------------------------------------------------------===//
731 /// ImutContainerInfo - Generic definition of comparison operations for
732 /// elements of immutable containers that defaults to using
733 /// std::equal_to<> and std::less<> to perform comparison of elements.
734 template <typename T>
735 struct ImutContainerInfo : public ImutProfileInfo<T> {
736 typedef typename ImutProfileInfo<T>::value_type value_type;
737 typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref;
738 typedef value_type key_type;
739 typedef value_type_ref key_type_ref;
741 static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
743 static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
744 return std::equal_to<key_type>()(LHS,RHS);
747 static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
748 return std::less<key_type>()(LHS,RHS);
752 /// ImutContainerInfo - Specialization for pointer values to treat pointers
753 /// as references to unique objects. Pointers are thus compared by
755 template <typename T>
756 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
757 typedef typename ImutProfileInfo<T*>::value_type value_type;
758 typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref;
759 typedef value_type key_type;
760 typedef value_type_ref key_type_ref;
762 static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
764 static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
768 static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
773 //===----------------------------------------------------------------------===//
775 //===----------------------------------------------------------------------===//
777 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
780 typedef typename ValInfo::value_type value_type;
781 typedef typename ValInfo::value_type_ref value_type_ref;
784 typedef ImutAVLTree<ValInfo> TreeTy;
787 ImmutableSet(TreeTy* R) : Root(R) {}
792 typename TreeTy::Factory F;
797 /// GetEmptySet - Returns an immutable set that contains no elements.
798 ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); }
800 /// Add - Creates a new immutable set that contains all of the values
801 /// of the original set with the addition of the specified value. If
802 /// the original set already included the value, then the original set is
803 /// returned and no memory is allocated. The time and space complexity
804 /// of this operation is logarithmic in the size of the original set.
805 /// The memory allocated to represent the set is released when the
806 /// factory object that created the set is destroyed.
807 ImmutableSet Add(ImmutableSet Old, value_type_ref V) {
808 return ImmutableSet(F.Add(Old.Root,V));
811 /// Remove - Creates a new immutable set that contains all of the values
812 /// of the original set with the exception of the specified value. If
813 /// the original set did not contain the value, the original set is
814 /// returned and no memory is allocated. The time and space complexity
815 /// of this operation is logarithmic in the size of the original set.
816 /// The memory allocated to represent the set is released when the
817 /// factory object that created the set is destroyed.
818 ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {
819 return ImmutableSet(F.Remove(Old.Root,V));
822 BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
825 Factory(const Factory& RHS) {};
826 void operator=(const Factory& RHS) {};
829 friend class Factory;
831 /// contains - Returns true if the set contains the specified value.
832 bool contains(const value_type_ref V) const {
833 return Root ? Root->contains(V) : false;
836 bool operator==(ImmutableSet RHS) const {
837 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
840 bool operator!=(ImmutableSet RHS) const {
841 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
844 /// isEmpty - Return true if the set contains no elements.
845 bool isEmpty() const { return !Root; }
847 template <typename Callback>
848 void foreach(Callback& C) { if (Root) Root->foreach(C); }
850 template <typename Callback>
851 void foreach() { if (Root) { Callback C; Root->foreach(C); } }
853 //===--------------------------------------------------===//
855 //===--------------------------------------------------===//
858 typename TreeTy::iterator itr;
861 iterator(TreeTy* t) : itr(t) {}
862 friend class ImmutableSet<ValT,ValInfo>;
864 inline value_type_ref operator*() const { return itr->getValue(); }
865 inline iterator& operator++() { ++itr; return *this; }
866 inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; }
867 inline iterator& operator--() { --itr; return *this; }
868 inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; }
869 inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
870 inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
873 iterator begin() const { return iterator(Root); }
874 iterator end() const { return iterator(); }
876 //===--------------------------------------------------===//
878 //===--------------------------------------------------===//
880 void verify() const { if (Root) Root->verify(); }
881 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
884 } // end namespace llvm