X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableMap.h;h=81ac9cc31d74a9ff0d793107409dc2e21080b56f;hb=779a96362e18d008e224c1683e54181ba1fbe943;hp=d6cce7ccfa05f30e5485612c28858bdd8b2cbb55;hpb=2d76ad6df91d3192f986efd19d70a6d892a05b6c;p=oota-llvm.git diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index d6cce7ccfa0..81ac9cc31d7 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" @@ -117,9 +117,13 @@ public: return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T); } + typename TreeTy::Factory *getTreeFactory() const { + return const_cast(&F); + } + private: - Factory(const Factory& RHS); // DO NOT IMPLEMENT - void operator=(const Factory& RHS); // DO NOT IMPLEMENT + Factory(const Factory& RHS) LLVM_DELETED_FUNCTION; + void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION; }; bool contains(key_type_ref K) const { @@ -207,17 +211,22 @@ public: friend class ImmutableMap; public: - value_type_ref operator*() const { return itr->getValue(); } - value_type* operator->() const { return &itr->getValue(); } + typedef ImmutableMap::value_type value_type; + typedef ImmutableMap::value_type_ref reference; + typedef iterator::value_type *pointer; + typedef std::bidirectional_iterator_tag iterator_category; + + iterator::reference operator*() const { return itr->getValue(); } + iterator::pointer 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; } }; @@ -256,6 +265,174 @@ 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 { + typename TreeTy::iterator itr; + + iterator() {} + iterator(TreeTy* t) : itr(t) {} + friend class ImmutableMapRef; + + 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; } + }; + + 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