Page Speed Optimization Libraries  1.13.35.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Public Member Functions | List of all members
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: