1//===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the ImutAVLTree and ImmutableSet classes.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_IMMUTABLESET_H
15#define LLVM_ADT_IMMUTABLESET_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/FoldingSet.h"
19#include "llvm/Support/Allocator.h"
20#include "llvm/Support/DataTypes.h"
21#include "llvm/Support/ErrorHandling.h"
22#include <cassert>
23#include <functional>
24#include <vector>
25
26namespace llvm {
27
28//===----------------------------------------------------------------------===//
29// Immutable AVL-Tree Definition.
30//===----------------------------------------------------------------------===//
31
32template <typename ImutInfo> class ImutAVLFactory;
33template <typename ImutInfo> class ImutIntervalAVLFactory;
34template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
35template <typename ImutInfo> class ImutAVLTreeGenericIterator;
36
37template <typename ImutInfo >
38class ImutAVLTree {
39public:
40  typedef typename ImutInfo::key_type_ref   key_type_ref;
41  typedef typename ImutInfo::value_type     value_type;
42  typedef typename ImutInfo::value_type_ref value_type_ref;
43
44  typedef ImutAVLFactory<ImutInfo>          Factory;
45  friend class ImutAVLFactory<ImutInfo>;
46  friend class ImutIntervalAVLFactory<ImutInfo>;
47
48  friend class ImutAVLTreeGenericIterator<ImutInfo>;
49
50  typedef ImutAVLTreeInOrderIterator<ImutInfo>  iterator;
51
52  //===----------------------------------------------------===//
53  // Public Interface.
54  //===----------------------------------------------------===//
55
56  /// Return a pointer to the left subtree.  This value
57  ///  is NULL if there is no left subtree.
58  ImutAVLTree *getLeft() const { return left; }
59
60  /// Return a pointer to the right subtree.  This value is
61  ///  NULL if there is no right subtree.
62  ImutAVLTree *getRight() const { return right; }
63
64  /// getHeight - Returns the height of the tree.  A tree with no subtrees
65  ///  has a height of 1.
66  unsigned getHeight() const { return height; }
67
68  /// getValue - Returns the data value associated with the tree node.
69  const value_type& getValue() const { return value; }
70
71  /// find - Finds the subtree associated with the specified key value.
72  ///  This method returns NULL if no matching subtree is found.
73  ImutAVLTree* find(key_type_ref K) {
74    ImutAVLTree *T = this;
75    while (T) {
76      key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
77      if (ImutInfo::isEqual(K,CurrentKey))
78        return T;
79      else if (ImutInfo::isLess(K,CurrentKey))
80        T = T->getLeft();
81      else
82        T = T->getRight();
83    }
84    return nullptr;
85  }
86
87  /// getMaxElement - Find the subtree associated with the highest ranged
88  ///  key value.
89  ImutAVLTree* getMaxElement() {
90    ImutAVLTree *T = this;
91    ImutAVLTree *Right = T->getRight();
92    while (Right) { T = Right; Right = T->getRight(); }
93    return T;
94  }
95
96  /// size - Returns the number of nodes in the tree, which includes
97  ///  both leaves and non-leaf nodes.
98  unsigned size() const {
99    unsigned n = 1;
100    if (const ImutAVLTree* L = getLeft())
101      n += L->size();
102    if (const ImutAVLTree* R = getRight())
103      n += R->size();
104    return n;
105  }
106
107  /// begin - Returns an iterator that iterates over the nodes of the tree
108  ///  in an inorder traversal.  The returned iterator thus refers to the
109  ///  the tree node with the minimum data element.
110  iterator begin() const { return iterator(this); }
111
112  /// end - Returns an iterator for the tree that denotes the end of an
113  ///  inorder traversal.
114  iterator end() const { return iterator(); }
115
116  bool isElementEqual(value_type_ref V) const {
117    // Compare the keys.
118    if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
119                           ImutInfo::KeyOfValue(V)))
120      return false;
121
122    // Also compare the data values.
123    if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
124                               ImutInfo::DataOfValue(V)))
125      return false;
126
127    return true;
128  }
129
130  bool isElementEqual(const ImutAVLTree* RHS) const {
131    return isElementEqual(RHS->getValue());
132  }
133
134  /// isEqual - Compares two trees for structural equality and returns true
135  ///   if they are equal.  This worst case performance of this operation is
136  //    linear in the sizes of the trees.
137  bool isEqual(const ImutAVLTree& RHS) const {
138    if (&RHS == this)
139      return true;
140
141    iterator LItr = begin(), LEnd = end();
142    iterator RItr = RHS.begin(), REnd = RHS.end();
143
144    while (LItr != LEnd && RItr != REnd) {
145      if (*LItr == *RItr) {
146        LItr.skipSubTree();
147        RItr.skipSubTree();
148        continue;
149      }
150
151      if (!LItr->isElementEqual(*RItr))
152        return false;
153
154      ++LItr;
155      ++RItr;
156    }
157
158    return LItr == LEnd && RItr == REnd;
159  }
160
161  /// isNotEqual - Compares two trees for structural inequality.  Performance
162  ///  is the same is isEqual.
163  bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
164
165  /// contains - Returns true if this tree contains a subtree (node) that
166  ///  has an data element that matches the specified key.  Complexity
167  ///  is logarithmic in the size of the tree.
168  bool contains(key_type_ref K) { return (bool) find(K); }
169
170  /// foreach - A member template the accepts invokes operator() on a functor
171  ///  object (specifed by Callback) for every node/subtree in the tree.
172  ///  Nodes are visited using an inorder traversal.
173  template <typename Callback>
174  void foreach(Callback& C) {
175    if (ImutAVLTree* L = getLeft())
176      L->foreach(C);
177
178    C(value);
179
180    if (ImutAVLTree* R = getRight())
181      R->foreach(C);
182  }
183
184  /// validateTree - A utility method that checks that the balancing and
185  ///  ordering invariants of the tree are satisifed.  It is a recursive
186  ///  method that returns the height of the tree, which is then consumed
187  ///  by the enclosing validateTree call.  External callers should ignore the
188  ///  return value.  An invalid tree will cause an assertion to fire in
189  ///  a debug build.
190  unsigned validateTree() const {
191    unsigned HL = getLeft() ? getLeft()->validateTree() : 0;
192    unsigned HR = getRight() ? getRight()->validateTree() : 0;
193    (void) HL;
194    (void) HR;
195
196    assert(getHeight() == ( HL > HR ? HL : HR ) + 1
197            && "Height calculation wrong");
198
199    assert((HL > HR ? HL-HR : HR-HL) <= 2
200           && "Balancing invariant violated");
201
202    assert((!getLeft() ||
203            ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
204                             ImutInfo::KeyOfValue(getValue()))) &&
205           "Value in left child is not less that current value");
206
207
208    assert(!(getRight() ||
209             ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
210                              ImutInfo::KeyOfValue(getRight()->getValue()))) &&
211           "Current value is not less that value of right child");
212
213    return getHeight();
214  }
215
216  //===----------------------------------------------------===//
217  // Internal values.
218  //===----------------------------------------------------===//
219
220private:
221  Factory *factory;
222  ImutAVLTree *left;
223  ImutAVLTree *right;
224  ImutAVLTree *prev;
225  ImutAVLTree *next;
226
227  unsigned height         : 28;
228  unsigned IsMutable      : 1;
229  unsigned IsDigestCached : 1;
230  unsigned IsCanonicalized : 1;
231
232  value_type value;
233  uint32_t digest;
234  uint32_t refCount;
235
236  //===----------------------------------------------------===//
237  // Internal methods (node manipulation; used by Factory).
238  //===----------------------------------------------------===//
239
240private:
241  /// ImutAVLTree - Internal constructor that is only called by
242  ///   ImutAVLFactory.
243  ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v,
244              unsigned height)
245    : factory(f), left(l), right(r), prev(nullptr), next(nullptr),
246      height(height), IsMutable(true), IsDigestCached(false),
247      IsCanonicalized(0), value(v), digest(0), refCount(0)
248  {
249    if (left) left->retain();
250    if (right) right->retain();
251  }
252
253  /// isMutable - Returns true if the left and right subtree references
254  ///  (as well as height) can be changed.  If this method returns false,
255  ///  the tree is truly immutable.  Trees returned from an ImutAVLFactory
256  ///  object should always have this method return true.  Further, if this
257  ///  method returns false for an instance of ImutAVLTree, all subtrees
258  ///  will also have this method return false.  The converse is not true.
259  bool isMutable() const { return IsMutable; }
260
261  /// hasCachedDigest - Returns true if the digest for this tree is cached.
262  ///  This can only be true if the tree is immutable.
263  bool hasCachedDigest() const { return IsDigestCached; }
264
265  //===----------------------------------------------------===//
266  // Mutating operations.  A tree root can be manipulated as
267  // long as its reference has not "escaped" from internal
268  // methods of a factory object (see below).  When a tree
269  // pointer is externally viewable by client code, the
270  // internal "mutable bit" is cleared to mark the tree
271  // immutable.  Note that a tree that still has its mutable
272  // bit set may have children (subtrees) that are themselves
273  // immutable.
274  //===----------------------------------------------------===//
275
276  /// markImmutable - Clears the mutable flag for a tree.  After this happens,
277  ///   it is an error to call setLeft(), setRight(), and setHeight().
278  void markImmutable() {
279    assert(isMutable() && "Mutable flag already removed.");
280    IsMutable = false;
281  }
282
283  /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
284  void markedCachedDigest() {
285    assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
286    IsDigestCached = true;
287  }
288
289  /// setHeight - Changes the height of the tree.  Used internally by
290  ///  ImutAVLFactory.
291  void setHeight(unsigned h) {
292    assert(isMutable() && "Only a mutable tree can have its height changed.");
293    height = h;
294  }
295
296  static inline
297  uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
298    uint32_t digest = 0;
299
300    if (L)
301      digest += L->computeDigest();
302
303    // Compute digest of stored data.
304    FoldingSetNodeID ID;
305    ImutInfo::Profile(ID,V);
306    digest += ID.ComputeHash();
307
308    if (R)
309      digest += R->computeDigest();
310
311    return digest;
312  }
313
314  inline uint32_t computeDigest() {
315    // Check the lowest bit to determine if digest has actually been
316    // pre-computed.
317    if (hasCachedDigest())
318      return digest;
319
320    uint32_t X = computeDigest(getLeft(), getRight(), getValue());
321    digest = X;
322    markedCachedDigest();
323    return X;
324  }
325
326  //===----------------------------------------------------===//
327  // Reference count operations.
328  //===----------------------------------------------------===//
329
330public:
331  void retain() { ++refCount; }
332  void release() {
333    assert(refCount > 0);
334    if (--refCount == 0)
335      destroy();
336  }
337  void destroy() {
338    if (left)
339      left->release();
340    if (right)
341      right->release();
342    if (IsCanonicalized) {
343      if (next)
344        next->prev = prev;
345
346      if (prev)
347        prev->next = next;
348      else
349        factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
350    }
351
352    // We need to clear the mutability bit in case we are
353    // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
354    IsMutable = false;
355    factory->freeNodes.push_back(this);
356  }
357};
358
359//===----------------------------------------------------------------------===//
360// Immutable AVL-Tree Factory class.
361//===----------------------------------------------------------------------===//
362
363template <typename ImutInfo >
364class ImutAVLFactory {
365  friend class ImutAVLTree<ImutInfo>;
366  typedef ImutAVLTree<ImutInfo> TreeTy;
367  typedef typename TreeTy::value_type_ref value_type_ref;
368  typedef typename TreeTy::key_type_ref   key_type_ref;
369
370  typedef DenseMap<unsigned, TreeTy*> CacheTy;
371
372  CacheTy Cache;
373  uintptr_t Allocator;
374  std::vector<TreeTy*> createdNodes;
375  std::vector<TreeTy*> freeNodes;
376
377  bool ownsAllocator() const {
378    return Allocator & 0x1 ? false : true;
379  }
380
381  BumpPtrAllocator& getAllocator() const {
382    return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
383  }
384
385  //===--------------------------------------------------===//
386  // Public interface.
387  //===--------------------------------------------------===//
388
389public:
390  ImutAVLFactory()
391    : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
392
393  ImutAVLFactory(BumpPtrAllocator& Alloc)
394    : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
395
396  ~ImutAVLFactory() {
397    if (ownsAllocator()) delete &getAllocator();
398  }
399
400  TreeTy* add(TreeTy* T, value_type_ref V) {
401    T = add_internal(V,T);
402    markImmutable(T);
403    recoverNodes();
404    return T;
405  }
406
407  TreeTy* remove(TreeTy* T, key_type_ref V) {
408    T = remove_internal(V,T);
409    markImmutable(T);
410    recoverNodes();
411    return T;
412  }
413
414  TreeTy* getEmptyTree() const { return nullptr; }
415
416protected:
417
418  //===--------------------------------------------------===//
419  // A bunch of quick helper functions used for reasoning
420  // about the properties of trees and their children.
421  // These have succinct names so that the balancing code
422  // is as terse (and readable) as possible.
423  //===--------------------------------------------------===//
424
425  bool            isEmpty(TreeTy* T) const { return !T; }
426  unsigned        getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
427  TreeTy*         getLeft(TreeTy* T) const { return T->getLeft(); }
428  TreeTy*         getRight(TreeTy* T) const { return T->getRight(); }
429  value_type_ref  getValue(TreeTy* T) const { return T->value; }
430
431  // Make sure the index is not the Tombstone or Entry key of the DenseMap.
432  static inline unsigned maskCacheIndex(unsigned I) {
433    return (I & ~0x02);
434  }
435
436  unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
437    unsigned hl = getHeight(L);
438    unsigned hr = getHeight(R);
439    return (hl > hr ? hl : hr) + 1;
440  }
441
442  static bool compareTreeWithSection(TreeTy* T,
443                                     typename TreeTy::iterator& TI,
444                                     typename TreeTy::iterator& TE) {
445    typename TreeTy::iterator I = T->begin(), E = T->end();
446    for ( ; I!=E ; ++I, ++TI) {
447      if (TI == TE || !I->isElementEqual(*TI))
448        return false;
449    }
450    return true;
451  }
452
453  //===--------------------------------------------------===//
454  // "createNode" is used to generate new tree roots that link
455  // to other trees.  The functon may also simply move links
456  // in an existing root if that root is still marked mutable.
457  // This is necessary because otherwise our balancing code
458  // would leak memory as it would create nodes that are
459  // then discarded later before the finished tree is
460  // returned to the caller.
461  //===--------------------------------------------------===//
462
463  TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
464    BumpPtrAllocator& A = getAllocator();
465    TreeTy* T;
466    if (!freeNodes.empty()) {
467      T = freeNodes.back();
468      freeNodes.pop_back();
469      assert(T != L);
470      assert(T != R);
471    } else {
472      T = (TreeTy*) A.Allocate<TreeTy>();
473    }
474    new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
475    createdNodes.push_back(T);
476    return T;
477  }
478
479  TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
480    return createNode(newLeft, getValue(oldTree), newRight);
481  }
482
483  void recoverNodes() {
484    for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
485      TreeTy *N = createdNodes[i];
486      if (N->isMutable() && N->refCount == 0)
487        N->destroy();
488    }
489    createdNodes.clear();
490  }
491
492  /// balanceTree - Used by add_internal and remove_internal to
493  ///  balance a newly created tree.
494  TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
495    unsigned hl = getHeight(L);
496    unsigned hr = getHeight(R);
497
498    if (hl > hr + 2) {
499      assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
500
501      TreeTy *LL = getLeft(L);
502      TreeTy *LR = getRight(L);
503
504      if (getHeight(LL) >= getHeight(LR))
505        return createNode(LL, L, createNode(LR,V,R));
506
507      assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1");
508
509      TreeTy *LRL = getLeft(LR);
510      TreeTy *LRR = getRight(LR);
511
512      return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
513    }
514
515    if (hr > hl + 2) {
516      assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
517
518      TreeTy *RL = getLeft(R);
519      TreeTy *RR = getRight(R);
520
521      if (getHeight(RR) >= getHeight(RL))
522        return createNode(createNode(L,V,RL), R, RR);
523
524      assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1");
525
526      TreeTy *RLL = getLeft(RL);
527      TreeTy *RLR = getRight(RL);
528
529      return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
530    }
531
532    return createNode(L,V,R);
533  }
534
535  /// add_internal - Creates a new tree that includes the specified
536  ///  data and the data from the original tree.  If the original tree
537  ///  already contained the data item, the original tree is returned.
538  TreeTy* add_internal(value_type_ref V, TreeTy* T) {
539    if (isEmpty(T))
540      return createNode(T, V, T);
541    assert(!T->isMutable());
542
543    key_type_ref K = ImutInfo::KeyOfValue(V);
544    key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
545
546    if (ImutInfo::isEqual(K,KCurrent))
547      return createNode(getLeft(T), V, getRight(T));
548    else if (ImutInfo::isLess(K,KCurrent))
549      return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T));
550    else
551      return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T)));
552  }
553
554  /// remove_internal - Creates a new tree that includes all the data
555  ///  from the original tree except the specified data.  If the
556  ///  specified data did not exist in the original tree, the original
557  ///  tree is returned.
558  TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
559    if (isEmpty(T))
560      return T;
561
562    assert(!T->isMutable());
563
564    key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
565
566    if (ImutInfo::isEqual(K,KCurrent)) {
567      return combineTrees(getLeft(T), getRight(T));
568    } else if (ImutInfo::isLess(K,KCurrent)) {
569      return balanceTree(remove_internal(K, getLeft(T)),
570                                            getValue(T), getRight(T));
571    } else {
572      return balanceTree(getLeft(T), getValue(T),
573                         remove_internal(K, getRight(T)));
574    }
575  }
576
577  TreeTy* combineTrees(TreeTy* L, TreeTy* R) {
578    if (isEmpty(L))
579      return R;
580    if (isEmpty(R))
581      return L;
582    TreeTy* OldNode;
583    TreeTy* newRight = removeMinBinding(R,OldNode);
584    return balanceTree(L, getValue(OldNode), newRight);
585  }
586
587  TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
588    assert(!isEmpty(T));
589    if (isEmpty(getLeft(T))) {
590      Noderemoved = T;
591      return getRight(T);
592    }
593    return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
594                       getValue(T), getRight(T));
595  }
596
597  /// markImmutable - Clears the mutable bits of a root and all of its
598  ///  descendants.
599  void markImmutable(TreeTy* T) {
600    if (!T || !T->isMutable())
601      return;
602    T->markImmutable();
603    markImmutable(getLeft(T));
604    markImmutable(getRight(T));
605  }
606
607public:
608  TreeTy *getCanonicalTree(TreeTy *TNew) {
609    if (!TNew)
610      return nullptr;
611
612    if (TNew->IsCanonicalized)
613      return TNew;
614
615    // Search the hashtable for another tree with the same digest, and
616    // if find a collision compare those trees by their contents.
617    unsigned digest = TNew->computeDigest();
618    TreeTy *&entry = Cache[maskCacheIndex(digest)];
619    do {
620      if (!entry)
621        break;
622      for (TreeTy *T = entry ; T != nullptr; T = T->next) {
623        // Compare the Contents('T') with Contents('TNew')
624        typename TreeTy::iterator TI = T->begin(), TE = T->end();
625        if (!compareTreeWithSection(TNew, TI, TE))
626          continue;
627        if (TI != TE)
628          continue; // T has more contents than TNew.
629        // Trees did match!  Return 'T'.
630        if (TNew->refCount == 0)
631          TNew->destroy();
632        return T;
633      }
634      entry->prev = TNew;
635      TNew->next = entry;
636    }
637    while (false);
638
639    entry = TNew;
640    TNew->IsCanonicalized = true;
641    return TNew;
642  }
643};
644
645//===----------------------------------------------------------------------===//
646// Immutable AVL-Tree Iterators.
647//===----------------------------------------------------------------------===//
648
649template <typename ImutInfo>
650class ImutAVLTreeGenericIterator {
651  SmallVector<uintptr_t,20> stack;
652public:
653  enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
654                   Flags=0x3 };
655
656  typedef ImutAVLTree<ImutInfo> TreeTy;
657  typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
658
659  inline ImutAVLTreeGenericIterator() {}
660  inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
661    if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
662  }
663
664  TreeTy* operator*() const {
665    assert(!stack.empty());
666    return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
667  }
668
669  uintptr_t getVisitState() const {
670    assert(!stack.empty());
671    return stack.back() & Flags;
672  }
673
674
675  bool atEnd() const { return stack.empty(); }
676
677  bool atBeginning() const {
678    return stack.size() == 1 && getVisitState() == VisitedNone;
679  }
680
681  void skipToParent() {
682    assert(!stack.empty());
683    stack.pop_back();
684    if (stack.empty())
685      return;
686    switch (getVisitState()) {
687      case VisitedNone:
688        stack.back() |= VisitedLeft;
689        break;
690      case VisitedLeft:
691        stack.back() |= VisitedRight;
692        break;
693      default:
694        llvm_unreachable("Unreachable.");
695    }
696  }
697
698  inline bool operator==(const _Self& x) const {
699    return stack == x.stack;
700  }
701
702  inline bool operator!=(const _Self& x) const { return !operator==(x); }
703
704  _Self& operator++() {
705    assert(!stack.empty());
706    TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
707    assert(Current);
708    switch (getVisitState()) {
709      case VisitedNone:
710        if (TreeTy* L = Current->getLeft())
711          stack.push_back(reinterpret_cast<uintptr_t>(L));
712        else
713          stack.back() |= VisitedLeft;
714        break;
715      case VisitedLeft:
716        if (TreeTy* R = Current->getRight())
717          stack.push_back(reinterpret_cast<uintptr_t>(R));
718        else
719          stack.back() |= VisitedRight;
720        break;
721      case VisitedRight:
722        skipToParent();
723        break;
724      default:
725        llvm_unreachable("Unreachable.");
726    }
727    return *this;
728  }
729
730  _Self& operator--() {
731    assert(!stack.empty());
732    TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
733    assert(Current);
734    switch (getVisitState()) {
735      case VisitedNone:
736        stack.pop_back();
737        break;
738      case VisitedLeft:
739        stack.back() &= ~Flags; // Set state to "VisitedNone."
740        if (TreeTy* L = Current->getLeft())
741          stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
742        break;
743      case VisitedRight:
744        stack.back() &= ~Flags;
745        stack.back() |= VisitedLeft;
746        if (TreeTy* R = Current->getRight())
747          stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
748        break;
749      default:
750        llvm_unreachable("Unreachable.");
751    }
752    return *this;
753  }
754};
755
756template <typename ImutInfo>
757class ImutAVLTreeInOrderIterator {
758  typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
759  InternalIteratorTy InternalItr;
760
761public:
762  typedef ImutAVLTree<ImutInfo> TreeTy;
763  typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
764
765  ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
766    if (Root) operator++(); // Advance to first element.
767  }
768
769  ImutAVLTreeInOrderIterator() : InternalItr() {}
770
771  inline bool operator==(const _Self& x) const {
772    return InternalItr == x.InternalItr;
773  }
774
775  inline bool operator!=(const _Self& x) const { return !operator==(x); }
776
777  inline TreeTy* operator*() const { return *InternalItr; }
778  inline TreeTy* operator->() const { return *InternalItr; }
779
780  inline _Self& operator++() {
781    do ++InternalItr;
782    while (!InternalItr.atEnd() &&
783           InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
784
785    return *this;
786  }
787
788  inline _Self& operator--() {
789    do --InternalItr;
790    while (!InternalItr.atBeginning() &&
791           InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
792
793    return *this;
794  }
795
796  inline void skipSubTree() {
797    InternalItr.skipToParent();
798
799    while (!InternalItr.atEnd() &&
800           InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
801      ++InternalItr;
802  }
803};
804
805//===----------------------------------------------------------------------===//
806// Trait classes for Profile information.
807//===----------------------------------------------------------------------===//
808
809/// Generic profile template.  The default behavior is to invoke the
810/// profile method of an object.  Specializations for primitive integers
811/// and generic handling of pointers is done below.
812template <typename T>
813struct ImutProfileInfo {
814  typedef const T  value_type;
815  typedef const T& value_type_ref;
816
817  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
818    FoldingSetTrait<T>::Profile(X,ID);
819  }
820};
821
822/// Profile traits for integers.
823template <typename T>
824struct ImutProfileInteger {
825  typedef const T  value_type;
826  typedef const T& value_type_ref;
827
828  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
829    ID.AddInteger(X);
830  }
831};
832
833#define PROFILE_INTEGER_INFO(X)\
834template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
835
836PROFILE_INTEGER_INFO(char)
837PROFILE_INTEGER_INFO(unsigned char)
838PROFILE_INTEGER_INFO(short)
839PROFILE_INTEGER_INFO(unsigned short)
840PROFILE_INTEGER_INFO(unsigned)
841PROFILE_INTEGER_INFO(signed)
842PROFILE_INTEGER_INFO(long)
843PROFILE_INTEGER_INFO(unsigned long)
844PROFILE_INTEGER_INFO(long long)
845PROFILE_INTEGER_INFO(unsigned long long)
846
847#undef PROFILE_INTEGER_INFO
848
849/// Profile traits for booleans.
850template <>
851struct ImutProfileInfo<bool> {
852  typedef const bool  value_type;
853  typedef const bool& value_type_ref;
854
855  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
856    ID.AddBoolean(X);
857  }
858};
859
860
861/// Generic profile trait for pointer types.  We treat pointers as
862/// references to unique objects.
863template <typename T>
864struct ImutProfileInfo<T*> {
865  typedef const T*   value_type;
866  typedef value_type value_type_ref;
867
868  static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
869    ID.AddPointer(X);
870  }
871};
872
873//===----------------------------------------------------------------------===//
874// Trait classes that contain element comparison operators and type
875//  definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap.  These
876//  inherit from the profile traits (ImutProfileInfo) to include operations
877//  for element profiling.
878//===----------------------------------------------------------------------===//
879
880
881/// ImutContainerInfo - Generic definition of comparison operations for
882///   elements of immutable containers that defaults to using
883///   std::equal_to<> and std::less<> to perform comparison of elements.
884template <typename T>
885struct ImutContainerInfo : public ImutProfileInfo<T> {
886  typedef typename ImutProfileInfo<T>::value_type      value_type;
887  typedef typename ImutProfileInfo<T>::value_type_ref  value_type_ref;
888  typedef value_type      key_type;
889  typedef value_type_ref  key_type_ref;
890  typedef bool            data_type;
891  typedef bool            data_type_ref;
892
893  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
894  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
895
896  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
897    return std::equal_to<key_type>()(LHS,RHS);
898  }
899
900  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
901    return std::less<key_type>()(LHS,RHS);
902  }
903
904  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
905};
906
907/// ImutContainerInfo - Specialization for pointer values to treat pointers
908///  as references to unique objects.  Pointers are thus compared by
909///  their addresses.
910template <typename T>
911struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
912  typedef typename ImutProfileInfo<T*>::value_type      value_type;
913  typedef typename ImutProfileInfo<T*>::value_type_ref  value_type_ref;
914  typedef value_type      key_type;
915  typedef value_type_ref  key_type_ref;
916  typedef bool            data_type;
917  typedef bool            data_type_ref;
918
919  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
920  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
921
922  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
923    return LHS == RHS;
924  }
925
926  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
927    return LHS < RHS;
928  }
929
930  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
931};
932
933//===----------------------------------------------------------------------===//
934// Immutable Set
935//===----------------------------------------------------------------------===//
936
937template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
938class ImmutableSet {
939public:
940  typedef typename ValInfo::value_type      value_type;
941  typedef typename ValInfo::value_type_ref  value_type_ref;
942  typedef ImutAVLTree<ValInfo> TreeTy;
943
944private:
945  TreeTy *Root;
946
947public:
948  /// Constructs a set from a pointer to a tree root.  In general one
949  /// should use a Factory object to create sets instead of directly
950  /// invoking the constructor, but there are cases where make this
951  /// constructor public is useful.
952  explicit ImmutableSet(TreeTy* R) : Root(R) {
953    if (Root) { Root->retain(); }
954  }
955  ImmutableSet(const ImmutableSet &X) : Root(X.Root) {
956    if (Root) { Root->retain(); }
957  }
958  ImmutableSet &operator=(const ImmutableSet &X) {
959    if (Root != X.Root) {
960      if (X.Root) { X.Root->retain(); }
961      if (Root) { Root->release(); }
962      Root = X.Root;
963    }
964    return *this;
965  }
966  ~ImmutableSet() {
967    if (Root) { Root->release(); }
968  }
969
970  class Factory {
971    typename TreeTy::Factory F;
972    const bool Canonicalize;
973
974  public:
975    Factory(bool canonicalize = true)
976      : Canonicalize(canonicalize) {}
977
978    Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
979      : F(Alloc), Canonicalize(canonicalize) {}
980
981    /// getEmptySet - Returns an immutable set that contains no elements.
982    ImmutableSet getEmptySet() {
983      return ImmutableSet(F.getEmptyTree());
984    }
985
986    /// add - Creates a new immutable set that contains all of the values
987    ///  of the original set with the addition of the specified value.  If
988    ///  the original set already included the value, then the original set is
989    ///  returned and no memory is allocated.  The time and space complexity
990    ///  of this operation is logarithmic in the size of the original set.
991    ///  The memory allocated to represent the set is released when the
992    ///  factory object that created the set is destroyed.
993    ImmutableSet add(ImmutableSet Old, value_type_ref V) {
994      TreeTy *NewT = F.add(Old.Root, V);
995      return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
996    }
997
998    /// remove - Creates a new immutable set that contains all of the values
999    ///  of the original set with the exception of the specified value.  If
1000    ///  the original set did not contain the value, the original set is
1001    ///  returned and no memory is allocated.  The time and space complexity
1002    ///  of this operation is logarithmic in the size of the original set.
1003    ///  The memory allocated to represent the set is released when the
1004    ///  factory object that created the set is destroyed.
1005    ImmutableSet remove(ImmutableSet Old, value_type_ref V) {
1006      TreeTy *NewT = F.remove(Old.Root, V);
1007      return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1008    }
1009
1010    BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
1011
1012    typename TreeTy::Factory *getTreeFactory() const {
1013      return const_cast<typename TreeTy::Factory *>(&F);
1014    }
1015
1016  private:
1017    Factory(const Factory& RHS) LLVM_DELETED_FUNCTION;
1018    void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION;
1019  };
1020
1021  friend class Factory;
1022
1023  /// Returns true if the set contains the specified value.
1024  bool contains(value_type_ref V) const {
1025    return Root ? Root->contains(V) : false;
1026  }
1027
1028  bool operator==(const ImmutableSet &RHS) const {
1029    return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
1030  }
1031
1032  bool operator!=(const ImmutableSet &RHS) const {
1033    return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
1034  }
1035
1036  TreeTy *getRoot() {
1037    if (Root) { Root->retain(); }
1038    return Root;
1039  }
1040
1041  TreeTy *getRootWithoutRetain() const {
1042    return Root;
1043  }
1044
1045  /// isEmpty - Return true if the set contains no elements.
1046  bool isEmpty() const { return !Root; }
1047
1048  /// isSingleton - Return true if the set contains exactly one element.
1049  ///   This method runs in constant time.
1050  bool isSingleton() const { return getHeight() == 1; }
1051
1052  template <typename Callback>
1053  void foreach(Callback& C) { if (Root) Root->foreach(C); }
1054
1055  template <typename Callback>
1056  void foreach() { if (Root) { Callback C; Root->foreach(C); } }
1057
1058  //===--------------------------------------------------===//
1059  // Iterators.
1060  //===--------------------------------------------------===//
1061
1062  class iterator {
1063    typename TreeTy::iterator itr;
1064
1065    iterator() {}
1066    iterator(TreeTy* t) : itr(t) {}
1067    friend class ImmutableSet<ValT,ValInfo>;
1068
1069  public:
1070    typedef ptrdiff_t difference_type;
1071    typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type;
1072    typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference;
1073    typedef typename iterator::value_type *pointer;
1074    typedef std::bidirectional_iterator_tag iterator_category;
1075
1076    typename iterator::reference operator*() const { return itr->getValue(); }
1077    typename iterator::pointer   operator->() const { return &(operator*()); }
1078
1079    iterator& operator++() { ++itr; return *this; }
1080    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
1081    iterator& operator--() { --itr; return *this; }
1082    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
1083
1084    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
1085    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
1086  };
1087
1088  iterator begin() const { return iterator(Root); }
1089  iterator end() const { return iterator(); }
1090
1091  //===--------------------------------------------------===//
1092  // Utility methods.
1093  //===--------------------------------------------------===//
1094
1095  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1096
1097  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
1098    ID.AddPointer(S.Root);
1099  }
1100
1101  inline void Profile(FoldingSetNodeID& ID) const {
1102    return Profile(ID,*this);
1103  }
1104
1105  //===--------------------------------------------------===//
1106  // For testing.
1107  //===--------------------------------------------------===//
1108
1109  void validateTree() const { if (Root) Root->validateTree(); }
1110};
1111
1112// NOTE: This may some day replace the current ImmutableSet.
1113template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
1114class ImmutableSetRef {
1115public:
1116  typedef typename ValInfo::value_type      value_type;
1117  typedef typename ValInfo::value_type_ref  value_type_ref;
1118  typedef ImutAVLTree<ValInfo> TreeTy;
1119  typedef typename TreeTy::Factory          FactoryTy;
1120
1121private:
1122  TreeTy *Root;
1123  FactoryTy *Factory;
1124
1125public:
1126  /// Constructs a set from a pointer to a tree root.  In general one
1127  /// should use a Factory object to create sets instead of directly
1128  /// invoking the constructor, but there are cases where make this
1129  /// constructor public is useful.
1130  explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
1131    : Root(R),
1132      Factory(F) {
1133    if (Root) { Root->retain(); }
1134  }
1135  ImmutableSetRef(const ImmutableSetRef &X)
1136    : Root(X.Root),
1137      Factory(X.Factory) {
1138    if (Root) { Root->retain(); }
1139  }
1140  ImmutableSetRef &operator=(const ImmutableSetRef &X) {
1141    if (Root != X.Root) {
1142      if (X.Root) { X.Root->retain(); }
1143      if (Root) { Root->release(); }
1144      Root = X.Root;
1145      Factory = X.Factory;
1146    }
1147    return *this;
1148  }
1149  ~ImmutableSetRef() {
1150    if (Root) { Root->release(); }
1151  }
1152
1153  static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
1154    return ImmutableSetRef(0, F);
1155  }
1156
1157  ImmutableSetRef add(value_type_ref V) {
1158    return ImmutableSetRef(Factory->add(Root, V), Factory);
1159  }
1160
1161  ImmutableSetRef remove(value_type_ref V) {
1162    return ImmutableSetRef(Factory->remove(Root, V), Factory);
1163  }
1164
1165  /// Returns true if the set contains the specified value.
1166  bool contains(value_type_ref V) const {
1167    return Root ? Root->contains(V) : false;
1168  }
1169
1170  ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
1171    return ImmutableSet<ValT>(canonicalize ?
1172                              Factory->getCanonicalTree(Root) : Root);
1173  }
1174
1175  TreeTy *getRootWithoutRetain() const {
1176    return Root;
1177  }
1178
1179  bool operator==(const ImmutableSetRef &RHS) const {
1180    return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
1181  }
1182
1183  bool operator!=(const ImmutableSetRef &RHS) const {
1184    return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
1185  }
1186
1187  /// isEmpty - Return true if the set contains no elements.
1188  bool isEmpty() const { return !Root; }
1189
1190  /// isSingleton - Return true if the set contains exactly one element.
1191  ///   This method runs in constant time.
1192  bool isSingleton() const { return getHeight() == 1; }
1193
1194  //===--------------------------------------------------===//
1195  // Iterators.
1196  //===--------------------------------------------------===//
1197
1198  class iterator {
1199    typename TreeTy::iterator itr;
1200    iterator(TreeTy* t) : itr(t) {}
1201    friend class ImmutableSetRef<ValT,ValInfo>;
1202  public:
1203    iterator() {}
1204    inline value_type_ref operator*() const { return itr->getValue(); }
1205    inline iterator& operator++() { ++itr; return *this; }
1206    inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
1207    inline iterator& operator--() { --itr; return *this; }
1208    inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
1209    inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
1210    inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
1211    inline value_type *operator->() const { return &(operator*()); }
1212  };
1213
1214  iterator begin() const { return iterator(Root); }
1215  iterator end() const { return iterator(); }
1216
1217  //===--------------------------------------------------===//
1218  // Utility methods.
1219  //===--------------------------------------------------===//
1220
1221  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1222
1223  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) {
1224    ID.AddPointer(S.Root);
1225  }
1226
1227  inline void Profile(FoldingSetNodeID& ID) const {
1228    return Profile(ID,*this);
1229  }
1230
1231  //===--------------------------------------------------===//
1232  // For testing.
1233  //===--------------------------------------------------===//
1234
1235  void validateTree() const { if (Root) Root->validateTree(); }
1236};
1237
1238} // end namespace llvm
1239
1240#endif
1241