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 #include "llvm/ADT/ImmutableMap.h"
  14
  15 namespace llvm {
  16
  17 class Interval {
  18 private:
  19   uint64_t Start;
  20   uint64_t End;
  21
  22 public:
  23   Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
  24
  25   uint64_t getStart() const { return Start; }
  26   uint64_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
  38   static key_type_ref KeyOfValue(value_type_ref V) {
  39     return V.first;
  40   }
  41
  42   static data_type_ref DataOfValue(value_type_ref V) {
  43     return V.second;
  44   }
  45
  46   static bool isEqual(key_type_ref L, key_type_ref R) {
  47     return L.getStart() == R.getStart() && L.getEnd() == R.getEnd();
  48   }
  49
  50   static bool isDataEqual(data_type_ref L, data_type_ref R) {
  51     return ImutContainerInfo<T>::isEqual(L,R);
  52   }
  53
  54   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
  68   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
  75   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:
  93   ImutIntervalAVLFactory(BumpPtrAllocator &Alloc)
  94     : ImutAVLFactory<ImutInfo>(Alloc) {}
  95
  96   TreeTy *Add(TreeTy *T, value_type_ref V) {
  97     T = Add_internal(V,T);
  98     this->MarkImmutable(T);
  99     return T;
 100   }
 101
 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:
 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), this->Right(T));
 129     else
 130       return this->Balance(this->Left(T), this->Value(T), Add_internal(V, this->Right(T)));
 131   }
 132
 133   // Remove all overlaps from T.
 134   TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
 135     bool Changed;
 136     do {
 137       Changed = false;
 138       T = RemoveOverlap(T, K, Changed);
 139       this->MarkImmutable(T);
 140     } while (Changed);
 141
 142     return T;
 143   }
 144
 145   // Remove one overlap from T.
 146   TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
 147     if (!T)
 148       return NULL;
 149     Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
 150
 151     // If current key does not overlap the inserted key.
 152     if (CurrentK.getStart() > K.getEnd())
 153       return this->Balance(RemoveOverlap(this->Left(T), K, Changed), this->Value(T), this->Right(T));
 154     else if (CurrentK.getEnd() < K.getStart())
 155       return this->Balance(this->Left(T), this->Value(T), RemoveOverlap(this->Right(T), K, Changed));
 156
 157     // Current key overlaps with the inserted key.
 158     // Remove the current key.
 159     Changed = true;
 160     data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
 161     T = this->Remove_internal(CurrentK, T);
 162     // Add back the unoverlapped part of the current key.
 163     if (CurrentK.getStart() < K.getStart()) {
 164       if (CurrentK.getEnd() <= K.getEnd()) {
 165         Interval NewK(CurrentK.getStart(), K.getStart()-1);
 166         return Add_internal(std::make_pair(NewK, OldData), T);
 167       } else {
 168         Interval NewK1(CurrentK.getStart(), K.getStart()-1);
 169         T = Add_internal(std::make_pair(NewK1, OldData), T);
 170
 171         Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
 172         return Add_internal(std::make_pair(NewK2, OldData), T);
 173       }
 174     } else {
 175       if (CurrentK.getEnd() > K.getEnd()) {
 176         Interval NewK(K.getEnd()+1, CurrentK.getEnd());
 177         return Add_internal(std::make_pair(NewK, OldData), T);
 178       } else
 179         return T;
 180     }
 181   }
 182 };
 183
 184 /// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals
 185 /// in the map are guaranteed to be disjoint.
 186 template <typename ValT>
 187 class ImmutableIntervalMap
 188   : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
 189
 190   typedef typename ImutIntervalInfo<ValT>::value_type      value_type;
 191   typedef typename ImutIntervalInfo<ValT>::value_type_ref  value_type_ref;
 192   typedef typename ImutIntervalInfo<ValT>::key_type        key_type;
 193   typedef typename ImutIntervalInfo<ValT>::key_type_ref    key_type_ref;
 194   typedef typename ImutIntervalInfo<ValT>::data_type       data_type;
 195   typedef typename ImutIntervalInfo<ValT>::data_type_ref   data_type_ref;
 196   typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy;
 197
 198 public:
 199   explicit ImmutableIntervalMap(TreeTy *R)
 200     : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
 201
 202   class Factory {
 203     ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
 204
 205   public:
 206     Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
 207
 208     ImmutableIntervalMap GetEmptyMap() {
 209       return ImmutableIntervalMap(F.GetEmptyTree());
 210     }
 211
 212     ImmutableIntervalMap Add(ImmutableIntervalMap Old,
 213                              key_type_ref K, data_type_ref D) {
 214       TreeTy *T = F.Add(Old.Root, std::make_pair<key_type, data_type>(K, D));
 215       return ImmutableIntervalMap(F.GetCanonicalTree(T));
 216     }
 217
 218     ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
 219       TreeTy *T = F.Remove(Old.Root, K);
 220       return ImmutableIntervalMap(F.GetCanonicalTree(T));
 221     }
 222
 223     data_type *Lookup(ImmutableIntervalMap M, key_type_ref K) {
 224       TreeTy *T = F.Find(M.getRoot(), K);
 225       if (T)
 226         return &T->getValue().second;
 227       else
 228         return 0;
 229     }
 230   };
 231
 232 private:
 233   // For ImmutableIntervalMap, the lookup operation has to be done by the
 234   // factory.
 235   data_type* lookup(key_type_ref K) const;
 236 };
 237
 238 } // end namespace llvm