LLVM  6.0.0svn
ImmutableSet.h
Go to the documentation of this file.
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/ADT/SmallVector.h"
20 #include "llvm/ADT/iterator.h"
21 #include "llvm/Support/Allocator.h"
23 #include <cassert>
24 #include <cstdint>
25 #include <functional>
26 #include <iterator>
27 #include <new>
28 #include <vector>
29 
30 namespace llvm {
31 
32 //===----------------------------------------------------------------------===//
33 // Immutable AVL-Tree Definition.
34 //===----------------------------------------------------------------------===//
35 
36 template <typename ImutInfo> class ImutAVLFactory;
37 template <typename ImutInfo> class ImutIntervalAVLFactory;
38 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
39 template <typename ImutInfo> class ImutAVLTreeGenericIterator;
40 
41 template <typename ImutInfo >
42 class ImutAVLTree {
43 public:
44  using key_type_ref = typename ImutInfo::key_type_ref;
45  using value_type = typename ImutInfo::value_type;
46  using value_type_ref = typename ImutInfo::value_type_ref;
49 
50  friend class ImutAVLFactory<ImutInfo>;
51  friend class ImutIntervalAVLFactory<ImutInfo>;
52  friend class ImutAVLTreeGenericIterator<ImutInfo>;
53 
54  //===----------------------------------------------------===//
55  // Public Interface.
56  //===----------------------------------------------------===//
57 
58  /// Return a pointer to the left subtree. This value
59  /// is NULL if there is no left subtree.
60  ImutAVLTree *getLeft() const { return left; }
61 
62  /// Return a pointer to the right subtree. This value is
63  /// NULL if there is no right subtree.
64  ImutAVLTree *getRight() const { return right; }
65 
66  /// getHeight - Returns the height of the tree. A tree with no subtrees
67  /// has a height of 1.
68  unsigned getHeight() const { return height; }
69 
70  /// getValue - Returns the data value associated with the tree node.
71  const value_type& getValue() const { return value; }
72 
73  /// find - Finds the subtree associated with the specified key value.
74  /// This method returns NULL if no matching subtree is found.
76  ImutAVLTree *T = this;
77  while (T) {
78  key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
79  if (ImutInfo::isEqual(K,CurrentKey))
80  return T;
81  else if (ImutInfo::isLess(K,CurrentKey))
82  T = T->getLeft();
83  else
84  T = T->getRight();
85  }
86  return nullptr;
87  }
88 
89  /// getMaxElement - Find the subtree associated with the highest ranged
90  /// key value.
92  ImutAVLTree *T = this;
93  ImutAVLTree *Right = T->getRight();
94  while (Right) { T = Right; Right = T->getRight(); }
95  return T;
96  }
97 
98  /// size - Returns the number of nodes in the tree, which includes
99  /// both leaves and non-leaf nodes.
100  unsigned size() const {
101  unsigned n = 1;
102  if (const ImutAVLTree* L = getLeft())
103  n += L->size();
104  if (const ImutAVLTree* R = getRight())
105  n += R->size();
106  return n;
107  }
108 
109  /// begin - Returns an iterator that iterates over the nodes of the tree
110  /// in an inorder traversal. The returned iterator thus refers to the
111  /// the tree node with the minimum data element.
112  iterator begin() const { return iterator(this); }
113 
114  /// end - Returns an iterator for the tree that denotes the end of an
115  /// inorder traversal.
116  iterator end() const { return iterator(); }
117 
119  // Compare the keys.
120  if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
121  ImutInfo::KeyOfValue(V)))
122  return false;
123 
124  // Also compare the data values.
125  if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
126  ImutInfo::DataOfValue(V)))
127  return false;
128 
129  return true;
130  }
131 
132  bool isElementEqual(const ImutAVLTree* RHS) const {
133  return isElementEqual(RHS->getValue());
134  }
135 
136  /// isEqual - Compares two trees for structural equality and returns true
137  /// if they are equal. This worst case performance of this operation is
138  // linear in the sizes of the trees.
139  bool isEqual(const ImutAVLTree& RHS) const {
140  if (&RHS == this)
141  return true;
142 
143  iterator LItr = begin(), LEnd = end();
144  iterator RItr = RHS.begin(), REnd = RHS.end();
145 
146  while (LItr != LEnd && RItr != REnd) {
147  if (&*LItr == &*RItr) {
148  LItr.skipSubTree();
149  RItr.skipSubTree();
150  continue;
151  }
152 
153  if (!LItr->isElementEqual(&*RItr))
154  return false;
155 
156  ++LItr;
157  ++RItr;
158  }
159 
160  return LItr == LEnd && RItr == REnd;
161  }
162 
163  /// isNotEqual - Compares two trees for structural inequality. Performance
164  /// is the same is isEqual.
165  bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
166 
167  /// contains - Returns true if this tree contains a subtree (node) that
168  /// has an data element that matches the specified key. Complexity
169  /// is logarithmic in the size of the tree.
170  bool contains(key_type_ref K) { return (bool) find(K); }
171 
172  /// foreach - A member template the accepts invokes operator() on a functor
173  /// object (specifed by Callback) for every node/subtree in the tree.
174  /// Nodes are visited using an inorder traversal.
175  template <typename Callback>
176  void foreach(Callback& C) {
177  if (ImutAVLTree* L = getLeft())
178  L->foreach(C);
179 
180  C(value);
181 
182  if (ImutAVLTree* R = getRight())
183  R->foreach(C);
184  }
185 
186  /// validateTree - A utility method that checks that the balancing and
187  /// ordering invariants of the tree are satisifed. It is a recursive
188  /// method that returns the height of the tree, which is then consumed
189  /// by the enclosing validateTree call. External callers should ignore the
190  /// return value. An invalid tree will cause an assertion to fire in
191  /// a debug build.
192  unsigned validateTree() const {
193  unsigned HL = getLeft() ? getLeft()->validateTree() : 0;
194  unsigned HR = getRight() ? getRight()->validateTree() : 0;
195  (void) HL;
196  (void) HR;
197 
198  assert(getHeight() == ( HL > HR ? HL : HR ) + 1
199  && "Height calculation wrong");
200 
201  assert((HL > HR ? HL-HR : HR-HL) <= 2
202  && "Balancing invariant violated");
203 
204  assert((!getLeft() ||
205  ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
206  ImutInfo::KeyOfValue(getValue()))) &&
207  "Value in left child is not less that current value");
208 
209 
210  assert(!(getRight() ||
211  ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
212  ImutInfo::KeyOfValue(getRight()->getValue()))) &&
213  "Current value is not less that value of right child");
214 
215  return getHeight();
216  }
217 
218  //===----------------------------------------------------===//
219  // Internal values.
220  //===----------------------------------------------------===//
221 
222 private:
223  Factory *factory;
224  ImutAVLTree *left;
225  ImutAVLTree *right;
226  ImutAVLTree *prev = nullptr;
227  ImutAVLTree *next = nullptr;
228 
229  unsigned height : 28;
230  bool IsMutable : 1;
231  bool IsDigestCached : 1;
232  bool IsCanonicalized : 1;
233 
234  value_type value;
235  uint32_t digest = 0;
236  uint32_t refCount = 0;
237 
238  //===----------------------------------------------------===//
239  // Internal methods (node manipulation; used by Factory).
240  //===----------------------------------------------------===//
241 
242 private:
243  /// ImutAVLTree - Internal constructor that is only called by
244  /// ImutAVLFactory.
246  unsigned height)
247  : factory(f), left(l), right(r), height(height), IsMutable(true),
248  IsDigestCached(false), IsCanonicalized(false), value(v)
249  {
250  if (left) left->retain();
251  if (right) right->retain();
252  }
253 
254  /// isMutable - Returns true if the left and right subtree references
255  /// (as well as height) can be changed. If this method returns false,
256  /// the tree is truly immutable. Trees returned from an ImutAVLFactory
257  /// object should always have this method return true. Further, if this
258  /// method returns false for an instance of ImutAVLTree, all subtrees
259  /// will also have this method return false. The converse is not true.
260  bool isMutable() const { return IsMutable; }
261 
262  /// hasCachedDigest - Returns true if the digest for this tree is cached.
263  /// This can only be true if the tree is immutable.
264  bool hasCachedDigest() const { return IsDigestCached; }
265 
266  //===----------------------------------------------------===//
267  // Mutating operations. A tree root can be manipulated as
268  // long as its reference has not "escaped" from internal
269  // methods of a factory object (see below). When a tree
270  // pointer is externally viewable by client code, the
271  // internal "mutable bit" is cleared to mark the tree
272  // immutable. Note that a tree that still has its mutable
273  // bit set may have children (subtrees) that are themselves
274  // immutable.
275  //===----------------------------------------------------===//
276 
277  /// markImmutable - Clears the mutable flag for a tree. After this happens,
278  /// it is an error to call setLeft(), setRight(), and setHeight().
279  void markImmutable() {
280  assert(isMutable() && "Mutable flag already removed.");
281  IsMutable = false;
282  }
283 
284  /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
285  void markedCachedDigest() {
286  assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
287  IsDigestCached = true;
288  }
289 
290  /// setHeight - Changes the height of the tree. Used internally by
291  /// ImutAVLFactory.
292  void setHeight(unsigned h) {
293  assert(isMutable() && "Only a mutable tree can have its height changed.");
294  height = h;
295  }
296 
297  static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
298  value_type_ref V) {
299  uint32_t digest = 0;
300 
301  if (L)
302  digest += L->computeDigest();
303 
304  // Compute digest of stored data.
306  ImutInfo::Profile(ID,V);
307  digest += ID.ComputeHash();
308 
309  if (R)
310  digest += R->computeDigest();
311 
312  return digest;
313  }
314 
315  uint32_t computeDigest() {
316  // Check the lowest bit to determine if digest has actually been
317  // pre-computed.
318  if (hasCachedDigest())
319  return digest;
320 
321  uint32_t X = computeDigest(getLeft(), getRight(), getValue());
322  digest = X;
323  markedCachedDigest();
324  return X;
325  }
326 
327  //===----------------------------------------------------===//
328  // Reference count operations.
329  //===----------------------------------------------------===//
330 
331 public:
332  void retain() { ++refCount; }
333 
334  void release() {
335  assert(refCount > 0);
336  if (--refCount == 0)
337  destroy();
338  }
339 
340  void destroy() {
341  if (left)
342  left->release();
343  if (right)
344  right->release();
345  if (IsCanonicalized) {
346  if (next)
347  next->prev = prev;
348 
349  if (prev)
350  prev->next = next;
351  else
352  factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
353  }
354 
355  // We need to clear the mutability bit in case we are
356  // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
357  IsMutable = false;
358  factory->freeNodes.push_back(this);
359  }
360 };
361 
362 //===----------------------------------------------------------------------===//
363 // Immutable AVL-Tree Factory class.
364 //===----------------------------------------------------------------------===//
365 
366 template <typename ImutInfo >
367 class ImutAVLFactory {
368  friend class ImutAVLTree<ImutInfo>;
369 
371  using value_type_ref = typename TreeTy::value_type_ref;
372  using key_type_ref = typename TreeTy::key_type_ref;
374 
375  CacheTy Cache;
376  uintptr_t Allocator;
377  std::vector<TreeTy*> createdNodes;
378  std::vector<TreeTy*> freeNodes;
379 
380  bool ownsAllocator() const {
381  return (Allocator & 0x1) == 0;
382  }
383 
384  BumpPtrAllocator& getAllocator() const {
385  return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
386  }
387 
388  //===--------------------------------------------------===//
389  // Public interface.
390  //===--------------------------------------------------===//
391 
392 public:
394  : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
395 
397  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
398 
400  if (ownsAllocator()) delete &getAllocator();
401  }
402 
403  TreeTy* add(TreeTy* T, value_type_ref V) {
404  T = add_internal(V,T);
405  markImmutable(T);
406  recoverNodes();
407  return T;
408  }
409 
410  TreeTy* remove(TreeTy* T, key_type_ref V) {
411  T = remove_internal(V,T);
412  markImmutable(T);
413  recoverNodes();
414  return T;
415  }
416 
417  TreeTy* getEmptyTree() const { return nullptr; }
418 
419 protected:
420  //===--------------------------------------------------===//
421  // A bunch of quick helper functions used for reasoning
422  // about the properties of trees and their children.
423  // These have succinct names so that the balancing code
424  // is as terse (and readable) as possible.
425  //===--------------------------------------------------===//
426 
427  bool isEmpty(TreeTy* T) const { return !T; }
428  unsigned getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
429  TreeTy* getLeft(TreeTy* T) const { return T->getLeft(); }
430  TreeTy* getRight(TreeTy* T) const { return T->getRight(); }
431  value_type_ref getValue(TreeTy* T) const { return T->value; }
432 
433  // Make sure the index is not the Tombstone or Entry key of the DenseMap.
434  static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
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 
607 public:
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 
649 template <typename ImutInfo>
651  : public std::iterator<std::bidirectional_iterator_tag,
652  ImutAVLTree<ImutInfo>> {
654 
655 public:
656  enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
657  Flags=0x3 };
658 
659  using TreeTy = ImutAVLTree<ImutInfo>;
660 
661  ImutAVLTreeGenericIterator() = default;
662  ImutAVLTreeGenericIterator(const TreeTy *Root) {
663  if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
664  }
665 
666  TreeTy &operator*() const {
667  assert(!stack.empty());
668  return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
669  }
670  TreeTy *operator->() const { return &*this; }
671 
672  uintptr_t getVisitState() const {
673  assert(!stack.empty());
674  return stack.back() & Flags;
675  }
676 
677  bool atEnd() const { return stack.empty(); }
678 
679  bool atBeginning() const {
680  return stack.size() == 1 && getVisitState() == VisitedNone;
681  }
682 
683  void skipToParent() {
684  assert(!stack.empty());
685  stack.pop_back();
686  if (stack.empty())
687  return;
688  switch (getVisitState()) {
689  case VisitedNone:
690  stack.back() |= VisitedLeft;
691  break;
692  case VisitedLeft:
693  stack.back() |= VisitedRight;
694  break;
695  default:
696  llvm_unreachable("Unreachable.");
697  }
698  }
699 
700  bool operator==(const ImutAVLTreeGenericIterator &x) const {
701  return stack == x.stack;
702  }
703 
704  bool operator!=(const ImutAVLTreeGenericIterator &x) const {
705  return !(*this == x);
706  }
707 
709  assert(!stack.empty());
710  TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
711  assert(Current);
712  switch (getVisitState()) {
713  case VisitedNone:
714  if (TreeTy* L = Current->getLeft())
715  stack.push_back(reinterpret_cast<uintptr_t>(L));
716  else
717  stack.back() |= VisitedLeft;
718  break;
719  case VisitedLeft:
720  if (TreeTy* R = Current->getRight())
721  stack.push_back(reinterpret_cast<uintptr_t>(R));
722  else
723  stack.back() |= VisitedRight;
724  break;
725  case VisitedRight:
726  skipToParent();
727  break;
728  default:
729  llvm_unreachable("Unreachable.");
730  }
731  return *this;
732  }
733 
735  assert(!stack.empty());
736  TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
737  assert(Current);
738  switch (getVisitState()) {
739  case VisitedNone:
740  stack.pop_back();
741  break;
742  case VisitedLeft:
743  stack.back() &= ~Flags; // Set state to "VisitedNone."
744  if (TreeTy* L = Current->getLeft())
745  stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
746  break;
747  case VisitedRight:
748  stack.back() &= ~Flags;
749  stack.back() |= VisitedLeft;
750  if (TreeTy* R = Current->getRight())
751  stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
752  break;
753  default:
754  llvm_unreachable("Unreachable.");
755  }
756  return *this;
757  }
758 };
759 
760 template <typename ImutInfo>
762  : public std::iterator<std::bidirectional_iterator_tag,
763  ImutAVLTree<ImutInfo>> {
764  using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>;
765 
766  InternalIteratorTy InternalItr;
767 
768 public:
769  using TreeTy = ImutAVLTree<ImutInfo>;
770 
771  ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
772  if (Root)
773  ++*this; // Advance to first element.
774  }
775 
776  ImutAVLTreeInOrderIterator() : InternalItr() {}
777 
778  bool operator==(const ImutAVLTreeInOrderIterator &x) const {
779  return InternalItr == x.InternalItr;
780  }
781 
782  bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
783  return !(*this == x);
784  }
785 
786  TreeTy &operator*() const { return *InternalItr; }
787  TreeTy *operator->() const { return &*InternalItr; }
788 
790  do ++InternalItr;
791  while (!InternalItr.atEnd() &&
792  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
793 
794  return *this;
795  }
796 
798  do --InternalItr;
799  while (!InternalItr.atBeginning() &&
800  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
801 
802  return *this;
803  }
804 
805  void skipSubTree() {
806  InternalItr.skipToParent();
807 
808  while (!InternalItr.atEnd() &&
809  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
810  ++InternalItr;
811  }
812 };
813 
814 /// Generic iterator that wraps a T::TreeTy::iterator and exposes
815 /// iterator::getValue() on dereference.
816 template <typename T>
819  ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
820  typename std::iterator_traits<
821  typename T::TreeTy::iterator>::iterator_category,
822  const typename T::value_type> {
823  ImutAVLValueIterator() = default;
824  explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
826 
827  typename ImutAVLValueIterator::reference operator*() const {
828  return this->I->getValue();
829  }
830 };
831 
832 //===----------------------------------------------------------------------===//
833 // Trait classes for Profile information.
834 //===----------------------------------------------------------------------===//
835 
836 /// Generic profile template. The default behavior is to invoke the
837 /// profile method of an object. Specializations for primitive integers
838 /// and generic handling of pointers is done below.
839 template <typename T>
841  using value_type = const T;
842  using value_type_ref = const T&;
843 
846  }
847 };
848 
849 /// Profile traits for integers.
850 template <typename T>
852  using value_type = const T;
853  using value_type_ref = const T&;
854 
856  ID.AddInteger(X);
857  }
858 };
859 
860 #define PROFILE_INTEGER_INFO(X)\
861 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
862 
864 PROFILE_INTEGER_INFO(unsigned char)
866 PROFILE_INTEGER_INFO(unsigned short)
867 PROFILE_INTEGER_INFO(unsigned)
868 PROFILE_INTEGER_INFO(signed)
870 PROFILE_INTEGER_INFO(unsigned long)
871 PROFILE_INTEGER_INFO(long long)
872 PROFILE_INTEGER_INFO(unsigned long long)
873 
874 #undef PROFILE_INTEGER_INFO
875 
876 /// Profile traits for booleans.
877 template <>
879  using value_type = const bool;
880  using value_type_ref = const bool&;
881 
883  ID.AddBoolean(X);
884  }
885 };
886 
887 /// Generic profile trait for pointer types. We treat pointers as
888 /// references to unique objects.
889 template <typename T>
890 struct ImutProfileInfo<T*> {
891  using value_type = const T*;
893 
895  ID.AddPointer(X);
896  }
897 };
898 
899 //===----------------------------------------------------------------------===//
900 // Trait classes that contain element comparison operators and type
901 // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
902 // inherit from the profile traits (ImutProfileInfo) to include operations
903 // for element profiling.
904 //===----------------------------------------------------------------------===//
905 
906 /// ImutContainerInfo - Generic definition of comparison operations for
907 /// elements of immutable containers that defaults to using
908 /// std::equal_to<> and std::less<> to perform comparison of elements.
909 template <typename T>
910 struct ImutContainerInfo : public ImutProfileInfo<T> {
915  using data_type = bool;
917 
919  static data_type_ref DataOfValue(value_type_ref) { return true; }
920 
921  static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
922  return std::equal_to<key_type>()(LHS,RHS);
923  }
924 
925  static bool isLess(key_type_ref LHS, key_type_ref RHS) {
926  return std::less<key_type>()(LHS,RHS);
927  }
928 
929  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
930 };
931 
932 /// ImutContainerInfo - Specialization for pointer values to treat pointers
933 /// as references to unique objects. Pointers are thus compared by
934 /// their addresses.
935 template <typename T>
941  using data_type = bool;
943 
945  static data_type_ref DataOfValue(value_type_ref) { return true; }
946 
947  static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
948 
949  static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
950 
951  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
952 };
953 
954 //===----------------------------------------------------------------------===//
955 // Immutable Set
956 //===----------------------------------------------------------------------===//
957 
958 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
960 public:
961  using value_type = typename ValInfo::value_type;
962  using value_type_ref = typename ValInfo::value_type_ref;
963  using TreeTy = ImutAVLTree<ValInfo>;
964 
965 private:
966  TreeTy *Root;
967 
968 public:
969  /// Constructs a set from a pointer to a tree root. In general one
970  /// should use a Factory object to create sets instead of directly
971  /// invoking the constructor, but there are cases where make this
972  /// constructor public is useful.
973  explicit ImmutableSet(TreeTy* R) : Root(R) {
974  if (Root) { Root->retain(); }
975  }
976 
977  ImmutableSet(const ImmutableSet &X) : Root(X.Root) {
978  if (Root) { Root->retain(); }
979  }
980 
982  if (Root) { Root->release(); }
983  }
984 
986  if (Root != X.Root) {
987  if (X.Root) { X.Root->retain(); }
988  if (Root) { Root->release(); }
989  Root = X.Root;
990  }
991  return *this;
992  }
993 
994  class Factory {
995  typename TreeTy::Factory F;
996  const bool Canonicalize;
997 
998  public:
999  Factory(bool canonicalize = true)
1000  : Canonicalize(canonicalize) {}
1001 
1002  Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
1003  : F(Alloc), Canonicalize(canonicalize) {}
1004 
1005  Factory(const Factory& RHS) = delete;
1006  void operator=(const Factory& RHS) = delete;
1007 
1008  /// getEmptySet - Returns an immutable set that contains no elements.
1010  return ImmutableSet(F.getEmptyTree());
1011  }
1012 
1013  /// add - Creates a new immutable set that contains all of the values
1014  /// of the original set with the addition of the specified value. If
1015  /// the original set already included the value, then the original set is
1016  /// returned and no memory is allocated. The time and space complexity
1017  /// of this operation is logarithmic in the size of the original set.
1018  /// The memory allocated to represent the set is released when the
1019  /// factory object that created the set is destroyed.
1021  TreeTy *NewT = F.add(Old.Root, V);
1022  return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1023  }
1024 
1025  /// remove - Creates a new immutable set that contains all of the values
1026  /// of the original set with the exception of the specified value. If
1027  /// the original set did not contain the value, the original set is
1028  /// returned and no memory is allocated. The time and space complexity
1029  /// of this operation is logarithmic in the size of the original set.
1030  /// The memory allocated to represent the set is released when the
1031  /// factory object that created the set is destroyed.
1033  TreeTy *NewT = F.remove(Old.Root, V);
1034  return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1035  }
1036 
1037  BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
1038 
1039  typename TreeTy::Factory *getTreeFactory() const {
1040  return const_cast<typename TreeTy::Factory *>(&F);
1041  }
1042  };
1043 
1044  friend class Factory;
1045 
1046  /// Returns true if the set contains the specified value.
1047  bool contains(value_type_ref V) const {
1048  return Root ? Root->contains(V) : false;
1049  }
1050 
1051  bool operator==(const ImmutableSet &RHS) const {
1052  return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
1053  }
1054 
1055  bool operator!=(const ImmutableSet &RHS) const {
1056  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
1057  }
1058 
1059  TreeTy *getRoot() {
1060  if (Root) { Root->retain(); }
1061  return Root;
1062  }
1063 
1064  TreeTy *getRootWithoutRetain() const {
1065  return Root;
1066  }
1067 
1068  /// isEmpty - Return true if the set contains no elements.
1069  bool isEmpty() const { return !Root; }
1070 
1071  /// isSingleton - Return true if the set contains exactly one element.
1072  /// This method runs in constant time.
1073  bool isSingleton() const { return getHeight() == 1; }
1074 
1075  template <typename Callback>
1076  void foreach(Callback& C) { if (Root) Root->foreach(C); }
1077 
1078  template <typename Callback>
1079  void foreach() { if (Root) { Callback C; Root->foreach(C); } }
1080 
1081  //===--------------------------------------------------===//
1082  // Iterators.
1083  //===--------------------------------------------------===//
1084 
1086 
1087  iterator begin() const { return iterator(Root); }
1088  iterator end() const { return iterator(); }
1089 
1090  //===--------------------------------------------------===//
1091  // Utility methods.
1092  //===--------------------------------------------------===//
1093 
1094  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1095 
1096  static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
1097  ID.AddPointer(S.Root);
1098  }
1099 
1100  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1101 
1102  //===--------------------------------------------------===//
1103  // For testing.
1104  //===--------------------------------------------------===//
1105 
1106  void validateTree() const { if (Root) Root->validateTree(); }
1107 };
1108 
1109 // NOTE: This may some day replace the current ImmutableSet.
1110 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
1112 public:
1113  using value_type = typename ValInfo::value_type;
1114  using value_type_ref = typename ValInfo::value_type_ref;
1115  using TreeTy = ImutAVLTree<ValInfo>;
1116  using FactoryTy = typename TreeTy::Factory;
1117 
1118 private:
1119  TreeTy *Root;
1120  FactoryTy *Factory;
1121 
1122 public:
1123  /// Constructs a set from a pointer to a tree root. In general one
1124  /// should use a Factory object to create sets instead of directly
1125  /// invoking the constructor, but there are cases where make this
1126  /// constructor public is useful.
1127  explicit ImmutableSetRef(TreeTy* R, FactoryTy *F)
1128  : Root(R),
1129  Factory(F) {
1130  if (Root) { Root->retain(); }
1131  }
1132 
1134  : Root(X.Root),
1135  Factory(X.Factory) {
1136  if (Root) { Root->retain(); }
1137  }
1138 
1140  if (Root) { Root->release(); }
1141  }
1142 
1144  if (Root != X.Root) {
1145  if (X.Root) { X.Root->retain(); }
1146  if (Root) { Root->release(); }
1147  Root = X.Root;
1148  Factory = X.Factory;
1149  }
1150  return *this;
1151  }
1152 
1154  return ImmutableSetRef(0, F);
1155  }
1156 
1158  return ImmutableSetRef(Factory->add(Root, V), Factory);
1159  }
1160 
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 
1199 
1200  iterator begin() const { return iterator(Root); }
1201  iterator end() const { return iterator(); }
1202 
1203  //===--------------------------------------------------===//
1204  // Utility methods.
1205  //===--------------------------------------------------===//
1206 
1207  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1208 
1209  static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
1210  ID.AddPointer(S.Root);
1211  }
1212 
1213  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1214 
1215  //===--------------------------------------------------===//
1216  // For testing.
1217  //===--------------------------------------------------===//
1218 
1219  void validateTree() const { if (Root) Root->validateTree(); }
1220 };
1221 
1222 } // end namespace llvm
1223 
1224 #endif // LLVM_ADT_IMMUTABLESET_H
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference...
Definition: ImmutableSet.h:817
unsigned getHeight() const
getHeight - Returns the height of the tree.
Definition: ImmutableSet.h:68
uint64_t CallInst * C
ImmutableSet add(ImmutableSet Old, value_type_ref V)
add - Creates a new immutable set that contains all of the values of the original set with the additi...
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:52
ImmutableSetRef(const ImmutableSetRef &X)
void push_back(const T &Elt)
Definition: SmallVector.h:212
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:894
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
TreeTy * getRootWithoutRetain() const
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:855
static bool isDataEqual(data_type_ref, data_type_ref)
Definition: ImmutableSet.h:951
Generic profile trait for pointer types.
Definition: ImmutableSet.h:890
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
TreeTy * balanceTree(TreeTy *L, value_type_ref V, TreeTy *R)
balanceTree - Used by add_internal and remove_internal to balance a newly created tree...
Definition: ImmutableSet.h:494
typename ImutInfo::value_type value_type
Definition: ImmutableSet.h:45
static data_type_ref DataOfValue(value_type_ref)
Definition: ImmutableSet.h:919
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
void Profile(FoldingSetNodeID &ID) const
TreeTy * add(TreeTy *T, value_type_ref V)
Definition: ImmutableSet.h:403
iterator begin() const
begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal...
Definition: ImmutableSet.h:112
typename ImutInfo::key_type_ref key_type_ref
Definition: ImmutableSet.h:44
ImutAVLValueIterator::reference operator*() const
Definition: ImmutableSet.h:827
BumpPtrAllocator & getAllocator()
TreeTy * remove_internal(key_type_ref K, TreeTy *T)
remove_internal - Creates a new tree that includes all the data from the original tree except the spe...
Definition: ImmutableSet.h:558
ImutAVLTreeInOrderIterator & operator--()
Definition: ImmutableSet.h:797
typename TreeTy::Factory FactoryTy
bool operator==(const ImutAVLTreeGenericIterator &x) const
Definition: ImmutableSet.h:700
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
TreeTy * createNode(TreeTy *newLeft, TreeTy *oldTree, TreeTy *newRight)
Definition: ImmutableSet.h:479
ImutAVLTreeGenericIterator(const TreeTy *Root)
Definition: ImmutableSet.h:662
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:226
ImmutableSet & operator=(const ImmutableSet &X)
Definition: ImmutableSet.h:985
bool isNotEqual(const ImutAVLTree &RHS) const
isNotEqual - Compares two trees for structural inequality.
Definition: ImmutableSet.h:165
unsigned ComputeHash() const
ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to lookup the node in the F...
Definition: FoldingSet.cpp:146
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
TreeTy::Factory * getTreeFactory() const
ImutAVLTree * getMaxElement()
getMaxElement - Find the subtree associated with the highest ranged key value.
Definition: ImmutableSet.h:91
TreeTy * getRight(TreeTy *T) const
Definition: ImmutableSet.h:430
iterator end() const
static ImmutableSetRef getEmptySet(FactoryTy *F)
TreeTy * createNode(TreeTy *L, value_type_ref V, TreeTy *R)
Definition: ImmutableSet.h:463
ImutAVLTreeInOrderIterator & operator++()
Definition: ImmutableSet.h:789
bool isEqual(const ImutAVLTree &RHS) const
isEqual - Compares two trees for structural equality and returns true if they are equal...
Definition: ImmutableSet.h:139
Generic profile template.
Definition: ImmutableSet.h:840
typename ImutProfileInfo< T * >::value_type_ref value_type_ref
Definition: ImmutableSet.h:938
void AddInteger(signed I)
Definition: FoldingSet.cpp:61
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:947
static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S)
ImutAVLFactory< ImutInfo > Factory
Definition: ImmutableSet.h:47
static bool compareTreeWithSection(TreeTy *T, typename TreeTy::iterator &TI, typename TreeTy::iterator &TE)
Definition: ImmutableSet.h:442
static data_type_ref DataOfValue(value_type_ref)
Definition: ImmutableSet.h:945
ImmutableSetRef add(value_type_ref V)
void Profile(FoldingSetNodeID &ID) const
#define PROFILE_INTEGER_INFO(X)
Definition: ImmutableSet.h:860
ImmutableSet getEmptySet()
getEmptySet - Returns an immutable set that contains no elements.
#define F(x, y, z)
Definition: MD5.cpp:55
static bool isEqual(const Function &Caller, const Function &Callee)
#define T
unsigned validateTree() const
validateTree - A utility method that checks that the balancing and ordering invariants of the tree ar...
Definition: ImmutableSet.h:192
ImmutableSetRef(TreeTy *R, FactoryTy *F)
Constructs a set from a pointer to a tree root.
bool operator!=(const ImmutableSet &RHS) const
ImutAVLValueIterator(typename T::TreeTy *Tree)
Definition: ImmutableSet.h:824
Profile traits for integers.
Definition: ImmutableSet.h:851
void foreach(Callback &C)
foreach - A member template the accepts invokes operator() on a functor object (specifed by Callback)...
Definition: ImmutableSet.h:176
bool isElementEqual(const ImutAVLTree *RHS) const
Definition: ImmutableSet.h:132
static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S)
bool operator!=(const ImmutableSetRef &RHS) const
bool operator!=(const ImutAVLTreeGenericIterator &x) const
Definition: ImmutableSet.h:704
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:311
iterator end() const
end - Returns an iterator for the tree that denotes the end of an inorder traversal.
Definition: ImmutableSet.h:116
Factory(bool canonicalize=true)
Definition: ImmutableSet.h:999
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
TreeTy * getLeft(TreeTy *T) const
Definition: ImmutableSet.h:429
TreeTy * add_internal(value_type_ref V, TreeTy *T)
add_internal - Creates a new tree that includes the specified data and the data from the original tre...
Definition: ImmutableSet.h:538
bool isEmpty(TreeTy *T) const
Definition: ImmutableSet.h:427
iterator begin() const
TreeTy * getEmptyTree() const
Definition: ImmutableSet.h:417
TreeTy * remove(TreeTy *T, key_type_ref V)
Definition: ImmutableSet.h:410
ImutAVLTreeGenericIterator & operator--()
Definition: ImmutableSet.h:734
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
bool operator==(const ImmutableSetRef &RHS) const
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:212
#define A
Definition: LargeTest.cpp:12
ImutAVLTree * find(key_type_ref K)
find - Finds the subtree associated with the specified key value.
Definition: ImmutableSet.h:75
void AddBoolean(bool B)
Definition: FoldingSet.h:331
void markImmutable(TreeTy *T)
markImmutable - Clears the mutable bits of a root and all of its descendants.
Definition: ImmutableSet.h:599
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:882
ImutAVLTreeInOrderIterator(const TreeTy *Root)
Definition: ImmutableSet.h:771
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:921
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
typename ImutInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:46
void validateTree() const
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
value_type_ref getValue(TreeTy *T) const
Definition: ImmutableSet.h:431
bool operator!=(const ImutAVLTreeInOrderIterator &x) const
Definition: ImmutableSet.h:782
iterator end() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool contains(key_type_ref K)
contains - Returns true if this tree contains a subtree (node) that has an data element that matches ...
Definition: ImmutableSet.h:170
TreeTy * getRootWithoutRetain() const
Basic Register Allocator
bool operator==(const ImutAVLTreeInOrderIterator &x) const
Definition: ImmutableSet.h:778
#define E
Definition: LargeTest.cpp:27
const value_type & getValue() const
getValue - Returns the data value associated with the tree node.
Definition: ImmutableSet.h:71
unsigned getHeight() const
Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:962
typename ValInfo::value_type value_type
Definition: ImmutableSet.h:961
const size_t N
typename ImutProfileInfo< T * >::value_type value_type
Definition: ImmutableSet.h:937
unsigned getHeight(TreeTy *T) const
Definition: ImmutableSet.h:428
ImmutableSetRef & operator=(const ImmutableSetRef &X)
static key_type_ref KeyOfValue(value_type_ref D)
Definition: ImmutableSet.h:944
TreeTy * getCanonicalTree(TreeTy *TNew)
Definition: ImmutableSet.h:608
static bool isDataEqual(data_type_ref, data_type_ref)
Definition: ImmutableSet.h:929
TreeTy * combineTrees(TreeTy *L, TreeTy *R)
Definition: ImmutableSet.h:577
TreeTy * removeMinBinding(TreeTy *T, TreeTy *&Noderemoved)
Definition: ImmutableSet.h:587
ImutAVLFactory(BumpPtrAllocator &Alloc)
Definition: ImmutableSet.h:396
unsigned size() const
size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes...
Definition: ImmutableSet.h:100
static std::vector< std::string > Flags
Definition: FlagsTest.cpp:8
ImutAVLTreeInOrderIterator< ImutInfo > iterator
Definition: ImmutableSet.h:48
ImutAVLTreeGenericIterator & operator++()
Definition: ImmutableSet.h:708
void validateTree() const
static key_type_ref KeyOfValue(value_type_ref D)
Definition: ImmutableSet.h:918
ImmutableSet(TreeTy *R)
Constructs a set from a pointer to a tree root.
Definition: ImmutableSet.h:973
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define I(x, y, z)
Definition: MD5.cpp:58
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:949
ImmutableSet(const ImmutableSet &X)
Definition: ImmutableSet.h:977
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:925
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ImutAVLTree * getRight() const
Return a pointer to the right subtree.
Definition: ImmutableSet.h:64
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:844
ImmutableSet< ValT > asImmutableSet(bool canonicalize=true) const
unsigned getHeight() const
typename ValInfo::value_type_ref value_type_ref
bool isElementEqual(value_type_ref V) const
Definition: ImmutableSet.h:118
unsigned incrementHeight(TreeTy *L, TreeTy *R) const
Definition: ImmutableSet.h:436
iterator begin() const
ImutContainerInfo - Generic definition of comparison operations for elements of immutable containers ...
Definition: ImmutableSet.h:910
static unsigned maskCacheIndex(unsigned I)
Definition: ImmutableSet.h:434
#define D
Definition: LargeTest.cpp:26
bool operator==(const ImmutableSet &RHS) const
typename ValInfo::value_type value_type
ImutAVLTree * getLeft() const
Return a pointer to the left subtree.
Definition: ImmutableSet.h:60