X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableIntervalMap.h;h=fa7ccb975e52b3cb055c0931bd2c498391009b9e;hb=a77b95a316e0eb04929c5d7fe96935124c3ed478;hp=4754e446a258367840941ae42da946c570be00fd;hpb=3a819568ca4ce1fdf04764ff466678e687479921;p=oota-llvm.git diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h index 4754e446a25..fa7ccb975e5 100644 --- a/include/llvm/ADT/ImmutableIntervalMap.h +++ b/include/llvm/ADT/ImmutableIntervalMap.h @@ -10,20 +10,24 @@ // 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 @@ -65,6 +69,13 @@ struct ImutIntervalInfo { } } + 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()); @@ -72,8 +83,6 @@ struct ImutIntervalInfo { } }; -template class ImutIntervalAVLFactory; - template class ImutIntervalAVLFactory : public ImutAVLFactory { typedef ImutAVLTree TreeTy; @@ -85,79 +94,97 @@ class ImutIntervalAVLFactory : public ImutAVLFactory { 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(Alloc) {} + + TreeTy *Add(TreeTy *T, value_type_ref V) { + T = add_internal(V,T); + this->MarkImmutable(T); return T; } + TreeTy *Find(TreeTy *T, key_type_ref K) { + if (!T) + return NULL; + + 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) { + TreeTy *add_internal(value_type_ref V, TreeTy *T) { key_type_ref K = ImutInfo::KeyOfValue(V); - T = RemoveAllOverlaps(T, K); - if (isEmpty(T)) - return CreateNode(NULL, V, NULL); + T = removeAllOverlaps(T, K); + if (this->isEmpty(T)) + return this->CreateNode(NULL, V, NULL); assert(!T->isMutable()); - key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T)); + 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 NewTree; + return T; } // Remove one overlap from T. - TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K) { + TreeTy *removeOverlap(TreeTy *T, key_type_ref K, bool &Changed) { if (!T) return NULL; - Interval CurrentK = ImutInfo::KeyOfValue(Value(T)); + 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. - TreeTy *OldNode = T; - 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(NewK, - ImutInfo::DataOfValue(Value(OldNode))), T); + return add_internal(std::make_pair(NewK, OldData), T); } else { Interval NewK1(CurrentK.getStart(), K.getStart()-1); - T = Add_internal(std::make_pair(NewK1, - ImutInfo::DataOfValue(Value(OldNode))), T); + T = add_internal(std::make_pair(NewK1, OldData), T); Interval NewK2(K.getEnd()+1, CurrentK.getEnd()); - return Add_internal(std::make_pair(NewK2, - ImutInfo::DataOfValue(Value(OldNode))), 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(NewK, - ImutInfo::DataOfValue(Value(OldNode))), T); - } + return add_internal(std::make_pair(NewK, OldData), T); + } else + return T; } } }; @@ -184,21 +211,38 @@ public: ImutIntervalAVLFactory > 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(K, D)); - return ImmutableIntervalMap(F.GetCanonicalTree(T)); + TreeTy *T = F.add(Old.Root, std::pair(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