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 void Profile(FoldingSetNodeID &ID, value_type_ref V) {
  69     ID.AddInteger(V.first.getStart());
  70     ID.AddInteger(V.first.getEnd());
  71     ImutProfileInfo<T>::Profile(ID, V.second);
  72   }
  73 };
  74
  75 template <typename ImutInfo> class ImutIntervalAVLFactory;
  76
  77 template <typename ImutInfo>
  78 class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
  79   typedef ImutAVLTree<ImutInfo> TreeTy;
  80   typedef typename ImutInfo::value_type     value_type;
  81   typedef typename ImutInfo::value_type_ref value_type_ref;
  82   typedef typename ImutInfo::key_type       key_type;
  83   typedef typename ImutInfo::key_type_ref   key_type_ref;
  84   typedef typename ImutInfo::data_type      data_type;
  85   typedef typename ImutInfo::data_type_ref  data_type_ref;
  86
  87 public:
  88   TreeTy *Add(TreeTy* T, value_type_ref V) {
  89     T = Add_internal(V,T);
  90     MarkImmutable(T);
  91     return T;
  92   }
  93
  94 private:
  95   TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
  96     key_type_ref K = ImutInfo::KeyOfValue(V);
  97     T = RemoveAllOverlaps(T, K);
  98     if (isEmpty(T))
  99       return CreateNode(NULL, V, NULL);
 100
 101     assert(!T->isMutable());
 102
 103     key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
 104
 105     if (ImutInfo::isLess(K, KCurrent))
 106       return Balance(Add_internal(V, Left(T)), Value(T), Right(T));
 107     else
 108       return Balance(Left(T), Value(T), Add_internal(V, Right(T)));
 109   }
 110
 111   // Remove all overlaps from T.
 112   TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
 113     TreeTy *OldTree, *NewTree;
 114     NewTree = T;
 115
 116     do {
 117       OldTree = NewTree;
 118       NewTree = RemoveOverlap(OldTree, K);
 119     } while (NewTree != OldTree);
 120
 121     return NewTree;
 122   }
 123
 124   // Remove one overlap from T.
 125   TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K) {
 126     if (!T)
 127       return NULL;
 128     Interval CurrentK = ImutInfo::KeyOfValue(Value(T));
 129
 130     // If current key does not overlap the inserted key.
 131     if (CurrentK.getStart() > K.getEnd())
 132       return RemoveOverlap(Left(T), K);
 133     else if (CurrentK.getEnd() < K.getStart())
 134       return RemoveOverlap(Right(T), K);
 135
 136     // Current key overlaps with the inserted key.
 137     // Remove the current key.
 138     TreeTy *OldNode = T;
 139     T = Remove_internal(CurrentK, T);
 140     // Add back the unoverlapped part of the current key.
 141     if (CurrentK.getStart() < K.getStart()) {
 142       if (CurrentK.getEnd() <= K.getEnd()) {
 143         Interval NewK(CurrentK.getStart(), K.getStart()-1);
 144         return Add_internal(std::make_pair<key_type, data_type>(NewK,
 145                                      ImutInfo::DataOfValue(Value(OldNode))), T);
 146       } else {
 147         Interval NewK1(CurrentK.getStart(), K.getStart()-1);
 148         T = Add_internal(std::make_pair<key_type, data_type>(NewK1,
 149                                      ImutInfo::DataOfValue(Value(OldNode))), T);
 150
 151         Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
 152         return Add_internal(std::make_pair<key_type, data_type>(NewK2,
 153                                      ImutInfo::DataOfValue(Value(OldNode))), T);
 154       }
 155     } else {
 156       if (CurrentK.getEnd() > K.getEnd()) {
 157         Interval NewK(K.getEnd()+1, CurrentK.getEnd());
 158         return Add_internal(std::make_pair<key_type, data_type>(NewK,
 159                                      ImutInfo::DataOfValue(Value(OldNode))), T);
 160       }
 161     }
 162   }
 163 };
 164
 165 /// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals
 166 /// in the map are guaranteed to be disjoint.
 167 template <typename ValT>
 168 class ImmutableIntervalMap
 169   : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
 170
 171   typedef typename ImutIntervalInfo<ValT>::value_type      value_type;
 172   typedef typename ImutIntervalInfo<ValT>::value_type_ref  value_type_ref;
 173   typedef typename ImutIntervalInfo<ValT>::key_type        key_type;
 174   typedef typename ImutIntervalInfo<ValT>::key_type_ref    key_type_ref;
 175   typedef typename ImutIntervalInfo<ValT>::data_type       data_type;
 176   typedef typename ImutIntervalInfo<ValT>::data_type_ref   data_type_ref;
 177   typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy;
 178
 179 public:
 180   explicit ImmutableIntervalMap(TreeTy *R)
 181     : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
 182
 183   class Factory {
 184     ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
 185
 186   public:
 187     ImmutableIntervalMap GetEmptyMap() {
 188       return ImmutableIntervalMap(F.GetEmptyTree());
 189     }
 190
 191     ImmutableIntervalMap Add(ImmutableIntervalMap Old,
 192                              key_type_ref K, data_type_ref D) {
 193       TreeTy *T = F.Add(Old.Root, std::make_pair<key_type, data_type>(K, D));
 194       return ImmutableIntervalMap(F.GetCanonicalTree(T));
 195     }
 196
 197     ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
 198       TreeTy *T = F.Remove(Old.Root, K);
 199       return ImmutableIntervalMap(F.GetCanonicalTree(T));
 200     }
 201   };
 202 };
 203
 204 } // end namespace llvm