LLVM  15.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 /// \file
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) {
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 
83  class Factory {
84  typename TreeTy::Factory F;
85  const bool Canonicalize;
86 
87  public:
88  Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
89 
90  Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
91  : F(Alloc), Canonicalize(canonicalize) {}
92 
93  Factory(const Factory &) = delete;
94  Factory &operator=(const Factory &) = delete;
95 
96  ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
97 
99  data_type_ref D) {
100  TreeTy *T = F.add(Old.Root.get(), std::pair<key_type, data_type>(K, D));
101  return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
102  }
103 
105  TreeTy *T = F.remove(Old.Root.get(), K);
106  return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
107  }
108 
109  typename TreeTy::Factory *getTreeFactory() const {
110  return const_cast<typename TreeTy::Factory *>(&F);
111  }
112  };
113 
114  bool contains(key_type_ref K) const {
115  return Root ? Root->contains(K) : false;
116  }
117 
118  bool operator==(const ImmutableMap &RHS) const {
119  return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
120  }
121 
122  bool operator!=(const ImmutableMap &RHS) const {
123  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
124  : Root != RHS.Root;
125  }
126 
127  TreeTy *getRoot() const {
128  if (Root) { Root->retain(); }
129  return Root.get();
130  }
131 
132  TreeTy *getRootWithoutRetain() const { return Root.get(); }
133 
134  void manualRetain() {
135  if (Root) Root->retain();
136  }
137 
138  void manualRelease() {
139  if (Root) Root->release();
140  }
141 
142  bool isEmpty() const { return !Root; }
143 
144 public:
145  //===--------------------------------------------------===//
146  // For testing.
147  //===--------------------------------------------------===//
148 
149  void verify() const { if (Root) Root->verify(); }
150 
151  //===--------------------------------------------------===//
152  // Iterators.
153  //===--------------------------------------------------===//
154 
155  class iterator : public ImutAVLValueIterator<ImmutableMap> {
156  friend class ImmutableMap;
157 
158  iterator() = default;
159  explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
160 
161  public:
162  key_type_ref getKey() const { return (*this)->first; }
163  data_type_ref getData() const { return (*this)->second; }
164  };
165 
166  iterator begin() const { return iterator(Root.get()); }
167  iterator end() const { return iterator(); }
168 
170  if (Root) {
171  TreeTy* T = Root->find(K);
172  if (T) return &T->getValue().second;
173  }
174 
175  return nullptr;
176  }
177 
178  /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
179  /// which key is the highest in the ordering of keys in the map. This
180  /// method returns NULL if the map is empty.
182  return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
183  }
184 
185  //===--------------------------------------------------===//
186  // Utility methods.
187  //===--------------------------------------------------===//
188 
189  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
190 
191  static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
192  ID.AddPointer(M.Root.get());
193  }
194 
195  inline void Profile(FoldingSetNodeID& ID) const {
196  return Profile(ID,*this);
197  }
198 };
199 
200 // NOTE: This will possibly become the new implementation of ImmutableMap some day.
201 template <typename KeyT, typename ValT,
202 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
204 public:
205  using value_type = typename ValInfo::value_type;
206  using value_type_ref = typename ValInfo::value_type_ref;
207  using key_type = typename ValInfo::key_type;
208  using key_type_ref = typename ValInfo::key_type_ref;
209  using data_type = typename ValInfo::data_type;
210  using data_type_ref = typename ValInfo::data_type_ref;
212  using FactoryTy = typename TreeTy::Factory;
213 
214 protected:
217 
218 public:
219  /// Constructs a map from a pointer to a tree root. In general one
220  /// should use a Factory object to create maps instead of directly
221  /// invoking the constructor, but there are cases where make this
222  /// constructor public is useful.
224  : Root(const_cast<TreeTy *>(R)), Factory(F) {}
225 
228  : Root(X.getRootWithoutRetain()), Factory(F.getTreeFactory()) {}
229 
231  return ImmutableMapRef(nullptr, F);
232  }
233 
234  void manualRetain() {
235  if (Root) Root->retain();
236  }
237 
238  void manualRelease() {
239  if (Root) Root->release();
240  }
241 
243  TreeTy *NewT =
244  Factory->add(Root.get(), std::pair<key_type, data_type>(K, D));
245  return ImmutableMapRef(NewT, Factory);
246  }
247 
249  TreeTy *NewT = Factory->remove(Root.get(), K);
250  return ImmutableMapRef(NewT, Factory);
251  }
252 
253  bool contains(key_type_ref K) const {
254  return Root ? Root->contains(K) : false;
255  }
256 
258  return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root.get()));
259  }
260 
261  bool operator==(const ImmutableMapRef &RHS) const {
262  return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
263  }
264 
265  bool operator!=(const ImmutableMapRef &RHS) const {
266  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
267  : Root != RHS.Root;
268  }
269 
270  bool isEmpty() const { return !Root; }
271 
272  //===--------------------------------------------------===//
273  // For testing.
274  //===--------------------------------------------------===//
275 
276  void verify() const {
277  if (Root)
278  Root->verify();
279  }
280 
281  //===--------------------------------------------------===//
282  // Iterators.
283  //===--------------------------------------------------===//
284 
285  class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
286  friend class ImmutableMapRef;
287 
288  iterator() = default;
289  explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
290 
291  public:
292  key_type_ref getKey() const { return (*this)->first; }
293  data_type_ref getData() const { return (*this)->second; }
294  };
295 
296  iterator begin() const { return iterator(Root.get()); }
297  iterator end() const { return iterator(); }
298 
300  if (Root) {
301  TreeTy* T = Root->find(K);
302  if (T) return &T->getValue().second;
303  }
304 
305  return nullptr;
306  }
307 
308  /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
309  /// which key is the highest in the ordering of keys in the map. This
310  /// method returns NULL if the map is empty.
312  return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
313  }
314 
315  //===--------------------------------------------------===//
316  // Utility methods.
317  //===--------------------------------------------------===//
318 
319  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
320 
321  static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
322  ID.AddPointer(M.Root.get());
323  }
324 
325  inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
326 };
327 
328 } // end namespace llvm
329 
330 #endif // LLVM_ADT_IMMUTABLEMAP_H
llvm::ImutKeyValueInfo::isEqual
static bool isEqual(key_type_ref L, key_type_ref R)
Definition: ImmutableMap.h:44
llvm::ImmutableMapRef::data_type
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:209
llvm::ImmutableMap::verify
void verify() const
Definition: ImmutableMap.h:149
llvm::ImutKeyValueInfo::value_type_ref
const value_type & value_type_ref
Definition: ImmutableMap.h:30
llvm::ImmutableMapRef::data_type_ref
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:210
llvm::ImmutableMapRef::Factory
FactoryTy * Factory
Definition: ImmutableMap.h:216
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::ImmutableMap::ImmutableMap
ImmutableMap(const TreeTy *R)
Constructs a map from a pointer to a tree root.
Definition: ImmutableMap.h:81
KeyT
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ImutKeyValueInfo::value_type
const std::pair< T, S > value_type
Definition: ImmutableMap.h:29
llvm::ImutKeyValueInfo::KeyOfValue
static key_type_ref KeyOfValue(value_type_ref V)
Definition: ImmutableMap.h:36
llvm::ImmutableMap::iterator::getKey
key_type_ref getKey() const
Definition: ImmutableMap.h:162
llvm::ImmutableMap::getMaxElement
value_type * getMaxElement() const
getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...
Definition: ImmutableMap.h:181
llvm::ImmutableMapRef::getEmptyMap
static ImmutableMapRef getEmptyMap(FactoryTy *F)
Definition: ImmutableMap.h:230
llvm::ImmutableMapRef::ImmutableMapRef
ImmutableMapRef(const TreeTy *R, FactoryTy *F)
Constructs a map from a pointer to a tree root.
Definition: ImmutableMap.h:223
llvm::ImmutableMap::Factory::Factory
Factory(bool canonicalize=true)
Definition: ImmutableMap.h:88
llvm::ImutKeyValueInfo::isLess
static bool isLess(key_type_ref L, key_type_ref R)
Definition: ImmutableMap.h:47
llvm::ImmutableMap::data_type
typename ValInfo::data_type data_type
Definition: ImmutableMap.h:69
Allocator.h
llvm::ImutAVLValueIterator
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference.
Definition: ImmutableSet.h:815
llvm::ImmutableMapRef::iterator
Definition: ImmutableMap.h:285
llvm::ImmutableMap::isEmpty
bool isEmpty() const
Definition: ImmutableMap.h:142
llvm::ImutContainerInfo::isEqual
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:919
llvm::ImmutableMapRef::contains
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:253
T
#define T
Definition: Mips16ISelLowering.cpp:341
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::ImmutableMapRef::isEmpty
bool isEmpty() const
Definition: ImmutableMap.h:270
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::ImutKeyValueInfo::key_type_ref
const T & key_type_ref
Definition: ImmutableMap.h:32
llvm::ImmutableMapRef::manualRetain
void manualRetain()
Definition: ImmutableMap.h:234
llvm::ImmutableMap::Factory::add
LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D)
Definition: ImmutableMap.h:98
llvm::ImmutableMap::Factory::operator=
Factory & operator=(const Factory &)=delete
llvm::ImmutableMapRef::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:325
llvm::ImutKeyValueInfo
ImutKeyValueInfo -Traits class used by ImmutableMap.
Definition: ImmutableMap.h:28
llvm::ImmutableMap
Definition: ImmutableMap.h:63
llvm::ImmutableMap::operator==
bool operator==(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:118
llvm::ImutAVLFactory
Definition: ImmutableSet.h:37
llvm::ImmutableMap::Factory::Factory
Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)
Definition: ImmutableMap.h:90
llvm::ImmutableMap::contains
bool contains(key_type_ref K) const
Definition: ImmutableMap.h:114
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ImmutableMap::manualRelease
void manualRelease()
Definition: ImmutableMap.h:138
llvm::ImmutableMap::Profile
static void Profile(FoldingSetNodeID &ID, const ImmutableMap &M)
Definition: ImmutableMap.h:191
llvm::ImmutableMapRef::end
iterator end() const
Definition: ImmutableMap.h:297
llvm::ImmutableMapRef::operator!=
bool operator!=(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:265
llvm::ImmutableMap::lookup
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:169
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ImmutableMapRef::Profile
static void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M)
Definition: ImmutableMap.h:321
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
llvm::ImmutableMap::getRoot
TreeTy * getRoot() const
Definition: ImmutableMap.h:127
llvm::ImutProfileInfo::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:842
llvm::ImmutableMap::Factory::getEmptyMap
ImmutableMap getEmptyMap()
Definition: ImmutableMap.h:96
llvm::ImutContainerInfo::isLess
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:923
llvm::ImmutableMapRef::key_type_ref
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:208
llvm::ImutKeyValueInfo::key_type
const T key_type
Definition: ImmutableMap.h:31
llvm::ImmutableMap::key_type
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:67
llvm::ImmutableMapRef::value_type
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:205
llvm::ImutKeyValueInfo::data_type_ref
const S & data_type_ref
Definition: ImmutableMap.h:34
llvm::ImmutableMapRef::operator==
bool operator==(const ImmutableMapRef &RHS) const
Definition: ImmutableMap.h:261
llvm::ImmutableMapRef::ImmutableMapRef
ImmutableMapRef(const ImmutableMap< KeyT, ValT > &X, typename ImmutableMap< KeyT, ValT >::Factory &F)
Definition: ImmutableMap.h:226
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:317
llvm::ImmutableMapRef::add
ImmutableMapRef add(key_type_ref K, data_type_ref D) const
Definition: ImmutableMap.h:242
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ImmutableMapRef::remove
ImmutableMapRef remove(key_type_ref K) const
Definition: ImmutableMap.h:248
llvm::ImmutableMapRef
Definition: ImmutableMap.h:203
FoldingSet.h
llvm::ImmutableMapRef::asImmutableMap
ImmutableMap< KeyT, ValT > asImmutableMap() const
Definition: ImmutableMap.h:257
llvm::ImmutableMap::data_type_ref
typename ValInfo::data_type_ref data_type_ref
Definition: ImmutableMap.h:70
llvm::ImmutableMapRef::getHeight
unsigned getHeight() const
Definition: ImmutableMap.h:319
llvm::ImmutableMap::value_type
typename ValInfo::value_type value_type
Definition: ImmutableMap.h:65
llvm::ImmutableMapRef::value_type_ref
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableMap.h:206
llvm::ImmutableMapRef::iterator::getKey
key_type_ref getKey() const
Definition: ImmutableMap.h:292
llvm::ImmutableMap::getHeight
unsigned getHeight() const
Definition: ImmutableMap.h:189
ImmutableSet.h
llvm::ImmutableMap::key_type_ref
typename ValInfo::key_type_ref key_type_ref
Definition: ImmutableMap.h:68
llvm::ImmutableMapRef::manualRelease
void manualRelease()
Definition: ImmutableMap.h:238
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:155
llvm::ImmutableMap::end
iterator end() const
Definition: ImmutableMap.h:167
llvm::ImmutableMapRef::verify
void verify() const
Definition: ImmutableMap.h:276
llvm::ImmutableMap::iterator::getData
data_type_ref getData() const
Definition: ImmutableMap.h:163
llvm::ImutKeyValueInfo::data_type
const S data_type
Definition: ImmutableMap.h:33
llvm::ImmutableMapRef::Root
IntrusiveRefCntPtr< TreeTy > Root
Definition: ImmutableMap.h:215
llvm::ImmutableMap::getRootWithoutRetain
TreeTy * getRootWithoutRetain() const
Definition: ImmutableMap.h:132
llvm::ImmutableMap::operator!=
bool operator!=(const ImmutableMap &RHS) const
Definition: ImmutableMap.h:122
llvm::ImmutableMapRef::key_type
typename ValInfo::key_type key_type
Definition: ImmutableMap.h:207
llvm::ImmutableMap::begin
iterator begin() const
Definition: ImmutableMap.h:166
llvm::ImmutableMap::Root
IntrusiveRefCntPtr< TreeTy > Root
Definition: ImmutableMap.h:74
llvm::ImmutableMapRef::lookup
data_type * lookup(key_type_ref K) const
Definition: ImmutableMap.h:299
llvm::ImmutableMapRef::FactoryTy
typename TreeTy::Factory FactoryTy
Definition: ImmutableMap.h:212
data_type
InstrProfLookupTrait::data_type data_type
Definition: InstrProfReader.cpp:636
llvm::ImmutableMap::Factory::getTreeFactory
TreeTy::Factory * getTreeFactory() const
Definition: ImmutableMap.h:109
llvm::ImmutableMap::iterator
Definition: ImmutableMap.h:155
llvm::ImutAVLTree
Definition: ImmutableSet.h:43
llvm::ImutKeyValueInfo::isDataEqual
static bool isDataEqual(data_type_ref L, data_type_ref R)
Definition: ImmutableMap.h:51
llvm::ImmutableMap::value_type_ref
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableMap.h:66
llvm::ImmutableMapRef::iterator::getData
data_type_ref getData() const
Definition: ImmutableMap.h:293
llvm::ImutKeyValueInfo::DataOfValue
static data_type_ref DataOfValue(value_type_ref V)
Definition: ImmutableMap.h:40
ValT
llvm::ImutKeyValueInfo::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref V)
Definition: ImmutableMap.h:55
llvm::ImmutableMap::Factory::remove
LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K)
Definition: ImmutableMap.h:104
llvm::IntrusiveRefCntPtr
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
Definition: IntrusiveRefCntPtr.h:168
llvm::ImmutableMapRef::begin
iterator begin() const
Definition: ImmutableMap.h:296
llvm::ImmutableMap::manualRetain
void manualRetain()
Definition: ImmutableMap.h:134
llvm::ImmutableMap::Factory
Definition: ImmutableMap.h:83
llvm::ImmutableMap::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableMap.h:195
llvm::ImutAVLTree::Factory
ImutAVLFactory< ImutInfo > Factory
Definition: ImmutableSet.h:48
llvm::ImmutableMapRef::getMaxElement
value_type * getMaxElement() const
getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...
Definition: ImmutableMap.h:311