LLVM  12.0.0git
ImmutableMap.h
Go to the documentation of this file.
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>
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 
36  return V.first;
37  }
38 
40  return V.second;
41  }
42 
43  static inline bool isEqual(key_type_ref L, key_type_ref 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) {
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;
71 
72 protected:
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 
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 
96 
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 
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 
147 private:
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 
164 public:
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 
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.
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.
237 template <typename KeyT, typename ValT,
238 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
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;
248  using FactoryTy = typename TreeTy::Factory;
249 
250 protected:
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.
260  : Root(const_cast<TreeTy *>(R)), Factory(F) {}
261 
264  : Root(X.getRootWithoutRetain()), Factory(F.getTreeFactory()) {}
265 
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 
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 
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 
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.
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);
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
unsigned getHeight() const
Definition: ImmutableMap.h:355
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference...
Definition: ImmutableSet.h:822
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableMap.h:242
uint64_t CallInst * C
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:52
ImmutableMapRef add(key_type_ref K, data_type_ref D) const
Definition: ImmutableMap.h:278
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
data_type_ref getData() const
Definition: ImmutableMap.h:329
bool operator!=(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:301
unsigned getHeight() const
Definition: ImmutableMap.h:225
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:361
This class represents lattice values for constants.
Definition: AllocatorList.h:23
TreeTy * add(TreeTy *T, value_type_ref V)
Definition: ImmutableSet.h:408
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:64
static key_type_ref KeyOfValue(value_type_ref V)
Definition: ImmutableMap.h:35
typename TreeTy::Factory FactoryTy
Definition: ImmutableMap.h:248
value_type * getMaxElement() const
getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...
Definition: ImmutableMap.h:217
F(f)
bool operator!=(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:121
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:243
ImmutableMap(const TreeTy *R)
Constructs a map from a pointer to a tree root.
Definition: ImmutableMap.h:80
IntrusiveRefCntPtr< TreeTy > Root
Definition: ImmutableMap.h:73
This file defines the BumpPtrAllocator interface.
key_type_ref getKey() const
Definition: ImmutableMap.h:198
TreeTy * getRoot() const
Definition: ImmutableMap.h:126
LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D)
Definition: ImmutableMap.h:97
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:245
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:69
TreeTy * getRootWithoutRetain() const
Definition: ImmutableMap.h:131
const std::pair< T, S > value_type
Definition: ImmutableMap.h:28
ImmutableMap getEmptyMap()
Definition: ImmutableMap.h:95
bool isEmpty() const
Definition: ImmutableMap.h:141
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableMap.h:65
data_type_ref getData() const
Definition: ImmutableMap.h:199
TreeTy::Factory * getTreeFactory() const
Definition: ImmutableMap.h:108
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:113
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:66
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:335
InstrProfLookupTrait::data_type data_type
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:205
TreeTy * getEmptyTree() const
Definition: ImmutableSet.h:422
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:246
TreeTy * remove(TreeTy *T, key_type_ref V)
Definition: ImmutableSet.h:415
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
static ImmutableMapRef getEmptyMap(FactoryTy *F)
Definition: ImmutableMap.h:266
iterator begin() const
Definition: ImmutableMap.h:332
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:926
IntrusiveRefCntPtr< TreeTy > Root
Definition: ImmutableMap.h:251
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
key_type_ref getKey() const
Definition: ImmutableMap.h:328
static void Profile(FoldingSetNodeID &ID, value_type_ref V)
Definition: ImmutableMap.h:54
const value_type & getValue() const
getValue - Returns the data value associated with the tree node.
Definition: ImmutableSet.h:71
value_type * getMaxElement() const
getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...
Definition: ImmutableMap.h:347
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:68
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
iterator end() const
Definition: ImmutableMap.h:333
void verify() const
Definition: ImmutableMap.h:185
TreeTy * getCanonicalTree(TreeTy *TNew)
Definition: ImmutableSet.h:613
ImmutableMapRef(const TreeTy *R, FactoryTy *F)
Constructs a map from a pointer to a tree root.
Definition: ImmutableMap.h:259
Factory(bool canonicalize=true)
Definition: ImmutableMap.h:87
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:231
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:289
static void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M)
Definition: ImmutableMap.h:357
iterator begin() const
Definition: ImmutableMap.h:202
const value_type & value_type_ref
Definition: ImmutableMap.h:29
bool operator==(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:297
ImmutableMapRef(const ImmutableMap< KeyT, ValT > &X, typename ImmutableMap< KeyT, ValT >::Factory &F)
Definition: ImmutableMap.h:262
static bool isDataEqual(data_type_ref L, data_type_ref R)
Definition: ImmutableMap.h:50
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:160
static bool isLess(key_type_ref L, key_type_ref R)
Definition: ImmutableMap.h:46
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:930
ImmutableMap< KeyT, ValT > asImmutableMap() const
Definition: ImmutableMap.h:293
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:849
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:241
ImutKeyValueInfo -Traits class used by ImmutableMap.
Definition: ImmutableMap.h:27
static void Profile(FoldingSetNodeID &ID, const ImmutableMap &M)
Definition: ImmutableMap.h:227
bool operator==(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:117
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:67
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:244
Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)
Definition: ImmutableMap.h:89
static data_type_ref DataOfValue(value_type_ref V)
Definition: ImmutableMap.h:39
static bool isEqual(key_type_ref L, key_type_ref R)
Definition: ImmutableMap.h:43
bool isEmpty() const
Definition: ImmutableMap.h:306
iterator end() const
Definition: ImmutableMap.h:203