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 
81   class Factory {
82     typename TreeTy::Factory F;
83     const bool Canonicalize;
84 
85   public:
86     Factory(bool canonicalize = true)
Canonicalize(canonicalize)87       : Canonicalize(canonicalize) {}
88 
89     Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
F(Alloc)90       : F(Alloc), Canonicalize(canonicalize) {}
91 
GetEmptyMap()92     ImmutableMap GetEmptyMap() { return ImmutableMap(F.GetEmptyTree()); }
93 
Add(ImmutableMap Old,key_type_ref K,data_type_ref D)94     ImmutableMap Add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
95       TreeTy *T = F.Add(Old.Root, std::pair<key_type,data_type>(K,D));
96       return ImmutableMap(Canonicalize ? F.GetCanonicalTree(T): T);
97     }
98 
Remove(ImmutableMap Old,key_type_ref K)99     ImmutableMap Remove(ImmutableMap Old, key_type_ref K) {
100       TreeTy *T = F.Remove(Old.Root,K);
101       return ImmutableMap(Canonicalize ? F.GetCanonicalTree(T): T);
102     }
103 
104   private:
105     Factory(const Factory& RHS); // DO NOT IMPLEMENT
106     void operator=(const Factory& RHS); // DO NOT IMPLEMENT
107   };
108 
contains(key_type_ref K)109   bool contains(key_type_ref K) const {
110     return Root ? Root->contains(K) : false;
111   }
112 
113   bool operator==(ImmutableMap RHS) const {
114     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
115   }
116 
117   bool operator!=(ImmutableMap RHS) const {
118     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
119   }
120 
getRoot()121   TreeTy* getRoot() const { return Root; }
122 
isEmpty()123   bool isEmpty() const { return !Root; }
124 
125   //===--------------------------------------------------===//
126   // Foreach - A limited form of map iteration.
127   //===--------------------------------------------------===//
128 
129 private:
130   template <typename Callback>
131   struct CBWrapper {
132     Callback C;
operatorCBWrapper133     void operator()(value_type_ref V) { C(V.first,V.second); }
134   };
135 
136   template <typename Callback>
137   struct CBWrapperRef {
138     Callback &C;
CBWrapperRefCBWrapperRef139     CBWrapperRef(Callback& c) : C(c) {}
140 
operatorCBWrapperRef141     void operator()(value_type_ref V) { C(V.first,V.second); }
142   };
143 
144 public:
145   template <typename Callback>
foreach(Callback & C)146   void foreach(Callback& C) {
147     if (Root) {
148       CBWrapperRef<Callback> CB(C);
149       Root->foreach(CB);
150     }
151   }
152 
153   template <typename Callback>
foreach()154   void foreach() {
155     if (Root) {
156       CBWrapper<Callback> CB;
157       Root->foreach(CB);
158     }
159   }
160 
161   //===--------------------------------------------------===//
162   // For testing.
163   //===--------------------------------------------------===//
164 
verify()165   void verify() const { if (Root) Root->verify(); }
166 
167   //===--------------------------------------------------===//
168   // Iterators.
169   //===--------------------------------------------------===//
170 
171   class iterator {
172     typename TreeTy::iterator itr;
173 
iterator()174     iterator() {}
iterator(TreeTy * t)175     iterator(TreeTy* t) : itr(t) {}
176     friend class ImmutableMap;
177 
178   public:
179     value_type_ref operator*() const { return itr->getValue(); }
180     value_type*    operator->() const { return &itr->getValue(); }
181 
getKey()182     key_type_ref getKey() const { return itr->getValue().first; }
getData()183     data_type_ref getData() const { return itr->getValue().second; }
184 
185 
186     iterator& operator++() { ++itr; return *this; }
187     iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
188     iterator& operator--() { --itr; return *this; }
189     iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
190     bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
191     bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
192   };
193 
begin()194   iterator begin() const { return iterator(Root); }
end()195   iterator end() const { return iterator(); }
196 
lookup(key_type_ref K)197   data_type* lookup(key_type_ref K) const {
198     if (Root) {
199       TreeTy* T = Root->find(K);
200       if (T) return &T->getValue().second;
201     }
202 
203     return 0;
204   }
205 
206   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
207   ///  which key is the highest in the ordering of keys in the map.  This
208   ///  method returns NULL if the map is empty.
getMaxElement()209   value_type* getMaxElement() const {
210     return Root ? &(Root->getMaxElement()->getValue()) : 0;
211   }
212 
213   //===--------------------------------------------------===//
214   // Utility methods.
215   //===--------------------------------------------------===//
216 
getHeight()217   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
218 
Profile(FoldingSetNodeID & ID,const ImmutableMap & M)219   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
220     ID.AddPointer(M.Root);
221   }
222 
Profile(FoldingSetNodeID & ID)223   inline void Profile(FoldingSetNodeID& ID) const {
224     return Profile(ID,*this);
225   }
226 };
227 
228 } // end namespace llvm
229 
230 #endif
231