Line data    Source code

       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : 
      10             : #ifndef MCRL2_UTILITIES_FIXED_SIZE_CACHE_H
      11             : #define MCRL2_UTILITIES_FIXED_SIZE_CACHE_H
      12             : 
      13             : #include "mcrl2/utilities/cache_policy.h"
      14             : #include "mcrl2/utilities/unordered_map.h"
      15             : 
      16             : namespace mcrl2
      17             : {
      18             : namespace utilities
      19             : {
      20             : 
      21             : /// \brief A cache keeps track of key-value pairs similar to a map. The difference is that a cache
      22             : ///        has (an optional) maximum size and a policy that determines what element gets evicted when
      23             : ///        the cache is full.
      24             : /// \details Works with arbirary maps that implement the unordered_map interface.
      25             : template<typename Policy>
      26             : class fixed_size_cache
      27             : {
      28             : public:
      29             :   using key_type = typename Policy::key_type;
      30             :   using iterator = typename Policy::map_type::iterator;
      31             :   using const_iterator = typename Policy::map_type::const_iterator;
      32             : 
      33           1 :   explicit fixed_size_cache(std::size_t max_size = 1024)
      34           1 :     : m_map(max_size)
      35             :   {
      36           1 :     if (max_size == 0)
      37             :     {
      38           0 :       m_maximum_size = std::numeric_limits<std::size_t>::max();
      39             :     }
      40             :     else
      41             :     {
      42             :       // The reason for this is that the internal mapping might only support powers of two and as such
      43             :       // we might as well use the additional capacity.
      44           1 :       m_maximum_size = m_map.capacity();
      45             :     }
      46           1 :   }
      47             : 
      48             :   const_iterator begin() const { return m_map.begin(); }
      49             :   const_iterator end() const { return m_map.end(); }
      50             : 
      51             :   void clear() { m_map.clear(); m_policy.clear(); }
      52             : 
      53             :   std::size_t count(const key_type& key) const { return m_map.count(key); }
      54             : 
      55         100 :   iterator find(const key_type& key)
      56             :   {
      57         100 :     return m_map.find(key);
      58             :   }
      59             : 
      60             :   /// \brief Stores the given key-value pair in the cache. Depending on the cache policy and capacity an existing element
      61             :   ///        might be removed.
      62             :   template<typename ...Args>
      63             :   std::pair<iterator, bool> emplace(Args&&... args)
      64             :   {
      65             :     // The reason to split the find and emplace is that when we insert an element the replacement_candidate should not be
      66             :     // the key that we just inserted. The other way around, when an element that we are looking for was first removed and
      67             :     // then searched for also leads to unnecessary inserts.
      68             :     auto result = find(args...);
      69             :     if (result == m_map.end())
      70             :     {
      71             :       // If the cache would be full after an inserted.
      72             :       if (m_map.size() + 1 >= m_maximum_size)
      73             :       {
      74             :         // Remove an existing element defined by the policy.
      75             :         m_map.erase(m_policy.replacement_candidate(m_map));
      76             :       }
      77             : 
      78             :       // Insert an element and inform the policy that an element was inserted.
      79             :       auto emplace_result = m_map.emplace(std::forward<Args>(args)...);
      80             :       m_policy.inserted((*emplace_result.first).first);
      81             :       return emplace_result;
      82             :     }
      83             : 
      84             :     assert(m_map.size() <= m_maximum_size);
      85             :     return std::make_pair(result, false);
      86             :   }
      87             : 
      88             : protected:
      89             :   typename Policy::map_type m_map;    ///< The underlying mapping from keys to their cached results.
      90             :   Policy                    m_policy; ///< The replacement policy for keys in the cache.
      91             : 
      92             :   std::size_t m_maximum_size; ///< The maximum number of elements to cache.
      93             : };
      94             : 
      95             : /// \brief A cache keeps track of key-value pairs similar to a map. The difference is that a cache
      96             : ///        has (an optional) maximum size and a policy that determines what element gets evicted when
      97             : ///        the cache is full.
      98             : /// \details Works with arbirary maps that implement the unordered_map interface.
      99             : template<typename Policy, typename F, typename ...Args>
     100             : class function_cache : public fixed_size_cache<Policy>
     101             : {
     102             : private:
     103             :   using super = fixed_size_cache<Policy>;
     104             :   using super::m_map;
     105             :   using super::m_maximum_size;
     106             :   using super::m_policy;
     107             :   using super::find;
     108             : 
     109             : public:
     110           1 :   explicit function_cache(F cached_function = F(), std::size_t max_size = 1024)
     111             :     : super(max_size),
     112           1 :       m_cached_function(cached_function)
     113           1 :   {}
     114             : 
     115             :   /// \brief Stores the given key-value pair in the cache. Depending on the cache policy and capacity an existing element
     116             :   ///        might be removed.
     117         100 :   auto operator()(Args... args) -> typename std::invoke_result_t<F, Args...>
     118             :   {
     119             :     // The reason to split the find and emplace is that when we insert an element the replacement_candidate should not be
     120             :     // the key that we just inserted. The other way around, when an element that we are looking for was first removed and
     121             :     // then searched for also leads to unnecessary inserts.
     122         100 :     auto result = find(args...);
     123         100 :     if (result == m_map.end())
     124             :     {
     125             :       // If the cache would be full after an inserted.
     126         100 :       if (m_map.size() + 1 >= m_maximum_size)
     127             :       {
     128             :         // Remove an existing element defined by the policy.
     129           0 :         m_map.erase(m_policy.replacement_candidate(m_map));
     130             :       }
     131             : 
     132             :       // Insert an element and inform the policy that an element was inserted.
     133         100 :       auto emplace_result = m_map.emplace(std::make_pair(args..., m_cached_function(args...)));
     134             : 
     135         100 :       m_policy.inserted((*emplace_result.first).first);
     136         100 :       return emplace_result.first->second;
     137             :     }
     138             : 
     139           0 :     assert(m_map.size() <= m_maximum_size);
     140           0 :     return result->second;
     141             :   }
     142             : 
     143             : private:
     144             :   F m_cached_function; ///< The function of which the results are cached.
     145             : };
     146             : 
     147             : 
     148             : template<typename Key, typename T>
     149             : using fifo_cache = fixed_size_cache<fifo_policy<mcrl2::utilities::unordered_map<Key, T>>>;
     150             : 
     151             : template<typename F, typename Args>
     152             : using fifo_function_cache = function_cache<
     153             :   fifo_policy<mcrl2::utilities::unordered_map<Args, decltype(std::declval<F>()(std::declval<Args>()))>>,
     154             :   F,
     155             :   Args>;
     156             : 
     157             : } // namespace utilities
     158             : } // namespace mcrl2
     159             : 
     160             : #endif // MCRL2_UTILITIES_FIXED_SIZE_CACHE_H