1193323Sed//===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the ImutAVLTree and ImmutableSet classes. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14252723Sdim#ifndef LLVM_ADT_IMMUTABLESET_H 15252723Sdim#define LLVM_ADT_IMMUTABLESET_H 16193323Sed 17218893Sdim#include "llvm/ADT/DenseMap.h" 18193323Sed#include "llvm/ADT/FoldingSet.h" 19252723Sdim#include "llvm/Support/Allocator.h" 20218893Sdim#include "llvm/Support/DataTypes.h" 21235633Sdim#include "llvm/Support/ErrorHandling.h" 22193323Sed#include <cassert> 23193323Sed#include <functional> 24218893Sdim#include <vector> 25193323Sed 26193323Sednamespace llvm { 27193323Sed 28193323Sed//===----------------------------------------------------------------------===// 29193323Sed// Immutable AVL-Tree Definition. 30193323Sed//===----------------------------------------------------------------------===// 31193323Sed 32193323Sedtemplate <typename ImutInfo> class ImutAVLFactory; 33203954Srdivackytemplate <typename ImutInfo> class ImutIntervalAVLFactory; 34193323Sedtemplate <typename ImutInfo> class ImutAVLTreeInOrderIterator; 35193323Sedtemplate <typename ImutInfo> class ImutAVLTreeGenericIterator; 36193323Sed 37193323Sedtemplate <typename ImutInfo > 38218893Sdimclass ImutAVLTree { 39193323Sedpublic: 40193323Sed typedef typename ImutInfo::key_type_ref key_type_ref; 41193323Sed typedef typename ImutInfo::value_type value_type; 42193323Sed typedef typename ImutInfo::value_type_ref value_type_ref; 43193323Sed 44193323Sed typedef ImutAVLFactory<ImutInfo> Factory; 45193323Sed friend class ImutAVLFactory<ImutInfo>; 46203954Srdivacky friend class ImutIntervalAVLFactory<ImutInfo>; 47193323Sed 48193323Sed friend class ImutAVLTreeGenericIterator<ImutInfo>; 49193323Sed 50193323Sed typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator; 51193323Sed 52193323Sed //===----------------------------------------------------===// 53193323Sed // Public Interface. 54193323Sed //===----------------------------------------------------===// 55193323Sed 56218893Sdim /// Return a pointer to the left subtree. This value 57193323Sed /// is NULL if there is no left subtree. 58218893Sdim ImutAVLTree *getLeft() const { return left; } 59193323Sed 60218893Sdim /// Return a pointer to the right subtree. This value is 61193323Sed /// NULL if there is no right subtree. 62218893Sdim ImutAVLTree *getRight() const { return right; } 63193323Sed 64193323Sed /// getHeight - Returns the height of the tree. A tree with no subtrees 65193323Sed /// has a height of 1. 66218893Sdim unsigned getHeight() const { return height; } 67193323Sed 68193323Sed /// getValue - Returns the data value associated with the tree node. 69218893Sdim const value_type& getValue() const { return value; } 70193323Sed 71193323Sed /// find - Finds the subtree associated with the specified key value. 72193323Sed /// This method returns NULL if no matching subtree is found. 73193323Sed ImutAVLTree* find(key_type_ref K) { 74193323Sed ImutAVLTree *T = this; 75193323Sed while (T) { 76193323Sed key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue()); 77193323Sed if (ImutInfo::isEqual(K,CurrentKey)) 78193323Sed return T; 79193323Sed else if (ImutInfo::isLess(K,CurrentKey)) 80193323Sed T = T->getLeft(); 81193323Sed else 82193323Sed T = T->getRight(); 83193323Sed } 84193323Sed return NULL; 85193323Sed } 86245431Sdim 87193323Sed /// getMaxElement - Find the subtree associated with the highest ranged 88193323Sed /// key value. 89193323Sed ImutAVLTree* getMaxElement() { 90193323Sed ImutAVLTree *T = this; 91245431Sdim ImutAVLTree *Right = T->getRight(); 92245431Sdim while (Right) { T = Right; Right = T->getRight(); } 93193323Sed return T; 94193323Sed } 95193323Sed 96193323Sed /// size - Returns the number of nodes in the tree, which includes 97193323Sed /// both leaves and non-leaf nodes. 98193323Sed unsigned size() const { 99193323Sed unsigned n = 1; 100218893Sdim if (const ImutAVLTree* L = getLeft()) 101218893Sdim n += L->size(); 102218893Sdim if (const ImutAVLTree* R = getRight()) 103218893Sdim n += R->size(); 104193323Sed return n; 105193323Sed } 106193323Sed 107193323Sed /// begin - Returns an iterator that iterates over the nodes of the tree 108193323Sed /// in an inorder traversal. The returned iterator thus refers to the 109193323Sed /// the tree node with the minimum data element. 110193323Sed iterator begin() const { return iterator(this); } 111193323Sed 112193323Sed /// end - Returns an iterator for the tree that denotes the end of an 113193323Sed /// inorder traversal. 114193323Sed iterator end() const { return iterator(); } 115193323Sed 116218893Sdim bool isElementEqual(value_type_ref V) const { 117193323Sed // Compare the keys. 118193323Sed if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()), 119193323Sed ImutInfo::KeyOfValue(V))) 120193323Sed return false; 121193323Sed 122193323Sed // Also compare the data values. 123193323Sed if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()), 124193323Sed ImutInfo::DataOfValue(V))) 125193323Sed return false; 126193323Sed 127193323Sed return true; 128193323Sed } 129193323Sed 130218893Sdim bool isElementEqual(const ImutAVLTree* RHS) const { 131218893Sdim return isElementEqual(RHS->getValue()); 132193323Sed } 133193323Sed 134193323Sed /// isEqual - Compares two trees for structural equality and returns true 135193323Sed /// if they are equal. This worst case performance of this operation is 136193323Sed // linear in the sizes of the trees. 137193323Sed bool isEqual(const ImutAVLTree& RHS) const { 138193323Sed if (&RHS == this) 139193323Sed return true; 140193323Sed 141193323Sed iterator LItr = begin(), LEnd = end(); 142193323Sed iterator RItr = RHS.begin(), REnd = RHS.end(); 143193323Sed 144193323Sed while (LItr != LEnd && RItr != REnd) { 145193323Sed if (*LItr == *RItr) { 146218893Sdim LItr.skipSubTree(); 147218893Sdim RItr.skipSubTree(); 148193323Sed continue; 149193323Sed } 150193323Sed 151218893Sdim if (!LItr->isElementEqual(*RItr)) 152193323Sed return false; 153193323Sed 154193323Sed ++LItr; 155193323Sed ++RItr; 156193323Sed } 157193323Sed 158193323Sed return LItr == LEnd && RItr == REnd; 159193323Sed } 160193323Sed 161193323Sed /// isNotEqual - Compares two trees for structural inequality. Performance 162193323Sed /// is the same is isEqual. 163193323Sed bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); } 164193323Sed 165193323Sed /// contains - Returns true if this tree contains a subtree (node) that 166193323Sed /// has an data element that matches the specified key. Complexity 167193323Sed /// is logarithmic in the size of the tree. 168198090Srdivacky bool contains(key_type_ref K) { return (bool) find(K); } 169193323Sed 170193323Sed /// foreach - A member template the accepts invokes operator() on a functor 171193323Sed /// object (specifed by Callback) for every node/subtree in the tree. 172193323Sed /// Nodes are visited using an inorder traversal. 173193323Sed template <typename Callback> 174193323Sed void foreach(Callback& C) { 175218893Sdim if (ImutAVLTree* L = getLeft()) 176218893Sdim L->foreach(C); 177193323Sed 178218893Sdim C(value); 179193323Sed 180218893Sdim if (ImutAVLTree* R = getRight()) 181218893Sdim R->foreach(C); 182193323Sed } 183193323Sed 184218893Sdim /// validateTree - A utility method that checks that the balancing and 185193323Sed /// ordering invariants of the tree are satisifed. It is a recursive 186193323Sed /// method that returns the height of the tree, which is then consumed 187218893Sdim /// by the enclosing validateTree call. External callers should ignore the 188193323Sed /// return value. An invalid tree will cause an assertion to fire in 189193323Sed /// a debug build. 190218893Sdim unsigned validateTree() const { 191218893Sdim unsigned HL = getLeft() ? getLeft()->validateTree() : 0; 192218893Sdim unsigned HR = getRight() ? getRight()->validateTree() : 0; 193207618Srdivacky (void) HL; 194207618Srdivacky (void) HR; 195193323Sed 196202878Srdivacky assert(getHeight() == ( HL > HR ? HL : HR ) + 1 197202878Srdivacky && "Height calculation wrong"); 198193323Sed 199202878Srdivacky assert((HL > HR ? HL-HR : HR-HL) <= 2 200202878Srdivacky && "Balancing invariant violated"); 201193323Sed 202218893Sdim assert((!getLeft() || 203218893Sdim ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()), 204218893Sdim ImutInfo::KeyOfValue(getValue()))) && 205218893Sdim "Value in left child is not less that current value"); 206193323Sed 207193323Sed 208218893Sdim assert(!(getRight() || 209218893Sdim ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()), 210218893Sdim ImutInfo::KeyOfValue(getRight()->getValue()))) && 211218893Sdim "Current value is not less that value of right child"); 212193323Sed 213193323Sed return getHeight(); 214193323Sed } 215193323Sed 216193323Sed //===----------------------------------------------------===// 217218893Sdim // Internal values. 218193323Sed //===----------------------------------------------------===// 219193323Sed 220193323Sedprivate: 221218893Sdim Factory *factory; 222218893Sdim ImutAVLTree *left; 223218893Sdim ImutAVLTree *right; 224218893Sdim ImutAVLTree *prev; 225218893Sdim ImutAVLTree *next; 226193323Sed 227218893Sdim unsigned height : 28; 228218893Sdim unsigned IsMutable : 1; 229218893Sdim unsigned IsDigestCached : 1; 230218893Sdim unsigned IsCanonicalized : 1; 231218893Sdim 232218893Sdim value_type value; 233218893Sdim uint32_t digest; 234218893Sdim uint32_t refCount; 235218893Sdim 236193323Sed //===----------------------------------------------------===// 237193323Sed // Internal methods (node manipulation; used by Factory). 238193323Sed //===----------------------------------------------------===// 239193323Sed 240193323Sedprivate: 241193323Sed /// ImutAVLTree - Internal constructor that is only called by 242193323Sed /// ImutAVLFactory. 243218893Sdim ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, 244202878Srdivacky unsigned height) 245218893Sdim : factory(f), left(l), right(r), prev(0), next(0), height(height), 246218893Sdim IsMutable(true), IsDigestCached(false), IsCanonicalized(0), 247218893Sdim value(v), digest(0), refCount(0) 248218893Sdim { 249218893Sdim if (left) left->retain(); 250218893Sdim if (right) right->retain(); 251218893Sdim } 252193323Sed 253193323Sed /// isMutable - Returns true if the left and right subtree references 254193323Sed /// (as well as height) can be changed. If this method returns false, 255193323Sed /// the tree is truly immutable. Trees returned from an ImutAVLFactory 256193323Sed /// object should always have this method return true. Further, if this 257193323Sed /// method returns false for an instance of ImutAVLTree, all subtrees 258193323Sed /// will also have this method return false. The converse is not true. 259218893Sdim bool isMutable() const { return IsMutable; } 260245431Sdim 261198090Srdivacky /// hasCachedDigest - Returns true if the digest for this tree is cached. 262198090Srdivacky /// This can only be true if the tree is immutable. 263218893Sdim bool hasCachedDigest() const { return IsDigestCached; } 264193323Sed 265193323Sed //===----------------------------------------------------===// 266193323Sed // Mutating operations. A tree root can be manipulated as 267193323Sed // long as its reference has not "escaped" from internal 268193323Sed // methods of a factory object (see below). When a tree 269193323Sed // pointer is externally viewable by client code, the 270193323Sed // internal "mutable bit" is cleared to mark the tree 271193323Sed // immutable. Note that a tree that still has its mutable 272193323Sed // bit set may have children (subtrees) that are themselves 273193323Sed // immutable. 274193323Sed //===----------------------------------------------------===// 275193323Sed 276218893Sdim /// markImmutable - Clears the mutable flag for a tree. After this happens, 277198090Srdivacky /// it is an error to call setLeft(), setRight(), and setHeight(). 278218893Sdim void markImmutable() { 279198090Srdivacky assert(isMutable() && "Mutable flag already removed."); 280218893Sdim IsMutable = false; 281193323Sed } 282245431Sdim 283218893Sdim /// markedCachedDigest - Clears the NoCachedDigest flag for a tree. 284218893Sdim void markedCachedDigest() { 285198090Srdivacky assert(!hasCachedDigest() && "NoCachedDigest flag already removed."); 286218893Sdim IsDigestCached = true; 287198090Srdivacky } 288193323Sed 289193323Sed /// setHeight - Changes the height of the tree. Used internally by 290193323Sed /// ImutAVLFactory. 291193323Sed void setHeight(unsigned h) { 292198090Srdivacky assert(isMutable() && "Only a mutable tree can have its height changed."); 293218893Sdim height = h; 294193323Sed } 295193323Sed 296193323Sed static inline 297218893Sdim uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { 298198090Srdivacky uint32_t digest = 0; 299193323Sed 300198090Srdivacky if (L) 301218893Sdim digest += L->computeDigest(); 302193323Sed 303198090Srdivacky // Compute digest of stored data. 304198090Srdivacky FoldingSetNodeID ID; 305198090Srdivacky ImutInfo::Profile(ID,V); 306198090Srdivacky digest += ID.ComputeHash(); 307193323Sed 308198090Srdivacky if (R) 309218893Sdim digest += R->computeDigest(); 310193323Sed 311193323Sed return digest; 312193323Sed } 313193323Sed 314218893Sdim inline uint32_t computeDigest() { 315198090Srdivacky // Check the lowest bit to determine if digest has actually been 316198090Srdivacky // pre-computed. 317198090Srdivacky if (hasCachedDigest()) 318218893Sdim return digest; 319193323Sed 320218893Sdim uint32_t X = computeDigest(getLeft(), getRight(), getValue()); 321218893Sdim digest = X; 322218893Sdim markedCachedDigest(); 323193323Sed return X; 324193323Sed } 325218893Sdim 326218893Sdim //===----------------------------------------------------===// 327218893Sdim // Reference count operations. 328218893Sdim //===----------------------------------------------------===// 329218893Sdim 330218893Sdimpublic: 331218893Sdim void retain() { ++refCount; } 332218893Sdim void release() { 333218893Sdim assert(refCount > 0); 334218893Sdim if (--refCount == 0) 335218893Sdim destroy(); 336218893Sdim } 337218893Sdim void destroy() { 338218893Sdim if (left) 339218893Sdim left->release(); 340218893Sdim if (right) 341218893Sdim right->release(); 342218893Sdim if (IsCanonicalized) { 343218893Sdim if (next) 344218893Sdim next->prev = prev; 345218893Sdim 346218893Sdim if (prev) 347218893Sdim prev->next = next; 348218893Sdim else 349235633Sdim factory->Cache[factory->maskCacheIndex(computeDigest())] = next; 350218893Sdim } 351245431Sdim 352218893Sdim // We need to clear the mutability bit in case we are 353218893Sdim // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes(). 354218893Sdim IsMutable = false; 355218893Sdim factory->freeNodes.push_back(this); 356218893Sdim } 357193323Sed}; 358193323Sed 359193323Sed//===----------------------------------------------------------------------===// 360193323Sed// Immutable AVL-Tree Factory class. 361193323Sed//===----------------------------------------------------------------------===// 362193323Sed 363193323Sedtemplate <typename ImutInfo > 364193323Sedclass ImutAVLFactory { 365218893Sdim friend class ImutAVLTree<ImutInfo>; 366193323Sed typedef ImutAVLTree<ImutInfo> TreeTy; 367193323Sed typedef typename TreeTy::value_type_ref value_type_ref; 368193323Sed typedef typename TreeTy::key_type_ref key_type_ref; 369193323Sed 370218893Sdim typedef DenseMap<unsigned, TreeTy*> CacheTy; 371193323Sed 372193323Sed CacheTy Cache; 373193323Sed uintptr_t Allocator; 374218893Sdim std::vector<TreeTy*> createdNodes; 375218893Sdim std::vector<TreeTy*> freeNodes; 376193323Sed 377193323Sed bool ownsAllocator() const { 378193323Sed return Allocator & 0x1 ? false : true; 379193323Sed } 380193323Sed 381193323Sed BumpPtrAllocator& getAllocator() const { 382193323Sed return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 383193323Sed } 384193323Sed 385193323Sed //===--------------------------------------------------===// 386193323Sed // Public interface. 387193323Sed //===--------------------------------------------------===// 388193323Sed 389193323Sedpublic: 390193323Sed ImutAVLFactory() 391193323Sed : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 392193323Sed 393193323Sed ImutAVLFactory(BumpPtrAllocator& Alloc) 394193323Sed : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 395193323Sed 396193323Sed ~ImutAVLFactory() { 397193323Sed if (ownsAllocator()) delete &getAllocator(); 398193323Sed } 399193323Sed 400218893Sdim TreeTy* add(TreeTy* T, value_type_ref V) { 401218893Sdim T = add_internal(V,T); 402218893Sdim markImmutable(T); 403218893Sdim recoverNodes(); 404193323Sed return T; 405193323Sed } 406193323Sed 407218893Sdim TreeTy* remove(TreeTy* T, key_type_ref V) { 408218893Sdim T = remove_internal(V,T); 409218893Sdim markImmutable(T); 410218893Sdim recoverNodes(); 411193323Sed return T; 412193323Sed } 413193323Sed 414218893Sdim TreeTy* getEmptyTree() const { return NULL; } 415193323Sed 416218893Sdimprotected: 417245431Sdim 418193323Sed //===--------------------------------------------------===// 419193323Sed // A bunch of quick helper functions used for reasoning 420193323Sed // about the properties of trees and their children. 421193323Sed // These have succinct names so that the balancing code 422193323Sed // is as terse (and readable) as possible. 423193323Sed //===--------------------------------------------------===// 424193323Sed 425218893Sdim bool isEmpty(TreeTy* T) const { return !T; } 426218893Sdim unsigned getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; } 427218893Sdim TreeTy* getLeft(TreeTy* T) const { return T->getLeft(); } 428218893Sdim TreeTy* getRight(TreeTy* T) const { return T->getRight(); } 429218893Sdim value_type_ref getValue(TreeTy* T) const { return T->value; } 430193323Sed 431235633Sdim // Make sure the index is not the Tombstone or Entry key of the DenseMap. 432235633Sdim static inline unsigned maskCacheIndex(unsigned I) { 433245431Sdim return (I & ~0x02); 434235633Sdim } 435235633Sdim 436218893Sdim unsigned incrementHeight(TreeTy* L, TreeTy* R) const { 437218893Sdim unsigned hl = getHeight(L); 438218893Sdim unsigned hr = getHeight(R); 439202878Srdivacky return (hl > hr ? hl : hr) + 1; 440193323Sed } 441193323Sed 442218893Sdim static bool compareTreeWithSection(TreeTy* T, 443193323Sed typename TreeTy::iterator& TI, 444193323Sed typename TreeTy::iterator& TE) { 445193323Sed typename TreeTy::iterator I = T->begin(), E = T->end(); 446218893Sdim for ( ; I!=E ; ++I, ++TI) { 447218893Sdim if (TI == TE || !I->isElementEqual(*TI)) 448193323Sed return false; 449218893Sdim } 450193323Sed return true; 451193323Sed } 452193323Sed 453193323Sed //===--------------------------------------------------===// 454218893Sdim // "createNode" is used to generate new tree roots that link 455193323Sed // to other trees. The functon may also simply move links 456193323Sed // in an existing root if that root is still marked mutable. 457193323Sed // This is necessary because otherwise our balancing code 458193323Sed // would leak memory as it would create nodes that are 459193323Sed // then discarded later before the finished tree is 460193323Sed // returned to the caller. 461193323Sed //===--------------------------------------------------===// 462193323Sed 463245431Sdim TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { 464193323Sed BumpPtrAllocator& A = getAllocator(); 465218893Sdim TreeTy* T; 466218893Sdim if (!freeNodes.empty()) { 467218893Sdim T = freeNodes.back(); 468218893Sdim freeNodes.pop_back(); 469218893Sdim assert(T != L); 470218893Sdim assert(T != R); 471245431Sdim } else { 472218893Sdim T = (TreeTy*) A.Allocate<TreeTy>(); 473218893Sdim } 474218893Sdim new (T) TreeTy(this, L, R, V, incrementHeight(L,R)); 475218893Sdim createdNodes.push_back(T); 476193323Sed return T; 477193323Sed } 478193323Sed 479218893Sdim TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) { 480218893Sdim return createNode(newLeft, getValue(oldTree), newRight); 481218893Sdim } 482193323Sed 483218893Sdim void recoverNodes() { 484218893Sdim for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) { 485218893Sdim TreeTy *N = createdNodes[i]; 486218893Sdim if (N->isMutable() && N->refCount == 0) 487218893Sdim N->destroy(); 488193323Sed } 489218893Sdim createdNodes.clear(); 490193323Sed } 491193323Sed 492218893Sdim /// balanceTree - Used by add_internal and remove_internal to 493193323Sed /// balance a newly created tree. 494218893Sdim TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) { 495218893Sdim unsigned hl = getHeight(L); 496218893Sdim unsigned hr = getHeight(R); 497193323Sed 498193323Sed if (hl > hr + 2) { 499202878Srdivacky assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2"); 500193323Sed 501218893Sdim TreeTy *LL = getLeft(L); 502218893Sdim TreeTy *LR = getRight(L); 503193323Sed 504218893Sdim if (getHeight(LL) >= getHeight(LR)) 505218893Sdim return createNode(LL, L, createNode(LR,V,R)); 506193323Sed 507202878Srdivacky assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1"); 508193323Sed 509218893Sdim TreeTy *LRL = getLeft(LR); 510218893Sdim TreeTy *LRR = getRight(LR); 511193323Sed 512218893Sdim return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R)); 513193323Sed } 514245431Sdim 515245431Sdim if (hr > hl + 2) { 516202878Srdivacky assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2"); 517193323Sed 518218893Sdim TreeTy *RL = getLeft(R); 519218893Sdim TreeTy *RR = getRight(R); 520193323Sed 521218893Sdim if (getHeight(RR) >= getHeight(RL)) 522218893Sdim return createNode(createNode(L,V,RL), R, RR); 523193323Sed 524202878Srdivacky assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1"); 525193323Sed 526218893Sdim TreeTy *RLL = getLeft(RL); 527218893Sdim TreeTy *RLR = getRight(RL); 528193323Sed 529218893Sdim return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR)); 530193323Sed } 531245431Sdim 532245431Sdim return createNode(L,V,R); 533193323Sed } 534193323Sed 535218893Sdim /// add_internal - Creates a new tree that includes the specified 536193323Sed /// data and the data from the original tree. If the original tree 537193323Sed /// already contained the data item, the original tree is returned. 538218893Sdim TreeTy* add_internal(value_type_ref V, TreeTy* T) { 539193323Sed if (isEmpty(T)) 540218893Sdim return createNode(T, V, T); 541202878Srdivacky assert(!T->isMutable()); 542193323Sed 543193323Sed key_type_ref K = ImutInfo::KeyOfValue(V); 544218893Sdim key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T)); 545193323Sed 546193323Sed if (ImutInfo::isEqual(K,KCurrent)) 547218893Sdim return createNode(getLeft(T), V, getRight(T)); 548193323Sed else if (ImutInfo::isLess(K,KCurrent)) 549218893Sdim return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T)); 550193323Sed else 551218893Sdim return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T))); 552193323Sed } 553193323Sed 554218893Sdim /// remove_internal - Creates a new tree that includes all the data 555193323Sed /// from the original tree except the specified data. If the 556193323Sed /// specified data did not exist in the original tree, the original 557193323Sed /// tree is returned. 558218893Sdim TreeTy* remove_internal(key_type_ref K, TreeTy* T) { 559193323Sed if (isEmpty(T)) 560193323Sed return T; 561193323Sed 562202878Srdivacky assert(!T->isMutable()); 563193323Sed 564218893Sdim key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T)); 565193323Sed 566218893Sdim if (ImutInfo::isEqual(K,KCurrent)) { 567218893Sdim return combineTrees(getLeft(T), getRight(T)); 568218893Sdim } else if (ImutInfo::isLess(K,KCurrent)) { 569218893Sdim return balanceTree(remove_internal(K, getLeft(T)), 570218893Sdim getValue(T), getRight(T)); 571218893Sdim } else { 572218893Sdim return balanceTree(getLeft(T), getValue(T), 573218893Sdim remove_internal(K, getRight(T))); 574218893Sdim } 575193323Sed } 576193323Sed 577218893Sdim TreeTy* combineTrees(TreeTy* L, TreeTy* R) { 578218893Sdim if (isEmpty(L)) 579218893Sdim return R; 580218893Sdim if (isEmpty(R)) 581218893Sdim return L; 582193323Sed TreeTy* OldNode; 583218893Sdim TreeTy* newRight = removeMinBinding(R,OldNode); 584218893Sdim return balanceTree(L, getValue(OldNode), newRight); 585193323Sed } 586193323Sed 587218893Sdim TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) { 588202878Srdivacky assert(!isEmpty(T)); 589218893Sdim if (isEmpty(getLeft(T))) { 590218893Sdim Noderemoved = T; 591218893Sdim return getRight(T); 592193323Sed } 593218893Sdim return balanceTree(removeMinBinding(getLeft(T), Noderemoved), 594218893Sdim getValue(T), getRight(T)); 595193323Sed } 596193323Sed 597218893Sdim /// markImmutable - Clears the mutable bits of a root and all of its 598193323Sed /// descendants. 599218893Sdim void markImmutable(TreeTy* T) { 600193323Sed if (!T || !T->isMutable()) 601193323Sed return; 602218893Sdim T->markImmutable(); 603218893Sdim markImmutable(getLeft(T)); 604218893Sdim markImmutable(getRight(T)); 605198090Srdivacky } 606245431Sdim 607198090Srdivackypublic: 608218893Sdim TreeTy *getCanonicalTree(TreeTy *TNew) { 609198090Srdivacky if (!TNew) 610218893Sdim return 0; 611218893Sdim 612218893Sdim if (TNew->IsCanonicalized) 613218893Sdim return TNew; 614218893Sdim 615218893Sdim // Search the hashtable for another tree with the same digest, and 616218893Sdim // if find a collision compare those trees by their contents. 617218893Sdim unsigned digest = TNew->computeDigest(); 618235633Sdim TreeTy *&entry = Cache[maskCacheIndex(digest)]; 619218893Sdim do { 620218893Sdim if (!entry) 621218893Sdim break; 622218893Sdim for (TreeTy *T = entry ; T != 0; T = T->next) { 623218893Sdim // Compare the Contents('T') with Contents('TNew') 624218893Sdim typename TreeTy::iterator TI = T->begin(), TE = T->end(); 625218893Sdim if (!compareTreeWithSection(TNew, TI, TE)) 626218893Sdim continue; 627218893Sdim if (TI != TE) 628218893Sdim continue; // T has more contents than TNew. 629218893Sdim // Trees did match! Return 'T'. 630218893Sdim if (TNew->refCount == 0) 631218893Sdim TNew->destroy(); 632218893Sdim return T; 633218893Sdim } 634218893Sdim entry->prev = TNew; 635218893Sdim TNew->next = entry; 636198090Srdivacky } 637218893Sdim while (false); 638193323Sed 639218893Sdim entry = TNew; 640218893Sdim TNew->IsCanonicalized = true; 641198090Srdivacky return TNew; 642193323Sed } 643193323Sed}; 644193323Sed 645193323Sed//===----------------------------------------------------------------------===// 646193323Sed// Immutable AVL-Tree Iterators. 647193323Sed//===----------------------------------------------------------------------===// 648193323Sed 649193323Sedtemplate <typename ImutInfo> 650193323Sedclass ImutAVLTreeGenericIterator { 651193323Sed SmallVector<uintptr_t,20> stack; 652193323Sedpublic: 653193323Sed enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3, 654193323Sed Flags=0x3 }; 655193323Sed 656193323Sed typedef ImutAVLTree<ImutInfo> TreeTy; 657193323Sed typedef ImutAVLTreeGenericIterator<ImutInfo> _Self; 658193323Sed 659193323Sed inline ImutAVLTreeGenericIterator() {} 660193323Sed inline ImutAVLTreeGenericIterator(const TreeTy* Root) { 661193323Sed if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root)); 662193323Sed } 663193323Sed 664193323Sed TreeTy* operator*() const { 665202878Srdivacky assert(!stack.empty()); 666193323Sed return reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 667193323Sed } 668193323Sed 669245431Sdim uintptr_t getVisitState() const { 670202878Srdivacky assert(!stack.empty()); 671193323Sed return stack.back() & Flags; 672193323Sed } 673193323Sed 674193323Sed 675218893Sdim bool atEnd() const { return stack.empty(); } 676193323Sed 677218893Sdim bool atBeginning() const { 678193323Sed return stack.size() == 1 && getVisitState() == VisitedNone; 679193323Sed } 680193323Sed 681218893Sdim void skipToParent() { 682202878Srdivacky assert(!stack.empty()); 683193323Sed stack.pop_back(); 684193323Sed if (stack.empty()) 685193323Sed return; 686193323Sed switch (getVisitState()) { 687193323Sed case VisitedNone: 688193323Sed stack.back() |= VisitedLeft; 689193323Sed break; 690193323Sed case VisitedLeft: 691193323Sed stack.back() |= VisitedRight; 692193323Sed break; 693193323Sed default: 694235633Sdim llvm_unreachable("Unreachable."); 695193323Sed } 696193323Sed } 697193323Sed 698193323Sed inline bool operator==(const _Self& x) const { 699193323Sed if (stack.size() != x.stack.size()) 700193323Sed return false; 701193323Sed for (unsigned i = 0 ; i < stack.size(); i++) 702193323Sed if (stack[i] != x.stack[i]) 703193323Sed return false; 704193323Sed return true; 705193323Sed } 706193323Sed 707193323Sed inline bool operator!=(const _Self& x) const { return !operator==(x); } 708193323Sed 709193323Sed _Self& operator++() { 710202878Srdivacky assert(!stack.empty()); 711193323Sed TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 712202878Srdivacky assert(Current); 713193323Sed switch (getVisitState()) { 714193323Sed case VisitedNone: 715198090Srdivacky if (TreeTy* L = Current->getLeft()) 716193323Sed stack.push_back(reinterpret_cast<uintptr_t>(L)); 717193323Sed else 718193323Sed stack.back() |= VisitedLeft; 719193323Sed break; 720193323Sed case VisitedLeft: 721193323Sed if (TreeTy* R = Current->getRight()) 722193323Sed stack.push_back(reinterpret_cast<uintptr_t>(R)); 723193323Sed else 724193323Sed stack.back() |= VisitedRight; 725193323Sed break; 726193323Sed case VisitedRight: 727218893Sdim skipToParent(); 728193323Sed break; 729193323Sed default: 730235633Sdim llvm_unreachable("Unreachable."); 731193323Sed } 732193323Sed return *this; 733193323Sed } 734193323Sed 735193323Sed _Self& operator--() { 736202878Srdivacky assert(!stack.empty()); 737193323Sed TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 738202878Srdivacky assert(Current); 739193323Sed switch (getVisitState()) { 740193323Sed case VisitedNone: 741193323Sed stack.pop_back(); 742193323Sed break; 743193323Sed case VisitedLeft: 744193323Sed stack.back() &= ~Flags; // Set state to "VisitedNone." 745193323Sed if (TreeTy* L = Current->getLeft()) 746193323Sed stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight); 747193323Sed break; 748193323Sed case VisitedRight: 749193323Sed stack.back() &= ~Flags; 750193323Sed stack.back() |= VisitedLeft; 751193323Sed if (TreeTy* R = Current->getRight()) 752193323Sed stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight); 753193323Sed break; 754193323Sed default: 755235633Sdim llvm_unreachable("Unreachable."); 756193323Sed } 757193323Sed return *this; 758193323Sed } 759193323Sed}; 760193323Sed 761193323Sedtemplate <typename ImutInfo> 762193323Sedclass ImutAVLTreeInOrderIterator { 763193323Sed typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy; 764193323Sed InternalIteratorTy InternalItr; 765193323Sed 766193323Sedpublic: 767193323Sed typedef ImutAVLTree<ImutInfo> TreeTy; 768193323Sed typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self; 769193323Sed 770193323Sed ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) { 771193323Sed if (Root) operator++(); // Advance to first element. 772193323Sed } 773193323Sed 774193323Sed ImutAVLTreeInOrderIterator() : InternalItr() {} 775193323Sed 776193323Sed inline bool operator==(const _Self& x) const { 777193323Sed return InternalItr == x.InternalItr; 778193323Sed } 779193323Sed 780193323Sed inline bool operator!=(const _Self& x) const { return !operator==(x); } 781193323Sed 782193323Sed inline TreeTy* operator*() const { return *InternalItr; } 783193323Sed inline TreeTy* operator->() const { return *InternalItr; } 784193323Sed 785193323Sed inline _Self& operator++() { 786193323Sed do ++InternalItr; 787218893Sdim while (!InternalItr.atEnd() && 788193323Sed InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 789193323Sed 790193323Sed return *this; 791193323Sed } 792193323Sed 793193323Sed inline _Self& operator--() { 794193323Sed do --InternalItr; 795218893Sdim while (!InternalItr.atBeginning() && 796193323Sed InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 797193323Sed 798193323Sed return *this; 799193323Sed } 800193323Sed 801218893Sdim inline void skipSubTree() { 802218893Sdim InternalItr.skipToParent(); 803193323Sed 804218893Sdim while (!InternalItr.atEnd() && 805193323Sed InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft) 806193323Sed ++InternalItr; 807193323Sed } 808193323Sed}; 809193323Sed 810193323Sed//===----------------------------------------------------------------------===// 811193323Sed// Trait classes for Profile information. 812193323Sed//===----------------------------------------------------------------------===// 813193323Sed 814193323Sed/// Generic profile template. The default behavior is to invoke the 815193323Sed/// profile method of an object. Specializations for primitive integers 816193323Sed/// and generic handling of pointers is done below. 817193323Sedtemplate <typename T> 818193323Sedstruct ImutProfileInfo { 819193323Sed typedef const T value_type; 820193323Sed typedef const T& value_type_ref; 821193323Sed 822193323Sed static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 823193323Sed FoldingSetTrait<T>::Profile(X,ID); 824193323Sed } 825193323Sed}; 826193323Sed 827193323Sed/// Profile traits for integers. 828193323Sedtemplate <typename T> 829193323Sedstruct ImutProfileInteger { 830193323Sed typedef const T value_type; 831193323Sed typedef const T& value_type_ref; 832193323Sed 833193323Sed static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 834193323Sed ID.AddInteger(X); 835193323Sed } 836193323Sed}; 837193323Sed 838193323Sed#define PROFILE_INTEGER_INFO(X)\ 839193323Sedtemplate<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; 840193323Sed 841193323SedPROFILE_INTEGER_INFO(char) 842193323SedPROFILE_INTEGER_INFO(unsigned char) 843193323SedPROFILE_INTEGER_INFO(short) 844193323SedPROFILE_INTEGER_INFO(unsigned short) 845193323SedPROFILE_INTEGER_INFO(unsigned) 846193323SedPROFILE_INTEGER_INFO(signed) 847193323SedPROFILE_INTEGER_INFO(long) 848193323SedPROFILE_INTEGER_INFO(unsigned long) 849193323SedPROFILE_INTEGER_INFO(long long) 850193323SedPROFILE_INTEGER_INFO(unsigned long long) 851193323Sed 852193323Sed#undef PROFILE_INTEGER_INFO 853193323Sed 854263509Sdim/// Profile traits for booleans. 855263509Sdimtemplate <> 856263509Sdimstruct ImutProfileInfo<bool> { 857263509Sdim typedef const bool value_type; 858263509Sdim typedef const bool& value_type_ref; 859263509Sdim 860263509Sdim static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 861263509Sdim ID.AddBoolean(X); 862263509Sdim } 863263509Sdim}; 864263509Sdim 865263509Sdim 866193323Sed/// Generic profile trait for pointer types. We treat pointers as 867193323Sed/// references to unique objects. 868193323Sedtemplate <typename T> 869193323Sedstruct ImutProfileInfo<T*> { 870193323Sed typedef const T* value_type; 871193323Sed typedef value_type value_type_ref; 872193323Sed 873193323Sed static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) { 874193323Sed ID.AddPointer(X); 875193323Sed } 876193323Sed}; 877193323Sed 878193323Sed//===----------------------------------------------------------------------===// 879193323Sed// Trait classes that contain element comparison operators and type 880193323Sed// definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These 881193323Sed// inherit from the profile traits (ImutProfileInfo) to include operations 882193323Sed// for element profiling. 883193323Sed//===----------------------------------------------------------------------===// 884193323Sed 885193323Sed 886193323Sed/// ImutContainerInfo - Generic definition of comparison operations for 887193323Sed/// elements of immutable containers that defaults to using 888193323Sed/// std::equal_to<> and std::less<> to perform comparison of elements. 889193323Sedtemplate <typename T> 890193323Sedstruct ImutContainerInfo : public ImutProfileInfo<T> { 891193323Sed typedef typename ImutProfileInfo<T>::value_type value_type; 892193323Sed typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref; 893193323Sed typedef value_type key_type; 894193323Sed typedef value_type_ref key_type_ref; 895193323Sed typedef bool data_type; 896193323Sed typedef bool data_type_ref; 897193323Sed 898193323Sed static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 899193323Sed static inline data_type_ref DataOfValue(value_type_ref) { return true; } 900193323Sed 901193323Sed static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 902193323Sed return std::equal_to<key_type>()(LHS,RHS); 903193323Sed } 904193323Sed 905193323Sed static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 906193323Sed return std::less<key_type>()(LHS,RHS); 907193323Sed } 908193323Sed 909193323Sed static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 910193323Sed}; 911193323Sed 912193323Sed/// ImutContainerInfo - Specialization for pointer values to treat pointers 913193323Sed/// as references to unique objects. Pointers are thus compared by 914193323Sed/// their addresses. 915193323Sedtemplate <typename T> 916193323Sedstruct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { 917193323Sed typedef typename ImutProfileInfo<T*>::value_type value_type; 918193323Sed typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref; 919193323Sed typedef value_type key_type; 920193323Sed typedef value_type_ref key_type_ref; 921193323Sed typedef bool data_type; 922193323Sed typedef bool data_type_ref; 923193323Sed 924193323Sed static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 925193323Sed static inline data_type_ref DataOfValue(value_type_ref) { return true; } 926193323Sed 927193323Sed static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 928193323Sed return LHS == RHS; 929193323Sed } 930193323Sed 931193323Sed static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 932193323Sed return LHS < RHS; 933193323Sed } 934193323Sed 935193323Sed static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 936193323Sed}; 937193323Sed 938193323Sed//===----------------------------------------------------------------------===// 939193323Sed// Immutable Set 940193323Sed//===----------------------------------------------------------------------===// 941193323Sed 942193323Sedtemplate <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 943193323Sedclass ImmutableSet { 944193323Sedpublic: 945193323Sed typedef typename ValInfo::value_type value_type; 946193323Sed typedef typename ValInfo::value_type_ref value_type_ref; 947193323Sed typedef ImutAVLTree<ValInfo> TreeTy; 948193323Sed 949193323Sedprivate: 950198090Srdivacky TreeTy *Root; 951245431Sdim 952193323Sedpublic: 953193323Sed /// Constructs a set from a pointer to a tree root. In general one 954193323Sed /// should use a Factory object to create sets instead of directly 955193323Sed /// invoking the constructor, but there are cases where make this 956193323Sed /// constructor public is useful. 957218893Sdim explicit ImmutableSet(TreeTy* R) : Root(R) { 958218893Sdim if (Root) { Root->retain(); } 959218893Sdim } 960218893Sdim ImmutableSet(const ImmutableSet &X) : Root(X.Root) { 961218893Sdim if (Root) { Root->retain(); } 962218893Sdim } 963218893Sdim ImmutableSet &operator=(const ImmutableSet &X) { 964218893Sdim if (Root != X.Root) { 965218893Sdim if (X.Root) { X.Root->retain(); } 966218893Sdim if (Root) { Root->release(); } 967218893Sdim Root = X.Root; 968218893Sdim } 969218893Sdim return *this; 970218893Sdim } 971218893Sdim ~ImmutableSet() { 972218893Sdim if (Root) { Root->release(); } 973218893Sdim } 974193323Sed 975193323Sed class Factory { 976193323Sed typename TreeTy::Factory F; 977198090Srdivacky const bool Canonicalize; 978193323Sed 979193323Sed public: 980198090Srdivacky Factory(bool canonicalize = true) 981198090Srdivacky : Canonicalize(canonicalize) {} 982193323Sed 983198090Srdivacky Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) 984198090Srdivacky : F(Alloc), Canonicalize(canonicalize) {} 985193323Sed 986218893Sdim /// getEmptySet - Returns an immutable set that contains no elements. 987218893Sdim ImmutableSet getEmptySet() { 988218893Sdim return ImmutableSet(F.getEmptyTree()); 989198090Srdivacky } 990193323Sed 991218893Sdim /// add - Creates a new immutable set that contains all of the values 992193323Sed /// of the original set with the addition of the specified value. If 993193323Sed /// the original set already included the value, then the original set is 994193323Sed /// returned and no memory is allocated. The time and space complexity 995193323Sed /// of this operation is logarithmic in the size of the original set. 996193323Sed /// The memory allocated to represent the set is released when the 997193323Sed /// factory object that created the set is destroyed. 998218893Sdim ImmutableSet add(ImmutableSet Old, value_type_ref V) { 999218893Sdim TreeTy *NewT = F.add(Old.Root, V); 1000218893Sdim return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); 1001193323Sed } 1002193323Sed 1003218893Sdim /// remove - Creates a new immutable set that contains all of the values 1004193323Sed /// of the original set with the exception of the specified value. If 1005193323Sed /// the original set did not contain the value, the original set is 1006193323Sed /// returned and no memory is allocated. The time and space complexity 1007193323Sed /// of this operation is logarithmic in the size of the original set. 1008193323Sed /// The memory allocated to represent the set is released when the 1009193323Sed /// factory object that created the set is destroyed. 1010218893Sdim ImmutableSet remove(ImmutableSet Old, value_type_ref V) { 1011218893Sdim TreeTy *NewT = F.remove(Old.Root, V); 1012218893Sdim return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); 1013193323Sed } 1014193323Sed 1015193323Sed BumpPtrAllocator& getAllocator() { return F.getAllocator(); } 1016193323Sed 1017226890Sdim typename TreeTy::Factory *getTreeFactory() const { 1018226890Sdim return const_cast<typename TreeTy::Factory *>(&F); 1019226890Sdim } 1020245431Sdim 1021193323Sed private: 1022245431Sdim Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; 1023245431Sdim void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; 1024193323Sed }; 1025193323Sed 1026193323Sed friend class Factory; 1027193323Sed 1028218893Sdim /// Returns true if the set contains the specified value. 1029198090Srdivacky bool contains(value_type_ref V) const { 1030193323Sed return Root ? Root->contains(V) : false; 1031193323Sed } 1032193323Sed 1033218893Sdim bool operator==(const ImmutableSet &RHS) const { 1034193323Sed return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 1035193323Sed } 1036193323Sed 1037218893Sdim bool operator!=(const ImmutableSet &RHS) const { 1038193323Sed return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 1039193323Sed } 1040193323Sed 1041245431Sdim TreeTy *getRoot() { 1042218893Sdim if (Root) { Root->retain(); } 1043198090Srdivacky return Root; 1044198090Srdivacky } 1045245431Sdim 1046226890Sdim TreeTy *getRootWithoutRetain() const { 1047226890Sdim return Root; 1048226890Sdim } 1049193323Sed 1050193323Sed /// isEmpty - Return true if the set contains no elements. 1051193323Sed bool isEmpty() const { return !Root; } 1052193323Sed 1053193323Sed /// isSingleton - Return true if the set contains exactly one element. 1054193323Sed /// This method runs in constant time. 1055193323Sed bool isSingleton() const { return getHeight() == 1; } 1056193323Sed 1057193323Sed template <typename Callback> 1058193323Sed void foreach(Callback& C) { if (Root) Root->foreach(C); } 1059193323Sed 1060193323Sed template <typename Callback> 1061193323Sed void foreach() { if (Root) { Callback C; Root->foreach(C); } } 1062193323Sed 1063193323Sed //===--------------------------------------------------===// 1064193323Sed // Iterators. 1065193323Sed //===--------------------------------------------------===// 1066193323Sed 1067193323Sed class iterator { 1068193323Sed typename TreeTy::iterator itr; 1069252723Sdim 1070252723Sdim iterator() {} 1071193323Sed iterator(TreeTy* t) : itr(t) {} 1072193323Sed friend class ImmutableSet<ValT,ValInfo>; 1073252723Sdim 1074193323Sed public: 1075263509Sdim typedef ptrdiff_t difference_type; 1076252723Sdim typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type; 1077252723Sdim typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference; 1078252723Sdim typedef typename iterator::value_type *pointer; 1079252723Sdim typedef std::bidirectional_iterator_tag iterator_category; 1080252723Sdim 1081252723Sdim typename iterator::reference operator*() const { return itr->getValue(); } 1082252723Sdim typename iterator::pointer operator->() const { return &(operator*()); } 1083252723Sdim 1084252723Sdim iterator& operator++() { ++itr; return *this; } 1085252723Sdim iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1086252723Sdim iterator& operator--() { --itr; return *this; } 1087252723Sdim iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1088252723Sdim 1089252723Sdim bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 1090252723Sdim bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 1091193323Sed }; 1092193323Sed 1093193323Sed iterator begin() const { return iterator(Root); } 1094193323Sed iterator end() const { return iterator(); } 1095193323Sed 1096193323Sed //===--------------------------------------------------===// 1097193323Sed // Utility methods. 1098193323Sed //===--------------------------------------------------===// 1099193323Sed 1100202878Srdivacky unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 1101193323Sed 1102193323Sed static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) { 1103193323Sed ID.AddPointer(S.Root); 1104193323Sed } 1105193323Sed 1106193323Sed inline void Profile(FoldingSetNodeID& ID) const { 1107193323Sed return Profile(ID,*this); 1108193323Sed } 1109193323Sed 1110193323Sed //===--------------------------------------------------===// 1111193323Sed // For testing. 1112193323Sed //===--------------------------------------------------===// 1113193323Sed 1114218893Sdim void validateTree() const { if (Root) Root->validateTree(); } 1115193323Sed}; 1116245431Sdim 1117226890Sdim// NOTE: This may some day replace the current ImmutableSet. 1118226890Sdimtemplate <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 1119226890Sdimclass ImmutableSetRef { 1120226890Sdimpublic: 1121226890Sdim typedef typename ValInfo::value_type value_type; 1122226890Sdim typedef typename ValInfo::value_type_ref value_type_ref; 1123226890Sdim typedef ImutAVLTree<ValInfo> TreeTy; 1124226890Sdim typedef typename TreeTy::Factory FactoryTy; 1125245431Sdim 1126226890Sdimprivate: 1127226890Sdim TreeTy *Root; 1128226890Sdim FactoryTy *Factory; 1129245431Sdim 1130226890Sdimpublic: 1131226890Sdim /// Constructs a set from a pointer to a tree root. In general one 1132226890Sdim /// should use a Factory object to create sets instead of directly 1133226890Sdim /// invoking the constructor, but there are cases where make this 1134226890Sdim /// constructor public is useful. 1135226890Sdim explicit ImmutableSetRef(TreeTy* R, FactoryTy *F) 1136226890Sdim : Root(R), 1137226890Sdim Factory(F) { 1138226890Sdim if (Root) { Root->retain(); } 1139226890Sdim } 1140226890Sdim ImmutableSetRef(const ImmutableSetRef &X) 1141226890Sdim : Root(X.Root), 1142226890Sdim Factory(X.Factory) { 1143226890Sdim if (Root) { Root->retain(); } 1144226890Sdim } 1145226890Sdim ImmutableSetRef &operator=(const ImmutableSetRef &X) { 1146226890Sdim if (Root != X.Root) { 1147226890Sdim if (X.Root) { X.Root->retain(); } 1148226890Sdim if (Root) { Root->release(); } 1149226890Sdim Root = X.Root; 1150226890Sdim Factory = X.Factory; 1151226890Sdim } 1152226890Sdim return *this; 1153226890Sdim } 1154226890Sdim ~ImmutableSetRef() { 1155226890Sdim if (Root) { Root->release(); } 1156226890Sdim } 1157245431Sdim 1158226890Sdim static inline ImmutableSetRef getEmptySet(FactoryTy *F) { 1159226890Sdim return ImmutableSetRef(0, F); 1160226890Sdim } 1161245431Sdim 1162226890Sdim ImmutableSetRef add(value_type_ref V) { 1163226890Sdim return ImmutableSetRef(Factory->add(Root, V), Factory); 1164226890Sdim } 1165245431Sdim 1166226890Sdim ImmutableSetRef remove(value_type_ref V) { 1167226890Sdim return ImmutableSetRef(Factory->remove(Root, V), Factory); 1168226890Sdim } 1169245431Sdim 1170226890Sdim /// Returns true if the set contains the specified value. 1171226890Sdim bool contains(value_type_ref V) const { 1172226890Sdim return Root ? Root->contains(V) : false; 1173226890Sdim } 1174245431Sdim 1175226890Sdim ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const { 1176226890Sdim return ImmutableSet<ValT>(canonicalize ? 1177226890Sdim Factory->getCanonicalTree(Root) : Root); 1178226890Sdim } 1179245431Sdim 1180226890Sdim TreeTy *getRootWithoutRetain() const { 1181226890Sdim return Root; 1182226890Sdim } 1183245431Sdim 1184226890Sdim bool operator==(const ImmutableSetRef &RHS) const { 1185226890Sdim return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 1186226890Sdim } 1187245431Sdim 1188226890Sdim bool operator!=(const ImmutableSetRef &RHS) const { 1189226890Sdim return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 1190226890Sdim } 1191193323Sed 1192226890Sdim /// isEmpty - Return true if the set contains no elements. 1193226890Sdim bool isEmpty() const { return !Root; } 1194245431Sdim 1195226890Sdim /// isSingleton - Return true if the set contains exactly one element. 1196226890Sdim /// This method runs in constant time. 1197226890Sdim bool isSingleton() const { return getHeight() == 1; } 1198226890Sdim 1199226890Sdim //===--------------------------------------------------===// 1200226890Sdim // Iterators. 1201226890Sdim //===--------------------------------------------------===// 1202245431Sdim 1203226890Sdim class iterator { 1204226890Sdim typename TreeTy::iterator itr; 1205226890Sdim iterator(TreeTy* t) : itr(t) {} 1206226890Sdim friend class ImmutableSetRef<ValT,ValInfo>; 1207226890Sdim public: 1208226890Sdim iterator() {} 1209226890Sdim inline value_type_ref operator*() const { return itr->getValue(); } 1210226890Sdim inline iterator& operator++() { ++itr; return *this; } 1211226890Sdim inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1212226890Sdim inline iterator& operator--() { --itr; return *this; } 1213226890Sdim inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1214226890Sdim inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 1215226890Sdim inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 1216226890Sdim inline value_type *operator->() const { return &(operator*()); } 1217226890Sdim }; 1218245431Sdim 1219226890Sdim iterator begin() const { return iterator(Root); } 1220226890Sdim iterator end() const { return iterator(); } 1221245431Sdim 1222226890Sdim //===--------------------------------------------------===// 1223226890Sdim // Utility methods. 1224226890Sdim //===--------------------------------------------------===// 1225245431Sdim 1226226890Sdim unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 1227245431Sdim 1228226890Sdim static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { 1229226890Sdim ID.AddPointer(S.Root); 1230226890Sdim } 1231245431Sdim 1232226890Sdim inline void Profile(FoldingSetNodeID& ID) const { 1233226890Sdim return Profile(ID,*this); 1234226890Sdim } 1235245431Sdim 1236226890Sdim //===--------------------------------------------------===// 1237226890Sdim // For testing. 1238226890Sdim //===--------------------------------------------------===// 1239245431Sdim 1240226890Sdim void validateTree() const { if (Root) Root->validateTree(); } 1241226890Sdim}; 1242226890Sdim 1243193323Sed} // end namespace llvm 1244193323Sed 1245193323Sed#endif 1246