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
19namespace llvm {
20
21class Interval {
22private:
23  int64_t Start;
24  int64_t End;
25
26public:
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
33template <typename T>
34struct 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
86template <typename ImutInfo>
87class 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
96public:
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
120private:
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.
194template <typename ValT>
195class 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
206public:
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
240private:
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