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 14674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ADT_IMMUTABLESET_H 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ADT_IMMUTABLESET_H 1633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek#include "llvm/ADT/DenseMap.h" 1833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#include "llvm/ADT/FoldingSet.h" 19255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/Allocator.h" 201f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 2150bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper#include "llvm/Support/ErrorHandling.h" 2233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#include <cassert> 23602d1c51e055efd56b284a2ba41083ff38c337bcAnton Korobeynikov#include <functional> 2475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek#include <vector> 2533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 2633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremeneknamespace llvm { 273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 2933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Immutable AVL-Tree Definition. 3033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 3133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 3233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename ImutInfo> class ImutAVLFactory; 33746f5b6eb1518986bdac750074cbf1899e459983Zhongxing Xutemplate <typename ImutInfo> class ImutIntervalAVLFactory; 34ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenektemplate <typename ImutInfo> class ImutAVLTreeInOrderIterator; 35f357afb4045307a24c52606e267385148367a7a3Ted Kremenektemplate <typename ImutInfo> class ImutAVLTreeGenericIterator; 363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename ImutInfo > 3875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenekclass ImutAVLTree { 3933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 4033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutInfo::key_type_ref key_type_ref; 4133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutInfo::value_type value_type; 4233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutInfo::value_type_ref value_type_ref; 43ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 4433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef ImutAVLFactory<ImutInfo> Factory; 4533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek friend class ImutAVLFactory<ImutInfo>; 46746f5b6eb1518986bdac750074cbf1899e459983Zhongxing Xu friend class ImutIntervalAVLFactory<ImutInfo>; 473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 48f357afb4045307a24c52606e267385148367a7a3Ted Kremenek friend class ImutAVLTreeGenericIterator<ImutInfo>; 493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 50ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator; 513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 5333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Public Interface. 543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek /// Return a pointer to the left subtree. This value 57ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// is NULL if there is no left subtree. 589c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImutAVLTree *getLeft() const { return left; } 593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek /// Return a pointer to the right subtree. This value is 61ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// NULL if there is no right subtree. 629c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImutAVLTree *getRight() const { return right; } 633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 64ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// getHeight - Returns the height of the tree. A tree with no subtrees 65ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// has a height of 1. 669c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned getHeight() const { return height; } 673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 68ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// getValue - Returns the data value associated with the tree node. 699c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek const value_type& getValue() const { return value; } 703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 71ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// find - Finds the subtree associated with the specified key value. 72ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// This method returns NULL if no matching subtree is found. 7333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutAVLTree* find(key_type_ref K) { 7433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutAVLTree *T = this; 7533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek while (T) { 76be24d91d824387cea4454bd16f63d5b2409c56e1Ted Kremenek key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue()); 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 } 8433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return NULL; 8533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 86644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 871c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// getMaxElement - Find the subtree associated with the highest ranged 881c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// key value. 891c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek ImutAVLTree* getMaxElement() { 901c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek ImutAVLTree *T = this; 91644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper ImutAVLTree *Right = T->getRight(); 92658c62862e470b59aaf25825de64d93fbaf8cb93Benjamin Kramer while (Right) { T = Right; Right = T->getRight(); } 931c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek return T; 941c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek } 953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 96ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// size - Returns the number of nodes in the tree, which includes 97ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// both leaves and non-leaf nodes. 9833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned size() const { 9933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek unsigned n = 1; 1009c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (const ImutAVLTree* L = getLeft()) 1019c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek n += L->size(); 1029c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (const ImutAVLTree* R = getRight()) 1039c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek n += R->size(); 10433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return n; 10533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 107ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// begin - Returns an iterator that iterates over the nodes of the tree 108ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// in an inorder traversal. The returned iterator thus refers to the 109ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// the tree node with the minimum data element. 110ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator begin() const { return iterator(this); } 1113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 112ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// end - Returns an iterator for the tree that denotes the end of an 113ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// inorder traversal. 114ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator end() const { return iterator(); } 1153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1169c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool isElementEqual(value_type_ref V) const { 117f357afb4045307a24c52606e267385148367a7a3Ted Kremenek // Compare the keys. 118f357afb4045307a24c52606e267385148367a7a3Ted Kremenek if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()), 119f357afb4045307a24c52606e267385148367a7a3Ted Kremenek ImutInfo::KeyOfValue(V))) 120f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return false; 1213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 122f357afb4045307a24c52606e267385148367a7a3Ted Kremenek // Also compare the data values. 123f357afb4045307a24c52606e267385148367a7a3Ted Kremenek if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()), 124f357afb4045307a24c52606e267385148367a7a3Ted Kremenek ImutInfo::DataOfValue(V))) 125f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return false; 1263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 127f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return true; 128f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 1293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1309c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool isElementEqual(const ImutAVLTree* RHS) const { 1319c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return isElementEqual(RHS->getValue()); 132f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 1333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 134ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// isEqual - Compares two trees for structural equality and returns true 135ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// if they are equal. This worst case performance of this operation is 136ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek // linear in the sizes of the trees. 13733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEqual(const ImutAVLTree& RHS) const { 138ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (&RHS == this) 139ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return true; 1403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 141ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator LItr = begin(), LEnd = end(); 142ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek iterator RItr = RHS.begin(), REnd = RHS.end(); 1433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 144ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek while (LItr != LEnd && RItr != REnd) { 145ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (*LItr == *RItr) { 1469c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek LItr.skipSubTree(); 1479c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek RItr.skipSubTree(); 148ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek continue; 149ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 1503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1519c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (!LItr->isElementEqual(*RItr)) 152e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek return false; 1533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 154ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek ++LItr; 155ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek ++RItr; 156ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 1573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 158ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return LItr == LEnd && RItr == REnd; 15933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 160ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek 161ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// isNotEqual - Compares two trees for structural inequality. Performance 162ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// is the same is isEqual. 16333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); } 1643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 165ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// contains - Returns true if this tree contains a subtree (node) that 166ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// has an data element that matches the specified key. Complexity 167ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// is logarithmic in the size of the tree. 168aafa94260d5b1b6422258ed3db7244fe4449f217Daniel Dunbar bool contains(key_type_ref K) { return (bool) find(K); } 1693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 170ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// foreach - A member template the accepts invokes operator() on a functor 171ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// object (specifed by Callback) for every node/subtree in the tree. 172ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// Nodes are visited using an inorder traversal. 17333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 17433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void foreach(Callback& C) { 1759c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (ImutAVLTree* L = getLeft()) 1769c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek L->foreach(C); 1773a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1789c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek C(value); 1793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1809c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (ImutAVLTree* R = getRight()) 1819c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek R->foreach(C); 18233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1849c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// validateTree - A utility method that checks that the balancing and 185ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// ordering invariants of the tree are satisifed. It is a recursive 186ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// method that returns the height of the tree, which is then consumed 1879c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// by the enclosing validateTree call. External callers should ignore the 188ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// return value. An invalid tree will cause an assertion to fire in 189ea34bc892c5341d1bbe49101ecab1d878ab8b621Ted Kremenek /// a debug build. 1909c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned validateTree() const { 1919c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned HL = getLeft() ? getLeft()->validateTree() : 0; 1929c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned HR = getRight() ? getRight()->validateTree() : 0; 19307b3a041b45f376ea182d8b4ade7b01bfaa9ab2cDaniel Dunbar (void) HL; 19407b3a041b45f376ea182d8b4ade7b01bfaa9ab2cDaniel Dunbar (void) HR; 1953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1968767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(getHeight() == ( HL > HR ? HL : HR ) + 1 1978767d32e758db3ffef796342a2650f337cf3404aTed Kremenek && "Height calculation wrong"); 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1998767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert((HL > HR ? HL-HR : HR-HL) <= 2 2008767d32e758db3ffef796342a2650f337cf3404aTed Kremenek && "Balancing invariant violated"); 2013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 20232df92dde60a027612880e4701ce1b0246d65eaeDan Gohman assert((!getLeft() || 20332df92dde60a027612880e4701ce1b0246d65eaeDan Gohman ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()), 20432df92dde60a027612880e4701ce1b0246d65eaeDan Gohman ImutInfo::KeyOfValue(getValue()))) && 20532df92dde60a027612880e4701ce1b0246d65eaeDan Gohman "Value in left child is not less that current value"); 2063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 20832df92dde60a027612880e4701ce1b0246d65eaeDan Gohman assert(!(getRight() || 20932df92dde60a027612880e4701ce1b0246d65eaeDan Gohman ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()), 21032df92dde60a027612880e4701ce1b0246d65eaeDan Gohman ImutInfo::KeyOfValue(getRight()->getValue()))) && 21132df92dde60a027612880e4701ce1b0246d65eaeDan Gohman "Current value is not less that value of right child"); 2123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 21333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return getHeight(); 214f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 2179c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek // Internal values. 21833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===----------------------------------------------------===// 2193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 22033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 22175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek Factory *factory; 22275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImutAVLTree *left; 22375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImutAVLTree *right; 22475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImutAVLTree *prev; 22575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImutAVLTree *next; 22675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 22775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek unsigned height : 28; 22875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek unsigned IsMutable : 1; 22975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek unsigned IsDigestCached : 1; 23075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek unsigned IsCanonicalized : 1; 23175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 23275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek value_type value; 23375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek uint32_t digest; 23475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek uint32_t refCount; 2353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 23733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Internal methods (node manipulation; used by Factory). 23833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===----------------------------------------------------===// 239f357afb4045307a24c52606e267385148367a7a3Ted Kremenek 24033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 24185d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// ImutAVLTree - Internal constructor that is only called by 24285d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// ImutAVLFactory. 24375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, 2443ec68f97ead4a2bc339b1b9012ca4cb2c4dd706aTed Kremenek unsigned height) 24575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek : factory(f), left(l), right(r), prev(0), next(0), height(height), 24675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek IsMutable(true), IsDigestCached(false), IsCanonicalized(0), 24775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek value(v), digest(0), refCount(0) 24875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek { 24975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (left) left->retain(); 25075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (right) right->retain(); 25175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 2523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 25385d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// isMutable - Returns true if the left and right subtree references 25485d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// (as well as height) can be changed. If this method returns false, 25585d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// the tree is truly immutable. Trees returned from an ImutAVLFactory 25685d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// object should always have this method return true. Further, if this 25785d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// method returns false for an instance of ImutAVLTree, all subtrees 25885d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// will also have this method return false. The converse is not true. 2599c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool isMutable() const { return IsMutable; } 260644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 261633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// hasCachedDigest - Returns true if the digest for this tree is cached. 262633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// This can only be true if the tree is immutable. 2639c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool hasCachedDigest() const { return IsDigestCached; } 2643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===----------------------------------------------------===// 26685d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // Mutating operations. A tree root can be manipulated as 2673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // long as its reference has not "escaped" from internal 26885d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // methods of a factory object (see below). When a tree 2693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // pointer is externally viewable by client code, the 2703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman // internal "mutable bit" is cleared to mark the tree 27185d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // immutable. Note that a tree that still has its mutable 27285d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek // bit set may have children (subtrees) that are themselves 27333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // immutable. 27485d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek //===----------------------------------------------------===// 2753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2769c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// markImmutable - Clears the mutable flag for a tree. After this happens, 277633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek /// it is an error to call setLeft(), setRight(), and setHeight(). 2789c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek void markImmutable() { 279633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek assert(isMutable() && "Mutable flag already removed."); 2809c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek IsMutable = false; 28133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 282644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 2839c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// markedCachedDigest - Clears the NoCachedDigest flag for a tree. 2849c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek void markedCachedDigest() { 285633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek assert(!hasCachedDigest() && "NoCachedDigest flag already removed."); 2869c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek IsDigestCached = true; 287633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek } 2883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 28985d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// setHeight - Changes the height of the tree. Used internally by 29085d03ae1ae767038d9781da44a7a7e3f5191053eTed Kremenek /// ImutAVLFactory. 29133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void setHeight(unsigned h) { 2928f3cfb4c657f0094e8bf1e67de4ee776d57a751eTed Kremenek assert(isMutable() && "Only a mutable tree can have its height changed."); 2939c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek height = h; 29433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 2953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 296f357afb4045307a24c52606e267385148367a7a3Ted Kremenek static inline 2979c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) { 298633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek uint32_t digest = 0; 2993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 300633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (L) 3019c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek digest += L->computeDigest(); 3023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 303633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek // Compute digest of stored data. 304633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek FoldingSetNodeID ID; 305633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek ImutInfo::Profile(ID,V); 306633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek digest += ID.ComputeHash(); 3073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 308633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (R) 3099c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek digest += R->computeDigest(); 3103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 31195da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek return digest; 312f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 3133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3149c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek inline uint32_t computeDigest() { 315633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek // Check the lowest bit to determine if digest has actually been 316633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek // pre-computed. 317633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (hasCachedDigest()) 3189c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return digest; 319633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek 3209c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek uint32_t X = computeDigest(getLeft(), getRight(), getValue()); 3219c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek digest = X; 3229c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek markedCachedDigest(); 323f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return X; 324f357afb4045307a24c52606e267385148367a7a3Ted Kremenek } 32575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 32675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek //===----------------------------------------------------===// 32775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // Reference count operations. 32875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek //===----------------------------------------------------===// 32975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 33075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenekpublic: 33175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek void retain() { ++refCount; } 33275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek void release() { 33375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek assert(refCount > 0); 33475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (--refCount == 0) 33575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek destroy(); 33675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 33775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek void destroy() { 33875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (left) 33975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek left->release(); 34075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (right) 34175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek right->release(); 34275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (IsCanonicalized) { 34375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (next) 34475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek next->prev = prev; 34575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 34675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (prev) 34775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek prev->next = next; 34875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek else 3494211c196d48a16748158452db918403f30088266Anna Zaks factory->Cache[factory->maskCacheIndex(computeDigest())] = next; 35075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 351644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 35275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // We need to clear the mutability bit in case we are 35375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes(). 35475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek IsMutable = false; 35575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek factory->freeNodes.push_back(this); 35675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 35733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 35833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 3593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 36033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Immutable AVL-Tree Factory class. 36133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 36233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 3633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate <typename ImutInfo > 36433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImutAVLFactory { 36575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek friend class ImutAVLTree<ImutInfo>; 36633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef ImutAVLTree<ImutInfo> TreeTy; 36733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename TreeTy::value_type_ref value_type_ref; 36833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename TreeTy::key_type_ref key_type_ref; 3693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 37075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek typedef DenseMap<unsigned, TreeTy*> CacheTy; 3713a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 372a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek CacheTy Cache; 373a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek uintptr_t Allocator; 37475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek std::vector<TreeTy*> createdNodes; 37575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek std::vector<TreeTy*> freeNodes; 3763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 377a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek bool ownsAllocator() const { 378a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek return Allocator & 0x1 ? false : true; 379a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek } 380a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek 3813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman BumpPtrAllocator& getAllocator() const { 382a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 383a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek } 3843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 38633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Public interface. 38733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 3883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 38933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 390a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek ImutAVLFactory() 391a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 3923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 393a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek ImutAVLFactory(BumpPtrAllocator& Alloc) 394a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 3953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 396a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek ~ImutAVLFactory() { 397a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek if (ownsAllocator()) delete &getAllocator(); 398a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek } 3993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4009c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* add(TreeTy* T, value_type_ref V) { 4019c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek T = add_internal(V,T); 4029c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek markImmutable(T); 40375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek recoverNodes(); 40433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 40533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4079c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* remove(TreeTy* T, key_type_ref V) { 4089c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek T = remove_internal(V,T); 4099c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek markImmutable(T); 41075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek recoverNodes(); 41133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 41233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4149c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* getEmptyTree() const { return NULL; } 4153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4169c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenekprotected: 417644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 4183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 41933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // A bunch of quick helper functions used for reasoning 42033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // about the properties of trees and their children. 42133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // These have succinct names so that the balancing code 42233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // is as terse (and readable) as possible. 42333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 4243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4259c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool isEmpty(TreeTy* T) const { return !T; } 4269c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; } 4279c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* getLeft(TreeTy* T) const { return T->getLeft(); } 4289c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* getRight(TreeTy* T) const { return T->getRight(); } 4299c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek value_type_ref getValue(TreeTy* T) const { return T->value; } 4303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4314211c196d48a16748158452db918403f30088266Anna Zaks // Make sure the index is not the Tombstone or Entry key of the DenseMap. 4324211c196d48a16748158452db918403f30088266Anna Zaks static inline unsigned maskCacheIndex(unsigned I) { 433aa7507d68dcc04f3118a05b5dff4123ded03253eBill Wendling return (I & ~0x02); 4344211c196d48a16748158452db918403f30088266Anna Zaks } 4354211c196d48a16748158452db918403f30088266Anna Zaks 4369c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned incrementHeight(TreeTy* L, TreeTy* R) const { 4379c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned hl = getHeight(L); 4389c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned hr = getHeight(R); 4393ec68f97ead4a2bc339b1b9012ca4cb2c4dd706aTed Kremenek return (hl > hr ? hl : hr) + 1; 44033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4429c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek static bool compareTreeWithSection(TreeTy* T, 443f357afb4045307a24c52606e267385148367a7a3Ted Kremenek typename TreeTy::iterator& TI, 444f357afb4045307a24c52606e267385148367a7a3Ted Kremenek typename TreeTy::iterator& TE) { 445f357afb4045307a24c52606e267385148367a7a3Ted Kremenek typename TreeTy::iterator I = T->begin(), E = T->end(); 4469c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek for ( ; I!=E ; ++I, ++TI) { 4479c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (TI == TE || !I->isElementEqual(*TI)) 448f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return false; 4499c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek } 450f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return true; 4513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 4523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 4549c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek // "createNode" is used to generate new tree roots that link 45533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // to other trees. The functon may also simply move links 45633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // in an existing root if that root is still marked mutable. 45733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // This is necessary because otherwise our balancing code 45833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // would leak memory as it would create nodes that are 45933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // then discarded later before the finished tree is 46033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // returned to the caller. 46133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 4623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 463644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) { 464a618f82c9fdbe869b41581f00ae357e1b22302d1Ted Kremenek BumpPtrAllocator& A = getAllocator(); 46575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek TreeTy* T; 46675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (!freeNodes.empty()) { 46775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek T = freeNodes.back(); 46875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek freeNodes.pop_back(); 46975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek assert(T != L); 47075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek assert(T != R); 471910cf7f712a1895b993df4677c1059c595353dccCraig Topper } else { 47275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek T = (TreeTy*) A.Allocate<TreeTy>(); 47375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 47475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek new (T) TreeTy(this, L, R, V, incrementHeight(L,R)); 47575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek createdNodes.push_back(T); 476f357afb4045307a24c52606e267385148367a7a3Ted Kremenek return T; 47733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4799c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) { 48075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return createNode(newLeft, getValue(oldTree), newRight); 48175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 48275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 48375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek void recoverNodes() { 48475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) { 48575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek TreeTy *N = createdNodes[i]; 48675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (N->isMutable() && N->refCount == 0) 48775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek N->destroy(); 48833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 48975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek createdNodes.clear(); 49033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 4913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4929c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// balanceTree - Used by add_internal and remove_internal to 49333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// balance a newly created tree. 4949c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) { 4959c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned hl = getHeight(L); 4969c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned hr = getHeight(R); 4973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 49833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (hl > hr + 2) { 4998767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2"); 5003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5019c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *LL = getLeft(L); 5029c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *LR = getRight(L); 5033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5049c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (getHeight(LL) >= getHeight(LR)) 5059c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return createNode(LL, L, createNode(LR,V,R)); 5063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5078767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1"); 5083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5099c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *LRL = getLeft(LR); 5109c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *LRR = getRight(LR); 5113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5129c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R)); 51333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 514910cf7f712a1895b993df4677c1059c595353dccCraig Topper 515910cf7f712a1895b993df4677c1059c595353dccCraig Topper if (hr > hl + 2) { 5168767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2"); 5173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5189c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *RL = getLeft(R); 5199c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *RR = getRight(R); 5203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5219c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (getHeight(RR) >= getHeight(RL)) 5229c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return createNode(createNode(L,V,RL), R, RR); 5233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5248767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1"); 5253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5269c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *RLL = getLeft(RL); 5279c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *RLR = getRight(RL); 5283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5299c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR)); 53033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 531910cf7f712a1895b993df4677c1059c595353dccCraig Topper 532910cf7f712a1895b993df4677c1059c595353dccCraig Topper return createNode(L,V,R); 53333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5359c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// add_internal - Creates a new tree that includes the specified 53633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// data and the data from the original tree. If the original tree 53733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// already contained the data item, the original tree is returned. 5389c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* add_internal(value_type_ref V, TreeTy* T) { 53933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (isEmpty(T)) 5409c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return createNode(T, V, T); 5418767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!T->isMutable()); 5423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 54333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek key_type_ref K = ImutInfo::KeyOfValue(V); 5449c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T)); 5453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 54633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (ImutInfo::isEqual(K,KCurrent)) 5479c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return createNode(getLeft(T), V, getRight(T)); 54833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else if (ImutInfo::isLess(K,KCurrent)) 5499c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return balanceTree(add_internal(V, getLeft(T)), getValue(T), getRight(T)); 55033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek else 5519c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return balanceTree(getLeft(T), getValue(T), add_internal(V, getRight(T))); 55233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5549c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// remove_internal - Creates a new tree that includes all the data 55533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// from the original tree except the specified data. If the 55633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// specified data did not exist in the original tree, the original 55733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// tree is returned. 5589c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* remove_internal(key_type_ref K, TreeTy* T) { 55933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (isEmpty(T)) 56033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return T; 5613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5628767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!T->isMutable()); 5633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5649c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T)); 5653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5669c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (ImutInfo::isEqual(K,KCurrent)) { 5679c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return combineTrees(getLeft(T), getRight(T)); 5689c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek } else if (ImutInfo::isLess(K,KCurrent)) { 5699c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return balanceTree(remove_internal(K, getLeft(T)), 5709c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek getValue(T), getRight(T)); 5719c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek } else { 5729c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return balanceTree(getLeft(T), getValue(T), 5739c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek remove_internal(K, getRight(T))); 5749c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek } 57533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5779c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* combineTrees(TreeTy* L, TreeTy* R) { 5789c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (isEmpty(L)) 5799c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return R; 5809c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (isEmpty(R)) 5819c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return L; 5823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman TreeTy* OldNode; 5839c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* newRight = removeMinBinding(R,OldNode); 5849c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return balanceTree(L, getValue(OldNode), newRight); 58533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5879c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) { 5888767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!isEmpty(T)); 5899c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek if (isEmpty(getLeft(T))) { 5909c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek Noderemoved = T; 5919c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return getRight(T); 59233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 5939c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return balanceTree(removeMinBinding(getLeft(T), Noderemoved), 5949c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek getValue(T), getRight(T)); 5953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 5963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5979c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// markImmutable - Clears the mutable bits of a root and all of its 59833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek /// descendants. 5999c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek void markImmutable(TreeTy* T) { 60033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (!T || !T->isMutable()) 60133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return; 6029c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek T->markImmutable(); 6039c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek markImmutable(getLeft(T)); 6049c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek markImmutable(getRight(T)); 6058b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek } 606644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 6078b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenekpublic: 6089c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *getCanonicalTree(TreeTy *TNew) { 6098b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek if (!TNew) 61075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return 0; 61175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 61275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (TNew->IsCanonicalized) 61375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return TNew; 61475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek 61575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // Search the hashtable for another tree with the same digest, and 61675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // if find a collision compare those trees by their contents. 6179c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek unsigned digest = TNew->computeDigest(); 6184211c196d48a16748158452db918403f30088266Anna Zaks TreeTy *&entry = Cache[maskCacheIndex(digest)]; 61975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek do { 62075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (!entry) 62175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek break; 62275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek for (TreeTy *T = entry ; T != 0; T = T->next) { 62375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // Compare the Contents('T') with Contents('TNew') 62475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek typename TreeTy::iterator TI = T->begin(), TE = T->end(); 62575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (!compareTreeWithSection(TNew, TI, TE)) 62675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek continue; 62775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (TI != TE) 62875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek continue; // T has more contents than TNew. 62975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek // Trees did match! Return 'T'. 63075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (TNew->refCount == 0) 63175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek TNew->destroy(); 63275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return T; 63375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 63475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek entry->prev = TNew; 63575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek TNew->next = entry; 6368b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek } 63775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek while (false); 6383a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 63975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek entry = TNew; 64075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek TNew->IsCanonicalized = true; 6418b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return TNew; 64233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 64333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 6443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 646ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek// Immutable AVL-Tree Iterators. 6473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 64833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 649ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenektemplate <typename ImutInfo> 650ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekclass ImutAVLTreeGenericIterator { 651ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek SmallVector<uintptr_t,20> stack; 652ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekpublic: 6533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3, 654ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek Flags=0x3 }; 6553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman typedef ImutAVLTree<ImutInfo> TreeTy; 657ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeGenericIterator<ImutInfo> _Self; 658ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 659ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline ImutAVLTreeGenericIterator() {} 660ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline ImutAVLTreeGenericIterator(const TreeTy* Root) { 661ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root)); 6623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 6633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 664ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek TreeTy* operator*() const { 6658767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!stack.empty()); 666ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 667ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 669e74ba3a46d1c86bb218e0d3ba5f28f986eb6e062Jordy Rose uintptr_t getVisitState() const { 6708767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!stack.empty()); 671ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return stack.back() & Flags; 672ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6743a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6759c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool atEnd() const { return stack.empty(); } 67633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 6779c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek bool atBeginning() const { 678ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return stack.size() == 1 && getVisitState() == VisitedNone; 679ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6819c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek void skipToParent() { 6828767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!stack.empty()); 683ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.pop_back(); 684ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (stack.empty()) 685ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return; 686ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek switch (getVisitState()) { 687ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedNone: 688ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedLeft; 689ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 690ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedLeft: 691ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedRight; 692ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 693ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek default: 69450bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unreachable."); 695ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 696ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 6973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 698ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline bool operator==(const _Self& x) const { 699ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (stack.size() != x.stack.size()) 700ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return false; 701ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek for (unsigned i = 0 ; i < stack.size(); i++) 702ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (stack[i] != x.stack[i]) 703ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return false; 704ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return true; 705ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline bool operator!=(const _Self& x) const { return !operator==(x); } 7083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 709ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek _Self& operator++() { 7108767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!stack.empty()); 711ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 7128767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(Current); 713ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek switch (getVisitState()) { 714ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedNone: 715633eb95f3ee4f6a831ce6fef47b5f2e5b52f297bTed Kremenek if (TreeTy* L = Current->getLeft()) 716ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(L)); 717ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek else 718ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedLeft; 719ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 720ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedLeft: 721ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (TreeTy* R = Current->getRight()) 722ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(R)); 723ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek else 724ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedRight; 725ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 726ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedRight: 7279c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek skipToParent(); 728ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 729ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek default: 73050bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unreachable."); 731ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 732ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 733ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 735ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek _Self& operator--() { 7368767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(!stack.empty()); 737ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags); 7388767d32e758db3ffef796342a2650f337cf3404aTed Kremenek assert(Current); 739ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek switch (getVisitState()) { 740ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek case VisitedNone: 741ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.pop_back(); 742ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman case VisitedLeft: 744ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() &= ~Flags; // Set state to "VisitedNone." 745ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (TreeTy* L = Current->getLeft()) 746ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight); 747ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 7483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman case VisitedRight: 749ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() &= ~Flags; 750ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.back() |= VisitedLeft; 751ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (TreeTy* R = Current->getRight()) 752ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight); 753ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek break; 754ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek default: 75550bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unreachable."); 756ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 757ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 758ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 759ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek}; 7603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 761ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenektemplate <typename ImutInfo> 762ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekclass ImutAVLTreeInOrderIterator { 763ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy; 764ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalIteratorTy InternalItr; 765ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 766ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenekpublic: 767ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTree<ImutInfo> TreeTy; 768ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self; 769ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 7703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) { 771ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek if (Root) operator++(); // Advance to first element. 772ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 774ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek ImutAVLTreeInOrderIterator() : InternalItr() {} 775ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 776ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek inline bool operator==(const _Self& x) const { 777ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return InternalItr == x.InternalItr; 778ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline bool operator!=(const _Self& x) const { return !operator==(x); } 7813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 782bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline TreeTy* operator*() const { return *InternalItr; } 783bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek inline TreeTy* operator->() const { return *InternalItr; } 7843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline _Self& operator++() { 786ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek do ++InternalItr; 7879c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek while (!InternalItr.atEnd() && 788ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 789ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek 790ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 791ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 7923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline _Self& operator--() { 794ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek do --InternalItr; 7959c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek while (!InternalItr.atBeginning() && 796ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft); 7973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 798ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek return *this; 799ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 8003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8019c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek inline void skipSubTree() { 8029c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek InternalItr.skipToParent(); 8033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8049c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek while (!InternalItr.atEnd() && 805ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft) 8063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ++InternalItr; 807ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek } 808ebdbed384411da83f0cdca014e52f65165919bdaTed Kremenek}; 8093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 81133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Trait classes for Profile information. 81233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 81333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 81433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// Generic profile template. The default behavior is to invoke the 81533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// profile method of an object. Specializations for primitive integers 81633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// and generic handling of pointers is done below. 81733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 81833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutProfileInfo { 81933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T value_type; 82033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T& value_type_ref; 8213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 82233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 8233cf8bec783809269a5dbb81d6d1693ee18fcb37cTed Kremenek FoldingSetTrait<T>::Profile(X,ID); 8243cf8bec783809269a5dbb81d6d1693ee18fcb37cTed Kremenek } 82533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 82633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 82733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// Profile traits for integers. 82833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 8293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanstruct ImutProfileInteger { 83033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T value_type; 83133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T& value_type_ref; 8323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 83333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) { 83433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ID.AddInteger(X); 8353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 83633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 83733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 83833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#define PROFILE_INTEGER_INFO(X)\ 83933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {}; 84033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 84133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(char) 84233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned char) 84333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(short) 84433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned short) 84533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned) 84633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(signed) 84733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(long) 84833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned long) 84933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(long long) 85033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted KremenekPROFILE_INTEGER_INFO(unsigned long long) 85133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 85233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#undef PROFILE_INTEGER_INFO 85333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 85433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// Generic profile trait for pointer types. We treat pointers as 85533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// references to unique objects. 85633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 85733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutProfileInfo<T*> { 85833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T* value_type; 85933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type value_type_ref; 8603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 86133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) { 86233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ID.AddPointer(X); 86333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 86433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 86533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 8663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 86733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Trait classes that contain element comparison operators and type 86833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These 86933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// inherit from the profile traits (ImutProfileInfo) to include operations 87033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// for element profiling. 87133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 87233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 87333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 87433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// ImutContainerInfo - Generic definition of comparison operations for 87533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// elements of immutable containers that defaults to using 87633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// std::equal_to<> and std::less<> to perform comparison of elements. 87733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 87833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutContainerInfo : public ImutProfileInfo<T> { 87933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T>::value_type value_type; 88033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref; 88133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type key_type; 88233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type_ref key_type_ref; 883e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type; 884e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type_ref; 8853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 88633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 887e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline data_type_ref DataOfValue(value_type_ref) { return true; } 8883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 89033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return std::equal_to<key_type>()(LHS,RHS); 89133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 8923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 89333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 89433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return std::less<key_type>()(LHS,RHS); 89533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 8963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 897e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 89833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 89933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 90033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// ImutContainerInfo - Specialization for pointer values to treat pointers 90133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// as references to unique objects. Pointers are thus compared by 90233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// their addresses. 90333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T> 90433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutContainerInfo<T*> : public ImutProfileInfo<T*> { 90533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T*>::value_type value_type; 90633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref; 90733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type key_type; 90833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef value_type_ref key_type_ref; 909e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type; 910e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek typedef bool data_type_ref; 9113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 91233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline key_type_ref KeyOfValue(value_type_ref D) { return D; } 913e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline data_type_ref DataOfValue(value_type_ref) { return true; } 9143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 91533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) { 91633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return LHS == RHS; 91733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 91933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isLess(key_type_ref LHS, key_type_ref RHS) { 92033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return LHS < RHS; 92133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 923e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; } 92433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 92533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 9263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//===----------------------------------------------------------------------===// 92733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// Immutable Set 92833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 92933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 93033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 93133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImmutableSet { 93233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 93333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type value_type; 93433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 93533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 9361eed950d7cb69906264cfb49895165e3b51524beTed Kremenek 9373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanprivate: 9388b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek TreeTy *Root; 939644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 94033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 9411eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// Constructs a set from a pointer to a tree root. In general one 9421eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// should use a Factory object to create sets instead of directly 9431eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// invoking the constructor, but there are cases where make this 9441eed950d7cb69906264cfb49895165e3b51524beTed Kremenek /// constructor public is useful. 94575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek explicit ImmutableSet(TreeTy* R) : Root(R) { 94675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 94775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 94875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImmutableSet(const ImmutableSet &X) : Root(X.Root) { 94975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 95075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 95175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImmutableSet &operator=(const ImmutableSet &X) { 95275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root != X.Root) { 95375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (X.Root) { X.Root->retain(); } 95475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->release(); } 95575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek Root = X.Root; 95675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 95775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return *this; 95875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 95975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ~ImmutableSet() { 96075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->release(); } 96175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 9623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 96333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek class Factory { 96433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typename TreeTy::Factory F; 9659688079e07dce7748d14a761d52732add634ba4cTed Kremenek const bool Canonicalize; 9663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 96733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek public: 9689688079e07dce7748d14a761d52732add634ba4cTed Kremenek Factory(bool canonicalize = true) 9699688079e07dce7748d14a761d52732add634ba4cTed Kremenek : Canonicalize(canonicalize) {} 9703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9719688079e07dce7748d14a761d52732add634ba4cTed Kremenek Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) 9729688079e07dce7748d14a761d52732add634ba4cTed Kremenek : F(Alloc), Canonicalize(canonicalize) {} 9733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9749c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// getEmptySet - Returns an immutable set that contains no elements. 9759c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableSet getEmptySet() { 9769c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableSet(F.getEmptyTree()); 9779688079e07dce7748d14a761d52732add634ba4cTed Kremenek } 9783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9799c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// add - Creates a new immutable set that contains all of the values 98037474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of the original set with the addition of the specified value. If 98137474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// the original set already included the value, then the original set is 98237474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// returned and no memory is allocated. The time and space complexity 98337474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of this operation is logarithmic in the size of the original set. 98437474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// The memory allocated to represent the set is released when the 98537474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// factory object that created the set is destroyed. 9869c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableSet add(ImmutableSet Old, value_type_ref V) { 9879c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *NewT = F.add(Old.Root, V); 9889c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); 98933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 9903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9919c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek /// remove - Creates a new immutable set that contains all of the values 99237474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of the original set with the exception of the specified value. If 99337474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// the original set did not contain the value, the original set is 99437474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// returned and no memory is allocated. The time and space complexity 99537474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// of this operation is logarithmic in the size of the original set. 99637474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// The memory allocated to represent the set is released when the 99737474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// factory object that created the set is destroyed. 9989c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableSet remove(ImmutableSet Old, value_type_ref V) { 9999c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *NewT = F.remove(Old.Root, V); 10009c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT); 100133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 10023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10030b22da3d7361f94c3811f2e7d603bb3513dc3d1cTed Kremenek BumpPtrAllocator& getAllocator() { return F.getAllocator(); } 10040b22da3d7361f94c3811f2e7d603bb3513dc3d1cTed Kremenek 1005166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typename TreeTy::Factory *getTreeFactory() const { 1006166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return const_cast<typename TreeTy::Factory *>(&F); 1007166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1008644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 100933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek private: 1010fc601db2ed899d800ea0a50f7ecf7de2a820cbc1Craig Topper Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; 1011fc601db2ed899d800ea0a50f7ecf7de2a820cbc1Craig Topper void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; 101233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 10133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman friend class Factory; 101537474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek 101675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek /// Returns true if the set contains the specified value. 1017aafa94260d5b1b6422258ed3db7244fe4449f217Daniel Dunbar bool contains(value_type_ref V) const { 101833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root ? Root->contains(V) : false; 101933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 10203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 102175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator==(const ImmutableSet &RHS) const { 102233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 102333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 10243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 102575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator!=(const ImmutableSet &RHS) const { 102633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 102733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 10283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1029644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper TreeTy *getRoot() { 103075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 10318b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek return Root; 10328b8a7fcf68c3bb6f8b90f5f1813ebb391b56e550Ted Kremenek } 1033644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1034166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *getRootWithoutRetain() const { 1035166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root; 1036166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 10373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 103837474bce024c4a1e85dd777a8b489af60eb4c699Ted Kremenek /// isEmpty - Return true if the set contains no elements. 103933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEmpty() const { return !Root; } 1040085a9ebbc705c6e7d3fd8c692ef1c46fdfb885ceMisha Brukman 1041da5eb715509685f4a5cfdf6cd781827e72199af6Ted Kremenek /// isSingleton - Return true if the set contains exactly one element. 1042da5eb715509685f4a5cfdf6cd781827e72199af6Ted Kremenek /// This method runs in constant time. 1043da5eb715509685f4a5cfdf6cd781827e72199af6Ted Kremenek bool isSingleton() const { return getHeight() == 1; } 10443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 104533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 104633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void foreach(Callback& C) { if (Root) Root->foreach(C); } 10473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 104833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 104933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void foreach() { if (Root) { Callback C; Root->foreach(C); } } 10503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1052bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek // Iterators. 10533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1054bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek 1055bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek class iterator { 1056bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek typename TreeTy::iterator itr; 1057779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes 1058779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes iterator() {} 1059bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek iterator(TreeTy* t) : itr(t) {} 1060bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek friend class ImmutableSet<ValT,ValInfo>; 10613df02ac9d46f7ce8f0f10bc693dfc3c6c5aa2863Ryan Govostes 1062779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes public: 1063a94d32284a00c544332464dd6b1efa65b1224ea3Francois Pichet typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type; 1064a94d32284a00c544332464dd6b1efa65b1224ea3Francois Pichet typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference; 1065a94d32284a00c544332464dd6b1efa65b1224ea3Francois Pichet typedef typename iterator::value_type *pointer; 10663df02ac9d46f7ce8f0f10bc693dfc3c6c5aa2863Ryan Govostes typedef std::bidirectional_iterator_tag iterator_category; 1067779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes 1068a94d32284a00c544332464dd6b1efa65b1224ea3Francois Pichet typename iterator::reference operator*() const { return itr->getValue(); } 1069a94d32284a00c544332464dd6b1efa65b1224ea3Francois Pichet typename iterator::pointer operator->() const { return &(operator*()); } 1070779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes 1071779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes iterator& operator++() { ++itr; return *this; } 1072779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1073779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes iterator& operator--() { --itr; return *this; } 1074779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1075779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes 1076779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 1077779a96362e18d008e224c1683e54181ba1fbe943Ryan Govostes bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 1078bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek }; 10793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1080bdc2154986f6f302ef59b506013b73f82a7a5ee5Ted Kremenek iterator begin() const { return iterator(Root); } 10813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman iterator end() const { return iterator(); } 10823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 10849dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek // Utility methods. 10853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 10863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10873ec68f97ead4a2bc339b1b9012ca4cb2c4dd706aTed Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 10883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10899dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) { 10909dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek ID.AddPointer(S.Root); 10919dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek } 10923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10939dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek inline void Profile(FoldingSetNodeID& ID) const { 10949dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek return Profile(ID,*this); 10959dc7ab538ee845e2477519c740a2c736a19bc30dTed Kremenek } 10963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 109833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // For testing. 10993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 11003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 11019c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek void validateTree() const { if (Root) Root->validateTree(); } 110233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 1103644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1104166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek// NOTE: This may some day replace the current ImmutableSet. 1105166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenektemplate <typename ValT, typename ValInfo = ImutContainerInfo<ValT> > 1106166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekclass ImmutableSetRef { 1107166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekpublic: 1108166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::value_type value_type; 1109166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 1110166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 1111166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename TreeTy::Factory FactoryTy; 1112644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1113166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekprivate: 1114166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *Root; 1115166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek FactoryTy *Factory; 1116644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1117166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekpublic: 1118166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// Constructs a set from a pointer to a tree root. In general one 1119166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// should use a Factory object to create sets instead of directly 1120166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// invoking the constructor, but there are cases where make this 1121166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// constructor public is useful. 1122166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek explicit ImmutableSetRef(TreeTy* R, FactoryTy *F) 1123166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek : Root(R), 1124166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory(F) { 1125166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { Root->retain(); } 1126166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1127166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableSetRef(const ImmutableSetRef &X) 1128166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek : Root(X.Root), 1129166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory(X.Factory) { 1130166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { Root->retain(); } 1131166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1132166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableSetRef &operator=(const ImmutableSetRef &X) { 1133166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root != X.Root) { 1134166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (X.Root) { X.Root->retain(); } 1135166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { Root->release(); } 1136166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root = X.Root; 1137166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory = X.Factory; 1138166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1139166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return *this; 1140166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1141166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ~ImmutableSetRef() { 1142166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { Root->release(); } 1143166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1144644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1145166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek static inline ImmutableSetRef getEmptySet(FactoryTy *F) { 1146166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableSetRef(0, F); 1147166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1148644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1149166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableSetRef add(value_type_ref V) { 1150166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableSetRef(Factory->add(Root, V), Factory); 1151166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1152644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1153166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableSetRef remove(value_type_ref V) { 1154166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableSetRef(Factory->remove(Root, V), Factory); 1155166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1156644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1157166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// Returns true if the set contains the specified value. 1158166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool contains(value_type_ref V) const { 1159166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root ? Root->contains(V) : false; 1160166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1161644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 11624f101db8852ba60d8d9545f7e0b5ad8a7b18c8b1Ted Kremenek ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const { 11634f101db8852ba60d8d9545f7e0b5ad8a7b18c8b1Ted Kremenek return ImmutableSet<ValT>(canonicalize ? 11644f101db8852ba60d8d9545f7e0b5ad8a7b18c8b1Ted Kremenek Factory->getCanonicalTree(Root) : Root); 1165166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1166644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1167166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *getRootWithoutRetain() const { 1168166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root; 1169166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1170644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1171166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator==(const ImmutableSetRef &RHS) const { 1172166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 1173166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1174644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1175166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator!=(const ImmutableSetRef &RHS) const { 1176166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 1177166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1178166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 1179166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// isEmpty - Return true if the set contains no elements. 1180166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool isEmpty() const { return !Root; } 1181644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1182166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// isSingleton - Return true if the set contains exactly one element. 1183166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// This method runs in constant time. 1184166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool isSingleton() const { return getHeight() == 1; } 1185166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 1186166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 1187166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // Iterators. 1188166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 1189644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1190166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek class iterator { 1191166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typename TreeTy::iterator itr; 1192166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator(TreeTy* t) : itr(t) {} 1193166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek friend class ImmutableSetRef<ValT,ValInfo>; 1194166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek public: 1195166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator() {} 1196166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline value_type_ref operator*() const { return itr->getValue(); } 1197166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline iterator& operator++() { ++itr; return *this; } 1198166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 1199166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline iterator& operator--() { --itr; return *this; } 1200166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 1201166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 1202166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 1203166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline value_type *operator->() const { return &(operator*()); } 1204166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek }; 1205644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1206166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator begin() const { return iterator(Root); } 1207166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator end() const { return iterator(); } 1208644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1209166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 1210166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // Utility methods. 1211166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 1212644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1213166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 1214644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1215166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) { 1216166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ID.AddPointer(S.Root); 1217166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1218644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1219166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline void Profile(FoldingSetNodeID& ID) const { 1220166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Profile(ID,*this); 1221166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 1222644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1223166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 1224166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // For testing. 1225166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 1226644b3840b975cdd7465d16700740dd1dd7034df0Craig Topper 1227166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek void validateTree() const { if (Root) Root->validateTree(); } 1228166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek}; 122933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 123033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek} // end namespace llvm 123133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 123233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#endif 1233