1 //===--- ImmutableIntervalMap.h - Immutable (functional) map ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the ImmutableIntervalMap class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H
15 #define LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H
17 #include "llvm/ADT/ImmutableMap.h"
27 Interval(int64_t S, int64_t E) : Start(S), End(E) {}
29 int64_t getStart() const { return Start; }
30 int64_t getEnd() const { return End; }
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;
42 static key_type_ref KeyOfValue(value_type_ref V) {
46 static data_type_ref DataOfValue(value_type_ref V) {
50 static bool isEqual(key_type_ref L, key_type_ref R) {
51 return L.getStart() == R.getStart() && L.getEnd() == R.getEnd();
54 static bool isDataEqual(data_type_ref L, data_type_ref R) {
55 return ImutContainerInfo<T>::isEqual(L,R);
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());
63 } else if (L.getStart() == R.getStart()) {
64 assert(L.getEnd() == R.getEnd());
67 assert(L.getStart() > R.getEnd());
72 static bool isContainedIn(key_type_ref K, key_type_ref L) {
73 if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd())
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);
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;
97 ImutIntervalAVLFactory(BumpPtrAllocator &Alloc)
98 : ImutAVLFactory<ImutInfo>(Alloc) {}
100 TreeTy *Add(TreeTy *T, value_type_ref V) {
101 T = add_internal(V,T);
102 this->MarkImmutable(T);
106 TreeTy *Find(TreeTy *T, key_type_ref K) {
110 key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->getValue(T));
112 if (ImutInfo::isContainedIn(K, CurrentKey))
114 else if (ImutInfo::isLess(K, CurrentKey))
115 return Find(this->getLeft(T), K);
117 return Find(this->getRight(T), K);
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);
127 assert(!T->isMutable());
129 key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
131 if (ImutInfo::isLess(K, KCurrent))
132 return this->Balance(add_internal(V, this->Left(T)), this->Value(T),
135 return this->Balance(this->Left(T), this->Value(T),
136 add_internal(V, this->Right(T)));
139 // Remove all overlaps from T.
140 TreeTy *removeAllOverlaps(TreeTy *T, key_type_ref K) {
144 T = removeOverlap(T, K, Changed);
145 this->markImmutable(T);
151 // Remove one overlap from T.
152 TreeTy *removeOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
155 Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
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));
165 // Current key overlaps with the inserted key.
166 // Remove the current key.
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);
176 Interval NewK1(CurrentK.getStart(), K.getStart()-1);
177 T = add_internal(std::make_pair(NewK1, OldData), T);
179 Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
180 return add_internal(std::make_pair(NewK2, OldData), T);
183 if (CurrentK.getEnd() > K.getEnd()) {
184 Interval NewK(K.getEnd()+1, CurrentK.getEnd());
185 return add_internal(std::make_pair(NewK, OldData), T);
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> > {
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;
207 explicit ImmutableIntervalMap(TreeTy *R)
208 : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
211 ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
214 Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
216 ImmutableIntervalMap getEmptyMap() {
217 return ImmutableIntervalMap(F.getEmptyTree());
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));
226 ImmutableIntervalMap remove(ImmutableIntervalMap Old, key_type_ref K) {
227 TreeTy *T = F.remove(Old.Root, K);
228 return ImmutableIntervalMap(F.getCanonicalTree(T));
231 data_type *lookup(ImmutableIntervalMap M, key_type_ref K) {
232 TreeTy *T = F.Find(M.getRoot(), K);
234 return &T->getValue().second;
241 // For ImmutableIntervalMap, the lookup operation has to be done by the
243 data_type* lookup(key_type_ref K) const;
246 } // end namespace llvm