1 //===--- ImmutableIntervalMap.h - Immutable (functional) map  ---*- 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 ImmutableIntervalMap class.
11 //
12 //===----------------------------------------------------------------------===//
13 #include "llvm/ADT/ImmutableMap.h"
14 
15 namespace llvm {
16 
17 class Interval {
18 private:
19   int64_t Start;
20   int64_t End;
21 
22 public:
Interval(int64_t S,int64_t E)23   Interval(int64_t S, int64_t E) : Start(S), End(E) {}
24 
getStart()25   int64_t getStart() const { return Start; }
getEnd()26   int64_t getEnd() const { return End; }
27 };
28 
29 template <typename T>
30 struct ImutIntervalInfo {
31   typedef const std::pair<Interval, T> value_type;
32   typedef const value_type &value_type_ref;
33   typedef const Interval key_type;
34   typedef const Interval &key_type_ref;
35   typedef const T data_type;
36   typedef const T &data_type_ref;
37 
KeyOfValueImutIntervalInfo38   static key_type_ref KeyOfValue(value_type_ref V) {
39     return V.first;
40   }
41 
DataOfValueImutIntervalInfo42   static data_type_ref DataOfValue(value_type_ref V) {
43     return V.second;
44   }
45 
isEqualImutIntervalInfo46   static bool isEqual(key_type_ref L, key_type_ref R) {
47     return L.getStart() == R.getStart() && L.getEnd() == R.getEnd();
48   }
49 
isDataEqualImutIntervalInfo50   static bool isDataEqual(data_type_ref L, data_type_ref R) {
51     return ImutContainerInfo<T>::isEqual(L,R);
52   }
53 
isLessImutIntervalInfo54   static bool isLess(key_type_ref L, key_type_ref R) {
55     // Assume L and R does not overlap.
56     if (L.getStart() < R.getStart()) {
57       assert(L.getEnd() < R.getStart());
58       return true;
59     } else if (L.getStart() == R.getStart()) {
60       assert(L.getEnd() == R.getEnd());
61       return false;
62     } else {
63       assert(L.getStart() > R.getEnd());
64       return false;
65     }
66   }
67 
isContainedInImutIntervalInfo68   static bool isContainedIn(key_type_ref K, key_type_ref L) {
69     if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd())
70       return true;
71     else
72       return false;
73   }
74 
ProfileImutIntervalInfo75   static void Profile(FoldingSetNodeID &ID, value_type_ref V) {
76     ID.AddInteger(V.first.getStart());
77     ID.AddInteger(V.first.getEnd());
78     ImutProfileInfo<T>::Profile(ID, V.second);
79   }
80 };
81 
82 template <typename ImutInfo>
83 class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
84   typedef ImutAVLTree<ImutInfo> TreeTy;
85   typedef typename ImutInfo::value_type     value_type;
86   typedef typename ImutInfo::value_type_ref value_type_ref;
87   typedef typename ImutInfo::key_type       key_type;
88   typedef typename ImutInfo::key_type_ref   key_type_ref;
89   typedef typename ImutInfo::data_type      data_type;
90   typedef typename ImutInfo::data_type_ref  data_type_ref;
91 
92 public:
ImutIntervalAVLFactory(BumpPtrAllocator & Alloc)93   ImutIntervalAVLFactory(BumpPtrAllocator &Alloc)
94     : ImutAVLFactory<ImutInfo>(Alloc) {}
95 
Add(TreeTy * T,value_type_ref V)96   TreeTy *Add(TreeTy *T, value_type_ref V) {
97     T = Add_internal(V,T);
98     this->MarkImmutable(T);
99     return T;
100   }
101 
Find(TreeTy * T,key_type_ref K)102   TreeTy *Find(TreeTy *T, key_type_ref K) {
103     if (!T)
104       return NULL;
105 
106     key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->Value(T));
107 
108     if (ImutInfo::isContainedIn(K, CurrentKey))
109       return T;
110     else if (ImutInfo::isLess(K, CurrentKey))
111       return Find(this->Left(T), K);
112     else
113       return Find(this->Right(T), K);
114   }
115 
116 private:
Add_internal(value_type_ref V,TreeTy * T)117   TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
118     key_type_ref K = ImutInfo::KeyOfValue(V);
119     T = RemoveAllOverlaps(T, K);
120     if (this->isEmpty(T))
121       return this->CreateNode(NULL, V, NULL);
122 
123     assert(!T->isMutable());
124 
125     key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
126 
127     if (ImutInfo::isLess(K, KCurrent))
128       return this->Balance(Add_internal(V, this->Left(T)), this->Value(T),
129                                         this->Right(T));
130     else
131       return this->Balance(this->Left(T), this->Value(T),
132                            Add_internal(V, this->Right(T)));
133   }
134 
135   // Remove all overlaps from T.
RemoveAllOverlaps(TreeTy * T,key_type_ref K)136   TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
137     bool Changed;
138     do {
139       Changed = false;
140       T = RemoveOverlap(T, K, Changed);
141       this->MarkImmutable(T);
142     } while (Changed);
143 
144     return T;
145   }
146 
147   // Remove one overlap from T.
RemoveOverlap(TreeTy * T,key_type_ref K,bool & Changed)148   TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
149     if (!T)
150       return NULL;
151     Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
152 
153     // If current key does not overlap the inserted key.
154     if (CurrentK.getStart() > K.getEnd())
155       return this->Balance(RemoveOverlap(this->Left(T), K, Changed),
156                            this->Value(T), this->Right(T));
157     else if (CurrentK.getEnd() < K.getStart())
158       return this->Balance(this->Left(T), this->Value(T),
159                            RemoveOverlap(this->Right(T), K, Changed));
160 
161     // Current key overlaps with the inserted key.
162     // Remove the current key.
163     Changed = true;
164     data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
165     T = this->Remove_internal(CurrentK, T);
166     // Add back the unoverlapped part of the current key.
167     if (CurrentK.getStart() < K.getStart()) {
168       if (CurrentK.getEnd() <= K.getEnd()) {
169         Interval NewK(CurrentK.getStart(), K.getStart()-1);
170         return Add_internal(std::make_pair(NewK, OldData), T);
171       } else {
172         Interval NewK1(CurrentK.getStart(), K.getStart()-1);
173         T = Add_internal(std::make_pair(NewK1, OldData), T);
174 
175         Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
176         return Add_internal(std::make_pair(NewK2, OldData), T);
177       }
178     } else {
179       if (CurrentK.getEnd() > K.getEnd()) {
180         Interval NewK(K.getEnd()+1, CurrentK.getEnd());
181         return Add_internal(std::make_pair(NewK, OldData), T);
182       } else
183         return T;
184     }
185   }
186 };
187 
188 /// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals
189 /// in the map are guaranteed to be disjoint.
190 template <typename ValT>
191 class ImmutableIntervalMap
192   : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
193 
194   typedef typename ImutIntervalInfo<ValT>::value_type      value_type;
195   typedef typename ImutIntervalInfo<ValT>::value_type_ref  value_type_ref;
196   typedef typename ImutIntervalInfo<ValT>::key_type        key_type;
197   typedef typename ImutIntervalInfo<ValT>::key_type_ref    key_type_ref;
198   typedef typename ImutIntervalInfo<ValT>::data_type       data_type;
199   typedef typename ImutIntervalInfo<ValT>::data_type_ref   data_type_ref;
200   typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy;
201 
202 public:
ImmutableIntervalMap(TreeTy * R)203   explicit ImmutableIntervalMap(TreeTy *R)
204     : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
205 
206   class Factory {
207     ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
208 
209   public:
Factory(BumpPtrAllocator & Alloc)210     Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
211 
GetEmptyMap()212     ImmutableIntervalMap GetEmptyMap() {
213       return ImmutableIntervalMap(F.GetEmptyTree());
214     }
215 
Add(ImmutableIntervalMap Old,key_type_ref K,data_type_ref D)216     ImmutableIntervalMap Add(ImmutableIntervalMap Old,
217                              key_type_ref K, data_type_ref D) {
218       TreeTy *T = F.Add(Old.Root, std::pair<key_type, data_type>(K, D));
219       return ImmutableIntervalMap(F.GetCanonicalTree(T));
220     }
221 
Remove(ImmutableIntervalMap Old,key_type_ref K)222     ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
223       TreeTy *T = F.Remove(Old.Root, K);
224       return ImmutableIntervalMap(F.GetCanonicalTree(T));
225     }
226 
Lookup(ImmutableIntervalMap M,key_type_ref K)227     data_type *Lookup(ImmutableIntervalMap M, key_type_ref K) {
228       TreeTy *T = F.Find(M.getRoot(), K);
229       if (T)
230         return &T->getValue().second;
231       else
232         return 0;
233     }
234   };
235 
236 private:
237   // For ImmutableIntervalMap, the lookup operation has to be done by the
238   // factory.
239   data_type* lookup(key_type_ref K) const;
240 };
241 
242 } // end namespace llvm
243