14 #ifndef LLVM_ADT_IMMUTABLEINTERVALMAP_H
15 #define LLVM_ADT_IMMUTABLEINTERVALMAP_H
27 Interval(int64_t S, int64_t E) : Start(S), End(E) {}
30 int64_t
getEnd()
const {
return End; }
86 template <
typename ImutInfo>
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;
101 T = add_internal(V,T);
102 this->MarkImmutable(T);
110 key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->
getValue(T));
112 if (ImutInfo::isContainedIn(K, CurrentKey))
114 else if (ImutInfo::isLess(K, CurrentKey))
121 TreeTy *add_internal(value_type_ref V, TreeTy *
T) {
122 key_type_ref K = ImutInfo::KeyOfValue(V);
123 T = removeAllOverlaps(T, K);
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)));
140 TreeTy *removeAllOverlaps(TreeTy *T, key_type_ref K) {
144 T = removeOverlap(T, K, Changed);
152 TreeTy *removeOverlap(TreeTy *T, key_type_ref K,
bool &Changed) {
155 Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
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));
168 data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
169 T = this->Remove_internal(CurrentK, T);
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);
194 template <
typename ValT>
196 :
public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
222 TreeTy *T = F.add(Old.
Root, std::pair<key_type, data_type>(K, D));
227 TreeTy *T = F.remove(Old.Root, K);
243 data_type* lookup(key_type_ref K)
const;
Interval(int64_t S, int64_t E)
ImmutableIntervalMap getEmptyMap()
ImutIntervalAVLFactory(BumpPtrAllocator &Alloc)
data_type * lookup(ImmutableIntervalMap M, key_type_ref K)
static key_type_ref KeyOfValue(value_type_ref V)
void AddInteger(signed I)
ID
LLVM Calling Convention Representation.
Factory(BumpPtrAllocator &Alloc)
static bool isLess(key_type_ref L, key_type_ref R)
static bool isDataEqual(data_type_ref L, data_type_ref R)
void markImmutable(TreeTy *T)
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
const value_type & value_type_ref
ImmutableIntervalMap(TreeTy *R)
TreeTy * getRight(TreeTy *T) const
value_type_ref getValue(TreeTy *T) const
static void Profile(FoldingSetNodeID &ID, value_type_ref V)
static data_type_ref DataOfValue(value_type_ref V)
static bool isEqual(key_type_ref L, key_type_ref R)
TreeTy * Add(TreeTy *T, value_type_ref V)
const value_type & getValue() const
getValue - Returns the data value associated with the tree node.
bool isEmpty(TreeTy *T) const
TreeTy * Find(TreeTy *T, key_type_ref K)
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
LLVM Value Representation.
const Interval & key_type_ref
static bool isContainedIn(key_type_ref K, key_type_ref L)
ImmutableIntervalMap add(ImmutableIntervalMap Old, key_type_ref K, data_type_ref D)
const std::pair< Interval, T > value_type
TreeTy * getLeft(TreeTy *T) const