splay_cache.h

Go to the documentation of this file.

#ifndef META_SPLAY_CACHE_H_
#define META_SPLAY_CACHE_H_

#include <memory>
#include <mutex>
#include <vector>

#include "meta.h"
#include "util/optional.h"

namespace meta
{
namespace caching
{

template <class Key, class Value>
class splay_cache
{
  public:
    splay_cache(uint64_t max_size = std::numeric_limits<uint64_t>::max());

    splay_cache(splay_cache&&);

    splay_cache& operator=(splay_cache&&);

    ~splay_cache();

    void insert(const Key& key, const Value& value);

    util::optional<Value> find(const Key& key);

    uint64_t size() const;

    void clear();

  private:
    splay_cache(const splay_cache&) = delete;

    splay_cache& operator=(const splay_cache&) = delete;

    struct node
    {
        node* left;
        node* right;
        Key key;
        Value value;

        node(const Key& new_key, const Value& new_value)
            : left(nullptr), right(nullptr), key(new_key), value(new_value)
        {
            /* nothing */
        }
    };

    uint64_t size_;
    uint64_t max_size_;
    node* root_;
    mutable std::mutex mutables_;

    void clear(node*& subroot);

    void insert(node*& subroot, const Key& key, const Value& value);

    void replace(node* subroot, const Key& key, const Value& value);

    void find(node*& subroot, const Key& key);

    void rotate_left(node*& subroot);

    void rotate_right(node*& subroot);

  public:
    class splay_cache_exception : public std::runtime_error
    {
      public:
        using std::runtime_error::runtime_error;
    };
};
}
}

#include "caching/splay_cache.tcc"
#endif