CernVM-FS  2.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
lru::LruCache< Key, Value > Class Template Reference

#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, CacheEntrycache_
 
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
Keytype of the key values
Valuetype 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_sizethe 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
keythe key to perform a lookup on
entrya 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
keyAddress to write the key
valueAddress 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
keythe 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
keythe key where the value is saved
valuethe 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>
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
keythe 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
entrythe 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>
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>
const unsigned int lru::LruCache< Key, Value >::cache_size_
private
template<class Key, class Value>
pthread_mutex_t lru::LruCache< Key, Value >::lock_
private
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().


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