include/llvm/ADT/ImmutableIntervalMap.h

   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_IMMUTABLEINTERVALMAP_H
  15 #define LLVM_ADT_IMMUTABLEINTERVALMAP_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