133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===--- ImmutableMap.h - Immutable (functional) map 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 ImmutableMap class. 1133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek// 1233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek//===----------------------------------------------------------------------===// 1333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#ifndef LLVM_ADT_IMMAP_H 1533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#define LLVM_ADT_IMMAP_H 1633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#include "llvm/ADT/ImmutableSet.h" 1833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremeneknamespace llvm { 2033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 21a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman/// ImutKeyValueInfo -Traits class used by ImmutableMap. While both the first 22a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman/// and second elements in a pair are used to generate profile information, 2333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek/// only the first element (the key) is used by isEqual and isLess. 2433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenektemplate <typename T, typename S> 2533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekstruct ImutKeyValueInfo { 2633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const std::pair<T,S> value_type; 2733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const value_type& value_type_ref; 2833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T key_type; 2933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const T& key_type_ref; 3033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const S data_type; 3133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef const S& data_type_ref; 323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline key_type_ref KeyOfValue(value_type_ref V) { 3433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return V.first; 3533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 37e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline data_type_ref DataOfValue(value_type_ref V) { 38e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek return V.second; 3933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 41e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline bool isEqual(key_type_ref L, key_type_ref R) { 42e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek return ImutContainerInfo<T>::isEqual(L,R); 433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 4433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline bool isLess(key_type_ref L, key_type_ref R) { 4533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return ImutContainerInfo<T>::isLess(L,R); 4633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 48e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek static inline bool isDataEqual(data_type_ref L, data_type_ref R) { 49e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek return ImutContainerInfo<S>::isEqual(L,R); 50e509e7a17819f808dabb815474eb8c04540de7b3Ted Kremenek } 513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) { 5333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutContainerInfo<T>::Profile(ID, V.first); 5433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek ImutContainerInfo<S>::Profile(ID, V.second); 5533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 5733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate <typename KeyT, typename ValT, 6033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 6133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImmutableMap { 626632f952393834fde26d53ea724ce2a53781d210Ted Kremenekpublic: 6333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type value_type; 6433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 6533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::key_type key_type; 6633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::key_type_ref key_type_ref; 6733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::data_type data_type; 6833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::data_type_ref data_type_ref; 696632f952393834fde26d53ea724ce2a53781d210Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 71746f5b6eb1518986bdac750074cbf1899e459983Zhongxing Xuprotected: 7233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Root; 733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 756632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// Constructs a map from a pointer to a tree root. In general one 766632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// should use a Factory object to create maps instead of directly 776632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// invoking the constructor, but there are cases where make this 786632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// constructor public is useful. 7975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) { 8075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 8175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 8275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImmutableMap(const ImmutableMap &X) : Root(X.Root) { 8375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 8475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 8575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImmutableMap &operator=(const ImmutableMap &X) { 8675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root != X.Root) { 8775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (X.Root) { X.Root->retain(); } 8875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->release(); } 8975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek Root = X.Root; 9075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 9175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return *this; 9275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 9375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ~ImmutableMap() { 9475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->release(); } 9575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek class Factory { 9833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typename TreeTy::Factory F; 999688079e07dce7748d14a761d52732add634ba4cTed Kremenek const bool Canonicalize; 1003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek public: 1029688079e07dce7748d14a761d52732add634ba4cTed Kremenek Factory(bool canonicalize = true) 1039688079e07dce7748d14a761d52732add634ba4cTed Kremenek : Canonicalize(canonicalize) {} 1049688079e07dce7748d14a761d52732add634ba4cTed Kremenek 1059688079e07dce7748d14a761d52732add634ba4cTed Kremenek Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) 1069688079e07dce7748d14a761d52732add634ba4cTed Kremenek : F(Alloc), Canonicalize(canonicalize) {} 1073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1089c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } 1093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1109c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { 1112d76ad6df91d3192f986efd19d70a6d892a05b6cNick Lewycky TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D)); 1129c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 11333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1159c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableMap remove(ImmutableMap Old, key_type_ref K) { 1169c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *T = F.remove(Old.Root,K); 1179c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 1183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 1193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 120b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks typename TreeTy::Factory *getTreeFactory() const { 121b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks return const_cast<typename TreeTy::Factory *>(&F); 122b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks } 123b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks 12433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek private: 1250c8ae782cb966068f8317f8225633e2f4720ccb7Douglas Gregor Factory(const Factory& RHS); // DO NOT IMPLEMENT 1260c8ae782cb966068f8317f8225633e2f4720ccb7Douglas Gregor void operator=(const Factory& RHS); // DO NOT IMPLEMENT 12733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 1283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 12933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool contains(key_type_ref K) const { 13033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root ? Root->contains(K) : false; 13133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 132316e98447122fc3f1e99930583a305ba481e848cTed Kremenek 13375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator==(const ImmutableMap &RHS) const { 13433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 13533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 13775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator!=(const ImmutableMap &RHS) const { 13833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 13933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1413f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek TreeTy *getRoot() const { 14275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 14375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return Root; 14475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 1453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1463f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek TreeTy *getRootWithoutRetain() const { 1473f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek return Root; 1483f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek } 1493f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek 1503f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek void manualRetain() { 1513f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek if (Root) Root->retain(); 1523f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek } 1533f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek 1543f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek void manualRelease() { 1553f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek if (Root) Root->release(); 1563f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek } 1573f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek 15833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEmpty() const { return !Root; } 15933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 16133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Foreach - A limited form of map iteration. 16233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 16333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 16433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 16533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 16633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek struct CBWrapper { 16733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Callback C; 1683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator()(value_type_ref V) { C(V.first,V.second); } 1693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman }; 1703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 17133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 17233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek struct CBWrapperRef { 17333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Callback &C; 17433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapperRef(Callback& c) : C(c) {} 1753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator()(value_type_ref V) { C(V.first,V.second); } 17733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 1783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpublic: 18033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 1813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void foreach(Callback& C) { 1823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman if (Root) { 18333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapperRef<Callback> CB(C); 18433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Root->foreach(CB); 18533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 18633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 1893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void foreach() { 19033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (Root) { 19133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapper<Callback> CB; 19233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Root->foreach(CB); 19333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 19433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 19733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // For testing. 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 20033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void verify() const { if (Root) Root->verify(); } 2013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2033c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek // Iterators. 2043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2063c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek class iterator { 2073c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek typename TreeTy::iterator itr; 2083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2093c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator() {} 2103c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator(TreeTy* t) : itr(t) {} 211316e98447122fc3f1e99930583a305ba481e848cTed Kremenek friend class ImmutableMap; 2123c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek 2133c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek public: 2147a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek value_type_ref operator*() const { return itr->getValue(); } 2157a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek value_type* operator->() const { return &itr->getValue(); } 2163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2177a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek key_type_ref getKey() const { return itr->getValue().first; } 2187a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek data_type_ref getData() const { return itr->getValue().second; } 2193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2217a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator& operator++() { ++itr; return *this; } 2227a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 2237a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator& operator--() { --itr; return *this; } 2247a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 2257a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 2263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 2273c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek }; 2283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2293c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator begin() const { return iterator(Root); } 2303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman iterator end() const { return iterator(); } 2313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 232aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek data_type* lookup(key_type_ref K) const { 233316e98447122fc3f1e99930583a305ba481e848cTed Kremenek if (Root) { 234316e98447122fc3f1e99930583a305ba481e848cTed Kremenek TreeTy* T = Root->find(K); 235aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek if (T) return &T->getValue().second; 236316e98447122fc3f1e99930583a305ba481e848cTed Kremenek } 2373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 238aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek return 0; 239316e98447122fc3f1e99930583a305ba481e848cTed Kremenek } 2401c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek 2411c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 2421c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// which key is the highest in the ordering of keys in the map. This 2431c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// method returns NULL if the map is empty. 2441c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek value_type* getMaxElement() const { 245638b8b446e7f08d348fe4f3b290c08f6854fc8baTed Kremenek return Root ? &(Root->getMaxElement()->getValue()) : 0; 2461c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek } 2473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2493c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek // Utility methods. 2503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2523ec68f97ead4a2bc339b1b9012ca4cb2c4dd706aTed Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 2533c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek 254c695ea9e8dca7a4f955b6bc17da49be5553c9f37Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 25595da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek ID.AddPointer(M.Root); 2563c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek } 2573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2583c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek inline void Profile(FoldingSetNodeID& ID) const { 2596f2197699a53c5711ab7b0f8cc1b57f5e449e40aTed Kremenek return Profile(ID,*this); 2603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 26133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 2623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 263166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek// NOTE: This will possibly become the new implementation of ImmutableMap some day. 264166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenektemplate <typename KeyT, typename ValT, 265166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenektypename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 266166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekclass ImmutableMapRef { 267166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekpublic: 268166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::value_type value_type; 269166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 270166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::key_type key_type; 271166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::key_type_ref key_type_ref; 272166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::data_type data_type; 273166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::data_type_ref data_type_ref; 274166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 275166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename TreeTy::Factory FactoryTy; 276166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 277166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekprotected: 278166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *Root; 279166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek FactoryTy *Factory; 280166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 281166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekpublic: 282166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// Constructs a map from a pointer to a tree root. In general one 283166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// should use a Factory object to create maps instead of directly 284166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// invoking the constructor, but there are cases where make this 285166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// constructor public is useful. 286166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek explicit ImmutableMapRef(const TreeTy* R, FactoryTy *F) 287166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek : Root(const_cast<TreeTy*>(R)), 288166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory(F) { 289166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { Root->retain(); } 290166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 291166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 292166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMapRef(const ImmutableMapRef &X) 293166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek : Root(X.Root), 294166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory(X.Factory) { 295166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { Root->retain(); } 296166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 297166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 298166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMapRef &operator=(const ImmutableMapRef &X) { 299166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root != X.Root) { 300166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (X.Root) 301166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek X.Root->retain(); 302166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 303166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) 304166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root->release(); 305166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 306166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root = X.Root; 307166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory = X.Factory; 308166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 309166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return *this; 310166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 311166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 312166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ~ImmutableMapRef() { 313166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) 314166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root->release(); 315166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 316166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 317166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { 318166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMapRef(0, F); 319166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 320166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 321166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMapRef add(key_type_ref K, data_type_ref D) { 322166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D)); 323166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMapRef(NewT, Factory); 324166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 325166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 326166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMapRef remove(key_type_ref K) { 327166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *NewT = Factory->remove(Root, K); 328166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMapRef(NewT, Factory); 329166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 330166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 331166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool contains(key_type_ref K) const { 332166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root ? Root->contains(K) : false; 333166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 334166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 335166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMap<KeyT, ValT> asImmutableMap() const { 336166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root)); 337166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 338166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 339166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator==(const ImmutableMapRef &RHS) const { 340166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 341166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 342166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 343166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator!=(const ImmutableMapRef &RHS) const { 344166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 345166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 346166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 347166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool isEmpty() const { return !Root; } 348166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 349166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 350166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // For testing. 351166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 352166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 353166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek void verify() const { if (Root) Root->verify(); } 354166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 355166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 356166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // Iterators. 357166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 358166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 359166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek class iterator { 360166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typename TreeTy::iterator itr; 361166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 362166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator() {} 363166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator(TreeTy* t) : itr(t) {} 364166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek friend class ImmutableMapRef; 365166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 366166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek public: 367166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek value_type_ref operator*() const { return itr->getValue(); } 368166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek value_type* operator->() const { return &itr->getValue(); } 369166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 370166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek key_type_ref getKey() const { return itr->getValue().first; } 371166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek data_type_ref getData() const { return itr->getValue().second; } 372166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 373166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 374166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator& operator++() { ++itr; return *this; } 375166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 376166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator& operator--() { --itr; return *this; } 377166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 378166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 379166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 380166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek }; 381166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 382166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator begin() const { return iterator(Root); } 383166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator end() const { return iterator(); } 384166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 385166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek data_type* lookup(key_type_ref K) const { 386166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { 387166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy* T = Root->find(K); 388166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (T) return &T->getValue().second; 389166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 390166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 391166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return 0; 392166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 393166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 394166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 395166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// which key is the highest in the ordering of keys in the map. This 396166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// method returns NULL if the map is empty. 397166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek value_type* getMaxElement() const { 398166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root ? &(Root->getMaxElement()->getValue()) : 0; 399166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 400166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 401166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 402166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // Utility methods. 403166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 404166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 405166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 406166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 407166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableMapRef &M) { 408166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ID.AddPointer(M.Root); 409166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 410166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 411166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek inline void Profile(FoldingSetNodeID& ID) const { 412166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Profile(ID, *this); 413166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 414166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek}; 415166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 41633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek} // end namespace llvm 41733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 41833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#endif 419