EXT C++ Library - cache

The ext::cache is an abstract base class for implementing a complete STL-compatible container to introduce fast LRU cached access to slow data resources.


The caches are usually implemented by publicly inheriting the ext::cache parametrized to match the cache's requirements and overriding the .miss and .write virtual member functions. Template paramaters for the ext::cache are described below.


template <typename _T,
          unsigned int _Size,
          typename _IndexT = unsigned int>
class ext::cache {
        typedef _IndexT   key_type;
        typedef _T        data_type;
        typedef struct    value_type {
            data_type   item;
            key_type    index;
            bool        dirty;

            value_type ();

        typedef /* ... */          size_type;
        typedef /* ... */          difference_type;
        class                      iterator;
        class                      const_iterator;
        typedef value_type &       reference;
        typedef const value_type & const_reference;
        typedef value_type *       pointer;
        typedef const value_type * const_pointer;

        template <bool> data_type & hit (key_type);

        cache ();
        cache (const cache &); // deprecated
        cache & operator = (const cache &) // deprecated

        virtual ~cache () throw ();

        iterator          begin ();
        const_iterator    begin () const;
        iterator          end ();
        const_iterator    end () const;

        bool              empty () const;
        size_type         size () const;
        size_type         max_size () const;
        void              swap (cache &); // deprecated

        void              enable (bool = true);
        void              disable ();
        void              flush ();
        void              clear ();

        data_type &       access (key_type);
        const data_type & read (key_type);

        virtual void      miss  (key_type, data_type &) = 0;
        virtual void      write (key_type, const data_type &) = 0;

The ext::cache is not likely to fail due to memory issues during operations. The memory needed to store fully loaded cache is reserved in constructor.

Note that the destructor does not flush.

Call to any of the .read, .access, .disable, .flush or .clear member functions invalidates all iterators to the container. They invalidate also the reference returned by previous call to .read or .access member functions. It is not defined what these invalidated iterators and references remains pointing to, and this may change in future releases.

The overriden member function .miss is called everytime an item accessed is not present in the cache. It is supposed to load the data into a buffer referenced by the second function parameter.

The overriden member function .write is called everytime an item that has been changed is being flushed from the cache (due to flush operation or when there is no empty space for an item being loaded). The function is supposed to write data from a buffer referenced by the second function parameter back to the resource.


#include <ext/c++>

struct buffer_type {
    unsigned char page [4096];

class myCache : public ext::cache <buffer_type, 16> {
        virtual void miss  (unsigned int i, buffer_type & f) {
            // ... f = resource [i];
        virtual void write (unsigned int i, const buffer_type & f) {
            // ... resource [i] = f;

        ~myCache () throw () { this->flush (); }; };

See EXT C++ Library testsuite for another example.


Unless EXT_NO_WARNINGS is defined, although fully supported, the copy constructor, the assignment operator and the swap member function are marked as deprecated in GCC. This is introduced to issue a warning in case of using these dangerous operations because copying or assigning a ext::cache can result in cache incoherency bugs if not used very carefully.

Again, note that the destructor does not flush (does nothing at all). Derived classes should flush the cache. This is intended behavior to allow the .write member function to safely throw exceptions.

Note that it is safe to throw an exceptions from the .miss and .write overrides. In that case the state and contents of the container remains unchanged.

To improve access speed to huge resources, consider chaining two caches while keeping the cache closest to the user very small.