LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 176 329 53.5 %
Date: 2018-10-20 13:21:21 Functions: 60 430 14.0 %
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           0 :   static inline bool isEqual(key_type_ref L, key_type_ref R) {
      45           0 :     return ImutContainerInfo<T>::isEqual(L,R);
      46             :   }
      47           0 :   static inline bool isLess(key_type_ref L, key_type_ref R) {
      48           0 :     return ImutContainerInfo<T>::isLess(L,R);
      49             :   }
      50           0 : 
      51           0 :   static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
      52           0 :     return ImutContainerInfo<S>::isEqual(L,R);
      53           0 :   }
      54           0 : 
      55     4066116 :   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
      56    11098966 :     ImutContainerInfo<T>::Profile(ID, V.first);
      57    10571771 :     ImutContainerInfo<S>::Profile(ID, V.second);
      58     4066116 :   }
      59           0 : };
      60           0 : 
      61             : template <typename KeyT, typename ValT,
      62           0 :           typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
      63           0 : class ImmutableMap {
      64           0 : public:
      65           0 :   using value_type = typename ValInfo::value_type;
      66           0 :   using value_type_ref = typename ValInfo::value_type_ref;
      67        4949 :   using key_type = typename ValInfo::key_type;
      68       13043 :   using key_type_ref = typename ValInfo::key_type_ref;
      69        8062 :   using data_type = typename ValInfo::data_type;
      70        4949 :   using data_type_ref = typename ValInfo::data_type_ref;
      71           0 :   using TreeTy = ImutAVLTree<ValInfo>;
      72           0 : 
      73         590 : protected:
      74        4244 :   TreeTy* Root;
      75        9142 : 
      76        5539 : public:
      77         480 :   /// Constructs a map from a pointer to a tree root.  In general one
      78        5429 :   /// should use a Factory object to create maps instead of directly
      79        1069 :   /// invoking the constructor, but there are cases where make this
      80        6588 :   /// constructor public is useful.
      81     8584317 :   explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
      82     2130199 :     if (Root) { Root->retain(); }
      83           0 :   }
      84         110 : 
      85    10486326 :   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
      86   101237582 :     if (Root) { Root->retain(); }
      87           0 :   }
      88           0 : 
      89   167759038 :   ~ImmutableMap() {
      90   167759030 :     if (Root) { Root->release(); }
      91   167759024 :   }
      92     1053439 : 
      93     1065663 :   ImmutableMap &operator=(const ImmutableMap &X) {
      94     1108496 :     if (Root != X.Root) {
      95     2147533 :       if (X.Root) { X.Root->retain(); }
      96     2147533 :       if (Root) { Root->release(); }
      97     2150575 :       Root = X.Root;
      98        2201 :     }
      99           0 :     return *this;
     100           0 :   }
     101      166774 : 
     102      113811 :   class Factory {
     103       90268 :     typename TreeTy::Factory F;
     104       88586 :     const bool Canonicalize;
     105      105086 : 
     106      110813 :   public:
     107     4007158 :     Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
     108      161903 : 
     109      111000 :     Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
     110      109318 :         : F(Alloc), Canonicalize(canonicalize) {}
     111      129844 : 
     112       86332 :     Factory(const Factory &) = delete;
     113       47981 :     Factory &operator=(const Factory &) = delete;
     114       47981 : 
     115       55856 :     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
     116       55856 : 
     117      166310 :     LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K,
     118        1613 :                                     data_type_ref D) {
     119      361964 :       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
     120      122614 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     121      546468 :     }
     122      562389 : 
     123      569716 :     LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
     124       18908 :       TreeTy *T = F.remove(Old.Root,K);
     125       67503 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     126       77262 :     }
     127     6492246 : 
     128      177388 :     typename TreeTy::Factory *getTreeFactory() const {
     129      435604 :       return const_cast<typename TreeTy::Factory *>(&F);
     130     6365565 :     }
     131     6374284 :   };
     132     6374284 : 
     133       13943 :   bool contains(key_type_ref K) const {
     134      213155 :     return Root ? Root->contains(K) : false;
     135     8320839 :   }
     136       10951 : 
     137       24557 :   bool operator==(const ImmutableMap &RHS) const {
     138       24557 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     139       51850 :   }
     140       27341 : 
     141       27399 :   bool operator!=(const ImmutableMap &RHS) const {
     142     3075327 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     143     2420912 :   }
     144     3036516 : 
     145     3561628 :   TreeTy *getRoot() const {
     146     3862702 :     if (Root) { Root->retain(); }
     147     3561628 :     return Root;
     148           0 :   }
     149           0 : 
     150        2923 :   TreeTy *getRootWithoutRetain() const { return Root; }
     151        2923 : 
     152     1676428 :   void manualRetain() {
     153           0 :     if (Root) Root->retain();
     154           0 :   }
     155           0 : 
     156           0 :   void manualRelease() {
     157           0 :     if (Root) Root->release();
     158           0 :   }
     159           0 : 
     160           1 :   bool isEmpty() const { return !Root; }
     161           0 : 
     162           0 :   //===--------------------------------------------------===//
     163           0 :   // Foreach - A limited form of map iteration.
     164        8078 :   //===--------------------------------------------------===//
     165           0 : 
     166         706 : private:
     167           0 :   template <typename Callback>
     168           0 :   struct CBWrapper {
     169           0 :     Callback C;
     170           0 : 
     171           0 :     void operator()(value_type_ref V) { C(V.first,V.second); }
     172             :   };
     173         706 : 
     174         706 :   template <typename Callback>
     175           0 :   struct CBWrapperRef {
     176           0 :     Callback &C;
     177           0 : 
     178           0 :     CBWrapperRef(Callback& c) : C(c) {}
     179           0 : 
     180        2276 :     void operator()(value_type_ref V) { C(V.first,V.second); }
     181           0 :   };
     182       19763 : 
     183           0 : public:
     184           0 :   template <typename Callback>
     185           0 :   void foreach(Callback& C) {
     186           0 :     if (Root) {
     187        9759 :       CBWrapperRef<Callback> CB(C);
     188           0 :       Root->foreach(CB);
     189        9763 :     }
     190        9759 :   }
     191           0 : 
     192           0 :   template <typename Callback>
     193           0 :   void foreach() {
     194           0 :     if (Root) {
     195           0 :       CBWrapper<Callback> CB;
     196         836 :       Root->foreach(CB);
     197           6 :     }
     198           0 :   }
     199          18 : 
     200           6 :   //===--------------------------------------------------===//
     201           0 :   // For testing.
     202           6 :   //===--------------------------------------------------===//
     203           0 : 
     204          18 :   void verify() const { if (Root) Root->verify(); }
     205           6 : 
     206             :   //===--------------------------------------------------===//
     207           0 :   // Iterators.
     208           0 :   //===--------------------------------------------------===//
     209           0 : 
     210     1315471 :   class iterator : public ImutAVLValueIterator<ImmutableMap> {
     211           0 :     friend class ImmutableMap;
     212           0 : 
     213           0 :     iterator() = default;
     214     1319888 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     215           0 : 
     216     1381648 :   public:
     217     1522303 :     key_type_ref getKey() const { return (*this)->first; }
     218     1522303 :     data_type_ref getData() const { return (*this)->second; }
     219           0 :   };
     220     1381648 : 
     221           0 :   iterator begin() const { return iterator(Root); }
     222     1315473 :   iterator end() const { return iterator(); }
     223          90 : 
     224     1558752 :   data_type* lookup(key_type_ref K) const {
     225     2725839 :     if (Root) {
     226     1459276 :       TreeTy* T = Root->find(K);
     227     2328213 :       if (T) return &T->getValue().second;
     228     1389468 :     }
     229             : 
     230           0 :     return nullptr;
     231      262570 :   }
     232      270390 : 
     233      262570 :   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
     234          24 :   ///  which key is the highest in the ordering of keys in the map.  This
     235         841 :   ///  method returns NULL if the map is empty.
     236           0 :   value_type* getMaxElement() const {
     237           1 :     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
     238      915149 :   }
     239           0 : 
     240        7820 :   //===--------------------------------------------------===//
     241           0 :   // Utility methods.
     242           0 :   //===--------------------------------------------------===//
     243       49110 : 
     244           1 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     245       38603 : 
     246        4278 :   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
     247           0 :     ID.AddPointer(M.Root);
     248           0 :   }
     249           0 : 
     250           0 :   inline void Profile(FoldingSetNodeID& ID) const {
     251        4051 :     return Profile(ID,*this);
     252           0 :   }
     253           0 : };
     254           0 : 
     255         158 : // NOTE: This will possibly become the new implementation of ImmutableMap some day.
     256           0 : template <typename KeyT, typename ValT,
     257      612023 : typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
     258           0 : class ImmutableMapRef {
     259           0 : public:
     260           0 :   using value_type = typename ValInfo::value_type;
     261           0 :   using value_type_ref = typename ValInfo::value_type_ref;
     262           0 :   using key_type = typename ValInfo::key_type;
     263           0 :   using key_type_ref = typename ValInfo::key_type_ref;
     264           0 :   using data_type = typename ValInfo::data_type;
     265           0 :   using data_type_ref = typename ValInfo::data_type_ref;
     266           0 :   using TreeTy = ImutAVLTree<ValInfo>;
     267       10123 :   using FactoryTy = typename TreeTy::Factory;
     268           0 : 
     269        5810 : protected:
     270             :   TreeTy *Root;
     271         144 :   FactoryTy *Factory;
     272           0 : 
     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           0 :   /// constructor public is useful.
     278      259596 :   explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
     279      259596 :       : Root(const_cast<TreeTy *>(R)), Factory(F) {
     280      259596 :     if (Root) {
     281           0 :       Root->retain();
     282           0 :     }
     283         556 :   }
     284             : 
     285     8540118 :   explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
     286     8307563 :                            typename ImmutableMap<KeyT, ValT>::Factory &F)
     287             :     : Root(X.getRootWithoutRetain()),
     288             :       Factory(F.getTreeFactory()) {
     289             :     if (Root) { Root->retain(); }
     290      362258 :   }
     291       20810 : 
     292             :   ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
     293             :     if (Root) {
     294      403878 :       Root->retain();
     295       20810 :     }
     296             :   }
     297             : 
     298     2407444 :   ~ImmutableMapRef() {
     299     2375689 :     if (Root)
     300             :       Root->release();
     301     1033915 :   }
     302      362258 : 
     303           0 :   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
     304    10370016 :     if (Root != X.Root) {
     305    10487595 :       if (X.Root)
     306             :         X.Root->retain();
     307    10423590 : 
     308       35010 :       if (Root)
     309       35010 :         Root->release();
     310             : 
     311       35010 :       Root = X.Root;
     312    10335006 :       Factory = X.Factory;
     313    10335006 :     }
     314           0 :     return *this;
     315    10335006 :   }
     316             : 
     317           0 :   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
     318           0 :     return ImmutableMapRef(0, F);
     319           0 :   }
     320             : 
     321             :   void manualRetain() {
     322           0 :     if (Root) Root->retain();
     323             :   }
     324             : 
     325           0 :   void manualRelease() {
     326        3133 :     if (Root) Root->release();
     327         109 :   }
     328           0 : 
     329           0 :   ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
     330        3133 :     TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
     331         109 :     return ImmutableMapRef(NewT, Factory);
     332           0 :   }
     333             : 
     334             :   ImmutableMapRef remove(key_type_ref K) const {
     335           0 :     TreeTy *NewT = Factory->remove(Root, K);
     336             :     return ImmutableMapRef(NewT, Factory);
     337           0 :   }
     338        3133 : 
     339         109 :   bool contains(key_type_ref K) const {
     340           0 :     return Root ? Root->contains(K) : false;
     341        7418 :   }
     342     2353933 : 
     343        4351 :   ImmutableMap<KeyT, ValT> asImmutableMap() const {
     344     2452967 :     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
     345           0 :   }
     346             : 
     347             :   bool operator==(const ImmutableMapRef &RHS) const {
     348           0 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     349           0 :   }
     350           0 : 
     351           0 :   bool operator!=(const ImmutableMapRef &RHS) const {
     352           0 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     353             :   }
     354           0 : 
     355             :   bool isEmpty() const { return !Root; }
     356             : 
     357           0 :   //===--------------------------------------------------===//
     358           0 :   // For testing.
     359             :   //===--------------------------------------------------===//
     360           0 : 
     361           0 :   void verify() const {
     362     3834975 :     if (Root)
     363           0 :       Root->verify();
     364             :   }
     365           0 : 
     366     3084253 :   //===--------------------------------------------------===//
     367           0 :   // Iterators.
     368           0 :   //===--------------------------------------------------===//
     369           0 : 
     370           0 :   class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
     371           0 :     friend class ImmutableMapRef;
     372             : 
     373           0 :     iterator() = default;
     374           0 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     375           0 : 
     376             :   public:
     377           0 :     key_type_ref getKey() const { return (*this)->first; }
     378           0 :     data_type_ref getData() const { return (*this)->second; }
     379           0 :   };
     380             : 
     381             :   iterator begin() const { return iterator(Root); }
     382           0 :   iterator end() const { return iterator(); }
     383      230539 : 
     384      230539 :   data_type *lookup(key_type_ref K) const {
     385             :     if (Root) {
     386           0 :       TreeTy* T = Root->find(K);
     387           0 :       if (T) return &T->getValue().second;
     388     7318326 :     }
     389           0 : 
     390           0 :     return nullptr;
     391           0 :   }
     392           0 : 
     393           0 :   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
     394           0 :   ///  which key is the highest in the ordering of keys in the map.  This
     395           0 :   ///  method returns NULL if the map is empty.
     396       69168 :   value_type* getMaxElement() const {
     397           0 :     return Root ? &(Root->getMaxElement()->getValue()) : 0;
     398           0 :   }
     399           0 : 
     400      481433 :   //===--------------------------------------------------===//
     401     7318326 :   // Utility methods.
     402           0 :   //===--------------------------------------------------===//
     403           0 : 
     404             :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     405           0 : 
     406           0 :   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