LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 81 81 100.0 %
Date: 2018-06-17 00:07:59 Functions: 144 148 97.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===--- ImmutableMap.h - Immutable (functional) map interface --*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the ImmutableMap class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_ADT_IMMUTABLEMAP_H
      15             : #define LLVM_ADT_IMMUTABLEMAP_H
      16             : 
      17             : #include "llvm/ADT/FoldingSet.h"
      18             : #include "llvm/ADT/ImmutableSet.h"
      19             : #include "llvm/Support/Allocator.h"
      20             : #include <utility>
      21             : 
      22             : namespace llvm {
      23             : 
      24             : /// ImutKeyValueInfo -Traits class used by ImmutableMap.  While both the first
      25             : /// and second elements in a pair are used to generate profile information,
      26             : /// only the first element (the key) is used by isEqual and isLess.
      27             : template <typename T, typename S>
      28             : struct ImutKeyValueInfo {
      29             :   using value_type = const std::pair<T,S>;
      30             :   using value_type_ref = const value_type&;
      31             :   using key_type = const T;
      32             :   using key_type_ref = const T&;
      33             :   using data_type = const S;
      34             :   using data_type_ref = const S&;
      35             : 
      36             :   static inline key_type_ref KeyOfValue(value_type_ref V) {
      37             :     return V.first;
      38             :   }
      39             : 
      40             :   static inline data_type_ref DataOfValue(value_type_ref V) {
      41             :     return V.second;
      42             :   }
      43             : 
      44             :   static inline bool isEqual(key_type_ref L, key_type_ref R) {
      45             :     return ImutContainerInfo<T>::isEqual(L,R);
      46             :   }
      47             :   static inline bool isLess(key_type_ref L, key_type_ref R) {
      48             :     return ImutContainerInfo<T>::isLess(L,R);
      49             :   }
      50             : 
      51             :   static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
      52             :     return ImutContainerInfo<S>::isEqual(L,R);
      53             :   }
      54             : 
      55     3305640 :   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
      56     1482936 :     ImutContainerInfo<T>::Profile(ID, V.first);
      57      756534 :     ImutContainerInfo<S>::Profile(ID, V.second);
      58     3305640 :   }
      59             : };
      60             : 
      61             : template <typename KeyT, typename ValT,
      62             :           typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
      63             : class ImmutableMap {
      64             : public:
      65             :   using value_type = typename ValInfo::value_type;
      66             :   using value_type_ref = typename ValInfo::value_type_ref;
      67             :   using key_type = typename ValInfo::key_type;
      68             :   using key_type_ref = typename ValInfo::key_type_ref;
      69             :   using data_type = typename ValInfo::data_type;
      70             :   using data_type_ref = typename ValInfo::data_type_ref;
      71             :   using TreeTy = ImutAVLTree<ValInfo>;
      72             : 
      73             : protected:
      74             :   TreeTy* Root;
      75             : 
      76             : public:
      77             :   /// Constructs a map from a pointer to a tree root.  In general one
      78             :   /// should use a Factory object to create maps instead of directly
      79             :   /// invoking the constructor, but there are cases where make this
      80             :   /// constructor public is useful.
      81     4717242 :   explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
      82     3472472 :     if (Root) { Root->retain(); }
      83             :   }
      84             : 
      85    10844986 :   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
      86    10611565 :     if (Root) { Root->retain(); }
      87             :   }
      88             : 
      89    13331476 :   ~ImmutableMap() {
      90    13331476 :     if (Root) { Root->release(); }
      91    13331476 :   }
      92             : 
      93     1396171 :   ImmutableMap &operator=(const ImmutableMap &X) {
      94     1396171 :     if (Root != X.Root) {
      95     1245906 :       if (X.Root) { X.Root->retain(); }
      96     1245906 :       if (Root) { Root->release(); }
      97     1245906 :       Root = X.Root;
      98             :     }
      99     1396171 :     return *this;
     100             :   }
     101             : 
     102       54689 :   class Factory {
     103             :     typename TreeTy::Factory F;
     104             :     const bool Canonicalize;
     105             : 
     106             :   public:
     107       10974 :     Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
     108             : 
     109       61829 :     Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
     110       61829 :         : F(Alloc), Canonicalize(canonicalize) {}
     111             : 
     112             :     Factory(const Factory &) = delete;
     113             :     Factory &operator=(const Factory &) = delete;
     114             : 
     115             :     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
     116             : 
     117     1204966 :     LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K,
     118             :                                     data_type_ref D) {
     119     2620374 :       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
     120     2409932 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     121             :     }
     122             : 
     123      163397 :     LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
     124      163397 :       TreeTy *T = F.remove(Old.Root,K);
     125      326794 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     126             :     }
     127             : 
     128             :     typename TreeTy::Factory *getTreeFactory() const {
     129     7459444 :       return const_cast<typename TreeTy::Factory *>(&F);
     130             :     }
     131             :   };
     132             : 
     133             :   bool contains(key_type_ref K) const {
     134         358 :     return Root ? Root->contains(K) : false;
     135             :   }
     136             : 
     137             :   bool operator==(const ImmutableMap &RHS) const {
     138     1173793 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     139             :   }
     140             : 
     141      516704 :   bool operator!=(const ImmutableMap &RHS) const {
     142     1033025 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     143             :   }
     144             : 
     145             :   TreeTy *getRoot() const {
     146     2106245 :     if (Root) { Root->retain(); }
     147             :     return Root;
     148             :   }
     149             : 
     150      648740 :   TreeTy *getRootWithoutRetain() const { return Root; }
     151             : 
     152             :   void manualRetain() {
     153             :     if (Root) Root->retain();
     154             :   }
     155             : 
     156             :   void manualRelease() {
     157             :     if (Root) Root->release();
     158             :   }
     159             : 
     160       90454 :   bool isEmpty() const { return !Root; }
     161             : 
     162             :   //===--------------------------------------------------===//
     163             :   // Foreach - A limited form of map iteration.
     164             :   //===--------------------------------------------------===//
     165             : 
     166             : private:
     167             :   template <typename Callback>
     168             :   struct CBWrapper {
     169             :     Callback C;
     170             : 
     171             :     void operator()(value_type_ref V) { C(V.first,V.second); }
     172             :   };
     173             : 
     174             :   template <typename Callback>
     175             :   struct CBWrapperRef {
     176             :     Callback &C;
     177             : 
     178             :     CBWrapperRef(Callback& c) : C(c) {}
     179             : 
     180             :     void operator()(value_type_ref V) { C(V.first,V.second); }
     181             :   };
     182             : 
     183             : public:
     184             :   template <typename Callback>
     185             :   void foreach(Callback& C) {
     186             :     if (Root) {
     187             :       CBWrapperRef<Callback> CB(C);
     188             :       Root->foreach(CB);
     189             :     }
     190             :   }
     191             : 
     192             :   template <typename Callback>
     193             :   void foreach() {
     194             :     if (Root) {
     195             :       CBWrapper<Callback> CB;
     196             :       Root->foreach(CB);
     197             :     }
     198             :   }
     199             : 
     200             :   //===--------------------------------------------------===//
     201             :   // For testing.
     202             :   //===--------------------------------------------------===//
     203             : 
     204             :   void verify() const { if (Root) Root->verify(); }
     205             : 
     206             :   //===--------------------------------------------------===//
     207             :   // Iterators.
     208             :   //===--------------------------------------------------===//
     209             : 
     210     2500553 :   class iterator : public ImutAVLValueIterator<ImmutableMap> {
     211             :     friend class ImmutableMap;
     212             : 
     213             :     iterator() = default;
     214     2250673 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     215             : 
     216             :   public:
     217     1264032 :     key_type_ref getKey() const { return (*this)->first; }
     218     2256532 :     data_type_ref getData() const { return (*this)->second; }
     219             :   };
     220             : 
     221     2249992 :   iterator begin() const { return iterator(Root); }
     222     2250673 :   iterator end() const { return iterator(); }
     223             : 
     224             :   data_type* lookup(key_type_ref K) const {
     225     4166360 :     if (Root) {
     226     1568898 :       TreeTy* T = Root->find(K);
     227     4056374 :       if (T) return &T->getValue().second;
     228             :     }
     229             : 
     230             :     return nullptr;
     231             :   }
     232             : 
     233             :   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
     234             :   ///  which key is the highest in the ordering of keys in the map.  This
     235             :   ///  method returns NULL if the map is empty.
     236             :   value_type* getMaxElement() const {
     237           1 :     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
     238             :   }
     239             : 
     240             :   //===--------------------------------------------------===//
     241             :   // Utility methods.
     242             :   //===--------------------------------------------------===//
     243             : 
     244           1 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     245             : 
     246             :   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
     247     6834475 :     ID.AddPointer(M.Root);
     248             :   }
     249             : 
     250             :   inline void Profile(FoldingSetNodeID& ID) const {
     251             :     return Profile(ID,*this);
     252             :   }
     253             : };
     254             : 
     255             : // NOTE: This will possibly become the new implementation of ImmutableMap some day.
     256             : template <typename KeyT, typename ValT,
     257             : typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
     258             : class ImmutableMapRef {
     259             : public:
     260             :   using value_type = typename ValInfo::value_type;
     261             :   using value_type_ref = typename ValInfo::value_type_ref;
     262             :   using key_type = typename ValInfo::key_type;
     263             :   using key_type_ref = typename ValInfo::key_type_ref;
     264             :   using data_type = typename ValInfo::data_type;
     265             :   using data_type_ref = typename ValInfo::data_type_ref;
     266             :   using TreeTy = ImutAVLTree<ValInfo>;
     267             :   using FactoryTy = typename TreeTy::Factory;
     268             : 
     269             : protected:
     270             :   TreeTy *Root;
     271             :   FactoryTy *Factory;
     272             : 
     273             : public:
     274             :   /// Constructs a map from a pointer to a tree root.  In general one
     275             :   /// should use a Factory object to create maps instead of directly
     276             :   /// invoking the constructor, but there are cases where make this
     277             :   /// constructor public is useful.
     278      220341 :   explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
     279     8413907 :       : Root(const_cast<TreeTy *>(R)), Factory(F) {
     280     8413907 :     if (Root) {
     281             :       Root->retain();
     282             :     }
     283             :   }
     284             : 
     285        8360 :   explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
     286             :                            typename ImmutableMap<KeyT, ValT>::Factory &F)
     287             :     : Root(X.getRootWithoutRetain()),
     288       16720 :       Factory(F.getTreeFactory()) {
     289        8360 :     if (Root) { Root->retain(); }
     290             :   }
     291             : 
     292     1489462 :   ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
     293     1489462 :     if (Root) {
     294             :       Root->retain();
     295             :     }
     296             :   }
     297             : 
     298     9911729 :   ~ImmutableMapRef() {
     299     9911729 :     if (Root)
     300             :       Root->release();
     301     9911729 :   }
     302             : 
     303      866353 :   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
     304      866353 :     if (Root != X.Root) {
     305      863094 :       if (X.Root)
     306             :         X.Root->retain();
     307             : 
     308      863094 :       if (Root)
     309             :         Root->release();
     310             : 
     311      863094 :       Root = X.Root;
     312      863094 :       Factory = X.Factory;
     313             :     }
     314      866353 :     return *this;
     315             :   }
     316             : 
     317             :   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
     318             :     return ImmutableMapRef(0, F);
     319             :   }
     320             : 
     321             :   void manualRetain() {
     322     3349283 :     if (Root) Root->retain();
     323             :   }
     324             : 
     325             :   void manualRelease() {
     326     2680268 :     if (Root) Root->release();
     327             :   }
     328             : 
     329      776579 :   ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
     330     1941148 :     TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
     331     1553158 :     return ImmutableMapRef(NewT, Factory);
     332             :   }
     333             : 
     334      186244 :   ImmutableMapRef remove(key_type_ref K) const {
     335      186244 :     TreeTy *NewT = Factory->remove(Root, K);
     336      372488 :     return ImmutableMapRef(NewT, Factory);
     337             :   }
     338             : 
     339             :   bool contains(key_type_ref K) const {
     340             :     return Root ? Root->contains(K) : false;
     341             :   }
     342             : 
     343      648268 :   ImmutableMap<KeyT, ValT> asImmutableMap() const {
     344     1296536 :     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
     345             :   }
     346             : 
     347             :   bool operator==(const ImmutableMapRef &RHS) const {
     348             :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     349             :   }
     350             : 
     351             :   bool operator!=(const ImmutableMapRef &RHS) const {
     352             :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     353             :   }
     354             : 
     355             :   bool isEmpty() const { return !Root; }
     356             : 
     357             :   //===--------------------------------------------------===//
     358             :   // For testing.
     359             :   //===--------------------------------------------------===//
     360             : 
     361             :   void verify() const {
     362             :     if (Root)
     363             :       Root->verify();
     364             :   }
     365             : 
     366             :   //===--------------------------------------------------===//
     367             :   // Iterators.
     368             :   //===--------------------------------------------------===//
     369             : 
     370      513921 :   class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
     371             :     friend class ImmutableMapRef;
     372             : 
     373             :     iterator() = default;
     374      513921 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     375             : 
     376             :   public:
     377             :     key_type_ref getKey() const { return (*this)->first; }
     378      766061 :     data_type_ref getData() const { return (*this)->second; }
     379             :   };
     380             : 
     381             :   iterator begin() const { return iterator(Root); }
     382      513921 :   iterator end() const { return iterator(); }
     383             : 
     384             :   data_type *lookup(key_type_ref K) const {
     385     3976195 :     if (Root) {
     386             :       TreeTy* T = Root->find(K);
     387     3852456 :       if (T) return &T->getValue().second;
     388             :     }
     389             : 
     390             :     return nullptr;
     391             :   }
     392             : 
     393             :   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
     394             :   ///  which key is the highest in the ordering of keys in the map.  This
     395             :   ///  method returns NULL if the map is empty.
     396             :   value_type* getMaxElement() const {
     397             :     return Root ? &(Root->getMaxElement()->getValue()) : 0;
     398             :   }
     399             : 
     400             :   //===--------------------------------------------------===//
     401             :   // Utility methods.
     402             :   //===--------------------------------------------------===//
     403             : 
     404             :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     405             : 
     406             :   static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
     407             :     ID.AddPointer(M.Root);
     408             :   }
     409             : 
     410             :   inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
     411             : };
     412             : 
     413             : } // end namespace llvm
     414             : 
     415             : #endif // LLVM_ADT_IMMUTABLEMAP_H

Generated by: LCOV version 1.13