cache.hpp

Go to the documentation of this file.

/******************************************************************************
** Copyright © 2005 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "thread_pool_sequential.hpp"
#include "thread_pool_master.hpp"
#include "thread_pool_workers.hpp"
 
#include <limits>
#include <map>
#include <time.h>
 
/** \file
   This file declares the various object that comprise the cache namespace.
*/
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE { namespace cache {
 
   namespace private_ {
      template<typename Mdl> struct multi_or_sequential {
         static constexpr enum ppd::pool_traits::size_mode_t infinite_size_type=ppd::pool_traits::size_mode_t::infinite;   ///< We allow an arbitrarily large amount of work to be transferred.
         static constexpr enum ppd::pool_traits::size_mode_t fixed_size_type=ppd::pool_traits::size_mode_t::fixed_size; ///< Specifies that the thread pool is finite in size.
      };
      template<> struct multi_or_sequential<ppd::sequential_mode> {
         static constexpr enum ppd::pool_traits::size_mode_t infinite_size_type=ppd::pool_traits::size_mode_t::sequential;
         static constexpr enum ppd::pool_traits::size_mode_t fixed_size_type=ppd::pool_traits::size_mode_t::sequential;
      };
   }
 
   /// Adaptors for the single & multi-threading traits.
   template<typename Key, typename Val, class Comp=std::less<Key>, class Alloc=std::allocator<Val> >
   struct threading {
      /// The sequential trait.
      template<ppd::generic_traits::api_type API>
      struct single {
         /// Use a standard map as the basic associative collection.
         typedef std::map<Key, Val, Comp, Alloc> assoc_colln_t;
         typedef typename assoc_colln_t::value_type::second_type mapped_type;
 
         /// A sequential trait for executing work from which we do not need to get the results.
         /**
            For compatibility with the multi-threaded version.
         */
         typedef ppd::thread_pool<
            ppd::pool_traits::work_distribution_mode_t::one_thread_distributes<>,   ///< The master thread distributes the work.
            ppd::pool_traits::size_mode_t::sequential,   ///< This parameter specifies that it is sequential.
            ppd::pool_aspects<
               ppd::generic_traits::return_data::joinable,  ///< This parameter specifies that we may be interested in any results.
               API,
               ppd::sequential_mode,   ///< This parameter specifies that it is sequential.
               ppd::pool_traits::normal_fifo
            >
         > flusher_pool_t;
 
         /// A sequential trait for executing work from which we want to get the results.
         /**
            For compatibility with the multi-threaded version.
         */
         typedef ppd::thread_pool<
            ppd::pool_traits::work_distribution_mode_t::worker_threads_get_work<ppd::pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>,   ///< The underlying "thread pool" uses a work-stealing model.
            ppd::pool_traits::size_mode_t::sequential,   ///< This parameter specifies that it is sequential.
            ppd::pool_aspects<
               ppd::generic_traits::return_data::joinable,  ///< This parameter specifies that we may be interested in any results.
               API,
               ppd::sequential_mode,   ///< This parameter specifies that it is sequential.
               ppd::pool_traits::normal_fifo
            >
         > populate_pool_t;
      };
 
      /// The multi-threaded trait.
      template<ppd::generic_traits::api_type API, typename Mdl>
      struct multi {
         /// Use a standard map as the basic associative collection.
         /**
            An associative collection that supported locking on its methods would avoid the gross locks required in the cache itself.
         */
         typedef std::map<Key,Val,Comp,Alloc> assoc_colln_t;
         typedef typename assoc_colln_t::value_type::second_type mapped_type;
         typedef private_::multi_or_sequential<Mdl> multi_or_sequential_chooser;
 
         /// A multi-threaded trait for executing work from which we do not need to get the results.
         typedef typename ppd::thread_pool<
            ppd::pool_traits::work_distribution_mode_t::one_thread_distributes<>,   ///< The master thread distributes the work.
            multi_or_sequential_chooser::infinite_size_type,
            ppd::pool_aspects<
               ppd::generic_traits::return_data::joinable,  ///< This parameter specifies that we may be interested in any results.
               API,
               Mdl,
               ppd::pool_traits::normal_fifo,
               std::less
            >
         > flusher_pool_t;
 
         /// A multi-threaded trait for executing work from which we want to get the results.
         /**
            Note that this is a finite-sized thread pool.
         */
         typedef typename ppd::thread_pool<
            ppd::pool_traits::work_distribution_mode_t::worker_threads_get_work<ppd::pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>,   ///< The underlying thread pool uses a work-stealing model.
            multi_or_sequential_chooser::fixed_size_type,
            ppd::pool_aspects<
               ppd::generic_traits::return_data::joinable,  ///< This parameter specifies that we may be interested in any results.
               API,
               Mdl,
               ppd::pool_traits::normal_fifo
            >
         > populate_pool_t;
      };
   };
 
   /// A simple factory class that allows us to tell the cache how a value is made for a particular key.
   template<typename Key, typename Data>
   struct factory_base {
      typedef Key key_type;
      typedef Data value_type;
 
      virtual value_type __fastcall make(const key_type &) const=0;
      virtual ~factory_base() {}
   };
 
   /// An implementation of an Least Recently Used (LRU) algorithm for selecting victim entries in the cache for flushing.
   template<typename Val>
   class lru {
   public:
      typedef Val value_type;
 
      class criterion_t {
      public:
         explicit constexpr __stdcall criterion_t(const clock_t c) noexcept(true)
         : oldest(c) {
         }
 
         void operator=(criterion_t const &)=delete;
 
         template<class MapT_> bool __fastcall
         operator()(const MapT_ &val) const noexcept(true) {
            return val.second.accessed()<=oldest;
         }
 
      private:
         const clock_t oldest;
      };
 
      constexpr __stdcall lru(void);
      explicit constexpr __stdcall lru(const value_type &);
      __stdcall lru(const lru &);
      __stdcall ~lru(void);
      lru & __fastcall operator=(const lru &);
 
      const value_type & __fastcall value(void) const noexcept(true);
      value_type & __fastcall value(void) noexcept(true);
 
      clock_t __fastcall accessed(void) const noexcept(true);
 
      template<typename Iter> static const criterion_t __fastcall
      select(Iter beg,const Iter &end) {
         clock_t oldest=std::numeric_limits<clock_t>::max();
         while (beg!=end) {
            oldest=std::min(oldest,beg++->second.accessed());
         }
         return criterion_t(oldest);
      }
 
   private:
      mutable clock_t age;
      value_type range_value;
   };
 
   /// A trivial "no statistics" class.
   struct no_statistics {
      typedef unsigned long accesses_type;
      typedef unsigned long hits_type;
      typedef unsigned long flushes_type;
      typedef unsigned long creations_type;
 
      static constexpr accesses_type __fastcall accesses() noexcept(true) {
         return 0;
      }
      static constexpr hits_type __fastcall hits() noexcept(true) {
         return 0;
      }
      static constexpr flushes_type __fastcall flushes() noexcept(true) {
         return 0;
      }
      static constexpr creations_type __fastcall outstanding_fills() noexcept(true) {
         return 0;
      }
      friend constexpr tostream &operator<<(tostream &os, const no_statistics &) noexcept(true) {
         return os;
      }
 
      static void __fastcall accessed(void) noexcept(true) {}
      static void __fastcall hit(void) noexcept(true) {}
      static void __fastcall reset(void) noexcept(true) {}
      static void __fastcall flushed(void) noexcept(true) {}
   };
 
   /// Some basic statistic gathering.
   class basic_statistics {
   public:
      typedef unsigned long accesses_type;
      typedef unsigned long hits_type;
      typedef unsigned long flushes_type;
      typedef unsigned long creations_type;
 
      constexpr __stdcall basic_statistics(void) noexcept(true);
      __stdcall basic_statistics(const basic_statistics &) noexcept(true);
      virtual __stdcall ~basic_statistics(void) noexcept(true);
      basic_statistics & __fastcall operator=(const basic_statistics &) noexcept(true);
 
      /// Total number of accesses to the cache.
      accesses_type __fastcall accesses(void) const noexcept(true);
      /// Total number of hits into the cache.
      hits_type __fastcall hits(void) const noexcept(true);
      /// Total number of cache flushes.
      flushes_type __fastcall flushes(void) const noexcept(true);
      /// Total number of outstanding cache fills.
      /**
         More useful for the multi-threaded cache to help tune the cache high- and low-water marks
         and pool size for creating range-data the cache.
      */
      creations_type __fastcall outstanding_fills(void) const noexcept(true);
 
      /// Write all of the statistics to an output stream, in a formatted manner.
      /**
         \param os   The output stream, templated for narrow or wide char use, based upon the definition or not of the preprocessor constant JMMCG_WIDE_CHARS. Idf not defined, standard "char" traits are used, otherwise "wchar_t" traits.
         \param stats   The basic_statistics object that should be written.
         \return  A reference to that "std::ostream" that was passed in.
      */
      friend tostream &operator<<(tostream &os, const basic_statistics &stats);
 
      /// Increment the "accessed" counter by 1.
      void __fastcall accessed(void) noexcept(true);
      /// Increment the "total hits" counter by 1.
      void __fastcall hit(void) noexcept(true);
      /// Increment the "total flushes" counter by 1.
      void __fastcall flushed(void) noexcept(true);
      /// Reset all of the counters.
      void __fastcall reset(void) noexcept(true);
 
   private:
      accesses_type total_accesses_;
      hits_type total_hits_;
      flushes_type total_flushes_;
   };
 
   /// A base cache class, for deriving from to provide the real functionality.
   /**
      This class provides a low-level interface for the various cache types that can be
      declared to allow some sort of compatibility and flexibility between them.
      It also contains the factory, that identifies the basic properties of a cache:
      the key and value types. Flush policies, statistics and threading are all extra
      sugar, to some extent.
   */
   template<
      class Factory
   >
   class base {
   public:
      typedef Factory factory_type; ///< The factory that is used to create a range-data value for a particular key.
      typedef typename factory_type::key_type key_type;  ///< The type of the key.
      typedef typename factory_type::value_type value_type; ///< The type of the range-data.
 
      __stdcall base(const base &);
      virtual __stdcall ~base(void) noexcept(true);
 
      base & __fastcall operator=(const base &);
 
      /// Returns "true" iff the internal, associative collection is empty.
      virtual bool __fastcall empty() const noexcept(true)=0;
      /// This function will reset any statistics upon clearing all contents from the internal, associative collection.
      virtual void __fastcall clear()=0;
 
      /// Flush the contents of the cache according to the flush policy.
      /**
         The flush policy must be specified by a deriving class. The direct call to "flush" is run on the same thread, not another thread wrt the caller.
      */
      virtual void __fastcall flush()=0;
 
   protected:
      struct range_data {
         typename factory_type::value_type data;
      };
      /// This class creates the data for a particular key, using the supplied factory.
      class find_range_data {
      public:
         typedef range_data result_type;
 
         explicit __stdcall find_range_data(const factory_type &f,const key_type &i)
         : data_factory_(f),id(i) {
         }
         __stdcall find_range_data(const find_range_data &gw) noexcept(true)
         : data_factory_(gw.data_factory_),id(gw.id) {
         }
         ~find_range_data() {
         }
 
         void operator=(find_range_data const &)=delete;
 
         void __fastcall process(range_data &res) {
            res.data=data_factory_.make(id);
         }
 
         bool __fastcall operator<(find_range_data const &) const noexcept(true) {
            return true;
         }
 
      private:
         const factory_type &data_factory_;
         const key_type id;
      };
 
      /// This class flushes the internal associative collection of the cache according to the flush policy.
      class flush_cache {
      public:
         typedef void result_type;
 
         explicit __stdcall flush_cache(base<Factory> &r) noexcept(true)
         : the_cache(r) {
         }
         __stdcall flush_cache(const flush_cache &r) noexcept(true)
         : the_cache(r.the_cache) {
         }
         ~flush_cache() {
         }
 
         void operator=(flush_cache const &)=delete;
 
         void __fastcall process() {
            the_cache.flush();
         }
 
         bool __fastcall operator<(flush_cache const &) const noexcept(true) {
            return true;
         }
 
      private:
         base<Factory> &the_cache;
      };
 
      explicit __stdcall base(const factory_type &f)
      : data_factory_(f) {
      }
 
      const factory_type & __fastcall data_factory() const noexcept(true);
 
   private:
      factory_type data_factory_;
   };
 
   /// A read-only cache that returns a const reference to the range data.
   /**
      The cache is a value-type, so you can have caches of caches.
   */
   template<
      class Factory,
      class FP=lru<typename Factory::value_type>,  ///< We default to an LRU flush policy.
      class ThrT=typename threading<typename Factory::key_type,FP>::template single<ppd::platform_api>,  ///< We default to a sequential policy.
      class Stats=no_statistics  ///< We default to not collecting any statistics.
   >
   class ro : public base<Factory> {
   public:
      typedef base<Factory>base_t;
      typedef typename base_t::factory_type factory_type;   ///< The actual factory type.
      typedef typename base_t::key_type key_type;  ///< The type of the key.
      typedef ThrT thread_traits;   ///< The type of threading in force.
      typedef Stats statistics_type;   ///< The statistics that will be gathered.
      typedef typename thread_traits::assoc_colln_t colln_t;   ///< The type of the internal associative collection.
      typedef typename colln_t::size_type size_type;  ///< The size type of the internal associative collection.
      typedef const typename thread_traits::mapped_type mapped_type; ///< The range-data type of the key type.
      typedef typename thread_traits::flusher_pool_t::exception_type exception_type;   ///< The base class from which the exceptions that will be thrown by this class are derived.
      typedef typename thread_traits::flusher_pool_t::pool_traits_type::os_traits os_traits;
      typedef typename os_traits::lock_traits lock_traits;
 
      /// The "low water mark" of the cache.
      /**
         The flush policy will attempt to ensure that size()>=low_water_mark.
         But this is not guaranteed, because there may be outstanding cache fills from another thread.
         \see size()
      */
      const size_type low_water_mark;
      /// The "high water mark" of the cache.
      /**
         The flush policy will attempt to ensure that size()<=high_water_mark.
         But this is not guaranteed, because there may be outstanding cache fills from another thread.
         \see size()
      */
      const size_type high_water_mark;
 
      /// Create an empty read-only cache.
      /**
         \param low_water  This is the low_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()>=low_water_mark.
         \param high_water This is the high_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()<=high_water_mark.
         \param num_threads   This is the number of threads in the thread pool used for creating range-data for satisfying data requests. This number is set to prevent any data source (e.g. a database) from becoming overwhelmed by requests.
         \param f    The factory that is used to create a range-data item for a particular key.
         \see size()
      */
      explicit constexpr __stdcall ro(const size_type low_water, const size_type high_water, const typename thread_traits::populate_pool_t::pool_type::size_type num_threads, const factory_type &f)
      : base<Factory>(f), low_water_mark(low_water), high_water_mark(high_water), serialize(), flusher_pool(), populate_pool(num_threads), internal_cache(), statistics_() {
      }
      /// Create a read-only cache and populate it with some values.
      /**
         Note that a (possibly) asynchronous flush() may occur after the population to ensure that the
         max_size of the cache is maintained.
         \param low_water  This is the low_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()>=low_water_mark.
         \param high_water This is the high_water_mark of the cache. i.e. using the flush policy the cache will attempt to ensure that size()<=high_water_mark.
         \param num_threads   This is the number of threads in the thread pool used for creating range-data for satisfying data requests. This number is set to prevent any data source (e.g. a database) from becoming overwhelmed by requests.
         \param f    The factory that is used to create a range-data item for a particular key.
         \param beg  An iterator to the beginning of the source data.
         \param end  An iterator to the end of the source data.
         \see size()
         \see insert()
      */
      template<typename Iter> constexpr __stdcall
      ro(const size_type low_water, const size_type high_water, const typename thread_traits::populate_pool_t::pool_type::size_type num_threads, const factory_type &f, const Iter &beg, const Iter &end)
      : base<Factory>(f), low_water_mark(low_water), high_water_mark(high_water), serialize(), flusher_pool(), populate_pool(num_threads), internal_cache(beg, end) {
      }
      __stdcall ro(const ro &);
      virtual __stdcall ~ro(void) noexcept(true);
 
      ro & __fastcall operator=(const ro &);
 
      /// Indicate if the cache is empty.
      /**
         Note that this does not take into account any outstanding cache fills nor flush()s.
         \return "true" iff size()==0.
         \see size()
         \see flush()
      */
      bool __fastcall empty(void) const noexcept(true) override;
      /// Indicate the number of data items in the cache.
      /**
         Note that this does not take into account any outstanding cache fills nor flush()s.
         \see flush()
      */
      const size_type __fastcall size(void) const noexcept(true);
      /// Synchronously remove all data within the cache.
      /**
         Note that this does not take into account any outstanding cache fills nor flush()s.
         Thus after this function it is not guaranteed that empty()==true.
         This function will reset any statistics upon clearing all contents from the cache.
         \see flush()
         \see empty()
      */
      void __fastcall clear(void) override;
 
      /// Synchronously insert a range of values into the cache.
      /**
         Note that a (possibly) asynchronous flush() may occur after the population to ensure that the
         size()~<=high_water_mark of the cache is maintained.
         \param beg  An iterator to the beginning of the source data.
         \param end  An iterator to the end of the source data.
         \see flush()
      */
      template<typename Iter> void __fastcall
      insert(const Iter &beg, const Iter &end) {
         internal_cache.insert(beg, end);
         flusher_pool<<flush_nonjoinable()<<flush_cache(*this);
      }
      /// Lookup and return the range-data value associated with a key from the map.
      /**
         The creation of the range-data value may be asynchronous, as an implementation-defined optimization for multi-threaded caches.
         A (possibly) asynchronous flush() is called to ensure that the high_water_mark is not exceeded before this function returns. Note that for asynchronous calls to flush(), they are only run once: overlapping calls to flush() will cause the later calls to be quashed, such that no buffering of flush()es occurs.
         Note that it is guaranteed that empty()==false after this call.
         \param key  The key to look up in the map and return the range-data value.
         \return A const-qualified copy of the range data value associated with the key. This ensures that if an asynchronous flush() of the data item occurs, this will not leave a dangling reference in the client.
         \see flush()
         \see empty()
      */
      const mapped_type __fastcall operator[](const key_type &key);
      /// A synchronous call to flush the cache according to the flush policy.
      /**
         Note that if two or more items within the cache satisfy the victimization criterion, and removing at least one of them would
         ensure that the max_size criterion is satisfied, it is implementation defined regarding which of those items woulsd be flushed.
      */
      void __fastcall flush(void) override;
 
      const statistics_type & __fastcall statistics(void) const noexcept(true);
 
   private:
      typedef FP victimization_traits;
      typedef typename lock_traits::critical_section_type atomic_t;
      typedef typename atomic_t::write_unlockable_type lock_t;
      typedef typename thread_traits::flusher_pool_t::nonjoinable flush_nonjoinable;
 
      mutable atomic_t serialize;
      mutable typename thread_traits::flusher_pool_t flusher_pool;
      mutable typename thread_traits::populate_pool_t populate_pool;
      mutable colln_t internal_cache;
      mutable statistics_type statistics_;
   };
 
   /**
      \todo Implement using the advice given in "Standard C++ IOStreams and Locales" by A.Langer & K.Kreft, page 170.
   */
   template<class F_,class P_,class TT_,class S_> tostream & __fastcall
   operator<<(tostream &os, const ro<F_,P_,TT_,S_> &r) {
      os<<_T("Low water-mark=")<<r.low_water_mark
         <<_T(", high water-mark=")<<r.high_water_mark
         <<_T(", current number of elements=")<<r.size();
      return os;
   }
 
} } }
 
#include "cache_impl.hpp"