LLVM  6.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  TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
119  return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
120  }
121 
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 
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.
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>>
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;
266  using FactoryTy = typename TreeTy::Factory;
267 
268 protected:
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 
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 
298  if (Root)
299  Root->release();
300  }
301 
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 
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 
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 
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 
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.
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
unsigned getHeight() const
Definition: ImmutableMap.h:403
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:260
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:328
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
data_type_ref getData() const
Definition: ImmutableMap.h:377
bool operator!=(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:350
unsigned getHeight() const
Definition: ImmutableMap.h:243
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:409
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:266
value_type * getMaxElement() const
getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...
Definition: ImmutableMap.h:235
F(f)
bool operator!=(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:140
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:261
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:216
TreeTy * getRoot() const
Definition: ImmutableMap.h:144
bool isEqual(const ImutAVLTree &RHS) const
isEqual - Compares two trees for structural equality and returns true if they are equal...
Definition: ImmutableSet.h:139
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:263
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:70
TreeTy * getRootWithoutRetain() const
Definition: ImmutableMap.h:149
#define T
const std::pair< T, S > value_type
Definition: ImmutableMap.h:29
bool isEmpty() const
Definition: ImmutableMap.h:159
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:217
TreeTy::Factory * getTreeFactory() const
Definition: ImmutableMap.h:127
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:132
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:383
InstrProfLookupTrait::data_type data_type
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:223
TreeTy * getEmptyTree() const
Definition: ImmutableSet.h:417
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:264
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:138
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:316
iterator begin() const
Definition: ImmutableMap.h:380
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:921
ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D)
Definition: ImmutableMap.h:117
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:376
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:395
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:291
iterator end() const
Definition: ImmutableMap.h:381
void verify() const
Definition: ImmutableMap.h:203
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:277
Factory(bool canonicalize=true)
Definition: ImmutableMap.h:107
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:249
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:338
static void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M)
Definition: ImmutableMap.h:405
iterator begin() const
Definition: ImmutableMap.h:220
const value_type & value_type_ref
Definition: ImmutableMap.h:30
bool operator==(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:346
ImmutableMapRef(const ImmutableMap< KeyT, ValT > &X, typename ImmutableMap< KeyT, ValT >::Factory &F)
Definition: ImmutableMap.h:284
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:342
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:844
ImmutableMapRef & operator=(const ImmutableMapRef &X)
Definition: ImmutableMap.h:302
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:259
ImutKeyValueInfo -Traits class used by ImmutableMap.
Definition: ImmutableMap.h:28
static void Profile(FoldingSetNodeID &ID, const ImmutableMap &M)
Definition: ImmutableMap.h:245
bool operator==(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:136
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:68
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:262
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:354
iterator end() const
Definition: ImmutableMap.h:221