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 template <typename KeyT, typename ValT, 59 typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 60 class ImmutableMap { 61 public: 62 typedef typename ValInfo::value_type value_type; 63 typedef typename ValInfo::value_type_ref value_type_ref; 64 typedef typename ValInfo::key_type key_type; 65 typedef typename ValInfo::key_type_ref key_type_ref; 66 typedef typename ValInfo::data_type data_type; 67 typedef typename ValInfo::data_type_ref data_type_ref; 68 typedef ImutAVLTree<ValInfo> TreeTy; 69 70 protected: 71 TreeTy* Root; 72 73 public: 74 /// Constructs a map from a pointer to a tree root. In general one 75 /// should use a Factory object to create maps instead of directly 76 /// invoking the constructor, but there are cases where make this 77 /// constructor public is useful. ImmutableMap(const TreeTy * R)78 explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) { 79 if (Root) { Root->retain(); } 80 } 81 ImmutableMap(const ImmutableMap & X)82 ImmutableMap(const ImmutableMap &X) : Root(X.Root) { 83 if (Root) { Root->retain(); } 84 } 85 86 ImmutableMap &operator=(const ImmutableMap &X) { 87 if (Root != X.Root) { 88 if (X.Root) { X.Root->retain(); } 89 if (Root) { Root->release(); } 90 Root = X.Root; 91 } 92 return *this; 93 } 94 ~ImmutableMap()95 ~ImmutableMap() { 96 if (Root) { Root->release(); } 97 } 98 99 class Factory { 100 typename TreeTy::Factory F; 101 const bool Canonicalize; 102 103 public: Canonicalize(canonicalize)104 Factory(bool canonicalize = true) : Canonicalize(canonicalize) {} 105 106 Factory(BumpPtrAllocator &Alloc, bool canonicalize = true) F(Alloc)107 : F(Alloc), Canonicalize(canonicalize) {} 108 getEmptyMap()109 ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } 110 add(ImmutableMap Old,key_type_ref K,data_type_ref D)111 ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { 112 TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D)); 113 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 114 } 115 remove(ImmutableMap Old,key_type_ref K)116 ImmutableMap remove(ImmutableMap Old, key_type_ref K) { 117 TreeTy *T = F.remove(Old.Root,K); 118 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 119 } 120 getTreeFactory()121 typename TreeTy::Factory *getTreeFactory() const { 122 return const_cast<typename TreeTy::Factory *>(&F); 123 } 124 125 private: 126 Factory(const Factory& RHS) = delete; 127 void operator=(const Factory& RHS) = delete; 128 }; 129 contains(key_type_ref K)130 bool contains(key_type_ref K) const { 131 return Root ? Root->contains(K) : false; 132 } 133 134 bool operator==(const ImmutableMap &RHS) const { 135 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 136 } 137 138 bool operator!=(const ImmutableMap &RHS) const { 139 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 140 } 141 getRoot()142 TreeTy *getRoot() const { 143 if (Root) { Root->retain(); } 144 return Root; 145 } 146 getRootWithoutRetain()147 TreeTy *getRootWithoutRetain() const { return Root; } 148 manualRetain()149 void manualRetain() { 150 if (Root) Root->retain(); 151 } 152 manualRelease()153 void manualRelease() { 154 if (Root) Root->release(); 155 } 156 isEmpty()157 bool isEmpty() const { return !Root; } 158 159 //===--------------------------------------------------===// 160 // Foreach - A limited form of map iteration. 161 //===--------------------------------------------------===// 162 163 private: 164 template <typename Callback> 165 struct CBWrapper { 166 Callback C; operatorCBWrapper167 void operator()(value_type_ref V) { C(V.first,V.second); } 168 }; 169 170 template <typename Callback> 171 struct CBWrapperRef { 172 Callback &C; CBWrapperRefCBWrapperRef173 CBWrapperRef(Callback& c) : C(c) {} 174 operatorCBWrapperRef175 void operator()(value_type_ref V) { C(V.first,V.second); } 176 }; 177 178 public: 179 template <typename Callback> foreach(Callback & C)180 void foreach(Callback& C) { 181 if (Root) { 182 CBWrapperRef<Callback> CB(C); 183 Root->foreach(CB); 184 } 185 } 186 187 template <typename Callback> foreach()188 void foreach() { 189 if (Root) { 190 CBWrapper<Callback> CB; 191 Root->foreach(CB); 192 } 193 } 194 195 //===--------------------------------------------------===// 196 // For testing. 197 //===--------------------------------------------------===// 198 verify()199 void verify() const { if (Root) Root->verify(); } 200 201 //===--------------------------------------------------===// 202 // Iterators. 203 //===--------------------------------------------------===// 204 205 class iterator : public ImutAVLValueIterator<ImmutableMap> { 206 iterator() = default; iterator(TreeTy * Tree)207 explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} 208 friend class ImmutableMap; 209 210 public: getKey()211 key_type_ref getKey() const { return (*this)->first; } getData()212 data_type_ref getData() const { return (*this)->second; } 213 }; 214 begin()215 iterator begin() const { return iterator(Root); } end()216 iterator end() const { return iterator(); } 217 lookup(key_type_ref K)218 data_type* lookup(key_type_ref K) const { 219 if (Root) { 220 TreeTy* T = Root->find(K); 221 if (T) return &T->getValue().second; 222 } 223 224 return nullptr; 225 } 226 227 /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 228 /// which key is the highest in the ordering of keys in the map. This 229 /// method returns NULL if the map is empty. getMaxElement()230 value_type* getMaxElement() const { 231 return Root ? &(Root->getMaxElement()->getValue()) : nullptr; 232 } 233 234 //===--------------------------------------------------===// 235 // Utility methods. 236 //===--------------------------------------------------===// 237 getHeight()238 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 239 Profile(FoldingSetNodeID & ID,const ImmutableMap & M)240 static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 241 ID.AddPointer(M.Root); 242 } 243 Profile(FoldingSetNodeID & ID)244 inline void Profile(FoldingSetNodeID& ID) const { 245 return Profile(ID,*this); 246 } 247 }; 248 249 // NOTE: This will possibly become the new implementation of ImmutableMap some day. 250 template <typename KeyT, typename ValT, 251 typename ValInfo = ImutKeyValueInfo<KeyT,ValT> > 252 class ImmutableMapRef { 253 public: 254 typedef typename ValInfo::value_type value_type; 255 typedef typename ValInfo::value_type_ref value_type_ref; 256 typedef typename ValInfo::key_type key_type; 257 typedef typename ValInfo::key_type_ref key_type_ref; 258 typedef typename ValInfo::data_type data_type; 259 typedef typename ValInfo::data_type_ref data_type_ref; 260 typedef ImutAVLTree<ValInfo> TreeTy; 261 typedef typename TreeTy::Factory FactoryTy; 262 263 protected: 264 TreeTy *Root; 265 FactoryTy *Factory; 266 267 public: 268 /// Constructs a map from a pointer to a tree root. In general one 269 /// should use a Factory object to create maps instead of directly 270 /// invoking the constructor, but there are cases where make this 271 /// constructor public is useful. ImmutableMapRef(const TreeTy * R,FactoryTy * F)272 explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F) 273 : Root(const_cast<TreeTy *>(R)), Factory(F) { 274 if (Root) { 275 Root->retain(); 276 } 277 } 278 ImmutableMapRef(const ImmutableMap<KeyT,ValT> & X,typename ImmutableMap<KeyT,ValT>::Factory & F)279 explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X, 280 typename ImmutableMap<KeyT, ValT>::Factory &F) 281 : Root(X.getRootWithoutRetain()), 282 Factory(F.getTreeFactory()) { 283 if (Root) { Root->retain(); } 284 } 285 ImmutableMapRef(const ImmutableMapRef & X)286 ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) { 287 if (Root) { 288 Root->retain(); 289 } 290 } 291 292 ImmutableMapRef &operator=(const ImmutableMapRef &X) { 293 if (Root != X.Root) { 294 if (X.Root) 295 X.Root->retain(); 296 297 if (Root) 298 Root->release(); 299 300 Root = X.Root; 301 Factory = X.Factory; 302 } 303 return *this; 304 } 305 ~ImmutableMapRef()306 ~ImmutableMapRef() { 307 if (Root) 308 Root->release(); 309 } 310 getEmptyMap(FactoryTy * F)311 static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { 312 return ImmutableMapRef(0, F); 313 } 314 manualRetain()315 void manualRetain() { 316 if (Root) Root->retain(); 317 } 318 manualRelease()319 void manualRelease() { 320 if (Root) Root->release(); 321 } 322 add(key_type_ref K,data_type_ref D)323 ImmutableMapRef add(key_type_ref K, data_type_ref D) const { 324 TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D)); 325 return ImmutableMapRef(NewT, Factory); 326 } 327 remove(key_type_ref K)328 ImmutableMapRef remove(key_type_ref K) const { 329 TreeTy *NewT = Factory->remove(Root, K); 330 return ImmutableMapRef(NewT, Factory); 331 } 332 contains(key_type_ref K)333 bool contains(key_type_ref K) const { 334 return Root ? Root->contains(K) : false; 335 } 336 asImmutableMap()337 ImmutableMap<KeyT, ValT> asImmutableMap() const { 338 return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root)); 339 } 340 341 bool operator==(const ImmutableMapRef &RHS) const { 342 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; 343 } 344 345 bool operator!=(const ImmutableMapRef &RHS) const { 346 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; 347 } 348 isEmpty()349 bool isEmpty() const { return !Root; } 350 351 //===--------------------------------------------------===// 352 // For testing. 353 //===--------------------------------------------------===// 354 verify()355 void verify() const { 356 if (Root) 357 Root->verify(); 358 } 359 360 //===--------------------------------------------------===// 361 // Iterators. 362 //===--------------------------------------------------===// 363 364 class iterator : public ImutAVLValueIterator<ImmutableMapRef> { 365 iterator() = default; iterator(TreeTy * Tree)366 explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} 367 friend class ImmutableMapRef; 368 369 public: getKey()370 key_type_ref getKey() const { return (*this)->first; } getData()371 data_type_ref getData() const { return (*this)->second; } 372 }; 373 begin()374 iterator begin() const { return iterator(Root); } end()375 iterator end() const { return iterator(); } 376 lookup(key_type_ref K)377 data_type *lookup(key_type_ref K) const { 378 if (Root) { 379 TreeTy* T = Root->find(K); 380 if (T) return &T->getValue().second; 381 } 382 383 return nullptr; 384 } 385 386 /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 387 /// which key is the highest in the ordering of keys in the map. This 388 /// method returns NULL if the map is empty. getMaxElement()389 value_type* getMaxElement() const { 390 return Root ? &(Root->getMaxElement()->getValue()) : 0; 391 } 392 393 //===--------------------------------------------------===// 394 // Utility methods. 395 //===--------------------------------------------------===// 396 getHeight()397 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 398 Profile(FoldingSetNodeID & ID,const ImmutableMapRef & M)399 static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) { 400 ID.AddPointer(M.Root); 401 } 402 Profile(FoldingSetNodeID & ID)403 inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } 404 }; 405 406 } // end namespace llvm 407 408 #endif // LLVM_ADT_IMMUTABLEMAP_H 409