PLearn 0.1
Public Types | Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes
PLearn::BoundedMemoryCache< KeyType, ValueType > Class Template Reference

Class description: More...

#include <BoundedMemoryCache.h>

Inheritance diagram for PLearn::BoundedMemoryCache< KeyType, ValueType >:
Inheritance graph
[legend]
Collaboration diagram for PLearn::BoundedMemoryCache< KeyType, ValueType >:
Collaboration graph
[legend]

List of all members.

Public Types

typedef intpointer

Public Member Functions

 BoundedMemoryCache (int max_memory_=0)
void clear ()
const ValueType * operator() (const KeyType &key) const
 Try to get value associataed with key.
ValueType * operator() (const KeyType &key)
void set (const KeyType &key, const ValueType &value)
 Associate value to key.
bool isCached (const KeyType &key) const
 Check if this key is in cache. This does not change the access priority of the key.
int nElements () const
int currentMemory () const
int maxMemory () const
void setMaxMemory (int new_max_memory)
float successRate ()
virtual ~BoundedMemoryCache ()
void verifyInvariants ()

Public Attributes

DoublyLinkedList< KeyType > * doubly_linked_list
int n_successful_hits
int n_failures
map< KeyType, pair< ValueType,
DoublyLinkedListElement
< KeyType > * > > 
elements

Protected Member Functions

virtual void removeExcess ()
 remove last element until current_memory <= max_memory;
virtual void removeAll ()
 remove all elements

Protected Attributes

int n_elements
int max_memory
int current_memory

Detailed Description

template<class KeyType, class ValueType>
class PLearn::BoundedMemoryCache< KeyType, ValueType >

Class description:

Similar semantically to a map<KeyType,ValueType>, except that a maximum memory usage can be set, and less frequently and less recently accessed elements that make memory usage go above that limit are dropped. The heuristic for giving more priority to more recently accessed stuff is the 'move-to-front' heuristic. When an entry is read or set it is moved to the front of a list. When the allowed memory has been overrun the last element of the list is dropped. The list is implemented with the new class plearn/base/DoublyLinkedList, a doubly-linked list with removeLast() and moveToFront() methods.

Definition at line 72 of file BoundedMemoryCache.h.


Member Typedef Documentation

template<class KeyType, class ValueType>
typedef int* PLearn::BoundedMemoryCache< KeyType, ValueType >::pointer

Definition at line 140 of file BoundedMemoryCache.h.


Constructor & Destructor Documentation

template<class KeyType, class ValueType>
PLearn::BoundedMemoryCache< KeyType, ValueType >::BoundedMemoryCache ( int  max_memory_ = 0) [inline]

Definition at line 85 of file BoundedMemoryCache.h.

        : n_elements(0), max_memory(max_memory_), current_memory(0), doubly_linked_list(new DoublyLinkedList<KeyType>),
          n_successful_hits(0), n_failures(0)
    {}
template<class KeyType, class ValueType>
virtual PLearn::BoundedMemoryCache< KeyType, ValueType >::~BoundedMemoryCache ( ) [inline, virtual]

Definition at line 189 of file BoundedMemoryCache.h.

References PLearn::clear().

{ clear(); }

Here is the call graph for this function:


Member Function Documentation

template<class KeyType, class ValueType>
void PLearn::BoundedMemoryCache< KeyType, ValueType >::clear ( ) [inline]

Reimplemented in PLearn::Cache< KeyType, ValueType >.

Definition at line 90 of file BoundedMemoryCache.h.

References PLERROR.

                        { 
/*
        int mm = max_memory;
        max_memory = 0;
        removeExcess(); // this is mostly useful when removeExcess is redefined, e.g. in sub-class Cache
        max_memory = mm;
        elements.clear();
*/
        removeAll(); // this is mostly useful when removeAll is redefined, e.g. in sub-class Cache
        if (elements.size() != 0)
            PLERROR("Weird");
    }
template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::currentMemory ( ) const [inline]

Definition at line 180 of file BoundedMemoryCache.h.

{ return current_memory; }
template<class KeyType, class ValueType>
bool PLearn::BoundedMemoryCache< KeyType, ValueType >::isCached ( const KeyType &  key) const [inline]

Check if this key is in cache. This does not change the access priority of the key.

Reimplemented in PLearn::Cache< KeyType, ValueType >.

Definition at line 178 of file BoundedMemoryCache.h.

{ return elements.find(key)!=elements.end(); }
template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::maxMemory ( ) const [inline]

Definition at line 181 of file BoundedMemoryCache.h.

{ return max_memory; }
template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::nElements ( ) const [inline]

Definition at line 179 of file BoundedMemoryCache.h.

{ return n_elements; }
template<class KeyType, class ValueType>
const ValueType* PLearn::BoundedMemoryCache< KeyType, ValueType >::operator() ( const KeyType &  key) const [inline]

Try to get value associataed with key.

If not in cache return 0, else return pointer to value. Recently accessed keys (with set or operator()) are less likely to be removed.

Reimplemented in PLearn::Cache< KeyType, ValueType >.

Definition at line 105 of file BoundedMemoryCache.h.

References PLearn::dbg, and PLERROR.

                                                          { 
        typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::const_iterator it = elements.find(key);
        if (it==elements.end()) 
        {
            n_failures++;
            return 0;
        }
        n_successful_hits++;
        doubly_linked_list->moveToFront(it->second.second); 
#ifdef BOUNDCHECK
        if (!doubly_linked_list->last || doubly_linked_list->last->next)
            PLERROR("something wrong with last element of doubly linked list!");
        if (dbg)
            verifyInvariants();
#endif
        return &(it->second.first);
    }
template<class KeyType, class ValueType>
ValueType* PLearn::BoundedMemoryCache< KeyType, ValueType >::operator() ( const KeyType &  key) [inline]

Reimplemented in PLearn::Cache< KeyType, ValueType >.

Definition at line 122 of file BoundedMemoryCache.h.

References PLearn::dbg, and PLERROR.

                                              { 
        typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key);
        if (it==elements.end()) 
        {
            n_failures++;
            return 0;
        }
        n_successful_hits++;
        doubly_linked_list->moveToFront(it->second.second); 
#ifdef BOUNDCHECK
        if (!doubly_linked_list->last || doubly_linked_list->last->next)
            PLERROR("something wrong with last element of doubly linked list!");
        if (dbg)
            verifyInvariants();
#endif
        return &(it->second.first);
    }
template<class KeyType, class ValueType>
virtual void PLearn::BoundedMemoryCache< KeyType, ValueType >::removeAll ( ) [inline, protected, virtual]

remove all elements

Reimplemented in PLearn::Cache< KeyType, ValueType >.

Definition at line 237 of file BoundedMemoryCache.h.

References PLearn::dbg, and PLERROR.

    {
        while (n_elements)
        {
            KeyType& key = doubly_linked_list->last->entry;
//            current_memory -= sizeInBytes(elements[key]);
            elements[key].second=0; elements.erase(key);
            doubly_linked_list->removeLast();
            n_elements--;
#ifdef BOUNDCHECK
            if (!doubly_linked_list->last || doubly_linked_list->last->next)
                PLERROR("something wrong with last element of doubly linked list!");
            if (dbg)
                verifyInvariants();
#endif            
        }
        current_memory = 0;
    }
template<class KeyType, class ValueType>
virtual void PLearn::BoundedMemoryCache< KeyType, ValueType >::removeExcess ( ) [inline, protected, virtual]

remove last element until current_memory <= max_memory;

Reimplemented in PLearn::Cache< KeyType, ValueType >.

Definition at line 218 of file BoundedMemoryCache.h.

References PLearn::dbg, PLERROR, and PLearn::sizeInBytes().

    {
        while (current_memory > max_memory)
        {
            KeyType& key = doubly_linked_list->last->entry;
            current_memory -= sizeInBytes(elements[key]);
            elements[key].second=0; elements.erase(key);
            doubly_linked_list->removeLast();
            n_elements--;
#ifdef BOUNDCHECK
            if (!doubly_linked_list->last || doubly_linked_list->last->next)
                PLERROR("something wrong with last element of doubly linked list!");
            if (dbg)
                verifyInvariants();
#endif
        }
    }

Here is the call graph for this function:

template<class KeyType, class ValueType>
void PLearn::BoundedMemoryCache< KeyType, ValueType >::set ( const KeyType &  key,
const ValueType &  value 
) [inline]

Associate value to key.

Recently accessed keys (with set or operator()) are less likely to be removed.

Definition at line 144 of file BoundedMemoryCache.h.

References PLearn::dbg, PLERROR, and PLearn::sizeInBytes().

                                                         {
        typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key);
        if (it==elements.end()) { // first time set
            DoublyLinkedListElement<KeyType>* p=doubly_linked_list->pushOnTop(key);
#ifdef BOUNDCHECK
            if (!doubly_linked_list->last || doubly_linked_list->last->next)
                PLERROR("something wrong with last element of doubly linked list!");
#endif
            pair<ValueType,DoublyLinkedListElement<KeyType>*> el(value,p);
            elements[key] = el;
            current_memory += sizeInBytes(el);
            n_elements++;
#ifdef BOUNDCHECK
            if (dbg)
                verifyInvariants();
#endif
        }
        else { // already there, move it to front of list and update the value
            ValueType& v = elements[key].first;
            current_memory += sizeInBytes(value) - sizeInBytes(v);
            doubly_linked_list->moveToFront(it->second.second);
#ifdef BOUNDCHECK
            if (!doubly_linked_list->last || doubly_linked_list->last->next)
                PLERROR("something wrong with last element of doubly linked list!");
#endif
            v = value;
#ifdef BOUNDCHECK
            if (dbg)
                verifyInvariants();
#endif
        }
        removeExcess();
    }

Here is the call graph for this function:

template<class KeyType, class ValueType>
void PLearn::BoundedMemoryCache< KeyType, ValueType >::setMaxMemory ( int  new_max_memory) [inline]

Definition at line 182 of file BoundedMemoryCache.h.

                                                  {
        max_memory=new_max_memory;
        removeExcess();
    }
template<class KeyType, class ValueType>
float PLearn::BoundedMemoryCache< KeyType, ValueType >::successRate ( ) [inline]

Definition at line 187 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
void PLearn::BoundedMemoryCache< KeyType, ValueType >::verifyInvariants ( ) [inline]

Definition at line 192 of file BoundedMemoryCache.h.

References PLearn::DoublyLinkedListElement< T >::entry, PLearn::DoublyLinkedListElement< T >::next, PLERROR, and PLearn::DoublyLinkedListElement< T >::previous.

                            {
        if (!doubly_linked_list->last || doubly_linked_list->last->next)
            PLERROR("something wrong with last element of doubly linked list!");
        if (max_memory - current_memory>500) return;
        typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.begin();
        for (;it!=elements.end();++it)
        {
            DoublyLinkedListElement<KeyType>* p = it->second.second;
            if (!p) 
                PLERROR("BoundedMemoryCache::verifyInvariants(): null linked list pointer!");
            DoublyLinkedListElement<KeyType>* next = p->next;
            DoublyLinkedListElement<KeyType>* previous = p->previous;
            if (previous && previous->next != p)
                PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (previous->next != element)\n");
            if (next && next->previous != p)
                PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (next->previous != element)\n");
            typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator pi = elements.find(p->entry);
            if (pi->second.second!=p)
                PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent pointers between map and list\n");
            if (pi->first!=p->entry)
                PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent keys between map and list\n");
        }
    }

Member Data Documentation

template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::current_memory [protected]

The current memory used to store the elements

Definition at line 77 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
DoublyLinkedList<KeyType>* PLearn::BoundedMemoryCache< KeyType, ValueType >::doubly_linked_list

Definition at line 79 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
map<KeyType, pair<ValueType,DoublyLinkedListElement<KeyType>*> > PLearn::BoundedMemoryCache< KeyType, ValueType >::elements

the indexed elements. Each entry has (value, pointer into doubly_linked_list)

Definition at line 83 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::max_memory [protected]

The maximum memory used to store the elements

Definition at line 76 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::n_elements [protected]

The actual number of elements stored in memory

Definition at line 75 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::n_failures [mutable]

Number of times operator() was called and entry not found

Definition at line 81 of file BoundedMemoryCache.h.

template<class KeyType, class ValueType>
int PLearn::BoundedMemoryCache< KeyType, ValueType >::n_successful_hits [mutable]

Number of times operator() was called successfully

Definition at line 80 of file BoundedMemoryCache.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines