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" 22#include "llvm/Support/ErrorHandling.h" 23#include <cassert> 24#include <cstdint> 25#include <functional> 26#include <iterator> 27#include <new> 28#include <vector> 29 30namespace llvm { 31 32//===----------------------------------------------------------------------===// 33// Immutable AVL-Tree Definition. 34//===----------------------------------------------------------------------===// 35 36template <typename ImutInfo> class ImutAVLFactory; 37template <typename ImutInfo> class ImutIntervalAVLFactory; 38template <typename ImutInfo> class ImutAVLTreeInOrderIterator; 39template <typename ImutInfo> class ImutAVLTreeGenericIterator; 40 41template <typename ImutInfo > 42class ImutAVLTree { 43public: 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; 47 using Factory = ImutAVLFactory<ImutInfo>; 48 using iterator = ImutAVLTreeInOrderIterator<ImutInfo>; 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. 75 ImutAVLTree* find(key_type_ref K) { 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. 91 ImutAVLTree* getMaxElement() { 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 118 bool isElementEqual(value_type_ref V) const { 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 222private: 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 242private: 243 /// ImutAVLTree - Internal constructor that is only called by 244 /// ImutAVLFactory. 245 ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, 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. 305 FoldingSetNodeID ID; 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 331public: 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 366template <typename ImutInfo > 367class ImutAVLFactory { 368 friend class ImutAVLTree<ImutInfo>; 369 370 using TreeTy = ImutAVLTree<ImutInfo>; 371 using value_type_ref = typename TreeTy::value_type_ref; 372 using key_type_ref = typename TreeTy::key_type_ref; 373 using CacheTy = DenseMap<unsigned, TreeTy*>; 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 392public: 393 ImutAVLFactory() 394 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 395 396 ImutAVLFactory(BumpPtrAllocator& Alloc) 397 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 398 399 ~ImutAVLFactory() { 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 419protected: 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 607public: 608 TreeTy *getCanonicalTree(TreeTy *TNew) { 609 if (!TNew) 610 return nullptr; 611 612 if (TNew->IsCanonicalized) 613 return TNew; 614 615 // Search the hashtable for another tree with the same digest, and 616 // if find a collision compare those trees by their contents. 617 unsigned digest = TNew->computeDigest(); 618 TreeTy *&entry = Cache[maskCacheIndex(digest)]; 619 do { 620 if (!entry) 621 break; 622 for (TreeTy *T = entry ; T != nullptr; T = T->next) { 623 // Compare the Contents('T') with Contents('TNew') 624 typename TreeTy::iterator TI = T->begin(), TE = T->end(); 625 if (!compareTreeWithSection(TNew, TI, TE)) 626 continue; 627 if (TI != TE) 628 continue; // T has more contents than TNew. 629 // Trees did match! Return 'T'. 630 if (TNew->refCount == 0) 631 TNew->destroy(); 632 return T; 633 } 634 entry->prev = TNew; 635 TNew->next = entry; 636 } 637 while (false); 638 639 entry = TNew; 640 TNew->IsCanonicalized = true; 641 return TNew; 642 } 643}; 644 645//===----------------------------------------------------------------------===// 646// Immutable AVL-Tree Iterators. 647//===----------------------------------------------------------------------===// 648 649template <typename ImutInfo> 650class ImutAVLTreeGenericIterator 651 : public std::iterator<std::bidirectional_iterator_tag, 652 ImutAVLTree<ImutInfo>> { 653 SmallVector<uintptr_t,20> stack; 654 655public: 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 708 ImutAVLTreeGenericIterator &operator++() { 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 734 ImutAVLTreeGenericIterator &operator--() { 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 760template <typename ImutInfo> 761class ImutAVLTreeInOrderIterator 762 : public std::iterator<std::bidirectional_iterator_tag, 763 ImutAVLTree<ImutInfo>> { 764 using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>; 765 766 InternalIteratorTy InternalItr; 767 768public: 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 789 ImutAVLTreeInOrderIterator &operator++() { 790 do ++InternalItr; 791 while (!InternalItr.atEnd() && 792 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 793 794 return *this; 795 } 796 797 ImutAVLTreeInOrderIterator &operator--() { 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. 816template <typename T> 817struct ImutAVLValueIterator 818 : iterator_adaptor_base< 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) 825 : ImutAVLValueIterator::iterator_adaptor_base(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. 839template <typename T> 840struct ImutProfileInfo { 841 using value_type = const T; 842 using value_type_ref = const T&; 843 844 static void Profile(FoldingSetNodeID &ID, value_type_ref X) { 845 FoldingSetTrait<T>::Profile(X,ID); 846 } 847}; 848 849/// Profile traits for integers. 850template <typename T> 851struct ImutProfileInteger { 852 using value_type = const T; 853 using value_type_ref = const T&; 854 855 static void Profile(FoldingSetNodeID &ID, value_type_ref X) { 856 ID.AddInteger(X); 857 } 858}; 859 860#define PROFILE_INTEGER_INFO(X)\ 861template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; 862 863PROFILE_INTEGER_INFO(char) 864PROFILE_INTEGER_INFO(unsigned char) 865PROFILE_INTEGER_INFO(short) 866PROFILE_INTEGER_INFO(unsigned short) 867PROFILE_INTEGER_INFO(unsigned) 868PROFILE_INTEGER_INFO(signed) 869PROFILE_INTEGER_INFO(long) 870PROFILE_INTEGER_INFO(unsigned long) 871PROFILE_INTEGER_INFO(long long) 872PROFILE_INTEGER_INFO(unsigned long long) 873 874#undef PROFILE_INTEGER_INFO 875 876/// Profile traits for booleans. 877template <> 878struct ImutProfileInfo<bool> { 879 using value_type = const bool; 880 using value_type_ref = const bool&; 881 882 static void Profile(FoldingSetNodeID &ID, value_type_ref X) { 883 ID.AddBoolean(X); 884 } 885}; 886 887/// Generic profile trait for pointer types. We treat pointers as 888/// references to unique objects. 889template <typename T> 890struct ImutProfileInfo<T*> { 891 using value_type = const T*; 892 using value_type_ref = value_type; 893 894 static void Profile(FoldingSetNodeID &ID, value_type_ref X) { 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. 909template <typename T> 910struct ImutContainerInfo : public ImutProfileInfo<T> { 911 using value_type = typename ImutProfileInfo<T>::value_type; 912 using value_type_ref = typename ImutProfileInfo<T>::value_type_ref; 913 using key_type = value_type; 914 using key_type_ref = value_type_ref; 915 using data_type = bool; 916 using data_type_ref = bool; 917 918 static key_type_ref KeyOfValue(value_type_ref D) { return D; } 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. 935template <typename T> 936struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { 937 using value_type = typename ImutProfileInfo<T*>::value_type; 938 using value_type_ref = typename ImutProfileInfo<T*>::value_type_ref; 939 using key_type = value_type; 940 using key_type_ref = value_type_ref; 941 using data_type = bool; 942 using data_type_ref = bool; 943 944 static key_type_ref KeyOfValue(value_type_ref D) { return D; } 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 958template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>> 959class ImmutableSet { 960public: 961 using value_type = typename ValInfo::value_type; 962 using value_type_ref = typename ValInfo::value_type_ref; 963 using TreeTy = ImutAVLTree<ValInfo>; 964 965private: 966 TreeTy *Root; 967 968public: 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 981 ~ImmutableSet() { 982 if (Root) { Root->release(); } 983 } 984 985 ImmutableSet &operator=(const ImmutableSet &X) { 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. 1009 ImmutableSet getEmptySet() { 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. 1020 ImmutableSet add(ImmutableSet Old, value_type_ref V) { 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. 1032 ImmutableSet remove(ImmutableSet Old, value_type_ref V) { 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 1085 using iterator = ImutAVLValueIterator<ImmutableSet>; 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. 1110template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>> 1111class ImmutableSetRef { 1112public: 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 1118private: 1119 TreeTy *Root; 1120 FactoryTy *Factory; 1121 1122public: 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 1133 ImmutableSetRef(const ImmutableSetRef &X) 1134 : Root(X.Root), 1135 Factory(X.Factory) { 1136 if (Root) { Root->retain(); } 1137 } 1138 1139 ~ImmutableSetRef() { 1140 if (Root) { Root->release(); } 1141 } 1142 1143 ImmutableSetRef &operator=(const ImmutableSetRef &X) { 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 1153 static ImmutableSetRef getEmptySet(FactoryTy *F) { 1154 return ImmutableSetRef(0, F); 1155 } 1156 1157 ImmutableSetRef add(value_type_ref V) { 1158 return ImmutableSetRef(Factory->add(Root, V), Factory); 1159 } 1160 1161 ImmutableSetRef remove(value_type_ref V) { 1162 return ImmutableSetRef(Factory->remove(Root, V), Factory); 1163 } 1164 1165 /// Returns true if the set contains the specified value. 1166 bool contains(value_type_ref V) const { 1167 return Root ? Root->contains(V) : false; 1168 } 1169 1170 ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const { 1171 return ImmutableSet<ValT>(canonicalize ? 1172 Factory->getCanonicalTree(Root) : Root); 1173 } 1174 1175 TreeTy *getRootWithoutRetain() const { 1176 return Root; 1177 } 1178 1179 bool operator==(const ImmutableSetRef &RHS) const { 1180 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 1181 } 1182 1183 bool operator!=(const ImmutableSetRef &RHS) const { 1184 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 1185 } 1186 1187 /// isEmpty - Return true if the set contains no elements. 1188 bool isEmpty() const { return !Root; } 1189 1190 /// isSingleton - Return true if the set contains exactly one element. 1191 /// This method runs in constant time. 1192 bool isSingleton() const { return getHeight() == 1; } 1193 1194 //===--------------------------------------------------===// 1195 // Iterators. 1196 //===--------------------------------------------------===// 1197 1198 using iterator = ImutAVLValueIterator<ImmutableSetRef>; 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 1225