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