LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableMap.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 97 97 100.0 %
Date: 2017-09-14 15:23:50 Functions: 142 143 99.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     8234714 :     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    20089803 :     return ImutContainerInfo<T>::isEqual(L,R);
      46             :   }
      47             :   static inline bool isLess(key_type_ref L, key_type_ref R) {
      48    11013771 :     return ImutContainerInfo<T>::isLess(L,R);
      49             :   }
      50             : 
      51             :   static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
      52     1984630 :     return ImutContainerInfo<S>::isEqual(L,R);
      53             :   }
      54             : 
      55     2862865 :   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
      56     8846202 :     ImutContainerInfo<T>::Profile(ID, V.first);
      57     8846202 :     ImutContainerInfo<S>::Profile(ID, V.second);
      58     2862865 :   }
      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     3981766 :   explicit ImmutableMap(const TreeTy* R) : Root(const_cast<TreeTy*>(R)) {
      82     3090553 :     if (Root) { Root->retain(); }
      83             :   }
      84             : 
      85     9135194 :   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
      86     8946651 :     if (Root) { Root->retain(); }
      87             :   }
      88             : 
      89    11174090 :   ~ImmutableMap() {
      90    11174090 :     if (Root) { Root->release(); }
      91    11174090 :   }
      92             : 
      93     1257733 :   ImmutableMap &operator=(const ImmutableMap &X) {
      94     1257733 :     if (Root != X.Root) {
      95     1138286 :       if (X.Root) { X.Root->retain(); }
      96     1138286 :       if (Root) { Root->release(); }
      97     1138286 :       Root = X.Root;
      98             :     }
      99     1257733 :     return *this;
     100             :   }
     101             : 
     102       53106 :   class Factory {
     103             :     typename TreeTy::Factory F;
     104             :     const bool Canonicalize;
     105             : 
     106             :   public:
     107        7852 :     Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
     108             : 
     109       38406 :     Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
     110       90508 :         : F(Alloc), Canonicalize(canonicalize) {}
     111             : 
     112             :     Factory(const Factory &) = delete;
     113             :     Factory &operator=(const Factory &) = delete;
     114             : 
     115      740082 :     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
     116             : 
     117     1093381 :     ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
     118     3489235 :       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
     119     2186762 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     120             :     }
     121             : 
     122      170519 :     ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
     123      170519 :       TreeTy *T = F.remove(Old.Root,K);
     124      341038 :       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
     125             :     }
     126             : 
     127             :     typename TreeTy::Factory *getTreeFactory() const {
     128     6437131 :       return const_cast<typename TreeTy::Factory *>(&F);
     129             :     }
     130             :   };
     131             : 
     132             :   bool contains(key_type_ref K) const {
     133         226 :     return Root ? Root->contains(K) : false;
     134             :   }
     135             : 
     136             :   bool operator==(const ImmutableMap &RHS) const {
     137     1094299 :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     138             :   }
     139             : 
     140      505842 :   bool operator!=(const ImmutableMap &RHS) const {
     141     1011307 :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     142             :   }
     143             : 
     144             :   TreeTy *getRoot() const {
     145     1311035 :     if (Root) { Root->retain(); }
     146             :     return Root;
     147             :   }
     148             : 
     149      533948 :   TreeTy *getRootWithoutRetain() const { return Root; }
     150             : 
     151             :   void manualRetain() {
     152             :     if (Root) Root->retain();
     153             :   }
     154             : 
     155             :   void manualRelease() {
     156             :     if (Root) Root->release();
     157             :   }
     158             : 
     159       87286 :   bool isEmpty() const { return !Root; }
     160             : 
     161             :   //===--------------------------------------------------===//
     162             :   // Foreach - A limited form of map iteration.
     163             :   //===--------------------------------------------------===//
     164             : 
     165             : private:
     166             :   template <typename Callback>
     167             :   struct CBWrapper {
     168             :     Callback C;
     169             : 
     170             :     void operator()(value_type_ref V) { C(V.first,V.second); }
     171             :   };
     172             : 
     173             :   template <typename Callback>
     174             :   struct CBWrapperRef {
     175             :     Callback &C;
     176             : 
     177             :     CBWrapperRef(Callback& c) : C(c) {}
     178             : 
     179             :     void operator()(value_type_ref V) { C(V.first,V.second); }
     180             :   };
     181             : 
     182             : public:
     183             :   template <typename Callback>
     184             :   void foreach(Callback& C) {
     185             :     if (Root) {
     186             :       CBWrapperRef<Callback> CB(C);
     187             :       Root->foreach(CB);
     188             :     }
     189             :   }
     190             : 
     191             :   template <typename Callback>
     192             :   void foreach() {
     193             :     if (Root) {
     194             :       CBWrapper<Callback> CB;
     195             :       Root->foreach(CB);
     196             :     }
     197             :   }
     198             : 
     199             :   //===--------------------------------------------------===//
     200             :   // For testing.
     201             :   //===--------------------------------------------------===//
     202             : 
     203             :   void verify() const { if (Root) Root->verify(); }
     204             : 
     205             :   //===--------------------------------------------------===//
     206             :   // Iterators.
     207             :   //===--------------------------------------------------===//
     208             : 
     209     6721074 :   class iterator : public ImutAVLValueIterator<ImmutableMap> {
     210             :     friend class ImmutableMap;
     211             : 
     212     3360546 :     iterator() = default;
     213     1680273 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     214             : 
     215             :   public:
     216     3086197 :     key_type_ref getKey() const { return (*this)->first; }
     217     1926304 :     data_type_ref getData() const { return (*this)->second; }
     218             :   };
     219             : 
     220     3360546 :   iterator begin() const { return iterator(Root); }
     221     3360546 :   iterator end() const { return iterator(); }
     222             : 
     223             :   data_type* lookup(key_type_ref K) const {
     224     3459276 :     if (Root) {
     225     3223922 :       TreeTy* T = Root->find(K);
     226     3445529 :       if (T) return &T->getValue().second;
     227             :     }
     228             : 
     229             :     return nullptr;
     230             :   }
     231             : 
     232             :   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
     233             :   ///  which key is the highest in the ordering of keys in the map.  This
     234             :   ///  method returns NULL if the map is empty.
     235             :   value_type* getMaxElement() const {
     236           3 :     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
     237             :   }
     238             : 
     239             :   //===--------------------------------------------------===//
     240             :   // Utility methods.
     241             :   //===--------------------------------------------------===//
     242             : 
     243           2 :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     244             : 
     245             :   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
     246     6250008 :     ID.AddPointer(M.Root);
     247             :   }
     248             : 
     249             :   inline void Profile(FoldingSetNodeID& ID) const {
     250     6250008 :     return Profile(ID,*this);
     251             :   }
     252             : };
     253             : 
     254             : // NOTE: This will possibly become the new implementation of ImmutableMap some day.
     255             : template <typename KeyT, typename ValT,
     256             : typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
     257             : class ImmutableMapRef {
     258             : public:
     259             :   using value_type = typename ValInfo::value_type;
     260             :   using value_type_ref = typename ValInfo::value_type_ref;
     261             :   using key_type = typename ValInfo::key_type;
     262             :   using key_type_ref = typename ValInfo::key_type_ref;
     263             :   using data_type = typename ValInfo::data_type;
     264             :   using data_type_ref = typename ValInfo::data_type_ref;
     265             :   using TreeTy = ImutAVLTree<ValInfo>;
     266             :   using FactoryTy = typename TreeTy::Factory;
     267             : 
     268             : protected:
     269             :   TreeTy *Root;
     270             :   FactoryTy *Factory;
     271             : 
     272             : public:
     273             :   /// Constructs a map from a pointer to a tree root.  In general one
     274             :   /// should use a Factory object to create maps instead of directly
     275             :   /// invoking the constructor, but there are cases where make this
     276             :   /// constructor public is useful.
     277      179230 :   explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
     278     7266179 :       : Root(const_cast<TreeTy *>(R)), Factory(F) {
     279     7266179 :     if (Root) {
     280     6693370 :       Root->retain();
     281             :     }
     282             :   }
     283             : 
     284        5236 :   explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
     285             :                            typename ImmutableMap<KeyT, ValT>::Factory &F)
     286             :     : Root(X.getRootWithoutRetain()),
     287       10472 :       Factory(F.getTreeFactory()) {
     288       10472 :     if (Root) { Root->retain(); }
     289             :   }
     290             : 
     291     1245937 :   ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
     292     1245937 :     if (Root) {
     293     1147031 :       Root->retain();
     294             :     }
     295             :   }
     296             : 
     297     8517352 :   ~ImmutableMapRef() {
     298     8517352 :     if (Root)
     299     8001236 :       Root->release();
     300     8517352 :   }
     301             : 
     302      738852 :   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
     303      738852 :     if (Root != X.Root) {
     304      736589 :       if (X.Root)
     305      729774 :         X.Root->retain();
     306             : 
     307      736589 :       if (Root)
     308      574175 :         Root->release();
     309             : 
     310      736589 :       Root = X.Root;
     311      736589 :       Factory = X.Factory;
     312             :     }
     313      738852 :     return *this;
     314             :   }
     315             : 
     316             :   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
     317             :     return ImmutableMapRef(0, F);
     318             :   }
     319             : 
     320             :   void manualRetain() {
     321     2910131 :     if (Root) Root->retain();
     322             :   }
     323             : 
     324             :   void manualRelease() {
     325     2343979 :     if (Root) Root->release();
     326             :   }
     327             : 
     328      663886 :   ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
     329     2326126 :     TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
     330     1327772 :     return ImmutableMapRef(NewT, Factory);
     331             :   }
     332             : 
     333      170398 :   ImmutableMapRef remove(key_type_ref K) const {
     334      170398 :     TreeTy *NewT = Factory->remove(Root, K);
     335      340796 :     return ImmutableMapRef(NewT, Factory);
     336             :   }
     337             : 
     338             :   bool contains(key_type_ref K) const {
     339             :     return Root ? Root->contains(K) : false;
     340             :   }
     341             : 
     342      533718 :   ImmutableMap<KeyT, ValT> asImmutableMap() const {
     343     1067436 :     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
     344             :   }
     345             : 
     346             :   bool operator==(const ImmutableMapRef &RHS) const {
     347             :     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
     348             :   }
     349             : 
     350             :   bool operator!=(const ImmutableMapRef &RHS) const {
     351             :     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
     352             :   }
     353             : 
     354             :   bool isEmpty() const { return !Root; }
     355             : 
     356             :   //===--------------------------------------------------===//
     357             :   // For testing.
     358             :   //===--------------------------------------------------===//
     359             : 
     360             :   void verify() const {
     361             :     if (Root)
     362             :       Root->verify();
     363             :   }
     364             : 
     365             :   //===--------------------------------------------------===//
     366             :   // Iterators.
     367             :   //===--------------------------------------------------===//
     368             : 
     369     1683238 :   class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
     370             :     friend class ImmutableMapRef;
     371             : 
     372      841914 :     iterator() = default;
     373      420957 :     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
     374             : 
     375             :   public:
     376     1155510 :     key_type_ref getKey() const { return (*this)->first; }
     377      770933 :     data_type_ref getData() const { return (*this)->second; }
     378             :   };
     379             : 
     380      841914 :   iterator begin() const { return iterator(Root); }
     381      841914 :   iterator end() const { return iterator(); }
     382             : 
     383             :   data_type *lookup(key_type_ref K) const {
     384     3255502 :     if (Root) {
     385     3164115 :       TreeTy* T = Root->find(K);
     386     3164115 :       if (T) return &T->getValue().second;
     387             :     }
     388             : 
     389             :     return nullptr;
     390             :   }
     391             : 
     392             :   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
     393             :   ///  which key is the highest in the ordering of keys in the map.  This
     394             :   ///  method returns NULL if the map is empty.
     395             :   value_type* getMaxElement() const {
     396             :     return Root ? &(Root->getMaxElement()->getValue()) : 0;
     397             :   }
     398             : 
     399             :   //===--------------------------------------------------===//
     400             :   // Utility methods.
     401             :   //===--------------------------------------------------===//
     402             : 
     403             :   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
     404             : 
     405             :   static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
     406             :     ID.AddPointer(M.Root);
     407             :   }
     408             : 
     409             :   inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
     410             : };
     411             : 
     412             : } // end namespace llvm
     413             : 
     414             : #endif // LLVM_ADT_IMMUTABLEMAP_H

Generated by: LCOV version 1.13