X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableIntervalMap.h;h=fa7ccb975e52b3cb055c0931bd2c498391009b9e;hb=fbaf206f470b5a6a54811547641ee41368a2cccd;hp=2ab78cd4deba73860c06ea338d77e8f9cdac9e65;hpb=1c8bd7dc0a9d6de3a4ff850fc5ba15265f2a6d33;p=oota-llvm.git diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h index 2ab78cd4deb..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 @@ -79,8 +83,6 @@ struct ImutIntervalInfo { } }; -template class ImutIntervalAVLFactory; - template class ImutIntervalAVLFactory : public ImutAVLFactory { typedef ImutAVLTree TreeTy; @@ -96,8 +98,8 @@ public: : ImutAVLFactory(Alloc) {} TreeTy *Add(TreeTy *T, value_type_ref V) { - T = Add_internal(V,T); - MarkImmutable(T); + T = add_internal(V,T); + this->MarkImmutable(T); return T; } @@ -105,78 +107,82 @@ public: if (!T) return NULL; - key_type_ref CurrentKey = ImutInfo::KeyOfValue(Value(T)); + key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->getValue(T)); if (ImutInfo::isContainedIn(K, CurrentKey)) return T; else if (ImutInfo::isLess(K, CurrentKey)) - return Find(Left(T), K); + return Find(this->getLeft(T), K); else - return Find(Right(T), K); + 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 *removeAllOverlaps(TreeTy *T, key_type_ref K) { bool Changed; do { Changed = false; - T = RemoveOverlap(T, K, Changed); - MarkImmutable(T); + 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, bool &Changed) { + 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 Balance(RemoveOverlap(Left(T), K, Changed), Value(T), Right(T)); + return this->Balance(removeOverlap(this->Left(T), K, Changed), + this->Value(T), this->Right(T)); else if (CurrentK.getEnd() < K.getStart()) - return Balance(Left(T), Value(T), RemoveOverlap(Right(T), K, Changed)); + 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. Changed = true; - data_type_ref OldData = ImutInfo::DataOfValue(Value(T)); - T = Remove_internal(CurrentK, T); + 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, OldData), 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, OldData), T); + T = add_internal(std::make_pair(NewK1, OldData), T); Interval NewK2(K.getEnd()+1, CurrentK.getEnd()); - return Add_internal(std::make_pair(NewK2, OldData), 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, OldData), T); + return add_internal(std::make_pair(NewK, OldData), T); } else return T; } @@ -207,22 +213,22 @@ public: public: Factory(BumpPtrAllocator& Alloc) : F(Alloc) {} - ImmutableIntervalMap GetEmptyMap() { - return ImmutableIntervalMap(F.GetEmptyTree()); + 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) { + data_type *lookup(ImmutableIntervalMap M, key_type_ref K) { TreeTy *T = F.Find(M.getRoot(), K); if (T) return &T->getValue().second; @@ -238,3 +244,5 @@ private: }; } // end namespace llvm + +#endif