1 //===--- ImmutableMap.h - Immutable (functional) map interface --*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the ImmutableMap class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_IMMUTABLEMAP_H 15 #define LLVM_ADT_IMMUTABLEMAP_H 16 17 #include "llvm/ADT/ImmutableSet.h" 18 19 namespace llvm { 20 21 /// ImutKeyValueInfo -Traits class used by ImmutableMap. While both the first 22 /// and second elements in a pair are used to generate profile information, 23 /// only the first element (the key) is used by isEqual and isLess. 24 template <typename T, typename S> 25 struct ImutKeyValueInfo { 26 typedef const std::pair<T,S> value_type; 27 typedef const value_type& value_type_ref; 28 typedef const T key_type; 29 typedef const T& key_type_ref; 30 typedef const S data_type; 31 typedef const S& data_type_ref; 32 KeyOfValueImutKeyValueInfo33 static inline key_type_ref KeyOfValue(value_type_ref V) { 34 return V.first; 35 } 36 DataOfValueImutKeyValueInfo37 static inline data_type_ref DataOfValue(value_type_ref V) { 38 return V.second; 39 } 40 isEqualImutKeyValueInfo41 static inline bool isEqual(key_type_ref L, key_type_ref R) { 42 return ImutContainerInfo<T>::isEqual(L,R); 43 } isLessImutKeyValueInfo44 static inline bool isLess(key_type_ref L, key_type_ref R) { 45 return ImutContainerInfo<T>::isLess(L,R); 46 } 47 isDataEqualImutKeyValueInfo48 static inline bool isDataEqual(data_type_ref L, data_type_ref R) { 49 return ImutContainerInfo<S>::isEqual(L,R); 50 } 51 ProfileImutKeyValueInfo52 static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) { 53 ImutContainerInfo<T>::Profile(ID, V.first); 54 ImutContainerInfo<S>::Profile(ID, V.second); 55 } 56 }; 57 58 59 template <typename KeyT, typename ValT, 60 typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 61 class ImmutableMap { 62 public: 63 typedef typename ValInfo::value_type value_type; 64 typedef typename ValInfo::value_type_ref value_type_ref; 65 typedef typename ValInfo::key_type key_type; 66 typedef typename ValInfo::key_type_ref key_type_ref; 67 typedef typename ValInfo::data_type data_type; 68 typedef typename ValInfo::data_type_ref data_type_ref; 69 typedef ImutAVLTree<ValInfo> TreeTy; 70 71 protected: 72 TreeTy* Root; 73 74 public: 75 /// Constructs a map from a pointer to a tree root. In general one 76 /// should use a Factory object to create maps instead of directly 77 /// invoking the constructor, but there are cases where make this 78 /// constructor public is useful. ImmutableMap(const TreeTy * R)79 explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) { 80 if (Root) { Root->retain(); } 81 } ImmutableMap(const ImmutableMap & X)82 ImmutableMap(const ImmutableMap &X) : Root(X.Root) { 83 if (Root) { Root->retain(); } 84 } 85 ImmutableMap &operator=(const ImmutableMap &X) { 86 if (Root != X.Root) { 87 if (X.Root) { X.Root->retain(); } 88 if (Root) { Root->release(); } 89 Root = X.Root; 90 } 91 return *this; 92 } ~ImmutableMap()93 ~ImmutableMap() { 94 if (Root) { Root->release(); } 95 } 96 97 class Factory { 98 typename TreeTy::Factory F; 99 const bool Canonicalize; 100 101 public: 102 Factory(bool canonicalize = true) Canonicalize(canonicalize)103 : Canonicalize(canonicalize) {} 104 105 Factory(BumpPtrAllocator& Alloc, bool canonicalize = true) F(Alloc)106 : F(Alloc), Canonicalize(canonicalize) {} 107 getEmptyMap()108 ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } 109 add(ImmutableMap Old,key_type_ref K,data_type_ref D)110 ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { 111 TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D)); 112 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 113 } 114 remove(ImmutableMap Old,key_type_ref K)115 ImmutableMap remove(ImmutableMap Old, key_type_ref K) { 116 TreeTy *T = F.remove(Old.Root,K); 117 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 118 } 119 getTreeFactory()120 typename TreeTy::Factory *getTreeFactory() const { 121 return const_cast<typename TreeTy::Factory *>(&F); 122 } 123 124 private: 125 Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; 126 void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; 127 }; 128 contains(key_type_ref K)129 bool contains(key_type_ref K) const { 130 return Root ? Root->contains(K) : false; 131 } 132 133 bool operator==(const ImmutableMap &RHS) const { 134 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 135 } 136 137 bool operator!=(const ImmutableMap &RHS) const { 138 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 139 } 140 getRoot()141 TreeTy *getRoot() const { 142 if (Root) { Root->retain(); } 143 return Root; 144 } 145 getRootWithoutRetain()146 TreeTy *getRootWithoutRetain() const { 147 return Root; 148 } 149 manualRetain()150 void manualRetain() { 151 if (Root) Root->retain(); 152 } 153 manualRelease()154 void manualRelease() { 155 if (Root) Root->release(); 156 } 157 isEmpty()158 bool isEmpty() const { return !Root; } 159 160 //===--------------------------------------------------===// 161 // Foreach - A limited form of map iteration. 162 //===--------------------------------------------------===// 163 164 private: 165 template <typename Callback> 166 struct CBWrapper { 167 Callback C; operatorCBWrapper168 void operator()(value_type_ref V) { C(V.first,V.second); } 169 }; 170 171 template <typename Callback> 172 struct CBWrapperRef { 173 Callback &C; CBWrapperRefCBWrapperRef174 CBWrapperRef(Callback& c) : C(c) {} 175 operatorCBWrapperRef176 void operator()(value_type_ref V) { C(V.first,V.second); } 177 }; 178 179 public: 180 template <typename Callback> foreach(Callback & C)181 void foreach(Callback& C) { 182 if (Root) { 183 CBWrapperRef<Callback> CB(C); 184 Root->foreach(CB); 185 } 186 } 187 188 template <typename Callback> foreach()189 void foreach() { 190 if (Root) { 191 CBWrapper<Callback> CB; 192 Root->foreach(CB); 193 } 194 } 195 196 //===--------------------------------------------------===// 197 // For testing. 198 //===--------------------------------------------------===// 199 verify()200 void verify() const { if (Root) Root->verify(); } 201 202 //===--------------------------------------------------===// 203 // Iterators. 204 //===--------------------------------------------------===// 205 206 class iterator { 207 typename TreeTy::iterator itr; 208 iterator()209 iterator() {} iterator(TreeTy * t)210 iterator(TreeTy* t) : itr(t) {} 211 friend class ImmutableMap; 212 213 public: 214 typedef ptrdiff_t difference_type; 215 typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type value_type; 216 typedef typename ImmutableMap<KeyT,ValT,ValInfo>::value_type_ref reference; 217 typedef typename iterator::value_type *pointer; 218 typedef std::bidirectional_iterator_tag iterator_category; 219 220 typename iterator::reference operator*() const { return itr->getValue(); } 221 typename iterator::pointer operator->() const { return &itr->getValue(); } 222 getKey()223 key_type_ref getKey() const { return itr->getValue().first; } getData()224 data_type_ref getData() const { return itr->getValue().second; } 225 226 iterator& operator++() { ++itr; return *this; } 227 iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 228 iterator& operator--() { --itr; return *this; } 229 iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 230 231 bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 232 bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 233 }; 234 begin()235 iterator begin() const { return iterator(Root); } end()236 iterator end() const { return iterator(); } 237 lookup(key_type_ref K)238 data_type* lookup(key_type_ref K) const { 239 if (Root) { 240 TreeTy* T = Root->find(K); 241 if (T) return &T->getValue().second; 242 } 243 244 return nullptr; 245 } 246 247 /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 248 /// which key is the highest in the ordering of keys in the map. This 249 /// method returns NULL if the map is empty. getMaxElement()250 value_type* getMaxElement() const { 251 return Root ? &(Root->getMaxElement()->getValue()) : nullptr; 252 } 253 254 //===--------------------------------------------------===// 255 // Utility methods. 256 //===--------------------------------------------------===// 257 getHeight()258 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 259 Profile(FoldingSetNodeID & ID,const ImmutableMap & M)260 static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 261 ID.AddPointer(M.Root); 262 } 263 Profile(FoldingSetNodeID & ID)264 inline void Profile(FoldingSetNodeID& ID) const { 265 return Profile(ID,*this); 266 } 267 }; 268 269 // NOTE: This will possibly become the new implementation of ImmutableMap some day. 270 template <typename KeyT, typename ValT, 271 typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 272 class ImmutableMapRef { 273 public: 274 typedef typename ValInfo::value_type value_type; 275 typedef typename ValInfo::value_type_ref value_type_ref; 276 typedef typename ValInfo::key_type key_type; 277 typedef typename ValInfo::key_type_ref key_type_ref; 278 typedef typename ValInfo::data_type data_type; 279 typedef typename ValInfo::data_type_ref data_type_ref; 280 typedef ImutAVLTree<ValInfo> TreeTy; 281 typedef typename TreeTy::Factory FactoryTy; 282 283 protected: 284 TreeTy *Root; 285 FactoryTy *Factory; 286 287 public: 288 /// Constructs a map from a pointer to a tree root. In general one 289 /// should use a Factory object to create maps instead of directly 290 /// invoking the constructor, but there are cases where make this 291 /// constructor public is useful. ImmutableMapRef(const TreeTy * R,FactoryTy * F)292 explicit ImmutableMapRef(const TreeTy* R, FactoryTy *F) 293 : Root(const_cast<TreeTy*>(R)), 294 Factory(F) { 295 if (Root) { Root->retain(); } 296 } 297 ImmutableMapRef(const ImmutableMap<KeyT,ValT> & X,typename ImmutableMap<KeyT,ValT>::Factory & F)298 explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X, 299 typename ImmutableMap<KeyT, ValT>::Factory &F) 300 : Root(X.getRootWithoutRetain()), 301 Factory(F.getTreeFactory()) { 302 if (Root) { Root->retain(); } 303 } 304 ImmutableMapRef(const ImmutableMapRef & X)305 ImmutableMapRef(const ImmutableMapRef &X) 306 : Root(X.Root), 307 Factory(X.Factory) { 308 if (Root) { Root->retain(); } 309 } 310 311 ImmutableMapRef &operator=(const ImmutableMapRef &X) { 312 if (Root != X.Root) { 313 if (X.Root) 314 X.Root->retain(); 315 316 if (Root) 317 Root->release(); 318 319 Root = X.Root; 320 Factory = X.Factory; 321 } 322 return *this; 323 } 324 ~ImmutableMapRef()325 ~ImmutableMapRef() { 326 if (Root) 327 Root->release(); 328 } 329 getEmptyMap(FactoryTy * F)330 static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { 331 return ImmutableMapRef(0, F); 332 } 333 manualRetain()334 void manualRetain() { 335 if (Root) Root->retain(); 336 } 337 manualRelease()338 void manualRelease() { 339 if (Root) Root->release(); 340 } 341 add(key_type_ref K,data_type_ref D)342 ImmutableMapRef add(key_type_ref K, data_type_ref D) const { 343 TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D)); 344 return ImmutableMapRef(NewT, Factory); 345 } 346 remove(key_type_ref K)347 ImmutableMapRef remove(key_type_ref K) const { 348 TreeTy *NewT = Factory->remove(Root, K); 349 return ImmutableMapRef(NewT, Factory); 350 } 351 contains(key_type_ref K)352 bool contains(key_type_ref K) const { 353 return Root ? Root->contains(K) : false; 354 } 355 asImmutableMap()356 ImmutableMap<KeyT, ValT> asImmutableMap() const { 357 return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root)); 358 } 359 360 bool operator==(const ImmutableMapRef &RHS) const { 361 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 362 } 363 364 bool operator!=(const ImmutableMapRef &RHS) const { 365 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 366 } 367 isEmpty()368 bool isEmpty() const { return !Root; } 369 370 //===--------------------------------------------------===// 371 // For testing. 372 //===--------------------------------------------------===// 373 verify()374 void verify() const { if (Root) Root->verify(); } 375 376 //===--------------------------------------------------===// 377 // Iterators. 378 //===--------------------------------------------------===// 379 380 class iterator { 381 typename TreeTy::iterator itr; 382 iterator()383 iterator() {} iterator(TreeTy * t)384 iterator(TreeTy* t) : itr(t) {} 385 friend class ImmutableMapRef; 386 387 public: 388 value_type_ref operator*() const { return itr->getValue(); } 389 value_type* operator->() const { return &itr->getValue(); } 390 getKey()391 key_type_ref getKey() const { return itr->getValue().first; } getData()392 data_type_ref getData() const { return itr->getValue().second; } 393 394 395 iterator& operator++() { ++itr; return *this; } 396 iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } 397 iterator& operator--() { --itr; return *this; } 398 iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } 399 bool operator==(const iterator& RHS) const { return RHS.itr == itr; } 400 bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } 401 }; 402 begin()403 iterator begin() const { return iterator(Root); } end()404 iterator end() const { return iterator(); } 405 lookup(key_type_ref K)406 data_type* lookup(key_type_ref K) const { 407 if (Root) { 408 TreeTy* T = Root->find(K); 409 if (T) return &T->getValue().second; 410 } 411 412 return 0; 413 } 414 415 /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 416 /// which key is the highest in the ordering of keys in the map. This 417 /// method returns NULL if the map is empty. getMaxElement()418 value_type* getMaxElement() const { 419 return Root ? &(Root->getMaxElement()->getValue()) : 0; 420 } 421 422 //===--------------------------------------------------===// 423 // Utility methods. 424 //===--------------------------------------------------===// 425 getHeight()426 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 427 Profile(FoldingSetNodeID & ID,const ImmutableMapRef & M)428 static inline void Profile(FoldingSetNodeID& ID, const ImmutableMapRef &M) { 429 ID.AddPointer(M.Root); 430 } 431 Profile(FoldingSetNodeID & ID)432 inline void Profile(FoldingSetNodeID& ID) const { 433 return Profile(ID, *this); 434 } 435 }; 436 437 } // end namespace llvm 438 439 #endif 440