ImmutableSet.h revision 8b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550
133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===// 233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// 333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// The LLVM Compiler Infrastructure 433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// 833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// 1033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// This file defines the ImutAVLTree and ImmutableSet classes. 1133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// 1233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 1333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#ifndef LLVM_ADT_IMSET_H 1533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#define LLVM_ADT_IMSET_H 1633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#include "llvm/Support/Allocator.h" 1833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#include "llvm/ADT/FoldingSet.h" 19a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek#include "llvm/Support/DataTypes.h" 2033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#include <cassert> 21602d1c51e055efd56b284a2ba41083ff38c337bcAnton Korobeynikov#include <functional> 2233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 2333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremeneknamespace llvm { 243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 2633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Immutable AVL-Tree Definition. 2733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 2833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 2933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename ImutInfo> class ImutAVLFactory; 30ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenektemplate <typename ImutInfo> class ImutAVLTreeInOrderIterator; 31f357afb4045307a24c52606e267385148367a7a3Ted Kremenektemplate <typename ImutInfo> class ImutAVLTreeGenericIterator; 323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename ImutInfo > 3433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImutAVLTree : public FoldingSetNode { 3533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 3633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutInfo::key_type_ref key_type_ref; 3733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutInfo::value_type value_type; 3833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutInfo::value_type_ref value_type_ref; 39ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 4033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef ImutAVLFactory<ImutInfo> Factory; 4133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek friend class ImutAVLFactory<ImutInfo>; 423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43f357afb4045307a24c52606e267385148367a7a3Ted Kremenek friend class ImutAVLTreeGenericIterator<ImutInfo>; 44f357afb4045307a24c52606e267385148367a7a3Ted Kremenek friend class FoldingSet<ImutAVLTree>; 453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 46ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator; 473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 4933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Public Interface. 503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 52ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// getLeft - Returns a pointer to the left subtree. This value 53ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// is NULL if there is no left subtree. 54633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek ImutAVLTree *getLeft() const { 55633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek return reinterpret_cast<ImutAVLTree*>(Left & ~LeftFlags); 56ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek } 573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 58ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// getRight - Returns a pointer to the right subtree. This value is 59ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// NULL if there is no right subtree. 603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ImutAVLTree* getRight() const { return Right; } 613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 62ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// getHeight - Returns the height of the tree. A tree with no subtrees 63ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// has a height of 1. 643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman unsigned getHeight() const { return Height; } 653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 66ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// getValue - Returns the data value associated with the tree node. 6733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek const value_type& getValue() const { return Value; } 683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 69ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// find - Finds the subtree associated with the specified key value. 70ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// This method returns NULL if no matching subtree is found. 7133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutAVLTree* find(key_type_ref K) { 7233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutAVLTree *T = this; 733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek while (T) { 75be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue()); 763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (ImutInfo::isEqual(K,CurrentKey)) 7833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 7933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else if (ImutInfo::isLess(K,CurrentKey)) 8033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek T = T->getLeft(); 8133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else 8233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek T = T->getRight(); 8333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return NULL; 8633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 871c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek 881c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// getMaxElement - Find the subtree associated with the highest ranged 891c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// key value. 901c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek ImutAVLTree* getMaxElement() { 911c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek ImutAVLTree *T = this; 921c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek ImutAVLTree *Right = T->getRight(); 931c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek while (Right) { T = Right; Right = T->getRight(); } 941c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek return T; 951c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek } 963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 97ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// size - Returns the number of nodes in the tree, which includes 98ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// both leaves and non-leaf nodes. 9933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned size() const { 10033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned n = 1; 1013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (const ImutAVLTree* L = getLeft()) n += L->size(); 10333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (const ImutAVLTree* R = getRight()) n += R->size(); 1043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return n; 10633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 108ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// begin - Returns an iterator that iterates over the nodes of the tree 109ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// in an inorder traversal. The returned iterator thus refers to the 110ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// the tree node with the minimum data element. 111ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator begin() const { return iterator(this); } 1123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 113ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// end - Returns an iterator for the tree that denotes the end of an 114ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// inorder traversal. 115ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator end() const { return iterator(); } 1163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 117f357afb4045307a24c52606e267385148367a7a3Ted Kremenek bool ElementEqual(value_type_ref V) const { 118f357afb4045307a24c52606e267385148367a7a3Ted Kremenek // Compare the keys. 119f357afb4045307a24c52606e267385148367a7a3Ted Kremenek if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()), 120f357afb4045307a24c52606e267385148367a7a3Ted Kremenek ImutInfo::KeyOfValue(V))) 121f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return false; 1223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 123f357afb4045307a24c52606e267385148367a7a3Ted Kremenek // Also compare the data values. 124f357afb4045307a24c52606e267385148367a7a3Ted Kremenek if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()), 125f357afb4045307a24c52606e267385148367a7a3Ted Kremenek ImutInfo::DataOfValue(V))) 126f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return false; 1273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 128f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return true; 129f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 1303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 131f357afb4045307a24c52606e267385148367a7a3Ted Kremenek bool ElementEqual(const ImutAVLTree* RHS) const { 132f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return ElementEqual(RHS->getValue()); 133f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 1343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 135ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// isEqual - Compares two trees for structural equality and returns true 136ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// if they are equal. This worst case performance of this operation is 137ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek // linear in the sizes of the trees. 13833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEqual(const ImutAVLTree& RHS) const { 139ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (&RHS == this) 140ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return true; 1413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 142ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator LItr = begin(), LEnd = end(); 143ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator RItr = RHS.begin(), REnd = RHS.end(); 1443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 145ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek while (LItr != LEnd && RItr != REnd) { 146ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (*LItr == *RItr) { 147ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek LItr.SkipSubTree(); 148ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek RItr.SkipSubTree(); 149ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek continue; 150ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 1513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 152f357afb4045307a24c52606e267385148367a7a3Ted Kremenek if (!LItr->ElementEqual(*RItr)) 153e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek return false; 1543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 155ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek ++LItr; 156ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek ++RItr; 157ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 1583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 159ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return LItr == LEnd && RItr == REnd; 16033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 161ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek 162ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// isNotEqual - Compares two trees for structural inequality. Performance 163ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// is the same is isEqual. 16433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); } 1653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 166ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// contains - Returns true if this tree contains a subtree (node) that 167ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// has an data element that matches the specified key. Complexity 168ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// is logarithmic in the size of the tree. 169aafa94260d5b1b6422258ed3db7244fe4449f217Daniel Dunbar bool contains(key_type_ref K) { return (bool) find(K); } 1703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 171ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// foreach - A member template the accepts invokes operator() on a functor 172ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// object (specifed by Callback) for every node/subtree in the tree. 173ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// Nodes are visited using an inorder traversal. 17433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 17533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void foreach(Callback& C) { 17633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (ImutAVLTree* L = getLeft()) L->foreach(C); 1773a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman C(Value); 1793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (ImutAVLTree* R = getRight()) R->foreach(C); 18133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 183ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// verify - A utility method that checks that the balancing and 184ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// ordering invariants of the tree are satisifed. It is a recursive 185ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// method that returns the height of the tree, which is then consumed 186ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// by the enclosing verify call. External callers should ignore the 187ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// return value. An invalid tree will cause an assertion to fire in 188ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// a debug build. 18933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned verify() const { 19033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned HL = getLeft() ? getLeft()->verify() : 0; 19133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned HR = getRight() ? getRight()->verify() : 0; 1923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman assert (getHeight() == ( HL > HR ? HL : HR ) + 1 19433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek && "Height calculation wrong."); 1953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 19633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert ((HL > HR ? HL-HR : HR-HL) <= 2 19733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek && "Balancing invariant violated."); 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 20033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!getLeft() 20133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()), 20233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutInfo::KeyOfValue(getValue())) 20333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek && "Value in left child is not less that current value."); 2043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 20633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!getRight() 20733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()), 20833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutInfo::KeyOfValue(getRight()->getValue())) 20933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek && "Current value is not less that value of right child."); 2103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 21133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return getHeight(); 212f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 2133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 21495da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek /// Profile - Profiling for ImutAVLTree. 21595da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek void Profile(llvm::FoldingSetNodeID& ID) { 21695da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek ID.AddInteger(ComputeDigest()); 21795da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek } 2183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 22033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Internal Values. 22133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===----------------------------------------------------===// 2223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 22333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 22433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek uintptr_t Left; 22533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutAVLTree* Right; 22633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned Height; 22733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek value_type Value; 228633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek uint32_t Digest; 2293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 23133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Internal methods (node manipulation; used by Factory). 23233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===----------------------------------------------------===// 233f357afb4045307a24c52606e267385148367a7a3Ted Kremenek 23433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 2353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 236633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek enum { Mutable = 0x1, NoCachedDigest = 0x2, LeftFlags = 0x3 }; 237f357afb4045307a24c52606e267385148367a7a3Ted Kremenek 23885d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// ImutAVLTree - Internal constructor that is only called by 23985d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// ImutAVLFactory. 24033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height) 241633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek : Left(reinterpret_cast<uintptr_t>(l) | (Mutable | NoCachedDigest)), 24295da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek Right(r), Height(height), Value(v), Digest(0) {} 2433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 24585d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// isMutable - Returns true if the left and right subtree references 24685d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// (as well as height) can be changed. If this method returns false, 24785d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// the tree is truly immutable. Trees returned from an ImutAVLFactory 24885d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// object should always have this method return true. Further, if this 24985d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// method returns false for an instance of ImutAVLTree, all subtrees 25085d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// will also have this method return false. The converse is not true. 25185d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek bool isMutable() const { return Left & Mutable; } 252633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek 253633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// hasCachedDigest - Returns true if the digest for this tree is cached. 254633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// This can only be true if the tree is immutable. 255633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek bool hasCachedDigest() const { return !(Left & NoCachedDigest); } 2563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 25885d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // Mutating operations. A tree root can be manipulated as 2593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // long as its reference has not "escaped" from internal 26085d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // methods of a factory object (see below). When a tree 2613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // pointer is externally viewable by client code, the 2623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // internal "mutable bit" is cleared to mark the tree 26385d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // immutable. Note that a tree that still has its mutable 26485d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // bit set may have children (subtrees) that are themselves 26533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // immutable. 26685d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek //===----------------------------------------------------===// 2673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 26885d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// MarkImmutable - Clears the mutable flag for a tree. After this happens, 269633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// it is an error to call setLeft(), setRight(), and setHeight(). 270fd9c58adde8d62c0e1bd852e2c8c1d58088f8f03Ted Kremenek void MarkImmutable() { 271633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek assert(isMutable() && "Mutable flag already removed."); 27285d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek Left &= ~Mutable; 27333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 274633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek 275633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// MarkedCachedDigest - Clears the NoCachedDigest flag for a tree. 276633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek void MarkedCachedDigest() { 277633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek assert(!hasCachedDigest() && "NoCachedDigest flag already removed."); 278633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek Left &= ~NoCachedDigest; 279633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek } 2803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 28185d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// setLeft - Changes the reference of the left subtree. Used internally 28285d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// by ImutAVLFactory. 28333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void setLeft(ImutAVLTree* NewLeft) { 284633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek assert(isMutable() && 285633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek "Only a mutable tree can have its left subtree changed."); 286633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek Left = reinterpret_cast<uintptr_t>(NewLeft) | LeftFlags; 28733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 2883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 28985d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// setRight - Changes the reference of the right subtree. Used internally 29085d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// by ImutAVLFactory. 29133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void setRight(ImutAVLTree* NewRight) { 2928f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek assert(isMutable() && 2938f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek "Only a mutable tree can have its right subtree changed."); 2943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 29533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Right = NewRight; 2968f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek // Set the NoCachedDigest flag. 2978f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek Left = Left | NoCachedDigest; 2988f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek 29933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 3003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 30185d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// setHeight - Changes the height of the tree. Used internally by 30285d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// ImutAVLFactory. 30333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void setHeight(unsigned h) { 3048f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek assert(isMutable() && "Only a mutable tree can have its height changed."); 30533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Height = h; 30633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 3073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 308f357afb4045307a24c52606e267385148367a7a3Ted Kremenek static inline 309633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek uint32_t ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { 310633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek uint32_t digest = 0; 3113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 312633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (L) 313633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek digest += L->ComputeDigest(); 3143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 315633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek // Compute digest of stored data. 316633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek FoldingSetNodeID ID; 317633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek ImutInfo::Profile(ID,V); 318633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek digest += ID.ComputeHash(); 3193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 320633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (R) 321633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek digest += R->ComputeDigest(); 3223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 32395da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek return digest; 324f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 3253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 326633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek inline uint32_t ComputeDigest() { 327633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek // Check the lowest bit to determine if digest has actually been 328633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek // pre-computed. 329633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (hasCachedDigest()) 330633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek return Digest; 331633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek 332633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek uint32_t X = ComputeDigest(getLeft(), getRight(), getValue()); 3338f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek Digest = X; 3349bd2acb3b253c77dd1f7680a2e6505039e9c49a5Ted Kremenek MarkedCachedDigest(); 335f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return X; 336f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 33733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 33833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 3393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 34033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Immutable AVL-Tree Factory class. 34133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 34233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 3433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate <typename ImutInfo > 34433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImutAVLFactory { 34533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef ImutAVLTree<ImutInfo> TreeTy; 34633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename TreeTy::value_type_ref value_type_ref; 34733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename TreeTy::key_type_ref key_type_ref; 3483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 34933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef FoldingSet<TreeTy> CacheTy; 3503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 351a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek CacheTy Cache; 352a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek uintptr_t Allocator; 3533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 354a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek bool ownsAllocator() const { 355a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek return Allocator & 0x1 ? false : true; 356a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek } 357a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek 3583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman BumpPtrAllocator& getAllocator() const { 359a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 360a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek } 3613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 36333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Public interface. 36433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 3653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 36633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 367a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek ImutAVLFactory() 368a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 3693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 370a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek ImutAVLFactory(BumpPtrAllocator& Alloc) 371a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 3723a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 373a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek ~ImutAVLFactory() { 374a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek if (ownsAllocator()) delete &getAllocator(); 375a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek } 3763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 37733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Add(TreeTy* T, value_type_ref V) { 37833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek T = Add_internal(V,T); 37933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek MarkImmutable(T); 38033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 38133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 3823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 38333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Remove(TreeTy* T, key_type_ref V) { 38433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek T = Remove_internal(V,T); 38533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek MarkImmutable(T); 38633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 38733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 3883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 38933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* GetEmptyTree() const { return NULL; } 3903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 39233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // A bunch of quick helper functions used for reasoning 39333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // about the properties of trees and their children. 39433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // These have succinct names so that the balancing code 39533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // is as terse (and readable) as possible. 39633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 39733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 3983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 399ac6084dfc22042da72b5170f52e3ceaad978fcffTed Kremenek bool isEmpty(TreeTy* T) const { return !T; } 4003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; } 401633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek TreeTy* Left(TreeTy* T) const { return T->getLeft(); } 4023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman TreeTy* Right(TreeTy* T) const { return T->getRight(); } 403ac6084dfc22042da72b5170f52e3ceaad978fcffTed Kremenek value_type_ref Value(TreeTy* T) const { return T->Value; } 4043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 40533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned IncrementHeight(TreeTy* L, TreeTy* R) const { 40633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned hl = Height(L); 40733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned hr = Height(R); 40833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return ( hl > hr ? hl : hr ) + 1; 40933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 411f357afb4045307a24c52606e267385148367a7a3Ted Kremenek static bool CompareTreeWithSection(TreeTy* T, 412f357afb4045307a24c52606e267385148367a7a3Ted Kremenek typename TreeTy::iterator& TI, 413f357afb4045307a24c52606e267385148367a7a3Ted Kremenek typename TreeTy::iterator& TE) { 4143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 415f357afb4045307a24c52606e267385148367a7a3Ted Kremenek typename TreeTy::iterator I = T->begin(), E = T->end(); 4163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 417f357afb4045307a24c52606e267385148367a7a3Ted Kremenek for ( ; I!=E ; ++I, ++TI) 418f357afb4045307a24c52606e267385148367a7a3Ted Kremenek if (TI == TE || !I->ElementEqual(*TI)) 419f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return false; 420f357afb4045307a24c52606e267385148367a7a3Ted Kremenek 421f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return true; 4223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 4233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 425be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek // "CreateNode" is used to generate new tree roots that link 42633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // to other trees. The functon may also simply move links 42733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // in an existing root if that root is still marked mutable. 42833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // This is necessary because otherwise our balancing code 42933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // would leak memory as it would create nodes that are 43033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // then discarded later before the finished tree is 43133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // returned to the caller. 43233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 4333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4348b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) { 435a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek BumpPtrAllocator& A = getAllocator(); 436a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek TreeTy* T = (TreeTy*) A.Allocate<TreeTy>(); 43713a21b02374a5a5fe541dbfbd1491b25a00369f4Ted Kremenek new (T) TreeTy(L,R,V,IncrementHeight(L,R)); 438f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return T; 43933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) { 44233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!isEmpty(OldTree)); 4433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 44433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (OldTree->isMutable()) { 44533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek OldTree->setLeft(L); 44633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek OldTree->setRight(R); 44733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek OldTree->setHeight(IncrementHeight(L,R)); 44833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return OldTree; 44933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4508f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek else 4518f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek return CreateNode(L, Value(OldTree), R); 45233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 45433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// Balance - Used by Add_internal and Remove_internal to 45533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// balance a newly created tree. 45633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) { 4573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 45833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned hl = Height(L); 45933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned hr = Height(R); 4603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 46133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (hl > hr + 2) { 46233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!isEmpty(L) && 46333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek "Left tree cannot be empty to have a height >= 2."); 4643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 46533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* LL = Left(L); 46633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* LR = Right(L); 4673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 46833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (Height(LL) >= Height(LR)) 469be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek return CreateNode(LL, L, CreateNode(LR,V,R)); 4703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 47133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!isEmpty(LR) && 47233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek "LR cannot be empty because it has a height >= 1."); 4733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 47433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* LRL = Left(LR); 47533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* LRR = Right(LR); 4763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4773a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R)); 47833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 47933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else if (hr > hl + 2) { 48033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!isEmpty(R) && 48133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek "Right tree cannot be empty to have a height >= 2."); 4823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 48333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* RL = Left(R); 48433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* RR = Right(R); 4853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 48633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (Height(RR) >= Height(RL)) 487be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek return CreateNode(CreateNode(L,V,RL), R, RR); 4883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 48933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!isEmpty(RL) && 49033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek "RL cannot be empty because it has a height >= 1."); 4913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 49233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* RLL = Left(RL); 49333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* RLR = Right(RL); 4943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 495be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR)); 49633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 49733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else 498be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek return CreateNode(L,V,R); 49933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 50133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// Add_internal - Creates a new tree that includes the specified 50233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// data and the data from the original tree. If the original tree 50333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// already contained the data item, the original tree is returned. 50433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Add_internal(value_type_ref V, TreeTy* T) { 50533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (isEmpty(T)) 506be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek return CreateNode(T, V, T); 5073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 50833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!T->isMutable()); 5093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 51033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek key_type_ref K = ImutInfo::KeyOfValue(V); 51133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T)); 5123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 51333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (ImutInfo::isEqual(K,KCurrent)) 514be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek return CreateNode(Left(T), V, Right(T)); 51533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else if (ImutInfo::isLess(K,KCurrent)) 51633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Balance(Add_internal(V,Left(T)), Value(T), Right(T)); 51733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else 51833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Balance(Left(T), Value(T), Add_internal(V,Right(T))); 51933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 521b90c37f64c5b856a4492f0c1f16c065ae9e31232Nick Lewycky /// Remove_internal - Creates a new tree that includes all the data 52233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// from the original tree except the specified data. If the 52333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// specified data did not exist in the original tree, the original 52433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// tree is returned. 52533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Remove_internal(key_type_ref K, TreeTy* T) { 52633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (isEmpty(T)) 52733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 5283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 52933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!T->isMutable()); 5303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 53133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T)); 5323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 53333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (ImutInfo::isEqual(K,KCurrent)) 53433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return CombineLeftRightTrees(Left(T),Right(T)); 53533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else if (ImutInfo::isLess(K,KCurrent)) 53633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Balance(Remove_internal(K,Left(T)), Value(T), Right(T)); 53733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else 53833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Balance(Left(T), Value(T), Remove_internal(K,Right(T))); 53933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 54133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) { 5423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman if (isEmpty(L)) return R; 54333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (isEmpty(R)) return L; 5443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman TreeTy* OldNode; 54633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* NewRight = RemoveMinBinding(R,OldNode); 54733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Balance(L,Value(OldNode),NewRight); 54833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 55033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) { 55133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek assert (!isEmpty(T)); 5523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 55333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (isEmpty(Left(T))) { 55433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek NodeRemoved = T; 55533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Right(T); 55633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 55833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T)); 5593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 5603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 56133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// MarkImmutable - Clears the mutable bits of a root and all of its 56233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// descendants. 56333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void MarkImmutable(TreeTy* T) { 56433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (!T || !T->isMutable()) 56533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return; 5663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 567fd9c58adde8d62c0e1bd852e2c8c1d58088f8f03Ted Kremenek T->MarkImmutable(); 56833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek MarkImmutable(Left(T)); 56933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek MarkImmutable(Right(T)); 5708b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek } 5718b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5728b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenekpublic: 5738b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek TreeTy *GetCanonicalTree(TreeTy *TNew) { 5748b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (!TNew) 5758b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return NULL; 5768b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5778b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // Search the FoldingSet bucket for a Tree with the same digest. 5788b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek FoldingSetNodeID ID; 5798b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek unsigned digest = TNew->ComputeDigest(); 5808b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek ID.AddInteger(digest); 5818b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek unsigned hash = ID.ComputeHash(); 5828b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5838b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash); 5848b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek typename CacheTy::bucket_iterator E = Cache.bucket_end(hash); 5858b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5868b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek for (; I != E; ++I) { 5878b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek TreeTy *T = &*I; 5888b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5898b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (T->ComputeDigest() != digest) 5908b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek continue; 5918b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5928b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // We found a collision. Perform a comparison of Contents('T') 5938b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // with Contents('L')+'V'+Contents('R'). 5948b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek typename TreeTy::iterator TI = T->begin(), TE = T->end(); 5958b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 5968b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // First compare Contents('L') with the (initial) contents of T. 5978b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (!CompareTreeWithSection(TNew->getLeft(), TI, TE)) 5988b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek continue; 5998b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 6008b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // Now compare the new data element. 6018b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (TI == TE || !TI->ElementEqual(TNew->getValue())) 6028b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek continue; 6038b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 6048b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek ++TI; 6058b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 6068b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // Now compare the remainder of 'T' with 'R'. 6078b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (!CompareTreeWithSection(TNew->getRight(), TI, TE)) 6088b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek continue; 6098b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 6108b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (TI != TE) 6118b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek continue; // Contents('R') did not match suffix of 'T'. 6128b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 6138b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // Trees did match! Return 'T'. 6148b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return T; 6158b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek } 6163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6178b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek // 'TNew' is the only tree of its kind. Return it. 6188b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek Cache.InsertNode(TNew, (void*) &*Cache.bucket_end(hash)); 6198b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return TNew; 62033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 62133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 6223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 625ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek// Immutable AVL-Tree Iterators. 6263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 62733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 628ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenektemplate <typename ImutInfo> 629ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekclass ImutAVLTreeGenericIterator { 630ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek SmallVector<uintptr_t,20> stack; 631ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekpublic: 6323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3, 633ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek Flags=0x3 }; 6343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman typedef ImutAVLTree<ImutInfo> TreeTy; 636ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeGenericIterator<ImutInfo> _Self; 637ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 638ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline ImutAVLTreeGenericIterator() {} 639ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline ImutAVLTreeGenericIterator(const TreeTy* Root) { 640ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root)); 6413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 6423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 643ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek TreeTy* operator*() const { 6443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman assert (!stack.empty()); 645ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 646ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 648ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek uintptr_t getVisitState() { 649ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (!stack.empty()); 650ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return stack.back() & Flags; 651ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 654ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek bool AtEnd() const { return stack.empty(); } 65533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 6563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman bool AtBeginning() const { 657ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return stack.size() == 1 && getVisitState() == VisitedNone; 658ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 660ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek void SkipToParent() { 661ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (!stack.empty()); 662ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.pop_back(); 6633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 664ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (stack.empty()) 665ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return; 6663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 667ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek switch (getVisitState()) { 668ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedNone: 669ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedLeft; 670ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 671ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedLeft: 672ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedRight; 673ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 674ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek default: 6753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman assert (false && "Unreachable."); 676ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 677ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 679ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline bool operator==(const _Self& x) const { 680ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (stack.size() != x.stack.size()) 681ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return false; 6823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 683ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek for (unsigned i = 0 ; i < stack.size(); i++) 684ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (stack[i] != x.stack[i]) 685ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return false; 6863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 687ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return true; 688ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline bool operator!=(const _Self& x) const { return !operator==(x); } 6913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 692ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek _Self& operator++() { 693ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (!stack.empty()); 6943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 695ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 696ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (Current); 6973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 698ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek switch (getVisitState()) { 699ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedNone: 700633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (TreeTy* L = Current->getLeft()) 701ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(L)); 702ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek else 703ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedLeft; 7043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 705ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 707ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedLeft: 708ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (TreeTy* R = Current->getRight()) 709ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(R)); 710ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek else 711ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedRight; 7123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 713ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 715ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedRight: 7163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman SkipToParent(); 717ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 719ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek default: 720ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (false && "Unreachable."); 721ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 723ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 724ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 726ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek _Self& operator--() { 727ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (!stack.empty()); 7283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 729ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 730ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (Current); 7313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 732ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek switch (getVisitState()) { 733ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedNone: 734ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.pop_back(); 735ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman case VisitedLeft: 738ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() &= ~Flags; // Set state to "VisitedNone." 7393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 740ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (TreeTy* L = Current->getLeft()) 741ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight); 7423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 743ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman case VisitedRight: 746ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() &= ~Flags; 747ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedLeft; 7483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 749ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (TreeTy* R = Current->getRight()) 750ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight); 7513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 752ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 754ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek default: 755ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek assert (false && "Unreachable."); 756ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 758ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 759ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 760ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek}; 7613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 762ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenektemplate <typename ImutInfo> 763ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekclass ImutAVLTreeInOrderIterator { 764ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy; 765ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalIteratorTy InternalItr; 766ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 767ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekpublic: 768ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTree<ImutInfo> TreeTy; 769ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self; 770ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 7713a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) { 772ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (Root) operator++(); // Advance to first element. 773ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7743a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 775ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek ImutAVLTreeInOrderIterator() : InternalItr() {} 776ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 777ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline bool operator==(const _Self& x) const { 778ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return InternalItr == x.InternalItr; 779ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline bool operator!=(const _Self& x) const { return !operator==(x); } 7823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 783bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline TreeTy* operator*() const { return *InternalItr; } 784bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline TreeTy* operator->() const { return *InternalItr; } 7853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline _Self& operator++() { 787ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek do ++InternalItr; 7883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (!InternalItr.AtEnd() && 789ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 790ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 791ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 792ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline _Self& operator--() { 795ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek do --InternalItr; 7963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (!InternalItr.AtBeginning() && 797ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 7983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 799ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 800ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 8013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 802ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline void SkipSubTree() { 803ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.SkipToParent(); 8043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 805ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek while (!InternalItr.AtEnd() && 806ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft) 8073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ++InternalItr; 808ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 809ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek}; 8103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 81233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Trait classes for Profile information. 81333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 81433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 81533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// Generic profile template. The default behavior is to invoke the 81633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// profile method of an object. Specializations for primitive integers 81733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// and generic handling of pointers is done below. 81833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 81933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutProfileInfo { 82033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T value_type; 82133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T& value_type_ref; 8223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 82333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 8243cf8bec783809269a5dbb81d6d1693ee18fcb37cTed Kremenek FoldingSetTrait<T>::Profile(X,ID); 8253cf8bec783809269a5dbb81d6d1693ee18fcb37cTed Kremenek } 82633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 82733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 82833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// Profile traits for integers. 82933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 8303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanstruct ImutProfileInteger { 83133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T value_type; 83233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T& value_type_ref; 8333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 83433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 83533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ID.AddInteger(X); 8363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 83733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 83833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 83933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#define PROFILE_INTEGER_INFO(X)\ 84033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; 84133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 84233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(char) 84333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned char) 84433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(short) 84533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned short) 84633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned) 84733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(signed) 84833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(long) 84933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned long) 85033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(long long) 85133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned long long) 85233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 85333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#undef PROFILE_INTEGER_INFO 85433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 85533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// Generic profile trait for pointer types. We treat pointers as 85633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// references to unique objects. 85733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 85833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutProfileInfo<T*> { 85933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T* value_type; 86033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type value_type_ref; 8613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 86233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) { 86333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ID.AddPointer(X); 86433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 86533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 86633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 8673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 86833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Trait classes that contain element comparison operators and type 86933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These 87033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// inherit from the profile traits (ImutProfileInfo) to include operations 87133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// for element profiling. 87233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 87333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 87433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 87533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// ImutContainerInfo - Generic definition of comparison operations for 87633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// elements of immutable containers that defaults to using 87733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// std::equal_to<> and std::less<> to perform comparison of elements. 87833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 87933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutContainerInfo : public ImutProfileInfo<T> { 88033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T>::value_type value_type; 88133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref; 88233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type key_type; 88333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type_ref key_type_ref; 884e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type; 885e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type_ref; 8863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 88733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 888e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline data_type_ref DataOfValue(value_type_ref) { return true; } 8893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 89133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return std::equal_to<key_type>()(LHS,RHS); 89233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 8933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 89433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 89533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return std::less<key_type>()(LHS,RHS); 89633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 8973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 898e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 89933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 90033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 90133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// ImutContainerInfo - Specialization for pointer values to treat pointers 90233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// as references to unique objects. Pointers are thus compared by 90333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// their addresses. 90433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 90533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { 90633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T*>::value_type value_type; 90733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref; 90833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type key_type; 90933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type_ref key_type_ref; 910e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type; 911e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type_ref; 9123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 91333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 914e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline data_type_ref DataOfValue(value_type_ref) { return true; } 9153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 91633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 91733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return LHS == RHS; 91833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 92033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 92133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return LHS < RHS; 92233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 924e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 92533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 92633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 9273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 92833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Immutable Set 92933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 93033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 93133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 93233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImmutableSet { 93333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 93433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type value_type; 93533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 93633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 9371eed950d7cb69906264cfb49895165e3b51524beTed Kremenek 9383a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanprivate: 9398b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek TreeTy *Root; 9408b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek 94133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 9421eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// Constructs a set from a pointer to a tree root. In general one 9431eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// should use a Factory object to create sets instead of directly 9441eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// invoking the constructor, but there are cases where make this 9451eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// constructor public is useful. 9461eed950d7cb69906264cfb49895165e3b51524beTed Kremenek explicit ImmutableSet(TreeTy* R) : Root(R) {} 9473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 94833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek class Factory { 94933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typename TreeTy::Factory F; 9503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 95133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek public: 95233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Factory() {} 9533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 954a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek Factory(BumpPtrAllocator& Alloc) 955a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek : F(Alloc) {} 9563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 95737474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// GetEmptySet - Returns an immutable set that contains no elements. 95833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); } 9593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 96037474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// Add - Creates a new immutable set that contains all of the values 96137474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of the original set with the addition of the specified value. If 96237474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// the original set already included the value, then the original set is 96337474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// returned and no memory is allocated. The time and space complexity 96437474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of this operation is logarithmic in the size of the original set. 96537474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// The memory allocated to represent the set is released when the 96637474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// factory object that created the set is destroyed. 96733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImmutableSet Add(ImmutableSet Old, value_type_ref V) { 9688b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return ImmutableSet(F.GetCanonicalTree(F.Add(Old.Root,V))); 96933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 97137474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// Remove - Creates a new immutable set that contains all of the values 97237474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of the original set with the exception of the specified value. If 97337474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// the original set did not contain the value, the original set is 97437474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// returned and no memory is allocated. The time and space complexity 97537474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of this operation is logarithmic in the size of the original set. 97637474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// The memory allocated to represent the set is released when the 97737474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// factory object that created the set is destroyed. 97833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImmutableSet Remove(ImmutableSet Old, value_type_ref V) { 9798b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return ImmutableSet(F.GetCanonicalTree(F.Remove(Old.Root,V))); 98033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9820b22da3d7361f94c3811f2e7d603bb3513dc3d1cTed Kremenek BumpPtrAllocator& getAllocator() { return F.getAllocator(); } 9830b22da3d7361f94c3811f2e7d603bb3513dc3d1cTed Kremenek 98433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek private: 98533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Factory(const Factory& RHS) {}; 9863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator=(const Factory& RHS) {}; 98733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 9883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman friend class Factory; 99037474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek 99137474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// contains - Returns true if the set contains the specified value. 992aafa94260d5b1b6422258ed3db7244fe4449f217Daniel Dunbar bool contains(value_type_ref V) const { 99333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root ? Root->contains(V) : false; 99433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 99633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool operator==(ImmutableSet RHS) const { 99733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 99833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 100033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool operator!=(ImmutableSet RHS) const { 100133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 100233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 10033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10048b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek TreeTy *getRoot() { 10058b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return Root; 10068b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek } 10073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 100837474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// isEmpty - Return true if the set contains no elements. 100933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEmpty() const { return !Root; } 1010085a9ebbc705c6e7d3fd8c692ef1c46fdfb885ceMisha Brukman 1011da5eb715509685f4a5cfdf6cd781827e72199af6Ted Kremenek /// isSingleton - Return true if the set contains exactly one element. 1012da5eb715509685f4a5cfdf6cd781827e72199af6Ted Kremenek /// This method runs in constant time. 1013da5eb715509685f4a5cfdf6cd781827e72199af6Ted Kremenek bool isSingleton() const { return getHeight() == 1; } 10143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 101533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 101633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void foreach(Callback& C) { if (Root) Root->foreach(C); } 10173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 101833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 101933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void foreach() { if (Root) { Callback C; Root->foreach(C); } } 10203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1022bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek // Iterators. 10233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1024bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek 1025bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek class iterator { 1026bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek typename TreeTy::iterator itr; 1027bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek iterator(TreeTy* t) : itr(t) {} 1028bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek friend class ImmutableSet<ValT,ValInfo>; 1029bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek public: 1030458ba32680488486b7166e40fd3e25b4dccf73fdTed Kremenek iterator() {} 1031bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline value_type_ref operator*() const { return itr->getValue(); } 1032bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline iterator& operator++() { ++itr; return *this; } 10330b22da3d7361f94c3811f2e7d603bb3513dc3d1cTed Kremenek inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1034bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline iterator& operator--() { --itr; return *this; } 10350b22da3d7361f94c3811f2e7d603bb3513dc3d1cTed Kremenek inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1036bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 10373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 10385b22efa61446797039dd19fc1e9be83676463f99Chris Lattner inline value_type *operator->() const { return &(operator*()); } 1039bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek }; 10403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1041bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek iterator begin() const { return iterator(Root); } 10423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman iterator end() const { return iterator(); } 10433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 10459dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek // Utility methods. 10463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 10473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10489dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek inline unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 10493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10509dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) { 10519dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek ID.AddPointer(S.Root); 10529dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek } 10533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10549dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek inline void Profile(FoldingSetNodeID& ID) const { 10559dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek return Profile(ID,*this); 10569dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek } 10573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 105933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // For testing. 10603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 10613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 106233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void verify() const { if (Root) Root->verify(); } 106333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 106433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 106533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek} // end namespace llvm 106633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 106733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#endif 1068