 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Radu Grigore
Guest
|
 Posted: Mon Aug 16, 2004 7:43 pm Post subject: cache - fixed size map |
 |
|
A cache can be implemented as a (hash_)map. In my case the growing
size might become a problem. A possible solution is to remove elements
(LFU, LRU) either periodically or, probably easier, in such a way as
to preserve a maximum size. It seems like a common problem and I'm
wondering if anyone has already done it: preferably as an open source
library, but an open source project (so I can read the code) is OK
too.
thanks,
radu
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Kai-Uwe Bux
Guest
|
| Posted: Tue Aug 17, 2004 9:45 am Post subject: Re: cache - fixed size map |
|
|
Radu Grigore wrote:
| Quote: | A cache can be implemented as a (hash_)map. In my case the growing
size might become a problem. A possible solution is to remove elements
(LFU, LRU) either periodically or, probably easier, in such a way as
to preserve a maximum size. It seems like a common problem and I'm
wondering if anyone has already done it: preferably as an open source
library, but an open source project (so I can read the code) is OK
too.
Hi, |
this is some simple code that might get you started. I have to give a
little warning notice:
(a) The code is *not* well tested.
(b) It could need better documentation.
// cache.cc (C) Kai-Uwe Bux [2004]
// ===============================
//
// Defines the cache container template.
/*
| Quote: | The cache template provides an object that wraps around a
computationally expensive function to avoid recomputation
of already known values.
The following example code snipplet should illustrate the
intended use:
class SomeIncrediblyHardFunction {
public:
data_type operator() ( const key_type & key ) {
// your code goes here
}
} the_function;
cache< key_type, data_type, SomeIncrediblyHardFunction
wrapper ( the_function, initial_size );
// later:
data = wrapper( key );
The wrapper will keep an internal table of up to
of
given argument, the warpper will return this value. Otherwise,
and only otherwise, the value will be computed from scratch
using <the_function>. Then the new pair will be stored in the
table. If need be, entries will be freed on a "least recently used"
basis.
*/ |
// ================================================================
// || INTERFACE ||
// ================================================================
#if 0
namespace kubux {
template< typename KeyType,
typename DataType,
typename Function,
std::size_t Max_Size = 4096,
typename Compare = std::less< KeyType >,
typename Allocator = std::allocator< std::pair< const KeyType,
DataType > >
public:
typedef KeyType key_type;
typedef DataType mapped_type;
typedef std::pair< const KeyType, DataType > value_type;
typedef Compare key_compare;
typedef Function transform;
typedef Allocator alloc_type;
cache ( const cache & other );
// copy constructor.
cache ( Function & function, std::size_t capacity = Max_Size );
// constructor.
~cache ( void );
// destructor.
const cache & operator= ( const cache & other );
// assignment operator.
DataType operator() ( const KeyType & key ) const;
// evaluate the stored function at <key>
void clear ( void ) const;
// clear the table.
std::size_t size ( void ) const;
// return the number of currently stored entries.
void resize ( std::size_t new_capacity ) const;
// set the capacity.
// if size() > new_capacity, remove entries based on
// a "least recently used" policy.
bool empty ( void ) const;
// return( size() == 0 )
std::size_t capacity ( void ) const;
// return the current capacity.
void copy ( const cache & other, std::size_t length );
// clear() and copy <length> entries from <other>
// choose those entries that are most recently used.
void write( std::ostream & ostr ) const;
// write a list entries to <ostr> in order of use:
// start from the most recently used and work your way
// to the least recently used.
}; // cache<>
} // namespace kubux
// in global namespace:
std::ostream & operator<< ( std::ostream & ostr,
const kubux::cache & the_cache );
#endif // end of interface description
// ====================================================================
// || IMPLEMENTATION ||
// ====================================================================
#ifndef __KUBUX_cache__
#define __KUBUX_cache__
#include
#include <utility>
#include <functional>
#include <memory>
#include <iostream>
#include "sequenceio.cc"
namespace kubux {
template< typename KeyType,
typename DataType,
typename Function,
std::size_t Max_Size = 4096,
typename Compare = std::less< KeyType >,
typename Allocator =
std::allocator< std::pair< const KeyType, DataType > >
private:
/*
| Quote: | We implement the cache on top of a map: the pairs <key,data> are
stored in a map for efficient retrieval. The "least recent use"
policy for removing entries is implemented by a self organizing
list: we keep a doubly linked list of entries and whenever an
element
is accessed it moves to the head. The tail is always the least
recently used entry.
The problem is to merge the two data structures. We want the list
to consist of the entries in the map. Thus, we would like to have a
next and prev field within each entry pointing to the next and
previous entry according to the list. The diffculty lies is that
next and prev should be of type map::iterator; and the map type
is yet to be formed. We overcome this, by a forward declaration.
*/ |
class EntryType;
typedef typename Allocator::template
rebind< std::pair< const KeyType, EntryType > >::other
MapEntryAllocator;
typedef typename
std::map< KeyType, EntryType, Compare, MapEntryAllocator > MapType;
typedef typename MapType::iterator IterType;
typedef typename MapType::value_type PairType;
class EntryType {
public:
DataType data;
IterType next;
IterType prev;
EntryType ( const DataType & _data,
const IterType & _next,
const IterType & _prev ) :
data( _data ),
next( _next ),
prev( _prev )
{}
}; // EntryType;
/*
| Quote: | The following are clearly needed:
*/ |
Function & the_function;
mutable MapType the_map;
std::size_t max_capacity;
/*
| Quote: | Now, we implement the doubly linked list.
*/ |
mutable IterType head;
mutable IterType tail;
/*
| Quote: | Since there is no nil value for iterators (the_map.end() may
change any the time!), we have no good values for
head->second.prev> and <tail->second.next
Thus, we will treat these as *undefined*.
*/ |
void head_insert ( const KeyType & key, const DataType & data ) const {
EntryType entry ( data, head, the_map.end() );
IterType new_head = the_map.insert( PairType( key, entry ) ).first;
if ( the_map.size() > 1 ) {
// head is still the old head !
head->second.prev = new_head;
} else {
tail = new_head;
}
head = new_head;
}
void tail_insert ( const KeyType & key, const DataType & data ) const {
EntryType entry ( data, head, the_map.end() );
IterType new_tail = the_map.insert( PairType( key, entry ) ).first;
if ( the_map.size() > 1 ) {
// tail is still the old tail !
tail->second.next = new_tail;
} else {
head = new_tail;
}
tail = new_tail;
}
void move_to_front ( const IterType & pos ) const {
if ( pos != head ) {
if ( pos != tail ) {
pos->second.next->second.prev = pos->second.prev;
pos->second.prev->second.next = pos->second.next;
} else {
tail = pos->second.prev;
}
pos->second.next = head;
head->second.prev= pos;
head = pos;
}
}
/*
| Quote: | Given the list operation, we can now implement some
basic routines.
*/ |
void remove_last ( void ) const {
assert( the_map.size() > 0 );
IterType old_tail ( tail );
if ( the_map.size() > 1 ) {
tail = old_tail->second.prev;
the_map.erase( old_tail );
} else {
the_map.erase( old_tail );
head = tail = the_map.end();
}
}
void shrink_to_fit ( void ) const {
while ( the_map.size() > max_capacity ) {
remove_last();
}
}
public:
typedef KeyType key_type;
typedef DataType mapped_type;
typedef std::pair< const KeyType, DataType > value_type;
typedef Compare key_compare;
typedef Function transform;
typedef Allocator alloc_type;
cache ( Function & _function, std::size_t new_capacity = Max_Size ) :
the_function( _function ),
the_map(),
max_capacity( new_capacity ),
head( the_map.end() ),
tail( the_map.end() )
{}
cache ( const cache & other ) {
copy( other, other.capacity() );
}
~cache ( void ) {
this->clear();
}
const cache & operator= ( const cache & other ) {
if ( this != &other ) {
copy( other, other.capacity() );
}
return( *this );
}
DataType operator() ( const KeyType & key ) const {
IterType entry_pos = the_map.find( key );
if ( entry_pos == the_map.end() ) {
// not cached
DataType result ( the_function( key ) );
head_insert( key, result );
this->shrink_to_fit();
return( result );
} else {
// cached
move_to_front( entry_pos );
return( head->second.data );
}
}
void clear ( void ) const {
the_map.clear();
head = the_map.end();
tail = the_map.end();
}
bool empty ( void ) const {
return( the_map.empty() );
}
std::size_t size ( void ) const {
return( the_map.size() );
}
void resize ( std::size_t new_capacity ) const {
max_capacity = new_capacity;
this->shrink_to_fit();
}
std::size_t capacity ( void ) const {
return( max_capacity );
}
void copy ( const cache & other, std::size_t length ) {
the_function = other.the_function;
the_map.clear();
max_capacity = length;
IterType iter = other.head;
for ( std::size_t i = std::min( length, other.size() );
i > 0;
--i ) {
tail_insert( iter->first, iter->second.data );
iter = iter->second.next;
}
}
void write ( std::ostream & ostr ) const {
ostr << '[';
if ( the_map.size() > 0 ) {
IterType iter = head;
while( true ) {
ostr << ' '
<< std::pair
( iter->first, iter->second.data );
if ( iter == tail ) {
break;
}
ostr << ',';
iter = iter->second.next;
}
}
ostr << " ]";
}
}; // cache<>
} // namespace kubux
template< typename KeyType,
typename DataType,
typename Function,
std::size_t Max_Size,
typename Compare,
typename Allocator
| Quote: |
std::ostream & operator<< ( std::ostream & ostr, |
const kubux::cache<
KeyType,
DataType,
Function,
Max_Size,
Compare,
Allocator > & the_cache ) {
the_cache.write( ostr );
return( ostr );
}
#endif // __KUBUX_cache__
// end of file
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Maciej Sobczak
Guest
|
| Posted: Tue Aug 17, 2004 7:59 pm Post subject: Re: cache - fixed size map |
|
|
Hi,
Radu Grigore wrote:
| Quote: | A cache can be implemented as a (hash_)map. In my case the growing
size might become a problem. A possible solution is to remove elements
(LFU, LRU) either periodically or, probably easier, in such a way as
to preserve a maximum size. It seems like a common problem and I'm
wondering if anyone has already done it: preferably as an open source
library, but an open source project (so I can read the code) is OK
too.
|
Take a look at: <http://www.msobczak.com/prog/downloads.html>
and get the agingcache.zip file.
Internally, it is a list that is kept within a given maximum size limit.
It is quite old code in the sense that today I would write it much
differently, but it may anyway give you some ideas for your own development.
--
Maciej Sobczak : http://www.msobczak.com/
Programming : http://www.msobczak.com/prog/
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
