// This file defines the ImmutableIntervalMap class.
//
//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H
+#define LLVM_ADT_IMMUTABLE_INTERVAL_MAP_H
+
#include "llvm/ADT/ImmutableMap.h"
namespace llvm {
class Interval {
private:
- uint64_t Start;
- uint64_t End;
+ int64_t Start;
+ int64_t End;
public:
- Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
+ Interval(int64_t S, int64_t E) : Start(S), End(E) {}
- uint64_t getStart() const { return Start; }
- uint64_t getEnd() const { return End; }
+ int64_t getStart() const { return Start; }
+ int64_t getEnd() const { return End; }
};
template <typename T>
}
}
+ static bool isContainedIn(key_type_ref K, key_type_ref L) {
+ if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd())
+ return true;
+ else
+ return false;
+ }
+
static void Profile(FoldingSetNodeID &ID, value_type_ref V) {
ID.AddInteger(V.first.getStart());
ID.AddInteger(V.first.getEnd());
}
};
-template <typename ImutInfo> class ImutIntervalAVLFactory;
-
template <typename ImutInfo>
class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
typedef ImutAVLTree<ImutInfo> TreeTy;
typedef typename ImutInfo::data_type_ref data_type_ref;
public:
- TreeTy *Add(TreeTy* T, value_type_ref V) {
- T = Add_internal(V,T);
- MarkImmutable(T);
+ ImutIntervalAVLFactory(BumpPtrAllocator &Alloc)
+ : ImutAVLFactory<ImutInfo>(Alloc) {}
+
+ TreeTy *Add(TreeTy *T, value_type_ref V) {
+ T = add_internal(V,T);
+ this->MarkImmutable(T);
return T;
}
-private:
- TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
- if (isEmpty(T))
- return CreateNode(NULL, V, NULL);
+ TreeTy *Find(TreeTy *T, key_type_ref K) {
+ if (!T)
+ return NULL;
- assert(!T->isMutable());
+ key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->getValue(T));
+
+ if (ImutInfo::isContainedIn(K, CurrentKey))
+ return T;
+ else if (ImutInfo::isLess(K, CurrentKey))
+ return Find(this->getLeft(T), K);
+ else
+ return Find(this->getRight(T), K);
+ }
+private:
+ TreeTy *add_internal(value_type_ref V, TreeTy *T) {
key_type_ref K = ImutInfo::KeyOfValue(V);
- key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
+ T = removeAllOverlaps(T, K);
+ if (this->isEmpty(T))
+ return this->CreateNode(NULL, V, NULL);
+
+ assert(!T->isMutable());
- T = RemoveAllOverlaps(T, K);
+ key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
if (ImutInfo::isLess(K, KCurrent))
- return Balance(Add_internal(V, Left(T)), Value(T), Right(T));
+ return this->Balance(add_internal(V, this->Left(T)), this->Value(T),
+ this->Right(T));
else
- return Balance(Left(T), Value(T), Add_internal(V, Right(T)));
+ return this->Balance(this->Left(T), this->Value(T),
+ add_internal(V, this->Right(T)));
}
// Remove all overlaps from T.
- TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
- TreeTy *OldTree, *NewTree;
- NewTree = T;
+ TreeTy *removeAllOverlaps(TreeTy *T, key_type_ref K) {
+ bool Changed;
do {
- OldTree = NewTree;
- NewTree = RemoveOverlap(OldTree, K);
- } while (NewTree != OldTree);
+ Changed = false;
+ T = removeOverlap(T, K, Changed);
+ this->markImmutable(T);
+ } while (Changed);
+
+ return T;
}
// Remove one overlap from T.
- TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K) {
- Interval CurrentK = ImutInfo::KeyOfValue(Value(T));
+ TreeTy *removeOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
+ if (!T)
+ return NULL;
+ Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
// If current key does not overlap the inserted key.
if (CurrentK.getStart() > K.getEnd())
- return RemoveOverlap(Left(T), K);
+ return this->Balance(removeOverlap(this->Left(T), K, Changed),
+ this->Value(T), this->Right(T));
else if (CurrentK.getEnd() < K.getStart())
- return RemoveOverlap(Right(T), K);
+ return this->Balance(this->Left(T), this->Value(T),
+ removeOverlap(this->Right(T), K, Changed));
// Current key overlaps with the inserted key.
// Remove the current key.
- T = Remove_internal(CurrentK, T);
+ Changed = true;
+ data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
+ T = this->Remove_internal(CurrentK, T);
// Add back the unoverlapped part of the current key.
if (CurrentK.getStart() < K.getStart()) {
if (CurrentK.getEnd() <= K.getEnd()) {
Interval NewK(CurrentK.getStart(), K.getStart()-1);
- return Add_internal(std::make_pair<key_type, data_type>(NewK,
- ImutInfo::DataOfValue(Value(T))), T);
+ return add_internal(std::make_pair(NewK, OldData), T);
} else {
Interval NewK1(CurrentK.getStart(), K.getStart()-1);
- T = Add_internal(std::make_pair<key_type, data_type>(NewK1,
- ImutInfo::DataOfValue(Value(T))), T);
+ T = add_internal(std::make_pair(NewK1, OldData), T);
Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
- return Add_internal(std::make_pair<key_type, data_type>(NewK2,
- ImutInfo::DataOfValue(Value(T))), T);
+ return add_internal(std::make_pair(NewK2, OldData), T);
}
} else {
if (CurrentK.getEnd() > K.getEnd()) {
Interval NewK(K.getEnd()+1, CurrentK.getEnd());
- return Add_internal(std::make_pair<key_type, data_type>(NewK,
- ImutInfo::DataOfValue(Value(T))), T);
- }
+ return add_internal(std::make_pair(NewK, OldData), T);
+ } else
+ return T;
}
}
};
ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
public:
- ImmutableIntervalMap GetEmptyMap() {
- return ImmutableIntervalMap(F.GetEmptyTree());
+ Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
+
+ ImmutableIntervalMap getEmptyMap() {
+ return ImmutableIntervalMap(F.getEmptyTree());
}
- ImmutableIntervalMap Add(ImmutableIntervalMap Old,
+ ImmutableIntervalMap add(ImmutableIntervalMap Old,
key_type_ref K, data_type_ref D) {
- TreeTy *T = F.Add(Old.Root, std::make_pair<key_type, data_type>(K, D));
- return ImmutableIntervalMap(F.GetCanonicalTree(T));
+ TreeTy *T = F.add(Old.Root, std::pair<key_type, data_type>(K, D));
+ return ImmutableIntervalMap(F.getCanonicalTree(T));
+ }
+
+ ImmutableIntervalMap remove(ImmutableIntervalMap Old, key_type_ref K) {
+ TreeTy *T = F.remove(Old.Root, K);
+ return ImmutableIntervalMap(F.getCanonicalTree(T));
}
- ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
- TreeTy *T = F.Remove(Old.Root, K);
- return ImmutableIntervalMap(F.GetCanonicalTree(T));
+ data_type *lookup(ImmutableIntervalMap M, key_type_ref K) {
+ TreeTy *T = F.Find(M.getRoot(), K);
+ if (T)
+ return &T->getValue().second;
+ else
+ return 0;
}
};
+
+private:
+ // For ImmutableIntervalMap, the lookup operation has to be done by the
+ // factory.
+ data_type* lookup(key_type_ref K) const;
};
} // end namespace llvm
+
+#endif
projects / oota-llvm.git / blobdiff