X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableMap.h;h=c5b8dcc667116a655385a425afd1b70da3c29b2b;hb=ff278be8cfd136b7e3d6128b7dc70114db2fa888;hp=52708bc8a10873ae2e11f9c08b5b60d46f5afc67;hpb=638b8b446e7f08d348fe4f3b290c08f6854fc8ba;p=oota-llvm.git diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 52708bc8a10..c5b8dcc6671 100644 --- a/include/llvm/ADT/ImmutableMap.h +++ b/include/llvm/ADT/ImmutableMap.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ADT_IMMAP_H -#define LLVM_ADT_IMMAP_H +#ifndef LLVM_ADT_IMMUTABLEMAP_H +#define LLVM_ADT_IMMUTABLEMAP_H #include "llvm/ADT/ImmutableSet.h" @@ -55,7 +55,6 @@ struct ImutKeyValueInfo { } }; - template > class ImmutableMap { @@ -68,7 +67,7 @@ public: typedef typename ValInfo::data_type_ref data_type_ref; typedef ImutAVLTree TreeTy; -private: +protected: TreeTy* Root; public: @@ -76,49 +75,81 @@ public: /// should use a Factory object to create maps instead of directly /// invoking the constructor, but there are cases where make this /// constructor public is useful. - explicit ImmutableMap(const TreeTy* R) : Root(const_cast(R)) {} + explicit ImmutableMap(const TreeTy* R) : Root(const_cast(R)) { + if (Root) { Root->retain(); } + } + ImmutableMap(const ImmutableMap &X) : Root(X.Root) { + if (Root) { Root->retain(); } + } + ImmutableMap &operator=(const ImmutableMap &X) { + if (Root != X.Root) { + if (X.Root) { X.Root->retain(); } + if (Root) { Root->release(); } + Root = X.Root; + } + return *this; + } + ~ImmutableMap() { + if (Root) { Root->release(); } + } class Factory { typename TreeTy::Factory F; + const bool Canonicalize; public: - Factory() {} + Factory(bool canonicalize = true) : Canonicalize(canonicalize) {} + + Factory(BumpPtrAllocator &Alloc, bool canonicalize = true) + : F(Alloc), Canonicalize(canonicalize) {} - Factory(BumpPtrAllocator& Alloc) - : F(Alloc) {} + ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); } - ImmutableMap GetEmptyMap() { return ImmutableMap(F.GetEmptyTree()); } + ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) { + TreeTy *T = F.add(Old.Root, std::pair(K,D)); + return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); + } - ImmutableMap Add(ImmutableMap Old, key_type_ref K, data_type_ref D) { - return ImmutableMap(F.Add(Old.Root, - std::make_pair(K,D))); + ImmutableMap remove(ImmutableMap Old, key_type_ref K) { + TreeTy *T = F.remove(Old.Root,K); + return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); } - ImmutableMap Remove(ImmutableMap Old, key_type_ref K) { - return ImmutableMap(F.Remove(Old.Root,K)); + typename TreeTy::Factory *getTreeFactory() const { + return const_cast(&F); } private: - Factory(const Factory& RHS) {}; - void operator=(const Factory& RHS) {}; + Factory(const Factory& RHS) = delete; + void operator=(const Factory& RHS) = delete; }; - friend class Factory; - bool contains(key_type_ref K) const { return Root ? Root->contains(K) : false; } - - bool operator==(ImmutableMap RHS) const { + bool operator==(const ImmutableMap &RHS) const { return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; } - bool operator!=(ImmutableMap RHS) const { + bool operator!=(const ImmutableMap &RHS) const { return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; } - TreeTy* getRoot() const { return Root; } + TreeTy *getRoot() const { + if (Root) { Root->retain(); } + return Root; + } + + TreeTy *getRootWithoutRetain() const { return Root; } + + void manualRetain() { + if (Root) Root->retain(); + } + + void manualRelease() { + if (Root) Root->release(); + } bool isEmpty() const { return !Root; } @@ -168,27 +199,14 @@ public: // Iterators. //===--------------------------------------------------===// - class iterator { - typename TreeTy::iterator itr; - - iterator() {} - iterator(TreeTy* t) : itr(t) {} + class iterator : public ImutAVLValueIterator { + iterator() = default; + explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} friend class ImmutableMap; public: - value_type_ref operator*() const { return itr->getValue(); } - value_type* operator->() const { return &itr->getValue(); } - - key_type_ref getKey() const { return itr->getValue().first; } - data_type_ref getData() const { return itr->getValue().second; } - - - iterator& operator++() { ++itr; return *this; } - iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; } - iterator& operator--() { --itr; return *this; } - iterator operator--(int) { iterator tmp(*this); --itr; return tmp; } - bool operator==(const iterator& RHS) const { return RHS.itr == itr; } - bool operator!=(const iterator& RHS) const { return RHS.itr != itr; } + key_type_ref getKey() const { return (*this)->first; } + data_type_ref getData() const { return (*this)->second; } }; iterator begin() const { return iterator(Root); } @@ -200,21 +218,21 @@ public: if (T) return &T->getValue().second; } - return 0; + return nullptr; } - + /// getMaxElement - Returns the pair in the ImmutableMap for /// which key is the highest in the ordering of keys in the map. This /// method returns NULL if the map is empty. value_type* getMaxElement() const { - return Root ? &(Root->getMaxElement()->getValue()) : 0; + return Root ? &(Root->getMaxElement()->getValue()) : nullptr; } //===--------------------------------------------------===// // Utility methods. //===--------------------------------------------------===// - inline unsigned getHeight() const { return Root ? Root->getHeight() : 0; } + unsigned getHeight() const { return Root ? Root->getHeight() : 0; } static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) { ID.AddPointer(M.Root); @@ -225,6 +243,163 @@ public: } }; +// NOTE: This will possibly become the new implementation of ImmutableMap some day. +template > +class ImmutableMapRef { +public: + typedef typename ValInfo::value_type value_type; + typedef typename ValInfo::value_type_ref value_type_ref; + typedef typename ValInfo::key_type key_type; + typedef typename ValInfo::key_type_ref key_type_ref; + typedef typename ValInfo::data_type data_type; + typedef typename ValInfo::data_type_ref data_type_ref; + typedef ImutAVLTree TreeTy; + typedef typename TreeTy::Factory FactoryTy; + +protected: + TreeTy *Root; + FactoryTy *Factory; + +public: + /// Constructs a map from a pointer to a tree root. In general one + /// should use a Factory object to create maps instead of directly + /// invoking the constructor, but there are cases where make this + /// constructor public is useful. + explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F) + : Root(const_cast(R)), Factory(F) { + if (Root) { + Root->retain(); + } + } + + explicit ImmutableMapRef(const ImmutableMap &X, + typename ImmutableMap::Factory &F) + : Root(X.getRootWithoutRetain()), + Factory(F.getTreeFactory()) { + if (Root) { Root->retain(); } + } + + ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) { + if (Root) { + Root->retain(); + } + } + + ImmutableMapRef &operator=(const ImmutableMapRef &X) { + if (Root != X.Root) { + if (X.Root) + X.Root->retain(); + + if (Root) + Root->release(); + + Root = X.Root; + Factory = X.Factory; + } + return *this; + } + + ~ImmutableMapRef() { + if (Root) + Root->release(); + } + + static inline ImmutableMapRef getEmptyMap(FactoryTy *F) { + return ImmutableMapRef(0, F); + } + + void manualRetain() { + if (Root) Root->retain(); + } + + void manualRelease() { + if (Root) Root->release(); + } + + ImmutableMapRef add(key_type_ref K, data_type_ref D) const { + TreeTy *NewT = Factory->add(Root, std::pair(K, D)); + return ImmutableMapRef(NewT, Factory); + } + + ImmutableMapRef remove(key_type_ref K) const { + TreeTy *NewT = Factory->remove(Root, K); + return ImmutableMapRef(NewT, Factory); + } + + bool contains(key_type_ref K) const { + return Root ? Root->contains(K) : false; + } + + ImmutableMap asImmutableMap() const { + return ImmutableMap(Factory->getCanonicalTree(Root)); + } + + bool operator==(const ImmutableMapRef &RHS) const { + return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root; + } + + bool operator!=(const ImmutableMapRef &RHS) const { + return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root; + } + + bool isEmpty() const { return !Root; } + + //===--------------------------------------------------===// + // For testing. + //===--------------------------------------------------===// + + void verify() const { + if (Root) + Root->verify(); + } + + //===--------------------------------------------------===// + // Iterators. + //===--------------------------------------------------===// + + class iterator : public ImutAVLValueIterator { + iterator() = default; + explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {} + friend class ImmutableMapRef; + + public: + key_type_ref getKey() const { return (*this)->first; } + data_type_ref getData() const { return (*this)->second; } + }; + + iterator begin() const { return iterator(Root); } + iterator end() const { return iterator(); } + + data_type *lookup(key_type_ref K) const { + if (Root) { + TreeTy* T = Root->find(K); + if (T) return &T->getValue().second; + } + + return 0; + } + + /// getMaxElement - Returns the pair in the ImmutableMap for + /// which key is the highest in the ordering of keys in the map. This + /// method returns NULL if the map is empty. + value_type* getMaxElement() const { + return Root ? &(Root->getMaxElement()->getValue()) : 0; + } + + //===--------------------------------------------------===// + // Utility methods. + //===--------------------------------------------------===// + + unsigned getHeight() const { return Root ? Root->getHeight() : 0; } + + static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) { + ID.AddPointer(M.Root); + } + + inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); } +}; + } // end namespace llvm #endif