mbl_lru_cache< I, V > Class Template Reference

Least recently used cache. More...

#include <mbl_lru_cache.h>

List of all members.

Public Member Functions
	mbl_lru_cache ()
	mbl_lru_cache (unsigned n)
	Create a cache of size n.
const V *	lookup (const I &index)
	Lookup index in the cache.
void	insert (const I &index, const V &value, bool dont_if_full=false)
	Insert this value into the cache.
void	clear ()
bool	full () const
void	resize (unsigned n)
Private Types
typedef vcl_list< I >	list_type
	Allow least recently used item to be found quickly $O(1)$.
typedef vcl_map< I, vcl_pair < V, typename list_type::iterator > >	map_type
	Allow value to be looked up quickly $O((n))$ given index.
Private Attributes
list_type	l_
	Allow least recently used item to be found quickly $O(1)$.
map_type	m_
unsigned long	n_
	Limit of cache size.

---

Detailed Description

template<class I, class V>
class mbl_lru_cache< I, V >

Least recently used cache.

This cache is optimised for speed and is not very memory efficient.

Parameters:

I	is the index type
V	is the value type

Definition at line 19 of file mbl_lru_cache.h.

---

Member Typedef Documentation

template<class I , class V >

typedef vcl_list<I> mbl_lru_cache< I, V >::list_type [private]

Allow least recently used item to be found quickly $O(1)$.

Definition at line 22 of file mbl_lru_cache.h.

template<class I , class V >

typedef vcl_map<I, vcl_pair<V, typename list_type::iterator> > mbl_lru_cache< I, V >::map_type [private]

Allow value to be looked up quickly $O((n))$ given index.

Definition at line 27 of file mbl_lru_cache.h.

---

Constructor & Destructor Documentation

template<class I , class V >

mbl_lru_cache< I, V >::mbl_lru_cache

(

)

[inline]

Definition at line 34 of file mbl_lru_cache.h.

template<class I , class V >

mbl_lru_cache< I, V >::mbl_lru_cache

(

unsigned

n

)

[inline]

Create a cache of size n.

The actual memory size of the cache will be n * (sizeof(V) + 2*sizeof(I) + overhead(map element) + overhead(list element).

For many implementations overhead(list element) = 2 * sizeof(void *), and overhead(map element) = 3 * sizeof(void *) + sizeof(enum).

e.g. on a 32 bit computer, where I is a pair<unsigned, unsigned> and V is a double, memory size = n * (8 + 16 + 16 + 8). This makes the cache 17% space efficient - not very good.

Definition at line 47 of file mbl_lru_cache.h.

---

Member Function Documentation

template<class I , class V >

void mbl_lru_cache< I, V >::clear

(

)

[inline]

Definition at line 93 of file mbl_lru_cache.h.

template<class I , class V >

bool mbl_lru_cache< I, V >::full

(

)

const [inline]

Definition at line 94 of file mbl_lru_cache.h.

template<class I , class V >

void mbl_lru_cache< I, V >::insert	(	const I &	index,
		const V &	value,
		bool	dont_if_full = false
	)		[inline]

Insert this value into the cache.

For speed this method assumes that the index isn't already in the cache.

Parameters:

dont_if_full	If true, and the cache is full, then the cache will not be modified.
value	The value to be inserted in the cache
index	Index to access the value

Definition at line 72 of file mbl_lru_cache.h.

template<class I , class V >

const V* mbl_lru_cache< I, V >::lookup

(

const I &

index

)

[inline]

Lookup index in the cache.

Returns:

A pointer to the value if it is in the cache, or 0 if not .

Definition at line 51 of file mbl_lru_cache.h.

template<class I , class V >

void mbl_lru_cache< I, V >::resize

(

unsigned

n

)

[inline]

Definition at line 95 of file mbl_lru_cache.h.

---

Member Data Documentation

template<class I , class V >

list_type mbl_lru_cache< I, V >::l_ [private]

Allow least recently used item to be found quickly $O(1)$.

Definition at line 24 of file mbl_lru_cache.h.

template<class I , class V >

map_type mbl_lru_cache< I, V >::m_ [private]

Definition at line 28 of file mbl_lru_cache.h.

template<class I , class V >

unsigned long mbl_lru_cache< I, V >::n_ [private]

Limit of cache size.

Definition at line 30 of file mbl_lru_cache.h.

---

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

• contrib/mul/mbl/mbl_lru_cache.h