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