net_instaweb::LRUCacheBase< ValueType, ValueHelper > Class Template Reference

#include "lru_cache_base.h"

Classes
class	Iterator

Public Member Functions
	LRUCacheBase (size_t max_size, ValueHelper *value_helper)
void	set_max_bytes_in_cache (size_t max_size)
ValueType *	GetFreshen (const GoogleString &key)
ValueType *	GetNoFreshen (const GoogleString &key) const
void	Put (const GoogleString &key, const ValueType &new_value)
void	Delete (const GoogleString &key)
void	DeleteWithPrefixForTesting (StringPiece prefix)
void	MergeStats (const LRUCacheBase &src)
size_t	size_bytes () const
	Total size in bytes of keys and values stored.
size_t	max_bytes_in_cache () const
	Maximum capacity.
size_t	num_elements () const
	Number of elements stored.
size_t	num_evictions () const
size_t	num_hits () const
size_t	num_misses () const
size_t	num_inserts () const
size_t	num_identical_reinserts () const
size_t	num_deletes () const
void	SanityCheck ()
	Sanity check the cache data structures. More...
void	Clear ()
void	ClearStats ()
	Clear the stats – note that this will not clear the content.
Iterator	Begin () const
	Iterators for walking cache entries from oldest to youngest.
Iterator	End () const

Detailed Description

template<class ValueType, class ValueHelper>
class net_instaweb::LRUCacheBase< ValueType, ValueHelper >

Implements a general purpose in-memory least-recently used (LRU) cache, using strings as keys and arbitrary values as objects. This implementation is not thread-safe, and must be combined with an externally managed mutex to make it so.

This is templated on ValueType, which holds the value, and on ValueHelper, which must define:

// Computes the size of a value. Used to track resource consumption. size_t size(const ValueType&) const;

// Determines whether two values are equal. bool Equal(const ValueType& a, const ValueType& b) const;

// Called when objects are evicted. Note that destruction does // not imply eviction. void EvictNotify(const ValueType&);

// Determines whether a new_value should supercede old_value on a Put. bool ShouldReplace(const ValueType& old_value, const ValueType& new_value) const;

ValueType must support copy-construction and assign-by-value.

Member Function Documentation

template<class ValueType, class ValueHelper>

void net_instaweb::LRUCacheBase< ValueType, ValueHelper >::Clear ( )

inline

Clear the entire cache. Used primarily for testing. Note that this will not clear the stats, however it will update current_bytes_in_cache_.

template<class ValueType, class ValueHelper>

void net_instaweb::LRUCacheBase< ValueType, ValueHelper >::Delete ( const GoogleString &  key )

inline

Todo:

TODO(jmarantz): count number of misses on a 'delete' request?

template<class ValueType, class ValueHelper>

void net_instaweb::LRUCacheBase< ValueType, ValueHelper >::DeleteWithPrefixForTesting ( StringPiece  prefix )

inline

Deletes all objects whose key starts with prefix. Note: this takes time proportional to the size of the map, and is only meant for test use.

template<class ValueType, class ValueHelper>

ValueType* net_instaweb::LRUCacheBase< ValueType, ValueHelper >::GetFreshen ( const GoogleString &  key )

inline

Returns a pointer to the stored value, or NULL if not found, freshening the entry in the lru-list. Note: this pointer is safe to use until the next call to Put or Delete in the cache.

Note: it's safe to assume the list iterator will remain valid so that the caller can do what's necessary with the pointer. http://stackoverflow.com/questions/759274/ what-is-the-lifetime-and-validity-of-c-iterators

template<class ValueType, class ValueHelper>

ValueType* net_instaweb::LRUCacheBase< ValueType, ValueHelper >::GetNoFreshen ( const GoogleString &  key ) const

inline

See the above comment about stl::list::iterator lifetime.

template<class ValueType, class ValueHelper>

void net_instaweb::LRUCacheBase< ValueType, ValueHelper >::Put ( const GoogleString &  key, const ValueType &  new_value  )

inline

Puts an object into the cache. The value is copied using the assignment operator.

Just do one map operation, calling the awkward 'insert' which returns a pair. The bool indicates whether a new value was inserted, and the iterator provides access to the element, whether it's new or old.

If the key is already in the map, this will give us access to the value cell, and the uninitialized cell will not be used.

Protect the element that we are rewriting by erasing it from the entry_list prior to calling EvictIfNecessary, which can't find it if it isn't in the list.

At this point, if we were doing a replacement, then the value is removed from the list, so we can treat replacements and new insertions the same way. In both cases, the new key is in the map as a result of the call to map_.insert above.

The new value fits. Put it in the LRU-list.

The new value was too big to fit. Remove it from the map. it's already removed from the list. We have failed. We could potentially log this somewhere or keep a stat.

template<class ValueType, class ValueHelper>

void net_instaweb::LRUCacheBase< ValueType, ValueHelper >::SanityCheck ( )

inline

Sanity check the cache data structures.

Walk forward through the list, making sure the map and list elements point to each other correctly.

Walk backward through the list, making sure it's coherent as well.

template<class ValueType, class ValueHelper>

void net_instaweb::LRUCacheBase< ValueType, ValueHelper >::set_max_bytes_in_cache ( size_t  max_size )

inline

Resets the max size in the cache. This does not take effect immediately; e.g. if you are shrinking the cache size, this call will not evict anything. Only when something new is put into the cache will we evict.

---

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

• pagespeed/kernel/cache/lru_cache_base.h