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