LibreOffice Module o3tl (master)  1
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
o3tl::lru_map< Key, Value, KeyHash, KeyEqual > Class Template Referencefinal

LRU map. More...

#include <lru_map.hxx>

Inheritance diagram for o3tl::lru_map< Key, Value, KeyHash, KeyEqual >:
[legend]

Public Types

typedef std::pair< Key, Value > key_value_pair_t
 
typedef list_iterator_t iterator
 
typedef list_const_iterator_t const_iterator
 

Public Member Functions

 lru_map (size_t nMaxSize)
 
 ~lru_map ()
 
void insert (key_value_pair_t &rPair)
 
void insert (key_value_pair_t &&rPair)
 
list_const_iterator_t find (const Key &key)
 
template<class UnaryPredicate >
void remove_if (UnaryPredicate pred)
 
list_const_iterator_t begin () const
 
list_const_iterator_t end () const
 
size_t size () const
 
void clear ()
 

Private Types

typedef std::list< key_value_pair_tlist_t
 
typedef list_t::iterator list_iterator_t
 
typedef list_t::const_iterator list_const_iterator_t
 
typedef std::unordered_map< Key, list_iterator_t, KeyHash, KeyEqual > map_t
 
typedef map_t::iterator map_iterator_t
 
typedef map_t::const_iterator map_const_iterator_t
 

Private Member Functions

void checkLRU ()
 

Private Attributes

list_t mLruList
 
map_t mLruMap
 
const size_t mMaxSize
 

Detailed Description

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
class o3tl::lru_map< Key, Value, KeyHash, KeyEqual >

LRU map.

Similar to unordered_map (it actually uses it) with additionally functionality which removes the entries that have been "least recently used" when the size hits the specified capacity.

It only implements the minimal methods needed and the implementation is NOT thread safe.

The implementation is as simple as possible but it still uses O(1) complexity for most of the operations with a combination unordered map and linked list.

Definition at line 35 of file lru_map.hxx.

Member Typedef Documentation

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef list_const_iterator_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::const_iterator

Definition at line 66 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef list_iterator_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::iterator

Definition at line 65 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef std::pair<Key, Value> o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::key_value_pair_t

Definition at line 38 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef list_t::const_iterator o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::list_const_iterator_t
private

Definition at line 43 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef list_t::iterator o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::list_iterator_t
private

Definition at line 42 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef std::list<key_value_pair_t> o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::list_t
private

Definition at line 41 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef map_t::const_iterator o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::map_const_iterator_t
private

Definition at line 47 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef map_t::iterator o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::map_iterator_t
private

Definition at line 46 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
typedef std::unordered_map<Key, list_iterator_t, KeyHash, KeyEqual> o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::map_t
private

Definition at line 45 of file lru_map.hxx.

Constructor & Destructor Documentation

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::lru_map ( size_t  nMaxSize)
inline

Definition at line 69 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::~lru_map ( )
inline

Definition at line 73 of file lru_map.hxx.

Member Function Documentation

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
list_const_iterator_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::begin ( ) const
inline

Definition at line 158 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::checkLRU ( )
inlineprivate
template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::clear ( )
inline

Definition at line 168 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
list_const_iterator_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::end ( ) const
inline

Definition at line 160 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
list_const_iterator_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::find ( const Key key)
inline

Definition at line 126 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::insert ( key_value_pair_t rPair)
inline

Definition at line 82 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::insert ( key_value_pair_t &&  rPair)
inline

Definition at line 104 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
template<class UnaryPredicate >
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::remove_if ( UnaryPredicate  pred)
inline

Definition at line 143 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
size_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::size ( ) const
inline

Definition at line 162 of file lru_map.hxx.

Member Data Documentation

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
list_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::mLruList
private
template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
map_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::mLruMap
private

Definition at line 50 of file lru_map.hxx.

template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
const size_t o3tl::lru_map< Key, Value, KeyHash, KeyEqual >::mMaxSize
private

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