1193323Sed//===--- ImmutableMap.h - Immutable (functional) map interface --*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the ImmutableMap class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14249423Sdim#ifndef LLVM_ADT_IMMUTABLEMAP_H 15249423Sdim#define LLVM_ADT_IMMUTABLEMAP_H 16193323Sed 17193323Sed#include "llvm/ADT/ImmutableSet.h" 18193323Sed 19193323Sednamespace llvm { 20193323Sed 21193323Sed/// ImutKeyValueInfo -Traits class used by ImmutableMap. While both the first 22193323Sed/// and second elements in a pair are used to generate profile information, 23193323Sed/// only the first element (the key) is used by isEqual and isLess. 24193323Sedtemplate <typename T, typename S> 25193323Sedstruct ImutKeyValueInfo { 26193323Sed typedef const std::pair<T,S> value_type; 27193323Sed typedef const value_type& value_type_ref; 28193323Sed typedef const T key_type; 29193323Sed typedef const T& key_type_ref; 30193323Sed typedef const S data_type; 31193323Sed typedef const S& data_type_ref; 32193323Sed 33193323Sed static inline key_type_ref KeyOfValue(value_type_ref V) { 34193323Sed return V.first; 35193323Sed } 36193323Sed 37193323Sed static inline data_type_ref DataOfValue(value_type_ref V) { 38193323Sed return V.second; 39193323Sed } 40193323Sed 41193323Sed static inline bool isEqual(key_type_ref L, key_type_ref R) { 42193323Sed return ImutContainerInfo<T>::isEqual(L,R); 43193323Sed } 44193323Sed static inline bool isLess(key_type_ref L, key_type_ref R) { 45193323Sed return ImutContainerInfo<T>::isLess(L,R); 46193323Sed } 47193323Sed 48193323Sed static inline bool isDataEqual(data_type_ref L, data_type_ref R) { 49193323Sed return ImutContainerInfo<S>::isEqual(L,R); 50193323Sed } 51193323Sed 52193323Sed static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) { 53193323Sed ImutContainerInfo<T>::Profile(ID, V.first); 54193323Sed ImutContainerInfo<S>::Profile(ID, V.second); 55193323Sed } 56193323Sed}; 57193323Sed 58193323Sed 59193323Sedtemplate <typename KeyT, typename ValT, 60193323Sed typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 61193323Sedclass ImmutableMap { 62193323Sedpublic: 63193323Sed typedef typename ValInfo::value_type value_type; 64193323Sed typedef typename ValInfo::value_type_ref value_type_ref; 65193323Sed typedef typename ValInfo::key_type key_type; 66193323Sed typedef typename ValInfo::key_type_ref key_type_ref; 67193323Sed typedef typename ValInfo::data_type data_type; 68193323Sed typedef typename ValInfo::data_type_ref data_type_ref; 69193323Sed typedef ImutAVLTree<ValInfo> TreeTy; 70193323Sed 71203954Srdivackyprotected: 72193323Sed TreeTy* Root; 73193323Sed 74193323Sedpublic: 75193323Sed /// Constructs a map from a pointer to a tree root. In general one 76193323Sed /// should use a Factory object to create maps instead of directly 77193323Sed /// invoking the constructor, but there are cases where make this 78193323Sed /// constructor public is useful. 79218893Sdim explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) { 80218893Sdim if (Root) { Root->retain(); } 81218893Sdim } 82218893Sdim ImmutableMap(const ImmutableMap &X) : Root(X.Root) { 83218893Sdim if (Root) { Root->retain(); } 84218893Sdim } 85218893Sdim ImmutableMap &operator=(const ImmutableMap &X) { 86218893Sdim if (Root != X.Root) { 87218893Sdim if (X.Root) { X.Root->retain(); } 88218893Sdim if (Root) { Root->release(); } 89218893Sdim Root = X.Root; 90218893Sdim } 91218893Sdim return *this; 92218893Sdim } 93218893Sdim ~ImmutableMap() { 94218893Sdim if (Root) { Root->release(); } 95218893Sdim } 96193323Sed 97193323Sed class Factory { 98193323Sed typename TreeTy::Factory F; 99198090Srdivacky const bool Canonicalize; 100193323Sed 101193323Sed public: 102198090Srdivacky Factory(bool canonicalize = true) 103198090Srdivacky : Canonicalize(canonicalize) {} 104198090Srdivacky 105198090Srdivacky Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) 106198090Srdivacky : F(Alloc), Canonicalize(canonicalize) {} 107193323Sed 108218893Sdim ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } 109193323Sed 110218893Sdim ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { 111219077Sdim TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D)); 112218893Sdim return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 113193323Sed } 114193323Sed 115218893Sdim ImmutableMap remove(ImmutableMap Old, key_type_ref K) { 116218893Sdim TreeTy *T = F.remove(Old.Root,K); 117218893Sdim return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 118193323Sed } 119193323Sed 120226633Sdim typename TreeTy::Factory *getTreeFactory() const { 121226633Sdim return const_cast<typename TreeTy::Factory *>(&F); 122226633Sdim } 123226633Sdim 124193323Sed private: 125243830Sdim Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; 126243830Sdim void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; 127193323Sed }; 128193323Sed 129193323Sed bool contains(key_type_ref K) const { 130193323Sed return Root ? Root->contains(K) : false; 131193323Sed } 132193323Sed 133218893Sdim bool operator==(const ImmutableMap &RHS) const { 134193323Sed return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 135193323Sed } 136193323Sed 137218893Sdim bool operator!=(const ImmutableMap &RHS) const { 138193323Sed return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 139193323Sed } 140193323Sed 141218893Sdim TreeTy *getRoot() const { 142218893Sdim if (Root) { Root->retain(); } 143218893Sdim return Root; 144218893Sdim } 145193323Sed 146218893Sdim TreeTy *getRootWithoutRetain() const { 147218893Sdim return Root; 148218893Sdim } 149218893Sdim 150218893Sdim void manualRetain() { 151218893Sdim if (Root) Root->retain(); 152218893Sdim } 153218893Sdim 154218893Sdim void manualRelease() { 155218893Sdim if (Root) Root->release(); 156218893Sdim } 157218893Sdim 158193323Sed bool isEmpty() const { return !Root; } 159193323Sed 160193323Sed //===--------------------------------------------------===// 161193323Sed // Foreach - A limited form of map iteration. 162193323Sed //===--------------------------------------------------===// 163193323Sed 164193323Sedprivate: 165193323Sed template <typename Callback> 166193323Sed struct CBWrapper { 167193323Sed Callback C; 168193323Sed void operator()(value_type_ref V) { C(V.first,V.second); } 169193323Sed }; 170193323Sed 171193323Sed template <typename Callback> 172193323Sed struct CBWrapperRef { 173193323Sed Callback &C; 174193323Sed CBWrapperRef(Callback& c) : C(c) {} 175193323Sed 176193323Sed void operator()(value_type_ref V) { C(V.first,V.second); } 177193323Sed }; 178193323Sed 179193323Sedpublic: 180193323Sed template <typename Callback> 181193323Sed void foreach(Callback& C) { 182193323Sed if (Root) { 183193323Sed CBWrapperRef<Callback> CB(C); 184193323Sed Root->foreach(CB); 185193323Sed } 186193323Sed } 187193323Sed 188193323Sed template <typename Callback> 189193323Sed void foreach() { 190193323Sed if (Root) { 191193323Sed CBWrapper<Callback> CB; 192193323Sed Root->foreach(CB); 193193323Sed } 194193323Sed } 195193323Sed 196193323Sed //===--------------------------------------------------===// 197193323Sed // For testing. 198193323Sed //===--------------------------------------------------===// 199193323Sed 200193323Sed void verify() const { if (Root) Root->verify(); } 201193323Sed 202193323Sed //===--------------------------------------------------===// 203193323Sed // Iterators. 204193323Sed //===--------------------------------------------------===// 205193323Sed 206193323Sed class iterator { 207193323Sed typename TreeTy::iterator itr; 208193323Sed 209193323Sed iterator() {} 210193323Sed iterator(TreeTy* t) : itr(t) {} 211193323Sed friend class ImmutableMap; 212193323Sed 213193323Sed public: 214263508Sdim typedef ptrdiff_t difference_type; 215249423Sdim typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type value_type; 216249423Sdim typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type_ref reference; 217249423Sdim typedef typename iterator::value_type *pointer; 218249423Sdim typedef std::bidirectional_iterator_tag iterator_category; 219193323Sed 220249423Sdim typename iterator::reference operator*() const { return itr->getValue(); } 221249423Sdim typename iterator::pointer operator->() const { return &itr->getValue(); } 222249423Sdim 223193323Sed key_type_ref getKey() const { return itr->getValue().first; } 224193323Sed data_type_ref getData() const { return itr->getValue().second; } 225193323Sed 226193323Sed iterator& operator++() { ++itr; return *this; } 227193323Sed iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 228193323Sed iterator& operator--() { --itr; return *this; } 229193323Sed iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 230249423Sdim 231193323Sed bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 232193323Sed bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 233193323Sed }; 234193323Sed 235193323Sed iterator begin() const { return iterator(Root); } 236193323Sed iterator end() const { return iterator(); } 237193323Sed 238193323Sed data_type* lookup(key_type_ref K) const { 239193323Sed if (Root) { 240193323Sed TreeTy* T = Root->find(K); 241193323Sed if (T) return &T->getValue().second; 242193323Sed } 243193323Sed 244193323Sed return 0; 245193323Sed } 246193323Sed 247193323Sed /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 248193323Sed /// which key is the highest in the ordering of keys in the map. This 249193323Sed /// method returns NULL if the map is empty. 250193323Sed value_type* getMaxElement() const { 251193323Sed return Root ? &(Root->getMaxElement()->getValue()) : 0; 252193323Sed } 253193323Sed 254193323Sed //===--------------------------------------------------===// 255193323Sed // Utility methods. 256193323Sed //===--------------------------------------------------===// 257193323Sed 258202878Srdivacky unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 259193323Sed 260193323Sed static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 261193323Sed ID.AddPointer(M.Root); 262193323Sed } 263193323Sed 264193323Sed inline void Profile(FoldingSetNodeID& ID) const { 265193323Sed return Profile(ID,*this); 266193323Sed } 267193323Sed}; 268193323Sed 269226633Sdim// NOTE: This will possibly become the new implementation of ImmutableMap some day. 270226633Sdimtemplate <typename KeyT, typename ValT, 271226633Sdimtypename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 272226633Sdimclass ImmutableMapRef { 273226633Sdimpublic: 274226633Sdim typedef typename ValInfo::value_type value_type; 275226633Sdim typedef typename ValInfo::value_type_ref value_type_ref; 276226633Sdim typedef typename ValInfo::key_type key_type; 277226633Sdim typedef typename ValInfo::key_type_ref key_type_ref; 278226633Sdim typedef typename ValInfo::data_type data_type; 279226633Sdim typedef typename ValInfo::data_type_ref data_type_ref; 280226633Sdim typedef ImutAVLTree<ValInfo> TreeTy; 281226633Sdim typedef typename TreeTy::Factory FactoryTy; 282226633Sdim 283226633Sdimprotected: 284226633Sdim TreeTy *Root; 285226633Sdim FactoryTy *Factory; 286226633Sdim 287226633Sdimpublic: 288226633Sdim /// Constructs a map from a pointer to a tree root. In general one 289226633Sdim /// should use a Factory object to create maps instead of directly 290226633Sdim /// invoking the constructor, but there are cases where make this 291226633Sdim /// constructor public is useful. 292226633Sdim explicit ImmutableMapRef(const TreeTy* R, FactoryTy *F) 293226633Sdim : Root(const_cast<TreeTy*>(R)), 294226633Sdim Factory(F) { 295226633Sdim if (Root) { Root->retain(); } 296226633Sdim } 297249423Sdim 298249423Sdim explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X, 299249423Sdim typename ImmutableMap<KeyT, ValT>::Factory &F) 300249423Sdim : Root(X.getRootWithoutRetain()), 301249423Sdim Factory(F.getTreeFactory()) { 302249423Sdim if (Root) { Root->retain(); } 303249423Sdim } 304226633Sdim 305226633Sdim ImmutableMapRef(const ImmutableMapRef &X) 306226633Sdim : Root(X.Root), 307226633Sdim Factory(X.Factory) { 308226633Sdim if (Root) { Root->retain(); } 309226633Sdim } 310226633Sdim 311226633Sdim ImmutableMapRef &operator=(const ImmutableMapRef &X) { 312226633Sdim if (Root != X.Root) { 313226633Sdim if (X.Root) 314226633Sdim X.Root->retain(); 315226633Sdim 316226633Sdim if (Root) 317226633Sdim Root->release(); 318226633Sdim 319226633Sdim Root = X.Root; 320226633Sdim Factory = X.Factory; 321226633Sdim } 322226633Sdim return *this; 323226633Sdim } 324226633Sdim 325226633Sdim ~ImmutableMapRef() { 326226633Sdim if (Root) 327226633Sdim Root->release(); 328226633Sdim } 329226633Sdim 330226633Sdim static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { 331226633Sdim return ImmutableMapRef(0, F); 332226633Sdim } 333226633Sdim 334249423Sdim void manualRetain() { 335249423Sdim if (Root) Root->retain(); 336249423Sdim } 337249423Sdim 338249423Sdim void manualRelease() { 339249423Sdim if (Root) Root->release(); 340249423Sdim } 341249423Sdim 342249423Sdim ImmutableMapRef add(key_type_ref K, data_type_ref D) const { 343226633Sdim TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D)); 344226633Sdim return ImmutableMapRef(NewT, Factory); 345226633Sdim } 346226633Sdim 347249423Sdim ImmutableMapRef remove(key_type_ref K) const { 348226633Sdim TreeTy *NewT = Factory->remove(Root, K); 349226633Sdim return ImmutableMapRef(NewT, Factory); 350226633Sdim } 351226633Sdim 352226633Sdim bool contains(key_type_ref K) const { 353226633Sdim return Root ? Root->contains(K) : false; 354226633Sdim } 355226633Sdim 356226633Sdim ImmutableMap<KeyT, ValT> asImmutableMap() const { 357226633Sdim return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root)); 358226633Sdim } 359226633Sdim 360226633Sdim bool operator==(const ImmutableMapRef &RHS) const { 361226633Sdim return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 362226633Sdim } 363226633Sdim 364226633Sdim bool operator!=(const ImmutableMapRef &RHS) const { 365226633Sdim return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 366226633Sdim } 367226633Sdim 368226633Sdim bool isEmpty() const { return !Root; } 369226633Sdim 370226633Sdim //===--------------------------------------------------===// 371226633Sdim // For testing. 372226633Sdim //===--------------------------------------------------===// 373226633Sdim 374226633Sdim void verify() const { if (Root) Root->verify(); } 375226633Sdim 376226633Sdim //===--------------------------------------------------===// 377226633Sdim // Iterators. 378226633Sdim //===--------------------------------------------------===// 379226633Sdim 380226633Sdim class iterator { 381226633Sdim typename TreeTy::iterator itr; 382226633Sdim 383226633Sdim iterator() {} 384226633Sdim iterator(TreeTy* t) : itr(t) {} 385226633Sdim friend class ImmutableMapRef; 386226633Sdim 387226633Sdim public: 388226633Sdim value_type_ref operator*() const { return itr->getValue(); } 389226633Sdim value_type* operator->() const { return &itr->getValue(); } 390226633Sdim 391226633Sdim key_type_ref getKey() const { return itr->getValue().first; } 392226633Sdim data_type_ref getData() const { return itr->getValue().second; } 393226633Sdim 394226633Sdim 395226633Sdim iterator& operator++() { ++itr; return *this; } 396226633Sdim iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 397226633Sdim iterator& operator--() { --itr; return *this; } 398226633Sdim iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 399226633Sdim bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 400226633Sdim bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 401226633Sdim }; 402226633Sdim 403226633Sdim iterator begin() const { return iterator(Root); } 404226633Sdim iterator end() const { return iterator(); } 405226633Sdim 406226633Sdim data_type* lookup(key_type_ref K) const { 407226633Sdim if (Root) { 408226633Sdim TreeTy* T = Root->find(K); 409226633Sdim if (T) return &T->getValue().second; 410226633Sdim } 411226633Sdim 412226633Sdim return 0; 413226633Sdim } 414226633Sdim 415226633Sdim /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 416226633Sdim /// which key is the highest in the ordering of keys in the map. This 417226633Sdim /// method returns NULL if the map is empty. 418226633Sdim value_type* getMaxElement() const { 419226633Sdim return Root ? &(Root->getMaxElement()->getValue()) : 0; 420226633Sdim } 421226633Sdim 422226633Sdim //===--------------------------------------------------===// 423226633Sdim // Utility methods. 424226633Sdim //===--------------------------------------------------===// 425226633Sdim 426226633Sdim unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 427226633Sdim 428226633Sdim static inline void Profile(FoldingSetNodeID& ID, const ImmutableMapRef &M) { 429226633Sdim ID.AddPointer(M.Root); 430226633Sdim } 431226633Sdim 432226633Sdim inline void Profile(FoldingSetNodeID& ID) const { 433226633Sdim return Profile(ID, *this); 434226633Sdim } 435226633Sdim}; 436226633Sdim 437193323Sed} // end namespace llvm 438193323Sed 439193323Sed#endif 440