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 14674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ADT_IMMUTABLEMAP_H 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ADT_IMMUTABLEMAP_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 Brukmantemplate <typename KeyT, typename ValT, 5933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 6033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekclass ImmutableMap { 616632f952393834fde26d53ea724ce2a53781d210Ted Kremenekpublic: 6233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type value_type; 6333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 6433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::key_type key_type; 6533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::key_type_ref key_type_ref; 6633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::data_type data_type; 6733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typedef typename ValInfo::data_type_ref data_type_ref; 686632f952393834fde26d53ea724ce2a53781d210Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 70746f5b6eb1518986bdac750074cbf1899e459983Zhongxing Xuprotected: 7133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek TreeTy* Root; 723a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekpublic: 746632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// Constructs a map from a pointer to a tree root. In general one 756632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// should use a Factory object to create maps instead of directly 766632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// invoking the constructor, but there are cases where make this 776632f952393834fde26d53ea724ce2a53781d210Ted Kremenek /// constructor public is useful. 7875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) { 7975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 8075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 81cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 8275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImmutableMap(const ImmutableMap &X) : Root(X.Root) { 8375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 8475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 85cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 8675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ImmutableMap &operator=(const ImmutableMap &X) { 8775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root != X.Root) { 8875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (X.Root) { X.Root->retain(); } 8975627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->release(); } 9075627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek Root = X.Root; 9175627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 9275627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return *this; 9375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 94cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 9575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek ~ImmutableMap() { 9675627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->release(); } 9775627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek class Factory { 10033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek typename TreeTy::Factory F; 101091508d3d0b0ebe0216b73b30161fbc599f9d4f1Ted Kremenek const bool Canonicalize; 1023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek public: 104cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Factory(bool canonicalize = true) : Canonicalize(canonicalize) {} 105cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 106cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Factory(BumpPtrAllocator &Alloc, bool canonicalize = true) 107cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : F(Alloc), Canonicalize(canonicalize) {} 1083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1099c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } 1103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 111091508d3d0b0ebe0216b73b30161fbc599f9d4f1Ted Kremenek ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { 1122d76ad6df91d3192f986efd19d70a6d892a05b6cNick Lewycky TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D)); 1139c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 11433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 116091508d3d0b0ebe0216b73b30161fbc599f9d4f1Ted Kremenek ImmutableMap remove(ImmutableMap Old, key_type_ref K) { 1179c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek TreeTy *T = F.remove(Old.Root,K); 1189c336fabd59fbdbe9129d76fbbee32261ac7c8f0Ted Kremenek return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 1193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 1203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 121b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks typename TreeTy::Factory *getTreeFactory() const { 122b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks return const_cast<typename TreeTy::Factory *>(&F); 123b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks } 124b3e3b006bd5c82516d6fdb487d5c1263a5249474Anna Zaks 12533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek private: 126ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Factory(const Factory& RHS) = delete; 127ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void operator=(const Factory& RHS) = delete; 12833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 1293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 13033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool contains(key_type_ref K) const { 13133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root ? Root->contains(K) : false; 13233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 133316e98447122fc3f1e99930583a305ba481e848cTed Kremenek 13475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator==(const ImmutableMap &RHS) const { 13533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 13633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 13875627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek bool operator!=(const ImmutableMap &RHS) const { 13933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 14033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1423f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek TreeTy *getRoot() const { 14375627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek if (Root) { Root->retain(); } 14475627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek return Root; 14575627d3d2e700b8fa0e040a5ec4ef1a0e299b9b5Ted Kremenek } 1463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 147cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar TreeTy *getRootWithoutRetain() const { return Root; } 148cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1493f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek void manualRetain() { 1503f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek if (Root) Root->retain(); 1513f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek } 152cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 1533f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek void manualRelease() { 1543f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek if (Root) Root->release(); 1553f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek } 1563f912adeae348cf230795c2c9d83165e7d854d43Ted Kremenek 15733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek bool isEmpty() const { return !Root; } 15833bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 1593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 16033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // Foreach - A limited form of map iteration. 16133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek //===--------------------------------------------------===// 16233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 16333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenekprivate: 16433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 16533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek struct CBWrapper { 16633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Callback C; 1673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator()(value_type_ref V) { C(V.first,V.second); } 1683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman }; 1693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 17033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 17133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek struct CBWrapperRef { 17233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Callback &C; 17333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapperRef(Callback& c) : C(c) {} 1743a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void operator()(value_type_ref V) { C(V.first,V.second); } 17633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek }; 1773a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpublic: 17933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 1803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void foreach(Callback& C) { 1813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman if (Root) { 18233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapperRef<Callback> CB(C); 18333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Root->foreach(CB); 18433bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 18533bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek template <typename Callback> 1883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman void foreach() { 18933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek if (Root) { 19033bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek CBWrapper<Callback> CB; 19133bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek Root->foreach(CB); 19233bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 19333bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek } 1943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 19633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek // For testing. 1973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 19933bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek void verify() const { if (Root) Root->verify(); } 2003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2023c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek // Iterators. 2033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2054c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar class iterator : public ImutAVLValueIterator<ImmutableMap> { 2064c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar iterator() = default; 2074c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} 208316e98447122fc3f1e99930583a305ba481e848cTed Kremenek friend class ImmutableMap; 2093c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek 2103c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek public: 2114c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar key_type_ref getKey() const { return (*this)->first; } 2124c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar data_type_ref getData() const { return (*this)->second; } 2133c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek }; 2143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2153c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek iterator begin() const { return iterator(Root); } 2163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman iterator end() const { return iterator(); } 2173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 218aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek data_type* lookup(key_type_ref K) const { 219316e98447122fc3f1e99930583a305ba481e848cTed Kremenek if (Root) { 220316e98447122fc3f1e99930583a305ba481e848cTed Kremenek TreeTy* T = Root->find(K); 221aa5044d3ce80a2759a6084911db77dec385a47fcTed Kremenek if (T) return &T->getValue().second; 222316e98447122fc3f1e99930583a305ba481e848cTed Kremenek } 2233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 225316e98447122fc3f1e99930583a305ba481e848cTed Kremenek } 226cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 2271c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 2281c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// which key is the highest in the ordering of keys in the map. This 2291c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek /// method returns NULL if the map is empty. 2301c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek value_type* getMaxElement() const { 231dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Root ? &(Root->getMaxElement()->getValue()) : nullptr; 2321c7a666fcef22e75dc675b06444f5a894f54d7beTed Kremenek } 2333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2353c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek // Utility methods. 2363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman //===--------------------------------------------------===// 2373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2383ec68f97ead4a2bc339b1b9012ca4cb2c4dd706aTed Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 2393c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek 240c695ea9e8dca7a4f955b6bc17da49be5553c9f37Ted Kremenek static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 24195da16e2881a662401220cd52a4267b7cd7f5860Ted Kremenek ID.AddPointer(M.Root); 2423c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek } 2433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2443c6255c376127f9e79b8bab47a2fd585131e8fcdTed Kremenek inline void Profile(FoldingSetNodeID& ID) const { 2456f2197699a53c5711ab7b0f8cc1b57f5e449e40aTed Kremenek return Profile(ID,*this); 2463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 24733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek}; 2483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 249166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek// NOTE: This will possibly become the new implementation of ImmutableMap some day. 250166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenektemplate <typename KeyT, typename ValT, 251166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenektypename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 252166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekclass ImmutableMapRef { 253166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekpublic: 254166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::value_type value_type; 255166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::value_type_ref value_type_ref; 256166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::key_type key_type; 257166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::key_type_ref key_type_ref; 258166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::data_type data_type; 259166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename ValInfo::data_type_ref data_type_ref; 260166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef ImutAVLTree<ValInfo> TreeTy; 261166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek typedef typename TreeTy::Factory FactoryTy; 262cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 263166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekprotected: 264166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *Root; 265166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek FactoryTy *Factory; 266cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 267166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenekpublic: 268166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// Constructs a map from a pointer to a tree root. In general one 269166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// should use a Factory object to create maps instead of directly 270166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// invoking the constructor, but there are cases where make this 271166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// constructor public is useful. 272cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F) 273cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar : Root(const_cast<TreeTy *>(R)), Factory(F) { 274cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (Root) { 275cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Root->retain(); 276cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar } 277166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 278b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek 279b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X, 280b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek typename ImmutableMap<KeyT, ValT>::Factory &F) 281b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek : Root(X.getRootWithoutRetain()), 282b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek Factory(F.getTreeFactory()) { 283b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek if (Root) { Root->retain(); } 284b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek } 285cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 286cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) { 287cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (Root) { 288cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Root->retain(); 289cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar } 290166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 291166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 292166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMapRef &operator=(const ImmutableMapRef &X) { 293166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root != X.Root) { 294166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (X.Root) 295166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek X.Root->retain(); 296cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 297166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) 298166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root->release(); 299cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 300166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root = X.Root; 301166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Factory = X.Factory; 302166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 303166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return *this; 304166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 305166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 306166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ~ImmutableMapRef() { 307166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) 308166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek Root->release(); 309166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 310cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 311166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { 312166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMapRef(0, F); 313166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 314166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 315b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek void manualRetain() { 316b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek if (Root) Root->retain(); 317b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek } 318b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek 319b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek void manualRelease() { 320b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek if (Root) Root->release(); 321b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek } 322b02ed5b8eafd11500bbefb7206ecbf5bc3fc324aTed Kremenek 3236cd738f33934a93b114d7dd9e4291f87f445c5c4Ted Kremenek ImmutableMapRef add(key_type_ref K, data_type_ref D) const { 324166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D)); 325166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMapRef(NewT, Factory); 326166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 327166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek 3286cd738f33934a93b114d7dd9e4291f87f445c5c4Ted Kremenek ImmutableMapRef remove(key_type_ref K) const { 329166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy *NewT = Factory->remove(Root, K); 330166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMapRef(NewT, Factory); 331166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 332cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 333166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool contains(key_type_ref K) const { 334166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root ? Root->contains(K) : false; 335166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 336cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 337166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ImmutableMap<KeyT, ValT> asImmutableMap() const { 338166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root)); 339166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 340cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 341166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator==(const ImmutableMapRef &RHS) const { 342166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 343166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 344cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 345166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool operator!=(const ImmutableMapRef &RHS) const { 346166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 347166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 348cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 349166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek bool isEmpty() const { return !Root; } 350cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 351166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 352166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // For testing. 353166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 354cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 355cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar void verify() const { 356cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar if (Root) 357cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar Root->verify(); 358cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar } 359cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 360166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 361166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // Iterators. 362166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 3634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 3644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar class iterator : public ImutAVLValueIterator<ImmutableMapRef> { 3654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar iterator() = default; 3664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} 367166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek friend class ImmutableMapRef; 3684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 369166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek public: 3704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar key_type_ref getKey() const { return (*this)->first; } 3714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar data_type_ref getData() const { return (*this)->second; } 372166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek }; 3734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 374166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator begin() const { return iterator(Root); } 375166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek iterator end() const { return iterator(); } 376cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 377cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar data_type *lookup(key_type_ref K) const { 378166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (Root) { 379166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek TreeTy* T = Root->find(K); 380166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek if (T) return &T->getValue().second; 381166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 382cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 383cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar return nullptr; 384166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 385cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 386166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 387166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// which key is the highest in the ordering of keys in the map. This 388166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek /// method returns NULL if the map is empty. 389166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek value_type* getMaxElement() const { 390166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek return Root ? &(Root->getMaxElement()->getValue()) : 0; 391166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 392cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 393166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 394166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek // Utility methods. 395166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek //===--------------------------------------------------===// 396cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 397166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 398cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 399cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) { 400166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek ID.AddPointer(M.Root); 401166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek } 402cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 403cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } 404166e0539c987a5bea2432354b2437eba29bb1ce0Ted Kremenek}; 405cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar 40633bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek} // end namespace llvm 40733bbed8f2a48ccf9ee349458db7ec4bd24dddb11Ted Kremenek 408cddc3e03e4ec99c0268c03a126195173e519ed58Pirama Arumuga Nainar#endif // LLVM_ADT_IMMUTABLEMAP_H 409