LLVM  7.0.0svn
ImmutableMap.h
Go to the documentation of this file.
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>
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 
37  return V.first;
38  }
39 
41  return V.second;
42  }
43 
44  static inline bool isEqual(key_type_ref L, key_type_ref 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) {
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;
72 
73 protected:
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  if (Root) { Root->retain(); }
83  }
84 
85  ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
86  if (Root) { Root->retain(); }
87  }
88 
90  if (Root) { Root->release(); }
91  }
92 
94  if (Root != X.Root) {
95  if (X.Root) { X.Root->retain(); }
96  if (Root) { Root->release(); }
97  Root = X.Root;
98  }
99  return *this;
100  }
101 
102  class Factory {
103  typename TreeTy::Factory F;
104  const bool Canonicalize;
105 
106  public:
107  Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
108 
109  Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
110  : F(Alloc), Canonicalize(canonicalize) {}
111 
112  Factory(const Factory &) = delete;
113  Factory &operator=(const Factory &) = delete;
114 
116 
118  data_type_ref D) {
119  TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
120  return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
121  }
122 
124  TreeTy *T = F.remove(Old.Root,K);
125  return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
126  }
127 
128  typename TreeTy::Factory *getTreeFactory() const {
129  return const_cast<typename TreeTy::Factory *>(&F);
130  }
131  };
132 
133  bool contains(key_type_ref K) const {
134  return Root ? Root->contains(K) : false;
135  }
136 
137  bool operator==(const ImmutableMap &RHS) const {
138  return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
139  }
140 
141  bool operator!=(const ImmutableMap &RHS) const {
142  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
143  }
144 
145  TreeTy *getRoot() const {
146  if (Root) { Root->retain(); }
147  return Root;
148  }
149 
150  TreeTy *getRootWithoutRetain() const { return Root; }
151 
152  void manualRetain() {
153  if (Root) Root->retain();
154  }
155 
156  void manualRelease() {
157  if (Root) Root->release();
158  }
159 
160  bool isEmpty() const { return !Root; }
161 
162  //===--------------------------------------------------===//
163  // Foreach - A limited form of map iteration.
164  //===--------------------------------------------------===//
165 
166 private:
167  template <typename Callback>
168  struct CBWrapper {
169  Callback C;
170 
171  void operator()(value_type_ref V) { C(V.first,V.second); }
172  };
173 
174  template <typename Callback>
175  struct CBWrapperRef {
176  Callback &C;
177 
178  CBWrapperRef(Callback& c) : C(c) {}
179 
180  void operator()(value_type_ref V) { C(V.first,V.second); }
181  };
182 
183 public:
184  template <typename Callback>
185  void foreach(Callback& C) {
186  if (Root) {
187  CBWrapperRef<Callback> CB(C);
188  Root->foreach(CB);
189  }
190  }
191 
192  template <typename Callback>
193  void foreach() {
194  if (Root) {
195  CBWrapper<Callback> CB;
196  Root->foreach(CB);
197  }
198  }
199 
200  //===--------------------------------------------------===//
201  // For testing.
202  //===--------------------------------------------------===//
203 
204  void verify() const { if (Root) Root->verify(); }
205 
206  //===--------------------------------------------------===//
207  // Iterators.
208  //===--------------------------------------------------===//
209 
210  class iterator : public ImutAVLValueIterator<ImmutableMap> {
211  friend class ImmutableMap;
212 
213  iterator() = default;
214  explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
215 
216  public:
217  key_type_ref getKey() const { return (*this)->first; }
218  data_type_ref getData() const { return (*this)->second; }
219  };
220 
221  iterator begin() const { return iterator(Root); }
222  iterator end() const { return iterator(); }
223 
225  if (Root) {
226  TreeTy* T = Root->find(K);
227  if (T) return &T->getValue().second;
228  }
229 
230  return nullptr;
231  }
232 
233  /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
234  /// which key is the highest in the ordering of keys in the map. This
235  /// method returns NULL if the map is empty.
237  return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
238  }
239 
240  //===--------------------------------------------------===//
241  // Utility methods.
242  //===--------------------------------------------------===//
243 
244  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
245 
246  static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
247  ID.AddPointer(M.Root);
248  }
249 
250  inline void Profile(FoldingSetNodeID& ID) const {
251  return Profile(ID,*this);
252  }
253 };
254 
255 // NOTE: This will possibly become the new implementation of ImmutableMap some day.
256 template <typename KeyT, typename ValT,
257 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
259 public:
260  using value_type = typename ValInfo::value_type;
261  using value_type_ref = typename ValInfo::value_type_ref;
262  using key_type = typename ValInfo::key_type;
263  using key_type_ref = typename ValInfo::key_type_ref;
264  using data_type = typename ValInfo::data_type;
265  using data_type_ref = typename ValInfo::data_type_ref;
267  using FactoryTy = typename TreeTy::Factory;
268 
269 protected:
272 
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  /// constructor public is useful.
278  explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
279  : Root(const_cast<TreeTy *>(R)), Factory(F) {
280  if (Root) {
281  Root->retain();
282  }
283  }
284 
287  : Root(X.getRootWithoutRetain()),
288  Factory(F.getTreeFactory()) {
289  if (Root) { Root->retain(); }
290  }
291 
292  ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
293  if (Root) {
294  Root->retain();
295  }
296  }
297 
299  if (Root)
300  Root->release();
301  }
302 
304  if (Root != X.Root) {
305  if (X.Root)
306  X.Root->retain();
307 
308  if (Root)
309  Root->release();
310 
311  Root = X.Root;
312  Factory = X.Factory;
313  }
314  return *this;
315  }
316 
318  return ImmutableMapRef(0, F);
319  }
320 
321  void manualRetain() {
322  if (Root) Root->retain();
323  }
324 
325  void manualRelease() {
326  if (Root) Root->release();
327  }
328 
330  TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
331  return ImmutableMapRef(NewT, Factory);
332  }
333 
334  ImmutableMapRef remove(key_type_ref K) const {
335  TreeTy *NewT = Factory->remove(Root, K);
336  return ImmutableMapRef(NewT, Factory);
337  }
338 
339  bool contains(key_type_ref K) const {
340  return Root ? Root->contains(K) : false;
341  }
342 
344  return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
345  }
346 
347  bool operator==(const ImmutableMapRef &RHS) const {
348  return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
349  }
350 
351  bool operator!=(const ImmutableMapRef &RHS) const {
352  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
353  }
354 
355  bool isEmpty() const { return !Root; }
356 
357  //===--------------------------------------------------===//
358  // For testing.
359  //===--------------------------------------------------===//
360 
361  void verify() const {
362  if (Root)
363  Root->verify();
364  }
365 
366  //===--------------------------------------------------===//
367  // Iterators.
368  //===--------------------------------------------------===//
369 
370  class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
371  friend class ImmutableMapRef;
372 
373  iterator() = default;
374  explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
375 
376  public:
377  key_type_ref getKey() const { return (*this)->first; }
378  data_type_ref getData() const { return (*this)->second; }
379  };
380 
381  iterator begin() const { return iterator(Root); }
382  iterator end() const { return iterator(); }
383 
385  if (Root) {
386  TreeTy* T = Root->find(K);
387  if (T) return &T->getValue().second;
388  }
389 
390  return nullptr;
391  }
392 
393  /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
394  /// which key is the highest in the ordering of keys in the map. This
395  /// method returns NULL if the map is empty.
397  return Root ? &(Root->getMaxElement()->getValue()) : 0;
398  }
399 
400  //===--------------------------------------------------===//
401  // Utility methods.
402  //===--------------------------------------------------===//
403 
404  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
405 
406  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
unsigned getHeight() const
Definition: ImmutableMap.h:404
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference...
Definition: ImmutableSet.h:817
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableMap.h:261
unsigned getHeight() const
getHeight - Returns the height of the tree.
Definition: ImmutableSet.h:68
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:329
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
data_type_ref getData() const
Definition: ImmutableMap.h:378
bool operator!=(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:351
unsigned getHeight() const
Definition: ImmutableMap.h:244
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:410
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
ImmutableMap & operator=(const ImmutableMap &X)
Definition: ImmutableMap.h:93
TreeTy * add(TreeTy *T, value_type_ref V)
Definition: ImmutableSet.h:403
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:65
static key_type_ref KeyOfValue(value_type_ref V)
Definition: ImmutableMap.h:36
typename TreeTy::Factory FactoryTy
Definition: ImmutableMap.h:267
value_type * getMaxElement() const
getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...
Definition: ImmutableMap.h:236
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:129
F(f)
bool operator!=(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:141
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:262
ImmutableMap(const TreeTy *R)
Constructs a map from a pointer to a tree root.
Definition: ImmutableMap.h:81
bool isNotEqual(const ImutAVLTree &RHS) const
isNotEqual - Compares two trees for structural inequality.
Definition: ImmutableSet.h:165
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
ImutAVLTree * getMaxElement()
getMaxElement - Find the subtree associated with the highest ranged key value.
Definition: ImmutableSet.h:91
key_type_ref getKey() const
Definition: ImmutableMap.h:217
TreeTy * getRoot() const
Definition: ImmutableMap.h:145
bool isEqual(const ImutAVLTree &RHS) const
isEqual - Compares two trees for structural equality and returns true if they are equal...
Definition: ImmutableSet.h:139
LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D)
Definition: ImmutableMap.h:117
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:264
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:70
TreeTy * getRootWithoutRetain() const
Definition: ImmutableMap.h:150
#define T
const std::pair< T, S > value_type
Definition: ImmutableMap.h:29
bool isEmpty() const
Definition: ImmutableMap.h:160
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableMap.h:66
void foreach(Callback &C)
foreach - A member template the accepts invokes operator() on a functor object (specifed by Callback)...
Definition: ImmutableSet.h:176
data_type_ref getData() const
Definition: ImmutableMap.h:218
TreeTy::Factory * getTreeFactory() const
Definition: ImmutableMap.h:128
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:133
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:67
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:306
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:384
InstrProfLookupTrait::data_type data_type
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:224
TreeTy * getEmptyTree() const
Definition: ImmutableSet.h:417
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:265
TreeTy * remove(TreeTy *T, key_type_ref V)
Definition: ImmutableSet.h:410
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:140
ImutAVLTree * find(key_type_ref K)
find - Finds the subtree associated with the specified key value.
Definition: ImmutableSet.h:75
static ImmutableMapRef getEmptyMap(FactoryTy *F)
Definition: ImmutableMap.h:317
iterator begin() const
Definition: ImmutableMap.h:381
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:921
bool contains(key_type_ref K)
contains - Returns true if this tree contains a subtree (node) that has an data element that matches ...
Definition: ImmutableSet.h:170
key_type_ref getKey() const
Definition: ImmutableMap.h:377
static void Profile(FoldingSetNodeID &ID, value_type_ref V)
Definition: ImmutableMap.h:55
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:396
ImmutableMap(const ImmutableMap &X)
Definition: ImmutableMap.h:85
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:69
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
ImmutableMapRef(const ImmutableMapRef &X)
Definition: ImmutableMap.h:292
iterator end() const
Definition: ImmutableMap.h:382
void verify() const
Definition: ImmutableMap.h:204
TreeTy * getCanonicalTree(TreeTy *TNew)
Definition: ImmutableSet.h:608
ImmutableMapRef(const TreeTy *R, FactoryTy *F)
Constructs a map from a pointer to a tree root.
Definition: ImmutableMap.h:278
Factory(bool canonicalize=true)
Definition: ImmutableMap.h:107
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:250
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:339
static void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M)
Definition: ImmutableMap.h:406
iterator begin() const
Definition: ImmutableMap.h:221
const value_type & value_type_ref
Definition: ImmutableMap.h:30
bool operator==(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:347
ImmutableMapRef(const ImmutableMap< KeyT, ValT > &X, typename ImmutableMap< KeyT, ValT >::Factory &F)
Definition: ImmutableMap.h:285
static bool isDataEqual(data_type_ref L, data_type_ref R)
Definition: ImmutableMap.h:51
static bool isLess(key_type_ref L, key_type_ref R)
Definition: ImmutableMap.h:47
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:925
ImmutableMap< KeyT, ValT > asImmutableMap() const
Definition: ImmutableMap.h:343
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:844
ImmutableMapRef & operator=(const ImmutableMapRef &X)
Definition: ImmutableMap.h:303
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:260
ImutKeyValueInfo -Traits class used by ImmutableMap.
Definition: ImmutableMap.h:28
static void Profile(FoldingSetNodeID &ID, const ImmutableMap &M)
Definition: ImmutableMap.h:246
bool operator==(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:137
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:68
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:263
Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)
Definition: ImmutableMap.h:109
static data_type_ref DataOfValue(value_type_ref V)
Definition: ImmutableMap.h:40
static bool isEqual(key_type_ref L, key_type_ref R)
Definition: ImmutableMap.h:44
bool isEmpty() const
Definition: ImmutableMap.h:355
iterator end() const
Definition: ImmutableMap.h:222