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-09-23 13:06:45 Functions: 59 418 14.1 %
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     4085008 :   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
      56    11018147 :     ImutContainerInfo<T>::Profile(ID, V.first);
      57    10488859 :     ImutContainerInfo<S>::Profile(ID, V.second);
      58     4085008 :   }
      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        4945 :   using key_type = typename ValInfo::key_type;
      68       13153 :   using key_type_ref = typename ValInfo::key_type_ref;
      69        8176 :   using data_type = typename ValInfo::data_type;
      70        4945 :   using data_type_ref = typename ValInfo::data_type_ref;
      71           0 :   using TreeTy = ImutAVLTree<ValInfo>;
      72           0 : 
      73         543 : protected:
      74        4213 :   TreeTy* Root;
      75        9135 : 
      76        5488 : public:
      77         440 :   /// Constructs a map from a pointer to a tree root.  In general one
      78        5385 :   /// should use a Factory object to create maps instead of directly
      79        1002 :   /// invoking the constructor, but there are cases where make this
      80        6302 :   /// constructor public is useful.
      81     7375896 :   explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
      82     2136485 :     if (Root) { Root->retain(); }
      83           0 :   }
      84         103 : 
      85     9275934 :   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
      86    86565417 :     if (Root) { Root->retain(); }
      87           0 :   }
      88           0 : 
      89   143850838 :   ~ImmutableMap() {
      90   143850830 :     if (Root) { Root->release(); }
      91   143850824 :   }
      92     1056464 : 
      93     1068615 :   ImmutableMap &operator=(const ImmutableMap &X) {
      94     1111843 :     if (Root != X.Root) {
      95     2148947 :       if (X.Root) { X.Root->retain(); }
      96     2148947 :       if (Root) { Root->release(); }
      97     2151983 :       Root = X.Root;
      98        2197 :     }
      99           0 :     return *this;
     100           0 :   }
     101      167832 : 
     102      114257 :   class Factory {
     103       90817 :     typename TreeTy::Factory F;
     104       89137 :     const bool Canonicalize;
     105      104832 : 
     106      109536 :   public:
     107     3386521 :     Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
     108      161220 : 
     109      111156 :     Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
     110      109476 :         : F(Alloc), Canonicalize(canonicalize) {}
     111      130213 : 
     112       86459 :     Factory(const Factory &) = delete;
     113       48252 :     Factory &operator=(const Factory &) = delete;
     114       48252 : 
     115       56412 :     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
     116       56412 : 
     117      167663 :     LLVM_NODISCARD ImmutableMap add(ImmutableMap Old, key_type_ref K,
     118        1613 :                                     data_type_ref D) {
     119      364364 :       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
     120      123412 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     121      545092 :     }
     122      561016 : 
     123      568340 :     LLVM_NODISCARD ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
     124       18836 :       TreeTy *T = F.remove(Old.Root,K);
     125       64298 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     126       74060 :     }
     127     6508505 : 
     128      176563 :     typename TreeTy::Factory *getTreeFactory() const {
     129      435249 :       return const_cast<typename TreeTy::Factory *>(&F);
     130     6386955 :     }
     131     6395123 :   };
     132     6395123 : 
     133       13161 :   bool contains(key_type_ref K) const {
     134      207775 :     return Root ? Root->contains(K) : false;
     135     8341897 :   }
     136       10300 : 
     137       23089 :   bool operator==(const ImmutableMap &RHS) const {
     138       23089 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     139       50382 :   }
     140       27341 : 
     141       27399 :   bool operator!=(const ImmutableMap &RHS) const {
     142     3091426 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     143     2430152 :   }
     144     3049186 : 
     145     3575039 :   TreeTy *getRoot() const {
     146     3877795 :     if (Root) { Root->retain(); }
     147     3575039 :     return Root;
     148           0 :   }
     149           0 : 
     150        2933 :   TreeTy *getRootWithoutRetain() const { return Root; }
     151        2933 : 
     152     1676896 :   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        8234 :   //===--------------------------------------------------===//
     165           0 : 
     166         685 : 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         685 : 
     174         685 :   template <typename Callback>
     175           0 :   struct CBWrapperRef {
     176           0 :     Callback &C;
     177           0 : 
     178           0 :     CBWrapperRef(Callback& c) : C(c) {}
     179           0 : 
     180        2277 :     void operator()(value_type_ref V) { C(V.first,V.second); }
     181           0 :   };
     182       19769 : 
     183           0 : public:
     184           0 :   template <typename Callback>
     185           0 :   void foreach(Callback& C) {
     186           0 :     if (Root) {
     187        9762 :       CBWrapperRef<Callback> CB(C);
     188           0 :       Root->foreach(CB);
     189        9766 :     }
     190        9762 :   }
     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     1307488 :   class iterator : public ImutAVLValueIterator<ImmutableMap> {
     211           0 :     friend class ImmutableMap;
     212           0 : 
     213           0 :     iterator() = default;
     214     1311905 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     215           0 : 
     216     1389088 :   public:
     217     1528418 :     key_type_ref getKey() const { return (*this)->first; }
     218     1528418 :     data_type_ref getData() const { return (*this)->second; }
     219           0 :   };
     220     1389088 : 
     221           0 :   iterator begin() const { return iterator(Root); }
     222     1307490 :   iterator end() const { return iterator(); }
     223          90 : 
     224     1564870 :   data_type* lookup(key_type_ref K) const {
     225     2780238 :     if (Root) {
     226     1468191 :       TreeTy* T = Root->find(K);
     227     2313235 :       if (T) return &T->getValue().second;
     228     1396888 :     }
     229             : 
     230           0 :     return nullptr;
     231      263317 :   }
     232      271117 : 
     233      263317 :   /// 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         839 :   ///  method returns NULL if the map is empty.
     236           0 :   value_type* getMaxElement() const {
     237           1 :     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
     238      918197 :   }
     239           0 : 
     240        7800 :   //===--------------------------------------------------===//
     241           0 :   // Utility methods.
     242           0 :   //===--------------------------------------------------===//
     243       49271 : 
     244           1 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     245       38716 : 
     246        4028 :   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        4047 :     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      615033 : 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       10155 :   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      260067 :   explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
     279      260067 :       : Root(const_cast<TreeTy *>(R)), Factory(F) {
     280      260067 :     if (Root) {
     281           0 :       Root->retain();
     282           0 :     }
     283         556 :   }
     284             : 
     285     8562713 :   explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
     286     8329272 :                            typename ImmutableMap<KeyT, ValT>::Factory &F)
     287             :     : Root(X.getRootWithoutRetain()),
     288             :       Factory(F.getTreeFactory()) {
     289             :     if (Root) { Root->retain(); }
     290      360996 :   }
     291       20772 : 
     292             :   ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
     293             :     if (Root) {
     294      402540 :       Root->retain();
     295       20772 :     }
     296             :   }
     297             : 
     298     2414337 :   ~ImmutableMapRef() {
     299     2382602 :     if (Root)
     300             :       Root->release();
     301     1037670 :   }
     302      360996 : 
     303           0 :   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
     304    10396901 :     if (Root != X.Root) {
     305    10514271 :       if (X.Root)
     306             :         X.Root->retain();
     307    10450475 : 
     308       34964 :       if (Root)
     309       34964 :         Root->release();
     310             : 
     311       34964 :       Root = X.Root;
     312    10361937 :       Factory = X.Factory;
     313    10361937 :     }
     314           0 :     return *this;
     315    10361937 :   }
     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        2937 :     if (Root) Root->release();
     327         109 :   }
     328           0 : 
     329           0 :   ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
     330        2937 :     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        2937 : 
     339         109 :   bool contains(key_type_ref K) const {
     340           0 :     return Root ? Root->contains(K) : false;
     341        6973 :   }
     342     2337047 : 
     343        4028 :   ImmutableMap<KeyT, ValT> asImmutableMap() const {
     344     2437059 :     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     3845915 :     if (Root)
     363           0 :       Root->verify();
     364             :   }
     365           0 : 
     366     3095429 :   //===--------------------------------------------------===//
     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      231429 : 
     384      231429 :   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     7338444 :     }
     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       69292 :   value_type* getMaxElement() const {
     397           0 :     return Root ? &(Root->getMaxElement()->getValue()) : 0;
     398           0 :   }
     399           0 : 
     400      482346 :   //===--------------------------------------------------===//
     401     7338444 :   // 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