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