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_IMSET_H 15 #define LLVM_ADT_IMSET_H 16 17 #include "llvm/Support/Allocator.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/FoldingSet.h" 20 #include "llvm/Support/DataTypes.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include <cassert> 23 #include <functional> 24 #include <vector> 25 #include <stdio.h> 26 27 namespace llvm { 28 29 //===----------------------------------------------------------------------===// 30 // Immutable AVL-Tree Definition. 31 //===----------------------------------------------------------------------===// 32 33 template <typename ImutInfo> class ImutAVLFactory; 34 template <typename ImutInfo> class ImutIntervalAVLFactory; 35 template <typename ImutInfo> class ImutAVLTreeInOrderIterator; 36 template <typename ImutInfo> class ImutAVLTreeGenericIterator; 37 38 template <typename ImutInfo > 39 class ImutAVLTree { 40 public: 41 typedef typename ImutInfo::key_type_ref key_type_ref; 42 typedef typename ImutInfo::value_type value_type; 43 typedef typename ImutInfo::value_type_ref value_type_ref; 44 45 typedef ImutAVLFactory<ImutInfo> Factory; 46 friend class ImutAVLFactory<ImutInfo>; 47 friend class ImutIntervalAVLFactory<ImutInfo>; 48 49 friend class ImutAVLTreeGenericIterator<ImutInfo>; 50 51 typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator; 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. 74 ImutAVLTree* find(key_type_ref K) { 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 NULL; 86 } 87 88 /// getMaxElement - Find the subtree associated with the highest ranged 89 /// key value. 90 ImutAVLTree* getMaxElement() { 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 117 bool isElementEqual(value_type_ref V) const { 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; 226 ImutAVLTree *next; 227 228 unsigned height : 28; 229 unsigned IsMutable : 1; 230 unsigned IsDigestCached : 1; 231 unsigned IsCanonicalized : 1; 232 233 value_type value; 234 uint32_t digest; 235 uint32_t refCount; 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. 244 ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, 245 unsigned height) 246 : factory(f), left(l), right(r), prev(0), next(0), height(height), 247 IsMutable(true), IsDigestCached(false), IsCanonicalized(0), 248 value(v), digest(0), refCount(0) 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 inline 298 uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, 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 inline 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 void release() { 334 assert(refCount > 0); 335 if (--refCount == 0) 336 destroy(); 337 } 338 void destroy() { 339 if (left) 340 left->release(); 341 if (right) 342 right->release(); 343 if (IsCanonicalized) { 344 if (next) 345 next->prev = prev; 346 347 if (prev) 348 prev->next = next; 349 else 350 factory->Cache[factory->maskCacheIndex(computeDigest())] = next; 351 } 352 353 // We need to clear the mutability bit in case we are 354 // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes(). 355 IsMutable = false; 356 factory->freeNodes.push_back(this); 357 } 358 }; 359 360 //===----------------------------------------------------------------------===// 361 // Immutable AVL-Tree Factory class. 362 //===----------------------------------------------------------------------===// 363 364 template <typename ImutInfo > 365 class ImutAVLFactory { 366 friend class ImutAVLTree<ImutInfo>; 367 typedef ImutAVLTree<ImutInfo> TreeTy; 368 typedef typename TreeTy::value_type_ref value_type_ref; 369 typedef typename TreeTy::key_type_ref key_type_ref; 370 371 typedef DenseMap<unsigned, TreeTy*> CacheTy; 372 373 CacheTy Cache; 374 uintptr_t Allocator; 375 std::vector<TreeTy*> createdNodes; 376 std::vector<TreeTy*> freeNodes; 377 378 bool ownsAllocator() const { 379 return Allocator & 0x1 ? false : true; 380 } 381 382 BumpPtrAllocator& getAllocator() const { 383 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 384 } 385 386 //===--------------------------------------------------===// 387 // Public interface. 388 //===--------------------------------------------------===// 389 390 public: 391 ImutAVLFactory() 392 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 393 394 ImutAVLFactory(BumpPtrAllocator& Alloc) 395 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 396 397 ~ImutAVLFactory() { 398 if (ownsAllocator()) delete &getAllocator(); 399 } 400 401 TreeTy* add(TreeTy* T, value_type_ref V) { 402 T = add_internal(V,T); 403 markImmutable(T); 404 recoverNodes(); 405 return T; 406 } 407 408 TreeTy* remove(TreeTy* T, key_type_ref V) { 409 T = remove_internal(V,T); 410 markImmutable(T); 411 recoverNodes(); 412 return T; 413 } 414 415 TreeTy* getEmptyTree() const { return NULL; } 416 417 protected: 418 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 inline unsigned maskCacheIndex(unsigned I) { 434 return (I & ~0x02); 435 } 436 437 unsigned incrementHeight(TreeTy* L, TreeTy* R) const { 438 unsigned hl = getHeight(L); 439 unsigned hr = getHeight(R); 440 return (hl > hr ? hl : hr) + 1; 441 } 442 443 static bool compareTreeWithSection(TreeTy* T, 444 typename TreeTy::iterator& TI, 445 typename TreeTy::iterator& TE) { 446 typename TreeTy::iterator I = T->begin(), E = T->end(); 447 for ( ; I!=E ; ++I, ++TI) { 448 if (TI == TE || !I->isElementEqual(*TI)) 449 return false; 450 } 451 return true; 452 } 453 454 //===--------------------------------------------------===// 455 // "createNode" is used to generate new tree roots that link 456 // to other trees. The functon may also simply move links 457 // in an existing root if that root is still marked mutable. 458 // This is necessary because otherwise our balancing code 459 // would leak memory as it would create nodes that are 460 // then discarded later before the finished tree is 461 // returned to the caller. 462 //===--------------------------------------------------===// 463 464 TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { 465 BumpPtrAllocator& A = getAllocator(); 466 TreeTy* T; 467 if (!freeNodes.empty()) { 468 T = freeNodes.back(); 469 freeNodes.pop_back(); 470 assert(T != L); 471 assert(T != R); 472 } 473 else { 474 T = (TreeTy*) A.Allocate<TreeTy>(); 475 } 476 new (T) TreeTy(this, L, R, V, incrementHeight(L,R)); 477 createdNodes.push_back(T); 478 return T; 479 } 480 481 TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) { 482 return createNode(newLeft, getValue(oldTree), newRight); 483 } 484 485 void recoverNodes() { 486 for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) { 487 TreeTy *N = createdNodes[i]; 488 if (N->isMutable() && N->refCount == 0) 489 N->destroy(); 490 } 491 createdNodes.clear(); 492 } 493 494 /// balanceTree - Used by add_internal and remove_internal to 495 /// balance a newly created tree. 496 TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) { 497 unsigned hl = getHeight(L); 498 unsigned hr = getHeight(R); 499 500 if (hl > hr + 2) { 501 assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2"); 502 503 TreeTy *LL = getLeft(L); 504 TreeTy *LR = getRight(L); 505 506 if (getHeight(LL) >= getHeight(LR)) 507 return createNode(LL, L, createNode(LR,V,R)); 508 509 assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1"); 510 511 TreeTy *LRL = getLeft(LR); 512 TreeTy *LRR = getRight(LR); 513 514 return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R)); 515 } 516 else if (hr > hl + 2) { 517 assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2"); 518 519 TreeTy *RL = getLeft(R); 520 TreeTy *RR = getRight(R); 521 522 if (getHeight(RR) >= getHeight(RL)) 523 return createNode(createNode(L,V,RL), R, RR); 524 525 assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1"); 526 527 TreeTy *RLL = getLeft(RL); 528 TreeTy *RLR = getRight(RL); 529 530 return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR)); 531 } 532 else 533 return createNode(L,V,R); 534 } 535 536 /// add_internal - Creates a new tree that includes the specified 537 /// data and the data from the original tree. If the original tree 538 /// already contained the data item, the original tree is returned. 539 TreeTy* add_internal(value_type_ref V, TreeTy* T) { 540 if (isEmpty(T)) 541 return createNode(T, V, T); 542 assert(!T->isMutable()); 543 544 key_type_ref K = ImutInfo::KeyOfValue(V); 545 key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T)); 546 547 if (ImutInfo::isEqual(K,KCurrent)) 548 return createNode(getLeft(T), V, getRight(T)); 549 else if (ImutInfo::isLess(K,KCurrent)) 550 return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T)); 551 else 552 return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T))); 553 } 554 555 /// remove_internal - Creates a new tree that includes all the data 556 /// from the original tree except the specified data. If the 557 /// specified data did not exist in the original tree, the original 558 /// tree is returned. 559 TreeTy* remove_internal(key_type_ref K, TreeTy* T) { 560 if (isEmpty(T)) 561 return T; 562 563 assert(!T->isMutable()); 564 565 key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T)); 566 567 if (ImutInfo::isEqual(K,KCurrent)) { 568 return combineTrees(getLeft(T), getRight(T)); 569 } else if (ImutInfo::isLess(K,KCurrent)) { 570 return balanceTree(remove_internal(K, getLeft(T)), 571 getValue(T), getRight(T)); 572 } else { 573 return balanceTree(getLeft(T), getValue(T), 574 remove_internal(K, getRight(T))); 575 } 576 } 577 578 TreeTy* combineTrees(TreeTy* L, TreeTy* R) { 579 if (isEmpty(L)) 580 return R; 581 if (isEmpty(R)) 582 return L; 583 TreeTy* OldNode; 584 TreeTy* newRight = removeMinBinding(R,OldNode); 585 return balanceTree(L, getValue(OldNode), newRight); 586 } 587 588 TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) { 589 assert(!isEmpty(T)); 590 if (isEmpty(getLeft(T))) { 591 Noderemoved = T; 592 return getRight(T); 593 } 594 return balanceTree(removeMinBinding(getLeft(T), Noderemoved), 595 getValue(T), getRight(T)); 596 } 597 598 /// markImmutable - Clears the mutable bits of a root and all of its 599 /// descendants. 600 void markImmutable(TreeTy* T) { 601 if (!T || !T->isMutable()) 602 return; 603 T->markImmutable(); 604 markImmutable(getLeft(T)); 605 markImmutable(getRight(T)); 606 } 607 608 public: 609 TreeTy *getCanonicalTree(TreeTy *TNew) { 610 if (!TNew) 611 return 0; 612 613 if (TNew->IsCanonicalized) 614 return TNew; 615 616 // Search the hashtable for another tree with the same digest, and 617 // if find a collision compare those trees by their contents. 618 unsigned digest = TNew->computeDigest(); 619 TreeTy *&entry = Cache[maskCacheIndex(digest)]; 620 do { 621 if (!entry) 622 break; 623 for (TreeTy *T = entry ; T != 0; T = T->next) { 624 // Compare the Contents('T') with Contents('TNew') 625 typename TreeTy::iterator TI = T->begin(), TE = T->end(); 626 if (!compareTreeWithSection(TNew, TI, TE)) 627 continue; 628 if (TI != TE) 629 continue; // T has more contents than TNew. 630 // Trees did match! Return 'T'. 631 if (TNew->refCount == 0) 632 TNew->destroy(); 633 return T; 634 } 635 entry->prev = TNew; 636 TNew->next = entry; 637 } 638 while (false); 639 640 entry = TNew; 641 TNew->IsCanonicalized = true; 642 return TNew; 643 } 644 }; 645 646 //===----------------------------------------------------------------------===// 647 // Immutable AVL-Tree Iterators. 648 //===----------------------------------------------------------------------===// 649 650 template <typename ImutInfo> 651 class ImutAVLTreeGenericIterator { 652 SmallVector<uintptr_t,20> stack; 653 public: 654 enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3, 655 Flags=0x3 }; 656 657 typedef ImutAVLTree<ImutInfo> TreeTy; 658 typedef ImutAVLTreeGenericIterator<ImutInfo> _Self; 659 660 inline ImutAVLTreeGenericIterator() {} 661 inline 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 670 uintptr_t getVisitState() { 671 assert(!stack.empty()); 672 return stack.back() & Flags; 673 } 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 inline bool operator==(const _Self& x) const { 700 if (stack.size() != x.stack.size()) 701 return false; 702 for (unsigned i = 0 ; i < stack.size(); i++) 703 if (stack[i] != x.stack[i]) 704 return false; 705 return true; 706 } 707 708 inline bool operator!=(const _Self& x) const { return !operator==(x); } 709 710 _Self& operator++() { 711 assert(!stack.empty()); 712 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 713 assert(Current); 714 switch (getVisitState()) { 715 case VisitedNone: 716 if (TreeTy* L = Current->getLeft()) 717 stack.push_back(reinterpret_cast<uintptr_t>(L)); 718 else 719 stack.back() |= VisitedLeft; 720 break; 721 case VisitedLeft: 722 if (TreeTy* R = Current->getRight()) 723 stack.push_back(reinterpret_cast<uintptr_t>(R)); 724 else 725 stack.back() |= VisitedRight; 726 break; 727 case VisitedRight: 728 skipToParent(); 729 break; 730 default: 731 llvm_unreachable("Unreachable."); 732 } 733 return *this; 734 } 735 736 _Self& operator--() { 737 assert(!stack.empty()); 738 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 739 assert(Current); 740 switch (getVisitState()) { 741 case VisitedNone: 742 stack.pop_back(); 743 break; 744 case VisitedLeft: 745 stack.back() &= ~Flags; // Set state to "VisitedNone." 746 if (TreeTy* L = Current->getLeft()) 747 stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight); 748 break; 749 case VisitedRight: 750 stack.back() &= ~Flags; 751 stack.back() |= VisitedLeft; 752 if (TreeTy* R = Current->getRight()) 753 stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight); 754 break; 755 default: 756 llvm_unreachable("Unreachable."); 757 } 758 return *this; 759 } 760 }; 761 762 template <typename ImutInfo> 763 class ImutAVLTreeInOrderIterator { 764 typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy; 765 InternalIteratorTy InternalItr; 766 767 public: 768 typedef ImutAVLTree<ImutInfo> TreeTy; 769 typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self; 770 771 ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) { 772 if (Root) operator++(); // Advance to first element. 773 } 774 775 ImutAVLTreeInOrderIterator() : InternalItr() {} 776 777 inline bool operator==(const _Self& x) const { 778 return InternalItr == x.InternalItr; 779 } 780 781 inline bool operator!=(const _Self& x) const { return !operator==(x); } 782 783 inline TreeTy* operator*() const { return *InternalItr; } 784 inline TreeTy* operator->() const { return *InternalItr; } 785 786 inline _Self& operator++() { 787 do ++InternalItr; 788 while (!InternalItr.atEnd() && 789 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 790 791 return *this; 792 } 793 794 inline _Self& operator--() { 795 do --InternalItr; 796 while (!InternalItr.atBeginning() && 797 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 798 799 return *this; 800 } 801 802 inline void skipSubTree() { 803 InternalItr.skipToParent(); 804 805 while (!InternalItr.atEnd() && 806 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft) 807 ++InternalItr; 808 } 809 }; 810 811 //===----------------------------------------------------------------------===// 812 // Trait classes for Profile information. 813 //===----------------------------------------------------------------------===// 814 815 /// Generic profile template. The default behavior is to invoke the 816 /// profile method of an object. Specializations for primitive integers 817 /// and generic handling of pointers is done below. 818 template <typename T> 819 struct ImutProfileInfo { 820 typedef const T value_type; 821 typedef const T& value_type_ref; 822 823 static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 824 FoldingSetTrait<T>::Profile(X,ID); 825 } 826 }; 827 828 /// Profile traits for integers. 829 template <typename T> 830 struct ImutProfileInteger { 831 typedef const T value_type; 832 typedef const T& value_type_ref; 833 834 static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 835 ID.AddInteger(X); 836 } 837 }; 838 839 #define PROFILE_INTEGER_INFO(X)\ 840 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; 841 842 PROFILE_INTEGER_INFO(char) 843 PROFILE_INTEGER_INFO(unsigned char) 844 PROFILE_INTEGER_INFO(short) 845 PROFILE_INTEGER_INFO(unsigned short) 846 PROFILE_INTEGER_INFO(unsigned) 847 PROFILE_INTEGER_INFO(signed) 848 PROFILE_INTEGER_INFO(long) 849 PROFILE_INTEGER_INFO(unsigned long) 850 PROFILE_INTEGER_INFO(long long) 851 PROFILE_INTEGER_INFO(unsigned long long) 852 853 #undef PROFILE_INTEGER_INFO 854 855 /// Generic profile trait for pointer types. We treat pointers as 856 /// references to unique objects. 857 template <typename T> 858 struct ImutProfileInfo<T*> { 859 typedef const T* value_type; 860 typedef value_type value_type_ref; 861 862 static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) { 863 ID.AddPointer(X); 864 } 865 }; 866 867 //===----------------------------------------------------------------------===// 868 // Trait classes that contain element comparison operators and type 869 // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These 870 // inherit from the profile traits (ImutProfileInfo) to include operations 871 // for element profiling. 872 //===----------------------------------------------------------------------===// 873 874 875 /// ImutContainerInfo - Generic definition of comparison operations for 876 /// elements of immutable containers that defaults to using 877 /// std::equal_to<> and std::less<> to perform comparison of elements. 878 template <typename T> 879 struct ImutContainerInfo : public ImutProfileInfo<T> { 880 typedef typename ImutProfileInfo<T>::value_type value_type; 881 typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref; 882 typedef value_type key_type; 883 typedef value_type_ref key_type_ref; 884 typedef bool data_type; 885 typedef bool data_type_ref; 886 887 static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 888 static inline data_type_ref DataOfValue(value_type_ref) { return true; } 889 890 static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 891 return std::equal_to<key_type>()(LHS,RHS); 892 } 893 894 static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 895 return std::less<key_type>()(LHS,RHS); 896 } 897 898 static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 899 }; 900 901 /// ImutContainerInfo - Specialization for pointer values to treat pointers 902 /// as references to unique objects. Pointers are thus compared by 903 /// their addresses. 904 template <typename T> 905 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { 906 typedef typename ImutProfileInfo<T*>::value_type value_type; 907 typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref; 908 typedef value_type key_type; 909 typedef value_type_ref key_type_ref; 910 typedef bool data_type; 911 typedef bool data_type_ref; 912 913 static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 914 static inline data_type_ref DataOfValue(value_type_ref) { return true; } 915 916 static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 917 return LHS == RHS; 918 } 919 920 static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 921 return LHS < RHS; 922 } 923 924 static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 925 }; 926 927 //===----------------------------------------------------------------------===// 928 // Immutable Set 929 //===----------------------------------------------------------------------===// 930 931 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 932 class ImmutableSet { 933 public: 934 typedef typename ValInfo::value_type value_type; 935 typedef typename ValInfo::value_type_ref value_type_ref; 936 typedef ImutAVLTree<ValInfo> TreeTy; 937 938 private: 939 TreeTy *Root; 940 941 public: 942 /// Constructs a set from a pointer to a tree root. In general one 943 /// should use a Factory object to create sets instead of directly 944 /// invoking the constructor, but there are cases where make this 945 /// constructor public is useful. 946 explicit ImmutableSet(TreeTy* R) : Root(R) { 947 if (Root) { Root->retain(); } 948 } 949 ImmutableSet(const ImmutableSet &X) : Root(X.Root) { 950 if (Root) { Root->retain(); } 951 } 952 ImmutableSet &operator=(const ImmutableSet &X) { 953 if (Root != X.Root) { 954 if (X.Root) { X.Root->retain(); } 955 if (Root) { Root->release(); } 956 Root = X.Root; 957 } 958 return *this; 959 } 960 ~ImmutableSet() { 961 if (Root) { Root->release(); } 962 } 963 964 class Factory { 965 typename TreeTy::Factory F; 966 const bool Canonicalize; 967 968 public: 969 Factory(bool canonicalize = true) 970 : Canonicalize(canonicalize) {} 971 972 Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) 973 : F(Alloc), Canonicalize(canonicalize) {} 974 975 /// getEmptySet - Returns an immutable set that contains no elements. 976 ImmutableSet getEmptySet() { 977 return ImmutableSet(F.getEmptyTree()); 978 } 979 980 /// add - Creates a new immutable set that contains all of the values 981 /// of the original set with the addition of the specified value. If 982 /// the original set already included the value, then the original set is 983 /// returned and no memory is allocated. The time and space complexity 984 /// of this operation is logarithmic in the size of the original set. 985 /// The memory allocated to represent the set is released when the 986 /// factory object that created the set is destroyed. 987 ImmutableSet add(ImmutableSet Old, value_type_ref V) { 988 TreeTy *NewT = F.add(Old.Root, V); 989 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); 990 } 991 992 /// remove - Creates a new immutable set that contains all of the values 993 /// of the original set with the exception of the specified value. If 994 /// the original set did not contain the value, the original set is 995 /// returned and no memory is allocated. The time and space complexity 996 /// of this operation is logarithmic in the size of the original set. 997 /// The memory allocated to represent the set is released when the 998 /// factory object that created the set is destroyed. 999 ImmutableSet remove(ImmutableSet Old, value_type_ref V) { 1000 TreeTy *NewT = F.remove(Old.Root, V); 1001 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); 1002 } 1003 1004 BumpPtrAllocator& getAllocator() { return F.getAllocator(); } 1005 1006 typename TreeTy::Factory *getTreeFactory() const { 1007 return const_cast<typename TreeTy::Factory *>(&F); 1008 } 1009 1010 private: 1011 Factory(const Factory& RHS); // DO NOT IMPLEMENT 1012 void operator=(const Factory& RHS); // DO NOT IMPLEMENT 1013 }; 1014 1015 friend class Factory; 1016 1017 /// Returns true if the set contains the specified value. 1018 bool contains(value_type_ref V) const { 1019 return Root ? Root->contains(V) : false; 1020 } 1021 1022 bool operator==(const ImmutableSet &RHS) const { 1023 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 1024 } 1025 1026 bool operator!=(const ImmutableSet &RHS) const { 1027 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 1028 } 1029 1030 TreeTy *getRoot() { 1031 if (Root) { Root->retain(); } 1032 return Root; 1033 } 1034 1035 TreeTy *getRootWithoutRetain() const { 1036 return Root; 1037 } 1038 1039 /// isEmpty - Return true if the set contains no elements. 1040 bool isEmpty() const { return !Root; } 1041 1042 /// isSingleton - Return true if the set contains exactly one element. 1043 /// This method runs in constant time. 1044 bool isSingleton() const { return getHeight() == 1; } 1045 1046 template <typename Callback> 1047 void foreach(Callback& C) { if (Root) Root->foreach(C); } 1048 1049 template <typename Callback> 1050 void foreach() { if (Root) { Callback C; Root->foreach(C); } } 1051 1052 //===--------------------------------------------------===// 1053 // Iterators. 1054 //===--------------------------------------------------===// 1055 1056 class iterator { 1057 typename TreeTy::iterator itr; 1058 iterator(TreeTy* t) : itr(t) {} 1059 friend class ImmutableSet<ValT,ValInfo>; 1060 public: 1061 iterator() {} 1062 inline value_type_ref operator*() const { return itr->getValue(); } 1063 inline iterator& operator++() { ++itr; return *this; } 1064 inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1065 inline iterator& operator--() { --itr; return *this; } 1066 inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1067 inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 1068 inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 1069 inline value_type *operator->() const { return &(operator*()); } 1070 }; 1071 1072 iterator begin() const { return iterator(Root); } 1073 iterator end() const { return iterator(); } 1074 1075 //===--------------------------------------------------===// 1076 // Utility methods. 1077 //===--------------------------------------------------===// 1078 1079 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 1080 1081 static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) { 1082 ID.AddPointer(S.Root); 1083 } 1084 1085 inline void Profile(FoldingSetNodeID& ID) const { 1086 return Profile(ID,*this); 1087 } 1088 1089 //===--------------------------------------------------===// 1090 // For testing. 1091 //===--------------------------------------------------===// 1092 1093 void validateTree() const { if (Root) Root->validateTree(); } 1094 }; 1095 1096 // NOTE: This may some day replace the current ImmutableSet. 1097 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 1098 class ImmutableSetRef { 1099 public: 1100 typedef typename ValInfo::value_type value_type; 1101 typedef typename ValInfo::value_type_ref value_type_ref; 1102 typedef ImutAVLTree<ValInfo> TreeTy; 1103 typedef typename TreeTy::Factory FactoryTy; 1104 1105 private: 1106 TreeTy *Root; 1107 FactoryTy *Factory; 1108 1109 public: 1110 /// Constructs a set from a pointer to a tree root. In general one 1111 /// should use a Factory object to create sets instead of directly 1112 /// invoking the constructor, but there are cases where make this 1113 /// constructor public is useful. 1114 explicit ImmutableSetRef(TreeTy* R, FactoryTy *F) 1115 : Root(R), 1116 Factory(F) { 1117 if (Root) { Root->retain(); } 1118 } 1119 ImmutableSetRef(const ImmutableSetRef &X) 1120 : Root(X.Root), 1121 Factory(X.Factory) { 1122 if (Root) { Root->retain(); } 1123 } 1124 ImmutableSetRef &operator=(const ImmutableSetRef &X) { 1125 if (Root != X.Root) { 1126 if (X.Root) { X.Root->retain(); } 1127 if (Root) { Root->release(); } 1128 Root = X.Root; 1129 Factory = X.Factory; 1130 } 1131 return *this; 1132 } 1133 ~ImmutableSetRef() { 1134 if (Root) { Root->release(); } 1135 } 1136 1137 static inline ImmutableSetRef getEmptySet(FactoryTy *F) { 1138 return ImmutableSetRef(0, F); 1139 } 1140 1141 ImmutableSetRef add(value_type_ref V) { 1142 return ImmutableSetRef(Factory->add(Root, V), Factory); 1143 } 1144 1145 ImmutableSetRef remove(value_type_ref V) { 1146 return ImmutableSetRef(Factory->remove(Root, V), Factory); 1147 } 1148 1149 /// Returns true if the set contains the specified value. 1150 bool contains(value_type_ref V) const { 1151 return Root ? Root->contains(V) : false; 1152 } 1153 1154 ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const { 1155 return ImmutableSet<ValT>(canonicalize ? 1156 Factory->getCanonicalTree(Root) : Root); 1157 } 1158 1159 TreeTy *getRootWithoutRetain() const { 1160 return Root; 1161 } 1162 1163 bool operator==(const ImmutableSetRef &RHS) const { 1164 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 1165 } 1166 1167 bool operator!=(const ImmutableSetRef &RHS) const { 1168 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 1169 } 1170 1171 /// isEmpty - Return true if the set contains no elements. 1172 bool isEmpty() const { return !Root; } 1173 1174 /// isSingleton - Return true if the set contains exactly one element. 1175 /// This method runs in constant time. 1176 bool isSingleton() const { return getHeight() == 1; } 1177 1178 //===--------------------------------------------------===// 1179 // Iterators. 1180 //===--------------------------------------------------===// 1181 1182 class iterator { 1183 typename TreeTy::iterator itr; 1184 iterator(TreeTy* t) : itr(t) {} 1185 friend class ImmutableSetRef<ValT,ValInfo>; 1186 public: 1187 iterator() {} 1188 inline value_type_ref operator*() const { return itr->getValue(); } 1189 inline iterator& operator++() { ++itr; return *this; } 1190 inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1191 inline iterator& operator--() { --itr; return *this; } 1192 inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1193 inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 1194 inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 1195 inline value_type *operator->() const { return &(operator*()); } 1196 }; 1197 1198 iterator begin() const { return iterator(Root); } 1199 iterator end() const { return iterator(); } 1200 1201 //===--------------------------------------------------===// 1202 // Utility methods. 1203 //===--------------------------------------------------===// 1204 1205 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 1206 1207 static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { 1208 ID.AddPointer(S.Root); 1209 } 1210 1211 inline void Profile(FoldingSetNodeID& ID) const { 1212 return Profile(ID,*this); 1213 } 1214 1215 //===--------------------------------------------------===// 1216 // For testing. 1217 //===--------------------------------------------------===// 1218 1219 void validateTree() const { if (Root) Root->validateTree(); } 1220 }; 1221 1222 } // end namespace llvm 1223 1224 #endif 1225