• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_IMMAP_H
15 #define LLVM_ADT_IMMAP_H
16 
17 #include "llvm/ADT/ImmutableSet.h"
18 
19 namespace llvm {
20 
21 /// ImutKeyValueInfo -Traits class used by ImmutableMap.  While both the first
22 /// and second elements in a pair are used to generate profile information,
23 /// only the first element (the key) is used by isEqual and isLess.
24 template <typename T, typename S>
25 struct ImutKeyValueInfo {
26   typedef const std::pair<T,S> value_type;
27   typedef const value_type& value_type_ref;
28   typedef const T   key_type;
29   typedef const T&  key_type_ref;
30   typedef const S   data_type;
31   typedef const S&  data_type_ref;
32 
KeyOfValueImutKeyValueInfo33   static inline key_type_ref KeyOfValue(value_type_ref V) {
34     return V.first;
35   }
36 
DataOfValueImutKeyValueInfo37   static inline data_type_ref DataOfValue(value_type_ref V) {
38     return V.second;
39   }
40 
isEqualImutKeyValueInfo41   static inline bool isEqual(key_type_ref L, key_type_ref R) {
42     return ImutContainerInfo<T>::isEqual(L,R);
43   }
isLessImutKeyValueInfo44   static inline bool isLess(key_type_ref L, key_type_ref R) {
45     return ImutContainerInfo<T>::isLess(L,R);
46   }
47 
isDataEqualImutKeyValueInfo48   static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
49     return ImutContainerInfo<S>::isEqual(L,R);
50   }
51 
ProfileImutKeyValueInfo52   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
53     ImutContainerInfo<T>::Profile(ID, V.first);
54     ImutContainerInfo<S>::Profile(ID, V.second);
55   }
56 };
57 
58 
59 template <typename KeyT, typename ValT,
60           typename ValInfo = ImutKeyValueInfo<KeyT,ValT> >
61 class ImmutableMap {
62 public:
63   typedef typename ValInfo::value_type      value_type;
64   typedef typename ValInfo::value_type_ref  value_type_ref;
65   typedef typename ValInfo::key_type        key_type;
66   typedef typename ValInfo::key_type_ref    key_type_ref;
67   typedef typename ValInfo::data_type       data_type;
68   typedef typename ValInfo::data_type_ref   data_type_ref;
69   typedef ImutAVLTree<ValInfo>              TreeTy;
70 
71 protected:
72   TreeTy* Root;
73 
74 public:
75   /// Constructs a map from a pointer to a tree root.  In general one
76   /// should use a Factory object to create maps instead of directly
77   /// invoking the constructor, but there are cases where make this
78   /// constructor public is useful.
ImmutableMap(const TreeTy * R)79   explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
80     if (Root) { Root->retain(); }
81   }
ImmutableMap(const ImmutableMap & X)82   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
83     if (Root) { Root->retain(); }
84   }
85   ImmutableMap &operator=(const ImmutableMap &X) {
86     if (Root != X.Root) {
87       if (X.Root) { X.Root->retain(); }
88       if (Root) { Root->release(); }
89       Root = X.Root;
90     }
91     return *this;
92   }
~ImmutableMap()93   ~ImmutableMap() {
94     if (Root) { Root->release(); }
95   }
96 
97   class Factory {
98     typename TreeTy::Factory F;
99     const bool Canonicalize;
100 
101   public:
102     Factory(bool canonicalize = true)
Canonicalize(canonicalize)103       : Canonicalize(canonicalize) {}
104 
105     Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
F(Alloc)106       : F(Alloc), Canonicalize(canonicalize) {}
107 
getEmptyMap()108     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
109 
add(ImmutableMap Old,key_type_ref K,data_type_ref D)110     ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
111       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
112       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
113     }
114 
remove(ImmutableMap Old,key_type_ref K)115     ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
116       TreeTy *T = F.remove(Old.Root,K);
117       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
118     }
119 
getTreeFactory()120     typename TreeTy::Factory *getTreeFactory() const {
121       return const_cast<typename TreeTy::Factory *>(&F);
122     }
123 
124   private:
125     Factory(const Factory& RHS); // DO NOT IMPLEMENT
126     void operator=(const Factory& RHS); // DO NOT IMPLEMENT
127   };
128 
contains(key_type_ref K)129   bool contains(key_type_ref K) const {
130     return Root ? Root->contains(K) : false;
131   }
132 
133   bool operator==(const ImmutableMap &RHS) const {
134     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
135   }
136 
137   bool operator!=(const ImmutableMap &RHS) const {
138     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
139   }
140 
getRoot()141   TreeTy *getRoot() const {
142     if (Root) { Root->retain(); }
143     return Root;
144   }
145 
getRootWithoutRetain()146   TreeTy *getRootWithoutRetain() const {
147     return Root;
148   }
149 
manualRetain()150   void manualRetain() {
151     if (Root) Root->retain();
152   }
153 
manualRelease()154   void manualRelease() {
155     if (Root) Root->release();
156   }
157 
isEmpty()158   bool isEmpty() const { return !Root; }
159 
160   //===--------------------------------------------------===//
161   // Foreach - A limited form of map iteration.
162   //===--------------------------------------------------===//
163 
164 private:
165   template <typename Callback>
166   struct CBWrapper {
167     Callback C;
operatorCBWrapper168     void operator()(value_type_ref V) { C(V.first,V.second); }
169   };
170 
171   template <typename Callback>
172   struct CBWrapperRef {
173     Callback &C;
CBWrapperRefCBWrapperRef174     CBWrapperRef(Callback& c) : C(c) {}
175 
operatorCBWrapperRef176     void operator()(value_type_ref V) { C(V.first,V.second); }
177   };
178 
179 public:
180   template <typename Callback>
foreach(Callback & C)181   void foreach(Callback& C) {
182     if (Root) {
183       CBWrapperRef<Callback> CB(C);
184       Root->foreach(CB);
185     }
186   }
187 
188   template <typename Callback>
foreach()189   void foreach() {
190     if (Root) {
191       CBWrapper<Callback> CB;
192       Root->foreach(CB);
193     }
194   }
195 
196   //===--------------------------------------------------===//
197   // For testing.
198   //===--------------------------------------------------===//
199 
verify()200   void verify() const { if (Root) Root->verify(); }
201 
202   //===--------------------------------------------------===//
203   // Iterators.
204   //===--------------------------------------------------===//
205 
206   class iterator {
207     typename TreeTy::iterator itr;
208 
iterator()209     iterator() {}
iterator(TreeTy * t)210     iterator(TreeTy* t) : itr(t) {}
211     friend class ImmutableMap;
212 
213   public:
214     value_type_ref operator*() const { return itr->getValue(); }
215     value_type*    operator->() const { return &itr->getValue(); }
216 
getKey()217     key_type_ref getKey() const { return itr->getValue().first; }
getData()218     data_type_ref getData() const { return itr->getValue().second; }
219 
220 
221     iterator& operator++() { ++itr; return *this; }
222     iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
223     iterator& operator--() { --itr; return *this; }
224     iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
225     bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
226     bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
227   };
228 
begin()229   iterator begin() const { return iterator(Root); }
end()230   iterator end() const { return iterator(); }
231 
lookup(key_type_ref K)232   data_type* lookup(key_type_ref K) const {
233     if (Root) {
234       TreeTy* T = Root->find(K);
235       if (T) return &T->getValue().second;
236     }
237 
238     return 0;
239   }
240 
241   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
242   ///  which key is the highest in the ordering of keys in the map.  This
243   ///  method returns NULL if the map is empty.
getMaxElement()244   value_type* getMaxElement() const {
245     return Root ? &(Root->getMaxElement()->getValue()) : 0;
246   }
247 
248   //===--------------------------------------------------===//
249   // Utility methods.
250   //===--------------------------------------------------===//
251 
getHeight()252   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
253 
Profile(FoldingSetNodeID & ID,const ImmutableMap & M)254   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
255     ID.AddPointer(M.Root);
256   }
257 
Profile(FoldingSetNodeID & ID)258   inline void Profile(FoldingSetNodeID& ID) const {
259     return Profile(ID,*this);
260   }
261 };
262 
263 // NOTE: This will possibly become the new implementation of ImmutableMap some day.
264 template <typename KeyT, typename ValT,
265 typename ValInfo = ImutKeyValueInfo<KeyT,ValT> >
266 class ImmutableMapRef {
267 public:
268   typedef typename ValInfo::value_type      value_type;
269   typedef typename ValInfo::value_type_ref  value_type_ref;
270   typedef typename ValInfo::key_type        key_type;
271   typedef typename ValInfo::key_type_ref    key_type_ref;
272   typedef typename ValInfo::data_type       data_type;
273   typedef typename ValInfo::data_type_ref   data_type_ref;
274   typedef ImutAVLTree<ValInfo>              TreeTy;
275   typedef typename TreeTy::Factory          FactoryTy;
276 
277 protected:
278   TreeTy *Root;
279   FactoryTy *Factory;
280 
281 public:
282   /// Constructs a map from a pointer to a tree root.  In general one
283   /// should use a Factory object to create maps instead of directly
284   /// invoking the constructor, but there are cases where make this
285   /// constructor public is useful.
ImmutableMapRef(const TreeTy * R,FactoryTy * F)286   explicit ImmutableMapRef(const TreeTy* R, FactoryTy *F)
287     : Root(const_cast<TreeTy*>(R)),
288       Factory(F) {
289     if (Root) { Root->retain(); }
290   }
291 
ImmutableMapRef(const ImmutableMapRef & X)292   ImmutableMapRef(const ImmutableMapRef &X)
293     : Root(X.Root),
294       Factory(X.Factory) {
295     if (Root) { Root->retain(); }
296   }
297 
298   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
299     if (Root != X.Root) {
300       if (X.Root)
301         X.Root->retain();
302 
303       if (Root)
304         Root->release();
305 
306       Root = X.Root;
307       Factory = X.Factory;
308     }
309     return *this;
310   }
311 
~ImmutableMapRef()312   ~ImmutableMapRef() {
313     if (Root)
314       Root->release();
315   }
316 
getEmptyMap(FactoryTy * F)317   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
318     return ImmutableMapRef(0, F);
319   }
320 
add(key_type_ref K,data_type_ref D)321   ImmutableMapRef add(key_type_ref K, data_type_ref D) {
322     TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
323     return ImmutableMapRef(NewT, Factory);
324   }
325 
remove(key_type_ref K)326   ImmutableMapRef remove(key_type_ref K) {
327     TreeTy *NewT = Factory->remove(Root, K);
328     return ImmutableMapRef(NewT, Factory);
329   }
330 
contains(key_type_ref K)331   bool contains(key_type_ref K) const {
332     return Root ? Root->contains(K) : false;
333   }
334 
asImmutableMap()335   ImmutableMap<KeyT, ValT> asImmutableMap() const {
336     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
337   }
338 
339   bool operator==(const ImmutableMapRef &RHS) const {
340     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
341   }
342 
343   bool operator!=(const ImmutableMapRef &RHS) const {
344     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
345   }
346 
isEmpty()347   bool isEmpty() const { return !Root; }
348 
349   //===--------------------------------------------------===//
350   // For testing.
351   //===--------------------------------------------------===//
352 
verify()353   void verify() const { if (Root) Root->verify(); }
354 
355   //===--------------------------------------------------===//
356   // Iterators.
357   //===--------------------------------------------------===//
358 
359   class iterator {
360     typename TreeTy::iterator itr;
361 
iterator()362     iterator() {}
iterator(TreeTy * t)363     iterator(TreeTy* t) : itr(t) {}
364     friend class ImmutableMapRef;
365 
366   public:
367     value_type_ref operator*() const { return itr->getValue(); }
368     value_type*    operator->() const { return &itr->getValue(); }
369 
getKey()370     key_type_ref getKey() const { return itr->getValue().first; }
getData()371     data_type_ref getData() const { return itr->getValue().second; }
372 
373 
374     iterator& operator++() { ++itr; return *this; }
375     iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
376     iterator& operator--() { --itr; return *this; }
377     iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
378     bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
379     bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
380   };
381 
begin()382   iterator begin() const { return iterator(Root); }
end()383   iterator end() const { return iterator(); }
384 
lookup(key_type_ref K)385   data_type* lookup(key_type_ref K) const {
386     if (Root) {
387       TreeTy* T = Root->find(K);
388       if (T) return &T->getValue().second;
389     }
390 
391     return 0;
392   }
393 
394   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
395   ///  which key is the highest in the ordering of keys in the map.  This
396   ///  method returns NULL if the map is empty.
getMaxElement()397   value_type* getMaxElement() const {
398     return Root ? &(Root->getMaxElement()->getValue()) : 0;
399   }
400 
401   //===--------------------------------------------------===//
402   // Utility methods.
403   //===--------------------------------------------------===//
404 
getHeight()405   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
406 
Profile(FoldingSetNodeID & ID,const ImmutableMapRef & M)407   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMapRef &M) {
408     ID.AddPointer(M.Root);
409   }
410 
Profile(FoldingSetNodeID & ID)411   inline void Profile(FoldingSetNodeID& ID) const {
412     return Profile(ID, *this);
413   }
414 };
415 
416 } // end namespace llvm
417 
418 #endif
419