STL::Cache - in-memory cache for C++ applications

Introduction

   STL::Cache is just a simple wrapper over standard map, that implements
   some cache algorithms, thus allowing you to limit the storage size and
   automatically remove unused items from it. (Right now the std::map
   interface is partially implemented, so it can't be used as a drop-in
   replacement for the std::map).

   It is intented to be used for keeping any key/value data, especially
   when data's size are too big, to just put it into the map and keep the
   whole thing. With STL::Cache you could put unlimited (really unlimited)
   amount of data into it, but it will store only some small part of your
   data. So re-usable data will be kept near your code and not so popular
   data will not spend expensive memory.

   STL::Cache uses configurable policies, for decisions, whether data are
   good, to be kept in cache or they should be thrown away. It is shipped
   with 8 policies and you are free to implement your own.

Getting and installing

   The STL::Cache source code is hosted on github, so you can download
   the source code using wget or other download tool:
     * https://github.com/akashihi/stlcache/tarball/master (tar.gz
       format)
     * https://github.com/akashihi/stlcache/zipball/master (or zip
       format)

   You could also clone the repository and check some unstable code:
     git clone git://github.com/akashihi/stlcache.git

   The 'master' branch is always pointing to the latest stable release and
   the 'next' branch is a unstable development branch.

   The STL::Cache is header only and does not require any building. Just
   copy the include/stlcache directory to your system's include
   directories or add it to your project's include directories.
   Alternativaly you could build the sources and then install it, using
   our build system.

   Yes, as i told you, the STL::Cache themself is a header-only library
   and doesn't requires building. Indeed, it is shipped with tests,
   documentation and other stuff, that could be built and used. For
   STL::Cache building you need:
     * Recent CMake (required)
     * Boost library (required for tests otherwise optional)
     * Doxygen (optional, only for documentation processing)

   After getting this stuff up and running, select a directory for
   building and issue the following commands:
        cmake /path/to/the/stlcache/sources
        make
        make test
        make doc
        make install

   The CMake is using a out-of-source build approach, so it is
   recommended to create a temporary build directory somewhere and remove
   it after installation.

   The generated documentation will be put into the <build>/doc directory
   and tests will be built and run directly in the <build> directory. They
   are NOT installed by 'make install' command, so you have to copy them
   manually, if you really need them.

Usage

   Select a cache expiration policy , configure cache with it,
   construct the cache, specifying it's size, and start putting data into
   the cache:
     typedef CacheLRU stlcache::cache<int,string,stlcache::policy_lru>;
     CacheLRU myCache(10);

   The policy, key data type and value data type are passed as parameters
   to the stlcache::cache class template. In the example above we have
   constructed cache, that keeps data of type std::string and keys are of
   type int. It uses a LRU policy for removal of excessive items.
   Cache object 'myCache' is able to keep only 10 items. Cache size is
   configured at the construction time and cannot be changed in the future
   (with exceptions for assignment and swap operations). Additionally you
   could specify a comparision object and allocator type, see the
   cache class documentation for the details.

   You could put objects into your cache object using insert call:
     myCache.insert(1,"One)";

   Note, that the insert call could throw a cache full exception
   or invalid key exception As keys have to be unique, the insert call
   may do nothing, if it meets the duplicate key. Don't forget to check
   it's return value.

   If you are not sure, whether you have element in the cache or not, 
   you can use a safe insert_or_assign call, that will either add new element 
   to the cache or update exiting one with the new value.

   Now, when you have some data in the cache, you may want to retrieve it
   back:
     string myOne = myCache.fetch(1);

   The fetch call will return a data value, associated with the
   supplied key or throw the invalid key exception when the key
   doesn't exists in the cache. For safier operations, you could check
   in advance, whether key is in the cache or not:
     string myOne;
     if (myCache.check(1)) {
       myOne = myCache.fetch(1);
     }

   The check is exception-safe.

   Both check and fetch calls are increasing internal reference
   count for the key, so, depending on the used policy, it will increase
   or decrease the entry's chance to become an expiration victim. Under
   some circumstances you may need to manually change those reference
   counter, without actually accesing the entry. Something like
   touching it:
     myCache.touch(1);

   The cache::touch call is exception-safe and could be used even on
   non-existent keys.

   When you have done your work, you may manually delete the entry:
     myCache.erase(1);

   Check it's return value, to get sure, whether something was deleted or
   not.

Thread safety

    cache can be configured with different locking implementations, thus implementing thread safety. By default a non-locking approach is used and cache is not thread-safe, allowing user to implement external locking. STL::Cache is shipped with the following locking implementations:

        * non-locking - No locking will be done with that implementation, leaving cache non thread-safe. Class name is lock_none
        * exclusive locking - cache will be locked exclusively on almost every call, thus limiting parallel usage to a single thread. Class name is lock_exclusive
        * shared locking - Some calls will be allowed to be run in parallel with this policy. But, due to nature of the cache , even operations, that seems to be non-modifying, require exclusive lock to 
          update access tracking data. This implementation is only available when Boost extensions are enabled. Class name is lock_shared
The locking implementation must be specified as a last parameter of cache type and it is optional.

Boost integration
    Since version 0.3 stlcache includes some Boost specific extensions: optional values, multi-map based policies and not really effective thread safety.

  boost::optional
    boost::optional allows user to safely get values from the cache for any key, whether key exists or not. You will need boost:optional headers available and have to define USE_BOOST_OPTIONAL macro.

    Example:

        cache<string,string,policy_lru> cache_lru(3);
        cache_lru.insert("key","value");
        cache_lru.touch("key");
        optional<string> value = cache_lru.get("key");
        if (name) {
            cout<<"We have some value in the cache: "<<*name;
        }
        cache_lru.erase("key");
  lock_shared
    lock_shared locking implementation allows user to execute some cache to calls in parallel and thread-safe way. You have to define USE_BOOST_OPTIONAL macro to access that locking implementation.

  lfu_multi_index
    lfu_multi_index implementes LFU algorithm using a Boost MultiIndex map, which is more slower, but uses less RAM, comparing to the typical LFU implementation. You have to define USE_BOOST_OPTIONAL macro to access that policy.


Policies

   The policy is a pluggable implementation of a cache algorithms,
   used for finding and removing excessive cache entries. STL::Cache is
   shipped with the following policies:
     * None - A random expiration policy. Removes some random entry on
       request
     * LRU - 'Least recently used' policy.
     * MRU - 'Most recentrly used' policy
     * LFU - 'Least frequently used' policy
     * LFU (Multi-index) - 'Least frequently used' policy implemented on top of the multi index map. Requires Boost.
     * LFU* - 'Least frequently used' policy, that expires only items
       with refcount 1, as proposed by M.Arlitt
     * LFU-Aging - 'Least frequently used' policy with time-based
       decreasing of usage count
     * LFU*-Aging - Combination of LFU* and LFU*-Aging
       policies
     * Adaptive Replacement - 'Adaptive Replacement' policy

   The cache expiration policy must be specified as a third parameter of
   cache type and it is mandatory.

your own policy

   The policy implementation should keep track of entries in the cache and
   it must be able to tell the cache, what item should be expired at the
   moment. There is not any limitations on policy internal structure and
   stuff, but it is expected, that policy conforms to some predefined
   interfaces.

   First of all - every policy is built in two classes, one class is the
   policy iteslf, and another one is a 'bind wrapper':

   Note:
          All code examples in this section are from policy none

        struct policy_none {
        template <typename Key, template <typename T> class Allocator>
            struct bind : _policy_none_type<Key,Allocator> {
                bind(const bind& x) : _policy_none_type<Key,Allocator>(x)  { }
                bind(const size_t& size) : _policy_none_type<Key,Allocator>(size
) { }
            };
        };

   As you may see, the policy itself is automatically configured with
   caches's Key type and Allocator type. Of course, you could also pass
   your own template parameters and partially instantiate the policy
   implementation template:
        template <class R> struct policy_none {
            template <typename Key, template <typename T> class Allocator>
                struct bind : _policy_none_type<R,Key,Allocator> {
                    bind(const bind& x) : _policy_none_type<R,Key,Allocator>(x)
{ }
                    bind(const size_t& size) : _policy_none_type<R,Key,Allocator
>(size) { }
                };
        };

   You could pass some implementation of R during cache type definition:
         stlcache::cache<int,int,stlcache::policy_none<Randomizer> > c;

   Well, the actual implementation must implement the policy interface
   :
        template <class Key,template <typename T> class Allocator> class policy
{
            public:
            virtual void insert(const Key& _k) throw(exception_invalid_key)
=0;
            virtual void remove(const Key& _k) throw() =0;
            virtual void touch(const Key& _k) throw() =0;
            virtual void clear() throw() =0;
            virtual void swap(policy<Key,Allocator>& _p) throw(exception_inv
alid_policy)=0;
            virtual const _victim<Key> victim() throw()  =0;
        };

   So, the policy could be asked for a victim , entries could be
   inserted , removed and touched . It's contents could also
   be cleared or swapped with another policy. Concrete policy
   implementation should be CopyConstructible, Assignable and must provide
   a constructor, for specifiying policy size:
        template <class Key, template <typename T> class Allocator> class _polic
y_none_type : public policy<Key,Allocator> {
        public:
            _policy_none_type<Key,Allocator>& operator= ( const _policy_none_typ
e<Key,Allocator>& x) throw() { }
            _policy_none_type(const _policy_none_type<Key,Allocator>& x) throw()
 {}
            _policy_none_type(const size_t& size ) throw() { }

            virtual void insert(const Key& _k) throw(exception_invalid_key)
{}
            virtual void remove(const Key& _k) throw() {}
            virtual void touch(const Key& _k) throw() {}
            virtual void clear() throw() {}
            virtual void swap(policy<Key,Allocator>& _p) throw(exception_inv
alid_policy) {}

            virtual const _victim<Key> victim() throw() {}
        };

   It's up to you, how you will implement those methods and so on. The
   only importatn thing, we haven't mentioned yet, is a victim class.
   It is a way to return optional value from a function. So, when your
   policy implementatiton cannot find any entry to remove, it will return
   empty victim object.

Authors and Licensing

   Copyright (C) 2011-2018 Denis V Chapligin, Martin Hrabovsky, Vojtech Ondruj, Tom Anderson
   Distributed under the Boost Software License, Version 1.0. 
   (See accompanying file LICENSE_1_0.txt
   or copy at http://www.boost.org/LICENSE_1_0.txt)