A splay_cache is a fixed-size splay tree for cache operations. More...

#include <splay_cache.h>

Classes
struct	node
	One node in the splay tree contains pointers to children and the templated (key, value) pair. More...

class	splay_cache_exception
	Basic exception for splay_cache interactions. More...

Public Member Functions
	splay_cache (uint64_t max_size=std::numeric_limits< uint64_t >::max())
	Creates a splay tree cache with maximum size (or unlimited size, if no size is given). More...

	splay_cache (splay_cache &&)
	splay_cache can be move constructed

splay_cache &	operator= (splay_cache &&)
	splay_cache can be move assigned More...

	~splay_cache ()
	Frees all objects in the cache.

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

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

uint64_t	size () const

void	clear ()
	Empties the cache.

Private Member Functions
	splay_cache (const splay_cache &)=delete
	disallow copying

splay_cache &	operator= (const splay_cache &)=delete
	disallow assignment

void	clear (node *&subroot)
	Deletes everything at this subroot and below. More...

void	insert (node *&subroot, const Key &key, const Value &value)
	Inserts the given key, value pair into the tree rooted at subroot. More...

void	replace (node *subroot, const Key &key, const Value &value)
	Replaces the key, value pair contained in the node pointed to by subroot with the given key, value pair. More...

void	find (node *&subroot, const Key &key)
	"Finds" the given key in the tree rooted at subroot. More...

void	rotate_left (node *&subroot)
	Rotates the tree rooted at subroot to the left. More...

void	rotate_right (node *&subroot)
	Rotates the tree rooted at subroot to the right. More...

Private Attributes
uint64_t	size_
	the current size of the cache

uint64_t	max_size_
	the maximum allowed size for the cache

node *	root_
	the root of the tree

std::mutex	mutables_
	the mutex that synchronizes access to the cache

Detailed Description

template<class Key, class Value>
class meta::caching::splay_cache< Key, Value >

A splay_cache is a fixed-size splay tree for cache operations.

Constructor & Destructor Documentation

template<class Key , class Value >

meta::caching::splay_cache< Key, Value >::splay_cache ( uint64_t max_size = std::numeric_limits<uint64_t>::max() )

Creates a splay tree cache with maximum size (or unlimited size, if no size is given).

Parameters

max_size The maximum number of nodes that will be in the splay tree

Member Function Documentation

template<class Key , class Value >

splay_cache< Key, Value > & meta::caching::splay_cache< Key, Value >::operator= ( splay_cache< Key, Value > && rhs )

splay_cache can be move assigned

Returns: the current splay_cache

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::insert	(	const Key &	key,
		const Value &	value
	)

Parameters

key	The key to insert
value	The value to insert

If the key exists in the map, it will be overwritten.

template<class Key , class Value >

util::optional< Value > meta::caching::splay_cache< Key, Value >::find ( const Key & key )

Parameters

key	The key to find the corresponding value for

Returns: an optional containing the associated value for the given key, if found

template<class Key , class Value >

uint64_t meta::caching::splay_cache< Key, Value >::size ( ) const

Returns: the number of elements in the cache

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::clear ( node *& subroot )

private

Deletes everything at this subroot and below.

Parameters

subroot The root of the subtree to clear

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::insert	(	node *&	subroot,
		const Key &	key,
		const Value &	value
	)

private

Inserts the given key, value pair into the tree rooted at subroot.

Parameters

subroot	The root of the subtree to insert into
key
value

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::replace	(	node *	subroot,
		const Key &	key,
		const Value &	value
	)

private

Replaces the key, value pair contained in the node pointed to by subroot with the given key, value pair.

Parameters

subroot
key
value

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::find	(	node *&	subroot,
		const Key &	key
	)

private

"Finds" the given key in the tree rooted at subroot.

This function does not return anything because it splays the desired value to the root, so the public find() can simply return the root after calling this function.

Parameters

subroot
key

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::rotate_left ( node *& subroot )

private

Rotates the tree rooted at subroot to the left.

Parameters

subroot

template<class Key , class Value >

void meta::caching::splay_cache< Key, Value >::rotate_right ( node *& subroot )

private

Rotates the tree rooted at subroot to the right.

Parameters

subroot

The documentation for this class was generated from the following files:

/home/chase/projects/meta/include/caching/splay_cache.h
/home/chase/projects/meta/include/caching/splay_cache.tcc

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class Key, class Value> class meta::caching::splay_cache< Key, Value >

Constructor & Destructor Documentation

Member Function Documentation

template<class Key, class Value>
class meta::caching::splay_cache< Key, Value >