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
21namespace 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.
26template <typename T, typename S>
27struct 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
60template <typename KeyT, typename ValT,
61 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
62class ImmutableMap {
63public:
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
72protected:
73 IntrusiveRefCntPtr<TreeTy> Root;
74
75public:
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
82 class Factory {
83 typename TreeTy::Factory F;
84 const bool Canonicalize;
85
86 public:
87 Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
88
89 Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
90 : F(Alloc), Canonicalize(canonicalize) {}
91
92 Factory(const Factory &) = delete;
93 Factory &operator=(const Factory &) = delete;
94
95 ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
96
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
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
108 typename TreeTy::Factory *getTreeFactory() const {
109 return const_cast<typename TreeTy::Factory *>(&F);
110 }
111 };
112
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
126 TreeTy *getRoot() const {
127 if (Root) { Root->retain(); }
128 return Root.get();
129 }
130
131 TreeTy *getRootWithoutRetain() const { return Root.get(); }
132
133 void manualRetain() {
134 if (Root) Root->retain();
135 }
136
137 void manualRelease() {
138 if (Root) Root->release();
139 }
140
141 bool isEmpty() const { return !Root; }
142
143 //===--------------------------------------------------===//
144 // Foreach - A limited form of map iteration.
145 //===--------------------------------------------------===//
146
147private:
148 template <typename Callback>
149 struct CBWrapper {
150 Callback C;
151
152 void operator()(value_type_ref V) { C(V.first,V.second); }
153 };
154
155 template <typename Callback>
156 struct CBWrapperRef {
157 Callback &C;
158
159 CBWrapperRef(Callback& c) : C(c) {}
160
161 void operator()(value_type_ref V) { C(V.first,V.second); }
162 };
163
164public:
165 template <typename Callback>
166 void foreach(Callback& C) {
167 if (Root) {
168 CBWrapperRef<Callback> CB(C);
169 Root->foreach(CB);
170 }
171 }
172
173 template <typename Callback>
174 void foreach() {
175 if (Root) {
176 CBWrapper<Callback> CB;
177 Root->foreach(CB);
178 }
179 }
180
181 //===--------------------------------------------------===//
182 // For testing.
183 //===--------------------------------------------------===//
184
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;
195 explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
196
197 public:
198 key_type_ref getKey() const { return (*this)->first; }
199 data_type_ref getData() const { return (*this)->second; }
200 };
201
202 iterator begin() const { return iterator(Root.get()); }
203 iterator end() const { return iterator(); }
204
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.
217 value_type* getMaxElement() const {
218 return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
219 }
220
221 //===--------------------------------------------------===//
222 // Utility methods.
223 //===--------------------------------------------------===//
224
225 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
226
227 static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
228 ID.AddPointer(M.Root.get());
229 }
230
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.
237template <typename KeyT, typename ValT,
238typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
239class ImmutableMapRef {
240public:
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
250protected:
251 IntrusiveRefCntPtr<TreeTy> Root;
252 FactoryTy *Factory;
253
254public:
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.
259 ImmutableMapRef(const TreeTy *R, FactoryTy *F)
260 : Root(const_cast<TreeTy *>(R)), Factory(F) {}
261
262 ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
263 typename ImmutableMap<KeyT, ValT>::Factory &F)
264 : Root(X.getRootWithoutRetain()), Factory(F.getTreeFactory()) {}
265
266 static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
267 return ImmutableMapRef(0, F);
268 }
269
270 void manualRetain() {
271 if (Root) Root->retain();
272 }
273
274 void manualRelease() {
275 if (Root) Root->release();
276 }
277
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
284 ImmutableMapRef remove(key_type_ref K) const {
285 TreeTy *NewT = Factory->remove(Root.get(), K);
286 return ImmutableMapRef(NewT, Factory);
287 }
288
289 bool contains(key_type_ref K) const {
290 return Root ? Root->contains(K) : false;
291 }
292
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
306 bool isEmpty() const { return !Root; }
307
308 //===--------------------------------------------------===//
309 // For testing.
310 //===--------------------------------------------------===//
311
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;
325 explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
326
327 public:
328 key_type_ref getKey() const { return (*this)->first; }
329 data_type_ref getData() const { return (*this)->second; }
330 };
331
332 iterator begin() const { return iterator(Root.get()); }
333 iterator end() const { return iterator(); }
334
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.
347 value_type* getMaxElement() const {
348 return Root ? &(Root->getMaxElement()->getValue()) : 0;
349 }
350
351 //===--------------------------------------------------===//
352 // Utility methods.
353 //===--------------------------------------------------===//
354
355 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
356
357 static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
358 ID.AddPointer(M.Root.get());
359 }
360
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