1 //===--- ImmutableMap.h - Immutable (functional) map interface --*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the ImmutableMap class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ADT_IMMUTABLEMAP_H 14 #define LLVM_ADT_IMMUTABLEMAP_H 15 16 #include "llvm/ADT/FoldingSet.h" 17 #include "llvm/ADT/ImmutableSet.h" 18 #include "llvm/Support/Allocator.h" 19 #include <utility> 20 21 namespace llvm { 22 23 /// ImutKeyValueInfo -Traits class used by ImmutableMap. While both the first 24 /// and second elements in a pair are used to generate profile information, 25 /// only the first element (the key) is used by isEqual and isLess. 26 template <typename T, typename S> 27 struct ImutKeyValueInfo { 28 using value_type = const std::pair<T,S>; 29 using value_type_ref = const value_type&; 30 using key_type = const T; 31 using key_type_ref = const T&; 32 using data_type = const S; 33 using data_type_ref = const S&; 34 KeyOfValueImutKeyValueInfo35 static inline key_type_ref KeyOfValue(value_type_ref V) { 36 return V.first; 37 } 38 DataOfValueImutKeyValueInfo39 static inline data_type_ref DataOfValue(value_type_ref V) { 40 return V.second; 41 } 42 isEqualImutKeyValueInfo43 static inline bool isEqual(key_type_ref L, key_type_ref R) { 44 return ImutContainerInfo<T>::isEqual(L,R); 45 } isLessImutKeyValueInfo46 static inline bool isLess(key_type_ref L, key_type_ref R) { 47 return ImutContainerInfo<T>::isLess(L,R); 48 } 49 isDataEqualImutKeyValueInfo50 static inline bool isDataEqual(data_type_ref L, data_type_ref R) { 51 return ImutContainerInfo<S>::isEqual(L,R); 52 } 53 ProfileImutKeyValueInfo54 static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) { 55 ImutContainerInfo<T>::Profile(ID, V.first); 56 ImutContainerInfo<S>::Profile(ID, V.second); 57 } 58 }; 59 60 template <typename KeyT, typename ValT, 61 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>> 62 class ImmutableMap { 63 public: 64 using value_type = typename ValInfo::value_type; 65 using value_type_ref = typename ValInfo::value_type_ref; 66 using key_type = typename ValInfo::key_type; 67 using key_type_ref = typename ValInfo::key_type_ref; 68 using data_type = typename ValInfo::data_type; 69 using data_type_ref = typename ValInfo::data_type_ref; 70 using TreeTy = ImutAVLTree<ValInfo>; 71 72 protected: 73 IntrusiveRefCntPtr<TreeTy> Root; 74 75 public: 76 /// Constructs a map from a pointer to a tree root. In general one 77 /// should use a Factory object to create maps instead of directly 78 /// invoking the constructor, but there are cases where make this 79 /// constructor public is useful. ImmutableMap(const TreeTy * R)80 explicit ImmutableMap(const TreeTy *R) : Root(const_cast<TreeTy *>(R)) {} 81 82 class Factory { 83 typename TreeTy::Factory F; 84 const bool Canonicalize; 85 86 public: Canonicalize(canonicalize)87 Factory(bool canonicalize = true) : Canonicalize(canonicalize) {} 88 89 Factory(BumpPtrAllocator &Alloc, bool canonicalize = true) F(Alloc)90 : F(Alloc), Canonicalize(canonicalize) {} 91 92 Factory(const Factory &) = delete; 93 Factory &operator=(const Factory &) = delete; 94 getEmptyMap()95 ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } 96 add(ImmutableMap Old,key_type_ref K,data_type_ref D)97 LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K, 98 data_type_ref D) { 99 TreeTy *T = F.add(Old.Root.get(), std::pair<key_type, data_type>(K, D)); 100 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 101 } 102 remove(ImmutableMap Old,key_type_ref K)103 LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K) { 104 TreeTy *T = F.remove(Old.Root.get(), K); 105 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); 106 } 107 getTreeFactory()108 typename TreeTy::Factory *getTreeFactory() const { 109 return const_cast<typename TreeTy::Factory *>(&F); 110 } 111 }; 112 contains(key_type_ref K)113 bool contains(key_type_ref K) const { 114 return Root ? Root->contains(K) : false; 115 } 116 117 bool operator==(const ImmutableMap &RHS) const { 118 return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root; 119 } 120 121 bool operator!=(const ImmutableMap &RHS) const { 122 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get()) 123 : Root != RHS.Root; 124 } 125 getRoot()126 TreeTy *getRoot() const { 127 if (Root) { Root->retain(); } 128 return Root.get(); 129 } 130 getRootWithoutRetain()131 TreeTy *getRootWithoutRetain() const { return Root.get(); } 132 manualRetain()133 void manualRetain() { 134 if (Root) Root->retain(); 135 } 136 manualRelease()137 void manualRelease() { 138 if (Root) Root->release(); 139 } 140 isEmpty()141 bool isEmpty() const { return !Root; } 142 143 //===--------------------------------------------------===// 144 // Foreach - A limited form of map iteration. 145 //===--------------------------------------------------===// 146 147 private: 148 template <typename Callback> 149 struct CBWrapper { 150 Callback C; 151 operatorCBWrapper152 void operator()(value_type_ref V) { C(V.first,V.second); } 153 }; 154 155 template <typename Callback> 156 struct CBWrapperRef { 157 Callback &C; 158 CBWrapperRefCBWrapperRef159 CBWrapperRef(Callback& c) : C(c) {} 160 operatorCBWrapperRef161 void operator()(value_type_ref V) { C(V.first,V.second); } 162 }; 163 164 public: 165 template <typename Callback> foreach(Callback & C)166 void foreach(Callback& C) { 167 if (Root) { 168 CBWrapperRef<Callback> CB(C); 169 Root->foreach(CB); 170 } 171 } 172 173 template <typename Callback> foreach()174 void foreach() { 175 if (Root) { 176 CBWrapper<Callback> CB; 177 Root->foreach(CB); 178 } 179 } 180 181 //===--------------------------------------------------===// 182 // For testing. 183 //===--------------------------------------------------===// 184 verify()185 void verify() const { if (Root) Root->verify(); } 186 187 //===--------------------------------------------------===// 188 // Iterators. 189 //===--------------------------------------------------===// 190 191 class iterator : public ImutAVLValueIterator<ImmutableMap> { 192 friend class ImmutableMap; 193 194 iterator() = default; iterator(TreeTy * Tree)195 explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} 196 197 public: getKey()198 key_type_ref getKey() const { return (*this)->first; } getData()199 data_type_ref getData() const { return (*this)->second; } 200 }; 201 begin()202 iterator begin() const { return iterator(Root.get()); } end()203 iterator end() const { return iterator(); } 204 lookup(key_type_ref K)205 data_type* lookup(key_type_ref K) const { 206 if (Root) { 207 TreeTy* T = Root->find(K); 208 if (T) return &T->getValue().second; 209 } 210 211 return nullptr; 212 } 213 214 /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 215 /// which key is the highest in the ordering of keys in the map. This 216 /// method returns NULL if the map is empty. getMaxElement()217 value_type* getMaxElement() const { 218 return Root ? &(Root->getMaxElement()->getValue()) : nullptr; 219 } 220 221 //===--------------------------------------------------===// 222 // Utility methods. 223 //===--------------------------------------------------===// 224 getHeight()225 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 226 Profile(FoldingSetNodeID & ID,const ImmutableMap & M)227 static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { 228 ID.AddPointer(M.Root.get()); 229 } 230 Profile(FoldingSetNodeID & ID)231 inline void Profile(FoldingSetNodeID& ID) const { 232 return Profile(ID,*this); 233 } 234 }; 235 236 // NOTE: This will possibly become the new implementation of ImmutableMap some day. 237 template <typename KeyT, typename ValT, 238 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>> 239 class ImmutableMapRef { 240 public: 241 using value_type = typename ValInfo::value_type; 242 using value_type_ref = typename ValInfo::value_type_ref; 243 using key_type = typename ValInfo::key_type; 244 using key_type_ref = typename ValInfo::key_type_ref; 245 using data_type = typename ValInfo::data_type; 246 using data_type_ref = typename ValInfo::data_type_ref; 247 using TreeTy = ImutAVLTree<ValInfo>; 248 using FactoryTy = typename TreeTy::Factory; 249 250 protected: 251 IntrusiveRefCntPtr<TreeTy> Root; 252 FactoryTy *Factory; 253 254 public: 255 /// Constructs a map from a pointer to a tree root. In general one 256 /// should use a Factory object to create maps instead of directly 257 /// invoking the constructor, but there are cases where make this 258 /// constructor public is useful. ImmutableMapRef(const TreeTy * R,FactoryTy * F)259 ImmutableMapRef(const TreeTy *R, FactoryTy *F) 260 : Root(const_cast<TreeTy *>(R)), Factory(F) {} 261 ImmutableMapRef(const ImmutableMap<KeyT,ValT> & X,typename ImmutableMap<KeyT,ValT>::Factory & F)262 ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X, 263 typename ImmutableMap<KeyT, ValT>::Factory &F) 264 : Root(X.getRootWithoutRetain()), Factory(F.getTreeFactory()) {} 265 getEmptyMap(FactoryTy * F)266 static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { 267 return ImmutableMapRef(0, F); 268 } 269 manualRetain()270 void manualRetain() { 271 if (Root) Root->retain(); 272 } 273 manualRelease()274 void manualRelease() { 275 if (Root) Root->release(); 276 } 277 add(key_type_ref K,data_type_ref D)278 ImmutableMapRef add(key_type_ref K, data_type_ref D) const { 279 TreeTy *NewT = 280 Factory->add(Root.get(), std::pair<key_type, data_type>(K, D)); 281 return ImmutableMapRef(NewT, Factory); 282 } 283 remove(key_type_ref K)284 ImmutableMapRef remove(key_type_ref K) const { 285 TreeTy *NewT = Factory->remove(Root.get(), K); 286 return ImmutableMapRef(NewT, Factory); 287 } 288 contains(key_type_ref K)289 bool contains(key_type_ref K) const { 290 return Root ? Root->contains(K) : false; 291 } 292 asImmutableMap()293 ImmutableMap<KeyT, ValT> asImmutableMap() const { 294 return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root.get())); 295 } 296 297 bool operator==(const ImmutableMapRef &RHS) const { 298 return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root; 299 } 300 301 bool operator!=(const ImmutableMapRef &RHS) const { 302 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get()) 303 : Root != RHS.Root; 304 } 305 isEmpty()306 bool isEmpty() const { return !Root; } 307 308 //===--------------------------------------------------===// 309 // For testing. 310 //===--------------------------------------------------===// 311 verify()312 void verify() const { 313 if (Root) 314 Root->verify(); 315 } 316 317 //===--------------------------------------------------===// 318 // Iterators. 319 //===--------------------------------------------------===// 320 321 class iterator : public ImutAVLValueIterator<ImmutableMapRef> { 322 friend class ImmutableMapRef; 323 324 iterator() = default; iterator(TreeTy * Tree)325 explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} 326 327 public: getKey()328 key_type_ref getKey() const { return (*this)->first; } getData()329 data_type_ref getData() const { return (*this)->second; } 330 }; 331 begin()332 iterator begin() const { return iterator(Root.get()); } end()333 iterator end() const { return iterator(); } 334 lookup(key_type_ref K)335 data_type *lookup(key_type_ref K) const { 336 if (Root) { 337 TreeTy* T = Root->find(K); 338 if (T) return &T->getValue().second; 339 } 340 341 return nullptr; 342 } 343 344 /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for 345 /// which key is the highest in the ordering of keys in the map. This 346 /// method returns NULL if the map is empty. getMaxElement()347 value_type* getMaxElement() const { 348 return Root ? &(Root->getMaxElement()->getValue()) : 0; 349 } 350 351 //===--------------------------------------------------===// 352 // Utility methods. 353 //===--------------------------------------------------===// 354 getHeight()355 unsigned getHeight() const { return Root ? Root->getHeight() : 0; } 356 Profile(FoldingSetNodeID & ID,const ImmutableMapRef & M)357 static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) { 358 ID.AddPointer(M.Root.get()); 359 } 360 Profile(FoldingSetNodeID & ID)361 inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } 362 }; 363 364 } // end namespace llvm 365 366 #endif // LLVM_ADT_IMMUTABLEMAP_H 367