#include <lru.h>

Inheritance diagram for lru::LruCache< Key, Value >:

Collaboration diagram for lru::LruCache< Key, Value >:

Classes
struct	CacheEntry

class	ListEntry

class	ListEntryContent

class	ListEntryHead

class	MemoryAllocator

Public Member Functions
	LruCache (const unsigned cache_size, const Key &empty_key, uint32_t(*hasher)(const Key &key), perf::StatisticsTemplate statistics)

virtual	~LruCache ()

virtual bool	Insert (const Key &key, const Value &value)

virtual void	Update (const Key &key)

virtual bool	UpdateValue (const Key &key, const Value &value)

virtual bool	Lookup (const Key &key, Value *value, bool update_lru=true)

virtual bool	Forget (const Key &key)

virtual void	Drop ()

void	Pause ()

void	Resume ()

bool	IsFull () const

bool	IsEmpty () const

Counters	counters ()

virtual void	FilterBegin ()

virtual void	FilterGet (Key key, Value value)

virtual bool	FilterNext ()

virtual void	FilterDelete ()

virtual void	FilterEnd ()

Static Public Member Functions
static double	GetEntrySize ()

Protected Attributes
Counters	counters_

Private Types
typedef ListEntryContent< Key >	ConcreteListEntryContent

typedef MemoryAllocator < ConcreteListEntryContent >	ConcreteMemoryAllocator

Private Member Functions
bool	DoLookup (const Key &key, CacheEntry *entry)

void	Touch (const CacheEntry &entry)

void	DeleteOldest ()

void	Lock ()

void	Unlock ()

Private Member Functions inherited from SingleCopy
	SingleCopy ()

Private Attributes
bool	pause_

unsigned int	cache_gauge_

const unsigned int	cache_size_

ConcreteMemoryAllocator	allocator_

ListEntryHead< Key >	lru_list_

SmallHashFixed< Key, CacheEntry >	cache_

ListEntry< Key > *	filter_entry_

pthread_mutex_t	lock_

Detailed Description

template<class Key, class Value>
class lru::LruCache< Key, Value >

Template class to create a LRU cache

Parameters

Key	type of the key values
Value	type of the value values

Definition at line 106 of file lru.h.

Member Typedef Documentation

template<class Key, class Value>

typedef ListEntryContent<Key> lru::LruCache< Key, Value >::ConcreteListEntryContent

private

Definition at line 112 of file lru.h.

template<class Key, class Value>

typedef MemoryAllocator<ConcreteListEntryContent> lru::LruCache< Key, Value >::ConcreteMemoryAllocator

private

Definition at line 116 of file lru.h.

Constructor & Destructor Documentation

template<class Key, class Value>

lru::LruCache< Key, Value >::LruCache	(	const unsigned	cache_size,
		const Key &	empty_key,
		uint32_t(*)(const Key &key)	hasher,
		perf::StatisticsTemplate	statistics
	)

inline

Create a new LRU cache object

Parameters

cache_size the maximal size of the cache

Definition at line 509 of file lru.h.

template<class Key, class Value>

virtual lru::LruCache< Key, Value >::~LruCache ( )

inlinevirtual

Definition at line 540 of file lru.h.

Member Function Documentation

template<class Key, class Value>

Counters lru::LruCache< Key, Value >::counters ( )

inline

Definition at line 726 of file lru.h.

template<class Key, class Value>

void lru::LruCache< Key, Value >::DeleteOldest ( )

inlineprivate

Deletes the least recently used entry from the cache.

Definition at line 823 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::Insert().

Here is the caller graph for this function:

template<class Key, class Value>

bool lru::LruCache< Key, Value >::DoLookup	(	const Key &	key,
		CacheEntry *	entry
	)

inlineprivate

this just performs a lookup in the cache WITHOUT changing the LRU order

Parameters

key	the key to perform a lookup on
entry	a pointer to the entry structure

Returns: true on successful lookup, false otherwise

Definition at line 806 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::FilterGet(), lru::LruCache< shash::Any, MemoryBuffer >::Forget(), lru::LruCache< shash::Any, MemoryBuffer >::Insert(), lru::LruCache< shash::Any, MemoryBuffer >::Lookup(), lru::LruCache< shash::Any, MemoryBuffer >::Update(), and lru::LruCache< shash::Any, MemoryBuffer >::UpdateValue().

Here is the caller graph for this function:

template<class Key, class Value>

virtual void lru::LruCache< Key, Value >::Drop ( )

inlinevirtual

Clears all elements from the cache. All memory of internal data structures will be freed but data of cache entries may stay in use, we do not call delete on any user data.

Reimplemented in lru::Md5PathCache, lru::PathCache, and lru::InodeCache.

Definition at line 697 of file lru.h.

Referenced by lru::InodeCache::Drop(), lru::PathCache::Drop(), and lru::Md5PathCache::Drop().

Here is the caller graph for this function:

template<class Key, class Value>

virtual void lru::LruCache< Key, Value >::FilterBegin ( )

inlinevirtual

Prepares for in-order iteration of the cache entries to perform a filter operation. To ensure consistency, the LruCache must be locked for the duration of the filter operation.

Definition at line 739 of file lru.h.

Referenced by MemoryKvStore::ShrinkTo().

Here is the caller graph for this function:

template<class Key, class Value>

virtual void lru::LruCache< Key, Value >::FilterDelete ( )

inlinevirtual

Delete the current cache list entry

Definition at line 773 of file lru.h.

Referenced by MemoryKvStore::ShrinkTo().

Here is the caller graph for this function:

template<class Key, class Value>

virtual void lru::LruCache< Key, Value >::FilterEnd ( )

inlinevirtual

Finish filtering the entries and unlock the cache

Definition at line 789 of file lru.h.

Referenced by MemoryKvStore::ShrinkTo().

Here is the caller graph for this function:

template<class Key, class Value>

virtual void lru::LruCache< Key, Value >::FilterGet	(	Key *	key,
		Value *	value
	)

inlinevirtual

Get the current key and value for the filter operation

Parameters

key	Address to write the key
value	Address to write the value

Definition at line 750 of file lru.h.

Referenced by MemoryKvStore::ShrinkTo().

Here is the caller graph for this function:

template<class Key, class Value>

virtual bool lru::LruCache< Key, Value >::FilterNext ( )

inlinevirtual

Advance to the next entry in the list

Returns: false upon reaching the end of the cache list

Definition at line 764 of file lru.h.

Referenced by MemoryKvStore::ShrinkTo().

Here is the caller graph for this function:

template<class Key, class Value>

virtual bool lru::LruCache< Key, Value >::Forget ( const Key & key )

inlinevirtual

Forgets about a specific cache entry

Parameters

key	the key to delete from the cache

Returns: true if key was deleted, false if key was not in the cache

Reimplemented in lru::Md5PathCache.

Definition at line 669 of file lru.h.

Referenced by MemoryKvStore::DoDelete(), and lru::Md5PathCache::Forget().

Here is the caller graph for this function:

template<class Key, class Value>

static double lru::LruCache< Key, Value >::GetEntrySize ( )

inlinestatic

Definition at line 535 of file lru.h.

Referenced by PluginRamCache::PluginRamCache().

Here is the caller graph for this function:

template<class Key, class Value>

virtual bool lru::LruCache< Key, Value >::Insert	(	const Key &	key,
		const Value &	value
	)

inlinevirtual

Insert a new key-value pair to the list. If the cache is already full, the least recently used object is removed; afterwards the new object is inserted. If the object is already present it is updated and moved back to the end of the list

Parameters

key	the key where the value is saved
value	the value of the cache entry

Returns: true on insert, false on update

Reimplemented in lru::Md5PathCache, lru::PathCache, and lru::InodeCache.

Definition at line 556 of file lru.h.

Referenced by MemoryKvStore::DoCommit(), MemoryKvStore::IncRef(), lru::InodeCache::Insert(), lru::PathCache::Insert(), lru::Md5PathCache::Insert(), and MemoryKvStore::Unref().

Here is the caller graph for this function:

template<class Key, class Value>

bool lru::LruCache< Key, Value >::IsEmpty ( ) const

inline

Definition at line 724 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::DeleteOldest().

Here is the caller graph for this function:

template<class Key, class Value>

bool lru::LruCache< Key, Value >::IsFull ( ) const

inline

Definition at line 723 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::Insert().

Here is the caller graph for this function:

template<class Key, class Value>

void lru::LruCache< Key, Value >::Lock ( )

inlineprivate

Locks the cache (thread safety).

Definition at line 836 of file lru.h.

Here is the caller graph for this function:

template<class Key, class Value>

virtual bool lru::LruCache< Key, Value >::Lookup	(	const Key &	key,
		Value *	value,
		bool	update_lru = `true`
	)

inlinevirtual

Retrieve an element from the cache. If the element was found, it will be marked as 'recently used' and returned

Parameters

key	the key to perform a lookup on
value	(out) here the result is saved (not touch in case of miss)

Returns: true on successful lookup, false if key was not found

Reimplemented in lru::Md5PathCache, lru::PathCache, and lru::InodeCache.

Definition at line 640 of file lru.h.

Referenced by MemoryKvStore::Contains(), MemoryKvStore::DoCommit(), MemoryKvStore::DoDelete(), MemoryKvStore::GetRefcount(), MemoryKvStore::GetSize(), MemoryKvStore::IncRef(), lru::InodeCache::Lookup(), lru::PathCache::Lookup(), lru::Md5PathCache::Lookup(), MemoryKvStore::OnBlockMove(), MemoryKvStore::Read(), and MemoryKvStore::Unref().

Here is the caller graph for this function:

template<class Key, class Value>

void lru::LruCache< Key, Value >::Pause ( )

inline

Definition at line 711 of file lru.h.

Referenced by FuseRemounter::TryFinish().

Here is the caller graph for this function:

template<class Key, class Value>

void lru::LruCache< Key, Value >::Resume ( )

inline

Definition at line 717 of file lru.h.

Referenced by FuseRemounter::TryFinish().

Here is the caller graph for this function:

template<class Key, class Value>

void lru::LruCache< Key, Value >::Touch ( const CacheEntry & entry )

inlineprivate

Touch an entry. The entry will be moved to the back of the LRU list to mark it as 'recently used'... this saves the entry from being deleted

Parameters

entry the CacheEntry to be touched (CacheEntry is the internal wrapper data structure)

Definition at line 816 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::Insert(), lru::LruCache< shash::Any, MemoryBuffer >::Lookup(), and lru::LruCache< shash::Any, MemoryBuffer >::Update().

Here is the caller graph for this function:

template<class Key, class Value>

void lru::LruCache< Key, Value >::Unlock ( )

inlineprivate

Unlocks the cache (thread safety).

Definition at line 845 of file lru.h.

Here is the caller graph for this function:

template<class Key, class Value>

virtual void lru::LruCache< Key, Value >::Update ( const Key & key )

inlinevirtual

Updates object and moves back to the end of the list. The object must be present.

Definition at line 595 of file lru.h.

template<class Key, class Value>

virtual bool lru::LruCache< Key, Value >::UpdateValue	(	const Key &	key,
		const Value &	value
	)

inlinevirtual

Changes the value of an entry in the LRU cache without updating the LRU order.

Definition at line 612 of file lru.h.

Referenced by MemoryKvStore::OnBlockMove().

Here is the caller graph for this function:

Member Data Documentation

template<class Key, class Value>

ConcreteMemoryAllocator lru::LruCache< Key, Value >::allocator_

private

Definition at line 856 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::Drop(), lru::LruCache< shash::Any, MemoryBuffer >::FilterDelete(), lru::LruCache< shash::Any, MemoryBuffer >::Forget(), and lru::LruCache< shash::Any, MemoryBuffer >::LruCache().

template<class Key, class Value>

SmallHashFixed<Key, CacheEntry> lru::LruCache< Key, Value >::cache_

private

Definition at line 866 of file lru.h.

template<class Key, class Value>

unsigned int lru::LruCache< Key, Value >::cache_gauge_

private

Definition at line 854 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::DeleteOldest(), lru::LruCache< shash::Any, MemoryBuffer >::Drop(), lru::LruCache< shash::Any, MemoryBuffer >::FilterDelete(), lru::LruCache< shash::Any, MemoryBuffer >::Forget(), lru::LruCache< shash::Any, MemoryBuffer >::Insert(), lru::LruCache< shash::Any, MemoryBuffer >::IsEmpty(), and lru::LruCache< shash::Any, MemoryBuffer >::IsFull().

template<class Key, class Value>

const unsigned int lru::LruCache< Key, Value >::cache_size_

private

Definition at line 855 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::IsFull(), and lru::LruCache< shash::Any, MemoryBuffer >::LruCache().

template<class Key, class Value>

Counters lru::LruCache< Key, Value >::counters_

protected

Definition at line 796 of file lru.h.

template<class Key, class Value>

ListEntry<Key>* lru::LruCache< Key, Value >::filter_entry_

private

Definition at line 868 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::FilterBegin(), lru::LruCache< shash::Any, MemoryBuffer >::FilterDelete(), lru::LruCache< shash::Any, MemoryBuffer >::FilterEnd(), lru::LruCache< shash::Any, MemoryBuffer >::FilterGet(), lru::LruCache< shash::Any, MemoryBuffer >::FilterNext(), and lru::LruCache< shash::Any, MemoryBuffer >::LruCache().

template<class Key, class Value>

pthread_mutex_t lru::LruCache< Key, Value >::lock_

private

Mutex to make cache thread safe.

Definition at line 870 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::Lock(), lru::LruCache< shash::Any, MemoryBuffer >::LruCache(), lru::LruCache< shash::Any, MemoryBuffer >::Unlock(), and lru::LruCache< shash::Any, MemoryBuffer >::~LruCache().

template<class Key, class Value>

ListEntryHead<Key> lru::LruCache< Key, Value >::lru_list_

private

A doubly linked list to keep track of the least recently used data entries. New entries get pushed back to the list. If an entry is touched it is moved to the back of the list again. If the cache gets too long, the first element (the oldest) gets deleted to obtain some space.

Definition at line 865 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::DeleteOldest(), lru::LruCache< shash::Any, MemoryBuffer >::Drop(), lru::LruCache< shash::Any, MemoryBuffer >::FilterBegin(), lru::LruCache< shash::Any, MemoryBuffer >::Insert(), and lru::LruCache< shash::Any, MemoryBuffer >::Touch().

template<class Key, class Value>

bool lru::LruCache< Key, Value >::pause_

private

Temporarily stops the cache in order to avoid poisoning

Definition at line 851 of file lru.h.

Referenced by lru::LruCache< shash::Any, MemoryBuffer >::Forget(), lru::LruCache< shash::Any, MemoryBuffer >::Insert(), lru::LruCache< shash::Any, MemoryBuffer >::Lookup(), lru::LruCache< shash::Any, MemoryBuffer >::Pause(), lru::LruCache< shash::Any, MemoryBuffer >::Resume(), lru::LruCache< shash::Any, MemoryBuffer >::Update(), and lru::LruCache< shash::Any, MemoryBuffer >::UpdateValue().

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

/home/sftnight/jenkins/workspace/CvmfsDoxygen/label/docker-x86_64/cvmfs/cvmfs/lru.h

Classes

Public Member Functions

Static Public Member Functions

Protected Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<class Key, class Value> class lru::LruCache< Key, Value >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Key, class Value>
class lru::LruCache< Key, Value >