1203954Srdivacky//===--- ImmutableIntervalMap.h - Immutable (functional) map ---*- C++ -*-===// 2203954Srdivacky// 3203954Srdivacky// The LLVM Compiler Infrastructure 4203954Srdivacky// 5203954Srdivacky// This file is distributed under the University of Illinois Open Source 6203954Srdivacky// License. See LICENSE.TXT for details. 7203954Srdivacky// 8203954Srdivacky//===----------------------------------------------------------------------===// 9203954Srdivacky// 10203954Srdivacky// This file defines the ImmutableIntervalMap class. 11203954Srdivacky// 12203954Srdivacky//===----------------------------------------------------------------------===// 13221345Sdim 14249423Sdim#ifndef LLVM_ADT_IMMUTABLEINTERVALMAP_H 15249423Sdim#define LLVM_ADT_IMMUTABLEINTERVALMAP_H 16221345Sdim 17203954Srdivacky#include "llvm/ADT/ImmutableMap.h" 18203954Srdivacky 19203954Srdivackynamespace llvm { 20203954Srdivacky 21203954Srdivackyclass Interval { 22203954Srdivackyprivate: 23212904Sdim int64_t Start; 24212904Sdim int64_t End; 25203954Srdivacky 26203954Srdivackypublic: 27212904Sdim Interval(int64_t S, int64_t E) : Start(S), End(E) {} 28203954Srdivacky 29212904Sdim int64_t getStart() const { return Start; } 30212904Sdim int64_t getEnd() const { return End; } 31203954Srdivacky}; 32203954Srdivacky 33203954Srdivackytemplate <typename T> 34203954Srdivackystruct ImutIntervalInfo { 35203954Srdivacky typedef const std::pair<Interval, T> value_type; 36203954Srdivacky typedef const value_type &value_type_ref; 37203954Srdivacky typedef const Interval key_type; 38203954Srdivacky typedef const Interval &key_type_ref; 39203954Srdivacky typedef const T data_type; 40203954Srdivacky typedef const T &data_type_ref; 41203954Srdivacky 42203954Srdivacky static key_type_ref KeyOfValue(value_type_ref V) { 43203954Srdivacky return V.first; 44203954Srdivacky } 45203954Srdivacky 46203954Srdivacky static data_type_ref DataOfValue(value_type_ref V) { 47203954Srdivacky return V.second; 48203954Srdivacky } 49203954Srdivacky 50203954Srdivacky static bool isEqual(key_type_ref L, key_type_ref R) { 51203954Srdivacky return L.getStart() == R.getStart() && L.getEnd() == R.getEnd(); 52203954Srdivacky } 53203954Srdivacky 54203954Srdivacky static bool isDataEqual(data_type_ref L, data_type_ref R) { 55203954Srdivacky return ImutContainerInfo<T>::isEqual(L,R); 56203954Srdivacky } 57203954Srdivacky 58203954Srdivacky static bool isLess(key_type_ref L, key_type_ref R) { 59203954Srdivacky // Assume L and R does not overlap. 60203954Srdivacky if (L.getStart() < R.getStart()) { 61203954Srdivacky assert(L.getEnd() < R.getStart()); 62203954Srdivacky return true; 63203954Srdivacky } else if (L.getStart() == R.getStart()) { 64203954Srdivacky assert(L.getEnd() == R.getEnd()); 65203954Srdivacky return false; 66203954Srdivacky } else { 67203954Srdivacky assert(L.getStart() > R.getEnd()); 68203954Srdivacky return false; 69203954Srdivacky } 70203954Srdivacky } 71203954Srdivacky 72203954Srdivacky static bool isContainedIn(key_type_ref K, key_type_ref L) { 73203954Srdivacky if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd()) 74203954Srdivacky return true; 75203954Srdivacky else 76203954Srdivacky return false; 77203954Srdivacky } 78203954Srdivacky 79203954Srdivacky static void Profile(FoldingSetNodeID &ID, value_type_ref V) { 80203954Srdivacky ID.AddInteger(V.first.getStart()); 81203954Srdivacky ID.AddInteger(V.first.getEnd()); 82203954Srdivacky ImutProfileInfo<T>::Profile(ID, V.second); 83203954Srdivacky } 84203954Srdivacky}; 85203954Srdivacky 86203954Srdivackytemplate <typename ImutInfo> 87203954Srdivackyclass ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> { 88203954Srdivacky typedef ImutAVLTree<ImutInfo> TreeTy; 89203954Srdivacky typedef typename ImutInfo::value_type value_type; 90203954Srdivacky typedef typename ImutInfo::value_type_ref value_type_ref; 91203954Srdivacky typedef typename ImutInfo::key_type key_type; 92203954Srdivacky typedef typename ImutInfo::key_type_ref key_type_ref; 93203954Srdivacky typedef typename ImutInfo::data_type data_type; 94203954Srdivacky typedef typename ImutInfo::data_type_ref data_type_ref; 95203954Srdivacky 96203954Srdivackypublic: 97203954Srdivacky ImutIntervalAVLFactory(BumpPtrAllocator &Alloc) 98203954Srdivacky : ImutAVLFactory<ImutInfo>(Alloc) {} 99203954Srdivacky 100203954Srdivacky TreeTy *Add(TreeTy *T, value_type_ref V) { 101218893Sdim T = add_internal(V,T); 102203954Srdivacky this->MarkImmutable(T); 103203954Srdivacky return T; 104203954Srdivacky } 105203954Srdivacky 106203954Srdivacky TreeTy *Find(TreeTy *T, key_type_ref K) { 107203954Srdivacky if (!T) 108203954Srdivacky return NULL; 109203954Srdivacky 110218893Sdim key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->getValue(T)); 111203954Srdivacky 112203954Srdivacky if (ImutInfo::isContainedIn(K, CurrentKey)) 113203954Srdivacky return T; 114203954Srdivacky else if (ImutInfo::isLess(K, CurrentKey)) 115218893Sdim return Find(this->getLeft(T), K); 116203954Srdivacky else 117218893Sdim return Find(this->getRight(T), K); 118203954Srdivacky } 119203954Srdivacky 120203954Srdivackyprivate: 121218893Sdim TreeTy *add_internal(value_type_ref V, TreeTy *T) { 122203954Srdivacky key_type_ref K = ImutInfo::KeyOfValue(V); 123218893Sdim T = removeAllOverlaps(T, K); 124203954Srdivacky if (this->isEmpty(T)) 125203954Srdivacky return this->CreateNode(NULL, V, NULL); 126203954Srdivacky 127203954Srdivacky assert(!T->isMutable()); 128203954Srdivacky 129203954Srdivacky key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T)); 130203954Srdivacky 131203954Srdivacky if (ImutInfo::isLess(K, KCurrent)) 132218893Sdim return this->Balance(add_internal(V, this->Left(T)), this->Value(T), 133210299Sed this->Right(T)); 134203954Srdivacky else 135210299Sed return this->Balance(this->Left(T), this->Value(T), 136218893Sdim add_internal(V, this->Right(T))); 137203954Srdivacky } 138203954Srdivacky 139203954Srdivacky // Remove all overlaps from T. 140218893Sdim TreeTy *removeAllOverlaps(TreeTy *T, key_type_ref K) { 141203954Srdivacky bool Changed; 142203954Srdivacky do { 143203954Srdivacky Changed = false; 144218893Sdim T = removeOverlap(T, K, Changed); 145218893Sdim this->markImmutable(T); 146203954Srdivacky } while (Changed); 147203954Srdivacky 148203954Srdivacky return T; 149203954Srdivacky } 150203954Srdivacky 151203954Srdivacky // Remove one overlap from T. 152218893Sdim TreeTy *removeOverlap(TreeTy *T, key_type_ref K, bool &Changed) { 153203954Srdivacky if (!T) 154203954Srdivacky return NULL; 155203954Srdivacky Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T)); 156203954Srdivacky 157203954Srdivacky // If current key does not overlap the inserted key. 158203954Srdivacky if (CurrentK.getStart() > K.getEnd()) 159218893Sdim return this->Balance(removeOverlap(this->Left(T), K, Changed), 160210299Sed this->Value(T), this->Right(T)); 161203954Srdivacky else if (CurrentK.getEnd() < K.getStart()) 162210299Sed return this->Balance(this->Left(T), this->Value(T), 163218893Sdim removeOverlap(this->Right(T), K, Changed)); 164203954Srdivacky 165203954Srdivacky // Current key overlaps with the inserted key. 166203954Srdivacky // Remove the current key. 167203954Srdivacky Changed = true; 168203954Srdivacky data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T)); 169203954Srdivacky T = this->Remove_internal(CurrentK, T); 170203954Srdivacky // Add back the unoverlapped part of the current key. 171203954Srdivacky if (CurrentK.getStart() < K.getStart()) { 172203954Srdivacky if (CurrentK.getEnd() <= K.getEnd()) { 173203954Srdivacky Interval NewK(CurrentK.getStart(), K.getStart()-1); 174218893Sdim return add_internal(std::make_pair(NewK, OldData), T); 175203954Srdivacky } else { 176203954Srdivacky Interval NewK1(CurrentK.getStart(), K.getStart()-1); 177218893Sdim T = add_internal(std::make_pair(NewK1, OldData), T); 178203954Srdivacky 179203954Srdivacky Interval NewK2(K.getEnd()+1, CurrentK.getEnd()); 180218893Sdim return add_internal(std::make_pair(NewK2, OldData), T); 181203954Srdivacky } 182203954Srdivacky } else { 183203954Srdivacky if (CurrentK.getEnd() > K.getEnd()) { 184203954Srdivacky Interval NewK(K.getEnd()+1, CurrentK.getEnd()); 185218893Sdim return add_internal(std::make_pair(NewK, OldData), T); 186203954Srdivacky } else 187203954Srdivacky return T; 188203954Srdivacky } 189203954Srdivacky } 190203954Srdivacky}; 191203954Srdivacky 192203954Srdivacky/// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals 193203954Srdivacky/// in the map are guaranteed to be disjoint. 194203954Srdivackytemplate <typename ValT> 195203954Srdivackyclass ImmutableIntervalMap 196203954Srdivacky : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > { 197203954Srdivacky 198203954Srdivacky typedef typename ImutIntervalInfo<ValT>::value_type value_type; 199203954Srdivacky typedef typename ImutIntervalInfo<ValT>::value_type_ref value_type_ref; 200203954Srdivacky typedef typename ImutIntervalInfo<ValT>::key_type key_type; 201203954Srdivacky typedef typename ImutIntervalInfo<ValT>::key_type_ref key_type_ref; 202203954Srdivacky typedef typename ImutIntervalInfo<ValT>::data_type data_type; 203203954Srdivacky typedef typename ImutIntervalInfo<ValT>::data_type_ref data_type_ref; 204203954Srdivacky typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy; 205203954Srdivacky 206203954Srdivackypublic: 207203954Srdivacky explicit ImmutableIntervalMap(TreeTy *R) 208203954Srdivacky : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {} 209203954Srdivacky 210203954Srdivacky class Factory { 211203954Srdivacky ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F; 212203954Srdivacky 213203954Srdivacky public: 214203954Srdivacky Factory(BumpPtrAllocator& Alloc) : F(Alloc) {} 215203954Srdivacky 216218893Sdim ImmutableIntervalMap getEmptyMap() { 217218893Sdim return ImmutableIntervalMap(F.getEmptyTree()); 218203954Srdivacky } 219203954Srdivacky 220218893Sdim ImmutableIntervalMap add(ImmutableIntervalMap Old, 221203954Srdivacky key_type_ref K, data_type_ref D) { 222219077Sdim TreeTy *T = F.add(Old.Root, std::pair<key_type, data_type>(K, D)); 223218893Sdim return ImmutableIntervalMap(F.getCanonicalTree(T)); 224203954Srdivacky } 225203954Srdivacky 226218893Sdim ImmutableIntervalMap remove(ImmutableIntervalMap Old, key_type_ref K) { 227218893Sdim TreeTy *T = F.remove(Old.Root, K); 228218893Sdim return ImmutableIntervalMap(F.getCanonicalTree(T)); 229203954Srdivacky } 230203954Srdivacky 231218893Sdim data_type *lookup(ImmutableIntervalMap M, key_type_ref K) { 232203954Srdivacky TreeTy *T = F.Find(M.getRoot(), K); 233203954Srdivacky if (T) 234203954Srdivacky return &T->getValue().second; 235203954Srdivacky else 236203954Srdivacky return 0; 237203954Srdivacky } 238203954Srdivacky }; 239203954Srdivacky 240203954Srdivackyprivate: 241203954Srdivacky // For ImmutableIntervalMap, the lookup operation has to be done by the 242203954Srdivacky // factory. 243203954Srdivacky data_type* lookup(key_type_ref K) const; 244203954Srdivacky}; 245203954Srdivacky 246203954Srdivacky} // end namespace llvm 247221345Sdim 248221345Sdim#endif 249