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_CACHE_POLICY_H
      11             : #define MCRL2_UTILITIES_CACHE_POLICY_H
      12             : 
      13             : #include <forward_list>
      14             : 
      15             : #include <cassert>
      16             : 
      17             : namespace mcrl2
      18             : {
      19             : namespace utilities
      20             : {
      21             : 
      22             : /// \brief An interface to implement a replacement policy for the fixed_size_cache.
      23             : template<typename Map>
      24             : class replacement_policy
      25             : {
      26             : public:
      27             :   using key_type = typename Map::key_type;
      28             :   using map_type = Map;
      29             : 
      30             : protected:
      31             :   /// \brief Called whenever the underlying cache is cleared.
      32             :   virtual void clear() = 0;
      33             : 
      34             :   /// \brief Called whenever a new element has been inserted into the cache.
      35             :   virtual void inserted(const key_type& key) = 0;
      36             : 
      37             :   /// \returns An iterator to the key that should be replaced when the cache is full.
      38             :   virtual typename Map::iterator replacement_candidate(Map& map) = 0;
      39             : 
      40             :   /// \brief Called whenever an element was found in the cache.
      41             :   virtual void touch(const key_type& key) = 0;
      42             : };
      43             : 
      44             : /// \brief A policy that replaces an arbitrary (but not random) element.
      45             : template<typename Map>
      46             : class no_policy final : public replacement_policy<Map>
      47             : {
      48             : public:
      49             :   using key_type = typename Map::key_type;
      50             : 
      51             :   typename Map::iterator replacement_candidate(Map& map) override { return map.begin(); }
      52             : 
      53             :   // Not implemented.
      54             :   void clear() override {}
      55             :   void inserted(const key_type&) override {}
      56             :   void touch(const key_type&) override {}
      57             : };
      58             : 
      59             : template<typename Map>
      60             : class fifo_policy final : public replacement_policy<Map>
      61             : {
      62             : public:
      63             :   using key_type = typename Map::key_type;
      64             : 
      65           1 :   fifo_policy()
      66           1 :   {
      67           1 :     m_last_element_it = m_queue.before_begin();
      68           1 :   }
      69             : 
      70             :   fifo_policy(const fifo_policy& other)
      71             :     : m_queue(other.m_queue)
      72             :   {
      73             :     update_last_element_it();
      74             :   }
      75             : 
      76             :   fifo_policy& operator=(const fifo_policy& other)
      77             :   {
      78             :     m_queue = other.m_queue;
      79             :     update_last_element_it();
      80             :     return *this;
      81             :   }
      82             : 
      83             :   // These moves work when moving m_queue guarantees that m_last_element_it remains valid.
      84             :   fifo_policy(fifo_policy&& other) noexcept = default;
      85             :   fifo_policy& operator=(fifo_policy&& other) noexcept = default;
      86             : 
      87           0 :   void clear() override
      88             :   {
      89           0 :     m_queue.clear();
      90           0 :     update_last_element_it();
      91           0 :   }
      92             : 
      93           0 :   typename Map::iterator replacement_candidate(Map& map) override
      94             :   {
      95           0 :     assert(!m_queue.empty());
      96             :     // Remove the first key (the first one to be inserted into the queue).
      97           0 :     auto it = map.find(m_queue.front());
      98           0 :     m_queue.erase_after(m_queue.before_begin());
      99           0 :     assert(it != map.end());
     100           0 :     return it;
     101             :   }
     102             : 
     103         100 :   void inserted(const key_type& key) override
     104             :   {
     105             :     // A new key was inserted, so it must be the last one to be removed.
     106         100 :     m_last_element_it = m_queue.insert_after(m_last_element_it, key);
     107         100 :   }
     108             : 
     109           0 :   void touch(const key_type&) override
     110           0 :   {}
     111             : 
     112             : private:
     113           0 :   void update_last_element_it()
     114             :   {
     115             :     // Update the iterator to the last element of the queue.
     116           0 :     for (auto it = m_queue.before_begin(); it != m_queue.end(); ++it)
     117             :     {
     118           0 :       m_last_element_it = it;
     119             :     }
     120           0 :   }
     121             : 
     122             :   std::forward_list<key_type> m_queue;
     123             :   typename std::forward_list<key_type>::iterator m_last_element_it;
     124             : };
     125             : 
     126             : } // namespace utilities
     127             : } // namespace mcrl2
     128             : 
     129             : #endif // MCRL2_UTILITIES_CACHE_POLICY_H