Line data Source code
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/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 0 : static inline bool isEqual(key_type_ref L, key_type_ref R) {
45 0 : return ImutContainerInfo<T>::isEqual(L,R);
46 : }
47 0 : static inline bool isLess(key_type_ref L, key_type_ref R) {
48 0 : return ImutContainerInfo<T>::isLess(L,R);
49 : }
50 0 :
51 0 : static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
52 0 : return ImutContainerInfo<S>::isEqual(L,R);
53 0 : }
54 0 :
55 4066116 : static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
56 11098966 : ImutContainerInfo<T>::Profile(ID, V.first);
57 10571771 : ImutContainerInfo<S>::Profile(ID, V.second);
58 4066116 : }
59 0 : };
60 0 :
61 : template <typename KeyT, typename ValT,
62 0 : typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
63 0 : class ImmutableMap {
64 0 : public:
65 0 : using value_type = typename ValInfo::value_type;
66 0 : using value_type_ref = typename ValInfo::value_type_ref;
67 4949 : using key_type = typename ValInfo::key_type;
68 13043 : using key_type_ref = typename ValInfo::key_type_ref;
69 8062 : using data_type = typename ValInfo::data_type;
70 4949 : using data_type_ref = typename ValInfo::data_type_ref;
71 0 : using TreeTy = ImutAVLTree<ValInfo>;
72 0 :
73 590 : protected:
74 4244 : TreeTy* Root;
75 9142 :
76 5539 : public:
77 480 : /// Constructs a map from a pointer to a tree root. In general one
78 5429 : /// should use a Factory object to create maps instead of directly
79 1069 : /// invoking the constructor, but there are cases where make this
80 6588 : /// constructor public is useful.
81 8584317 : explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
82 2130199 : if (Root) { Root->retain(); }
83 0 : }
84 110 :
85 10486326 : ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
86 101237582 : if (Root) { Root->retain(); }
87 0 : }
88 0 :
89 167759038 : ~ImmutableMap() {
90 167759030 : if (Root) { Root->release(); }
91 167759024 : }
92 1053439 :
93 1065663 : ImmutableMap &operator=(const ImmutableMap &X) {
94 1108496 : if (Root != X.Root) {
95 2147533 : if (X.Root) { X.Root->retain(); }
96 2147533 : if (Root) { Root->release(); }
97 2150575 : Root = X.Root;
98 2201 : }
99 0 : return *this;
100 0 : }
101 166774 :
102 113811 : class Factory {
103 90268 : typename TreeTy::Factory F;
104 88586 : const bool Canonicalize;
105 105086 :
106 110813 : public:
107 4007158 : Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
108 161903 :
109 111000 : Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
110 109318 : : F(Alloc), Canonicalize(canonicalize) {}
111 129844 :
112 86332 : Factory(const Factory &) = delete;
113 47981 : Factory &operator=(const Factory &) = delete;
114 47981 :
115 55856 : ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
116 55856 :
117 166310 : LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K,
118 1613 : data_type_ref D) {
119 361964 : TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
120 122614 : return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
121 546468 : }
122 562389 :
123 569716 : LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
124 18908 : TreeTy *T = F.remove(Old.Root,K);
125 67503 : return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
126 77262 : }
127 6492246 :
128 177388 : typename TreeTy::Factory *getTreeFactory() const {
129 435604 : return const_cast<typename TreeTy::Factory *>(&F);
130 6365565 : }
131 6374284 : };
132 6374284 :
133 13943 : bool contains(key_type_ref K) const {
134 213155 : return Root ? Root->contains(K) : false;
135 8320839 : }
136 10951 :
137 24557 : bool operator==(const ImmutableMap &RHS) const {
138 24557 : return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
139 51850 : }
140 27341 :
141 27399 : bool operator!=(const ImmutableMap &RHS) const {
142 3075327 : return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
143 2420912 : }
144 3036516 :
145 3561628 : TreeTy *getRoot() const {
146 3862702 : if (Root) { Root->retain(); }
147 3561628 : return Root;
148 0 : }
149 0 :
150 2923 : TreeTy *getRootWithoutRetain() const { return Root; }
151 2923 :
152 1676428 : void manualRetain() {
153 0 : if (Root) Root->retain();
154 0 : }
155 0 :
156 0 : void manualRelease() {
157 0 : if (Root) Root->release();
158 0 : }
159 0 :
160 1 : bool isEmpty() const { return !Root; }
161 0 :
162 0 : //===--------------------------------------------------===//
163 0 : // Foreach - A limited form of map iteration.
164 8078 : //===--------------------------------------------------===//
165 0 :
166 706 : private:
167 0 : template <typename Callback>
168 0 : struct CBWrapper {
169 0 : Callback C;
170 0 :
171 0 : void operator()(value_type_ref V) { C(V.first,V.second); }
172 : };
173 706 :
174 706 : template <typename Callback>
175 0 : struct CBWrapperRef {
176 0 : Callback &C;
177 0 :
178 0 : CBWrapperRef(Callback& c) : C(c) {}
179 0 :
180 2276 : void operator()(value_type_ref V) { C(V.first,V.second); }
181 0 : };
182 19763 :
183 0 : public:
184 0 : template <typename Callback>
185 0 : void foreach(Callback& C) {
186 0 : if (Root) {
187 9759 : CBWrapperRef<Callback> CB(C);
188 0 : Root->foreach(CB);
189 9763 : }
190 9759 : }
191 0 :
192 0 : template <typename Callback>
193 0 : void foreach() {
194 0 : if (Root) {
195 0 : CBWrapper<Callback> CB;
196 836 : Root->foreach(CB);
197 6 : }
198 0 : }
199 18 :
200 6 : //===--------------------------------------------------===//
201 0 : // For testing.
202 6 : //===--------------------------------------------------===//
203 0 :
204 18 : void verify() const { if (Root) Root->verify(); }
205 6 :
206 : //===--------------------------------------------------===//
207 0 : // Iterators.
208 0 : //===--------------------------------------------------===//
209 0 :
210 1315471 : class iterator : public ImutAVLValueIterator<ImmutableMap> {
211 0 : friend class ImmutableMap;
212 0 :
213 0 : iterator() = default;
214 1319888 : explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
215 0 :
216 1381648 : public:
217 1522303 : key_type_ref getKey() const { return (*this)->first; }
218 1522303 : data_type_ref getData() const { return (*this)->second; }
219 0 : };
220 1381648 :
221 0 : iterator begin() const { return iterator(Root); }
222 1315473 : iterator end() const { return iterator(); }
223 90 :
224 1558752 : data_type* lookup(key_type_ref K) const {
225 2725839 : if (Root) {
226 1459276 : TreeTy* T = Root->find(K);
227 2328213 : if (T) return &T->getValue().second;
228 1389468 : }
229 :
230 0 : return nullptr;
231 262570 : }
232 270390 :
233 262570 : /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
234 24 : /// which key is the highest in the ordering of keys in the map. This
235 841 : /// method returns NULL if the map is empty.
236 0 : value_type* getMaxElement() const {
237 1 : return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
238 915149 : }
239 0 :
240 7820 : //===--------------------------------------------------===//
241 0 : // Utility methods.
242 0 : //===--------------------------------------------------===//
243 49110 :
244 1 : unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
245 38603 :
246 4278 : static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
247 0 : ID.AddPointer(M.Root);
248 0 : }
249 0 :
250 0 : inline void Profile(FoldingSetNodeID& ID) const {
251 4051 : return Profile(ID,*this);
252 0 : }
253 0 : };
254 0 :
255 158 : // NOTE: This will possibly become the new implementation of ImmutableMap some day.
256 0 : template <typename KeyT, typename ValT,
257 612023 : typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
258 0 : class ImmutableMapRef {
259 0 : public:
260 0 : using value_type = typename ValInfo::value_type;
261 0 : using value_type_ref = typename ValInfo::value_type_ref;
262 0 : using key_type = typename ValInfo::key_type;
263 0 : using key_type_ref = typename ValInfo::key_type_ref;
264 0 : using data_type = typename ValInfo::data_type;
265 0 : using data_type_ref = typename ValInfo::data_type_ref;
266 0 : using TreeTy = ImutAVLTree<ValInfo>;
267 10123 : using FactoryTy = typename TreeTy::Factory;
268 0 :
269 5810 : protected:
270 : TreeTy *Root;
271 144 : FactoryTy *Factory;
272 0 :
273 : public:
274 : /// Constructs a map from a pointer to a tree root. In general one
275 : /// should use a Factory object to create maps instead of directly
276 : /// invoking the constructor, but there are cases where make this
277 0 : /// constructor public is useful.
278 259596 : explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
279 259596 : : Root(const_cast<TreeTy *>(R)), Factory(F) {
280 259596 : if (Root) {
281 0 : Root->retain();
282 0 : }
283 556 : }
284 :
285 8540118 : explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
286 8307563 : typename ImmutableMap<KeyT, ValT>::Factory &F)
287 : : Root(X.getRootWithoutRetain()),
288 : Factory(F.getTreeFactory()) {
289 : if (Root) { Root->retain(); }
290 362258 : }
291 20810 :
292 : ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
293 : if (Root) {
294 403878 : Root->retain();
295 20810 : }
296 : }
297 :
298 2407444 : ~ImmutableMapRef() {
299 2375689 : if (Root)
300 : Root->release();
301 1033915 : }
302 362258 :
303 0 : ImmutableMapRef &operator=(const ImmutableMapRef &X) {
304 10370016 : if (Root != X.Root) {
305 10487595 : if (X.Root)
306 : X.Root->retain();
307 10423590 :
308 35010 : if (Root)
309 35010 : Root->release();
310 :
311 35010 : Root = X.Root;
312 10335006 : Factory = X.Factory;
313 10335006 : }
314 0 : return *this;
315 10335006 : }
316 :
317 0 : static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
318 0 : return ImmutableMapRef(0, F);
319 0 : }
320 :
321 : void manualRetain() {
322 0 : if (Root) Root->retain();
323 : }
324 :
325 0 : void manualRelease() {
326 3133 : if (Root) Root->release();
327 109 : }
328 0 :
329 0 : ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
330 3133 : TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
331 109 : return ImmutableMapRef(NewT, Factory);
332 0 : }
333 :
334 : ImmutableMapRef remove(key_type_ref K) const {
335 0 : TreeTy *NewT = Factory->remove(Root, K);
336 : return ImmutableMapRef(NewT, Factory);
337 0 : }
338 3133 :
339 109 : bool contains(key_type_ref K) const {
340 0 : return Root ? Root->contains(K) : false;
341 7418 : }
342 2353933 :
343 4351 : ImmutableMap<KeyT, ValT> asImmutableMap() const {
344 2452967 : return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
345 0 : }
346 :
347 : bool operator==(const ImmutableMapRef &RHS) const {
348 0 : return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
349 0 : }
350 0 :
351 0 : bool operator!=(const ImmutableMapRef &RHS) const {
352 0 : return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
353 : }
354 0 :
355 : bool isEmpty() const { return !Root; }
356 :
357 0 : //===--------------------------------------------------===//
358 0 : // For testing.
359 : //===--------------------------------------------------===//
360 0 :
361 0 : void verify() const {
362 3834975 : if (Root)
363 0 : Root->verify();
364 : }
365 0 :
366 3084253 : //===--------------------------------------------------===//
367 0 : // Iterators.
368 0 : //===--------------------------------------------------===//
369 0 :
370 0 : class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
371 0 : friend class ImmutableMapRef;
372 :
373 0 : iterator() = default;
374 0 : explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
375 0 :
376 : public:
377 0 : key_type_ref getKey() const { return (*this)->first; }
378 0 : data_type_ref getData() const { return (*this)->second; }
379 0 : };
380 :
381 : iterator begin() const { return iterator(Root); }
382 0 : iterator end() const { return iterator(); }
383 230539 :
384 230539 : data_type *lookup(key_type_ref K) const {
385 : if (Root) {
386 0 : TreeTy* T = Root->find(K);
387 0 : if (T) return &T->getValue().second;
388 7318326 : }
389 0 :
390 0 : return nullptr;
391 0 : }
392 0 :
393 0 : /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
394 0 : /// which key is the highest in the ordering of keys in the map. This
395 0 : /// method returns NULL if the map is empty.
396 69168 : value_type* getMaxElement() const {
397 0 : return Root ? &(Root->getMaxElement()->getValue()) : 0;
398 0 : }
399 0 :
400 481433 : //===--------------------------------------------------===//
401 7318326 : // Utility methods.
402 0 : //===--------------------------------------------------===//
403 0 :
404 : unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
405 0 :
406 0 : static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
407 : ID.AddPointer(M.Root);
408 : }
409 :
410 : inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
411 : };
412 :
413 : } // end namespace llvm
414 :
415 : #endif // LLVM_ADT_IMMUTABLEMAP_H
|
