ImmutableMap.h revision 75627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5
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) { 1119c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *T = F.add(Old.Root, std::make_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 12033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek private: 1210c8ae782cb966068f8317f8225633e2f4720ccb7Douglas Gregor Factory(const Factory& RHS); // DO NOT IMPLEMENT 1220c8ae782cb966068f8317f8225633e2f4720ccb7Douglas Gregor void operator=(const Factory& RHS); // DO NOT IMPLEMENT 12333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 1243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 12533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool contains(key_type_ref K) const { 12633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root ? Root->contains(K) : false; 12733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 128316e98447122fc3f1e99930583a305ba481e848cTed Kremenek 12975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator==(const ImmutableMap &RHS) const { 13033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 13133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 13375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator!=(const ImmutableMap &RHS) const { 13433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 13533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 13775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek TreeTy* getRoot() const { 13875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 13975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return Root; 14075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 1413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 14233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEmpty() const { return !Root; } 14333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 14533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Foreach - A limited form of map iteration. 14633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 14733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 14833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 14933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 15033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek struct CBWrapper { 15133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Callback C; 1523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator()(value_type_ref V) { C(V.first,V.second); } 1533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman }; 1543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 15533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 15633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek struct CBWrapperRef { 15733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Callback &C; 15833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapperRef(Callback& c) : C(c) {} 1593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator()(value_type_ref V) { C(V.first,V.second); } 16133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 1623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpublic: 16433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 1653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void foreach(Callback& C) { 1663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman if (Root) { 16733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapperRef<Callback> CB(C); 16833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Root->foreach(CB); 16933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 17033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1713a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 17233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 1733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void foreach() { 17433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (Root) { 17533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapper<Callback> CB; 17633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Root->foreach(CB); 17733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 17833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 18133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // For testing. 1823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void verify() const { if (Root) Root->verify(); } 1853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1873c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek // Iterators. 1883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1903c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek class iterator { 1913c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek typename TreeTy::iterator itr; 1923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1933c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator() {} 1943c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator(TreeTy* t) : itr(t) {} 195316e98447122fc3f1e99930583a305ba481e848cTed Kremenek friend class ImmutableMap; 1963c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek 1973c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek public: 1987a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek value_type_ref operator*() const { return itr->getValue(); } 1997a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek value_type* operator->() const { return &itr->getValue(); } 2003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2017a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek key_type_ref getKey() const { return itr->getValue().first; } 2027a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek data_type_ref getData() const { return itr->getValue().second; } 2033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2057a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator& operator++() { ++itr; return *this; } 2067a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 2077a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator& operator--() { --itr; return *this; } 2087a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 2097a07428ad1015306d7235cabebd5f4f78e62d33cTed Kremenek bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 2103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 2113c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek }; 2123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2133c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator begin() const { return iterator(Root); } 2143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman iterator end() const { return iterator(); } 2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 216aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek data_type* lookup(key_type_ref K) const { 217316e98447122fc3f1e99930583a305ba481e848cTed Kremenek if (Root) { 218316e98447122fc3f1e99930583a305ba481e848cTed Kremenek TreeTy* T = Root->find(K); 219aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek if (T) return &T->getValue().second; 220316e98447122fc3f1e99930583a305ba481e848cTed Kremenek } 2213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 222aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek return 0; 223316e98447122fc3f1e99930583a305ba481e848cTed Kremenek } 2241c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek 2251c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 2261c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// which key is the highest in the ordering of keys in the map. This 2271c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// method returns NULL if the map is empty. 2281c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek value_type* getMaxElement() const { 229638b8b446e7f08d348fe4f3b290c08f6854fc8baTed Kremenek return Root ? &(Root->getMaxElement()->getValue()) : 0; 2301c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek } 2313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2333c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek // Utility methods. 2343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2363ec68f97ead4a2bc339b1b9012ca4cb2c4dd706aTed Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 2373c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek 238c695ea9e8dca7a4f955b6bc17da49be5553c9f37Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 23995da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek ID.AddPointer(M.Root); 2403c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek } 2413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2423c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek inline void Profile(FoldingSetNodeID& ID) const { 2436f2197699a53c5711ab7b0f8cc1b57f5e449e40aTed Kremenek return Profile(ID,*this); 2443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 24533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 2463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 24733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek} // end namespace llvm 24833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 24933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek#endif 250