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