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, ValueSize > Class Template Referencefinal

LRU map. More...

#include <lru_map.hxx>

Inheritance diagram for o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >:
[legend]
Collaboration diagram for o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >:
[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 setMaxSize (size_t nMaxSize)
 
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_t > list_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 addSize (const Value &value)
 
void removeSize (const Value &value)
 
void removeOldestItem ()
 
void checkLRUItemInsert ()
 
void checkLRUItemUpdate ()
 
void checkLRUMaxSize ()
 
void clearSize ()
 

Private Attributes

list_t mLruList
 
map_t mLruMap
 
size_t mMaxSize
 

Detailed Description

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

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.

It is optionally possible to specify a function for ValueSize template argument (that can be called as 'size_t func(Value)') that will return a size (cost) for an item instead of the default size of 1 for each item. The size of an item must not change for an item (if needed, re-insert the item). A newly inserted item is guaranteed to be in the container, even if its size exceeds the maximum size.

Definition at line 66 of file lru_map.hxx.

Member Typedef Documentation

◆ const_iterator

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

Definition at line 167 of file lru_map.hxx.

◆ iterator

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

Definition at line 166 of file lru_map.hxx.

◆ key_value_pair_t

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

Definition at line 69 of file lru_map.hxx.

◆ list_const_iterator_t

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

Definition at line 74 of file lru_map.hxx.

◆ list_iterator_t

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

Definition at line 73 of file lru_map.hxx.

◆ list_t

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

Definition at line 72 of file lru_map.hxx.

◆ map_const_iterator_t

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

Definition at line 78 of file lru_map.hxx.

◆ map_iterator_t

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

Definition at line 77 of file lru_map.hxx.

◆ map_t

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

Definition at line 76 of file lru_map.hxx.

Constructor & Destructor Documentation

◆ lru_map()

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

Definition at line 169 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mMaxSize.

◆ ~lru_map()

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

Definition at line 174 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clearSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap.

Member Function Documentation

◆ addSize()

template<typename Key , typename Value , class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class ValueSize = void>
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::addSize ( const Value &  value)
inlineprivate

Definition at line 84 of file lru_map.hxx.

References value.

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::insert().

◆ begin()

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

Definition at line 276 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList.

◆ checkLRUItemInsert()

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

Definition at line 111 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mMaxSize, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeOldestItem().

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::insert().

◆ checkLRUItemUpdate()

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

Definition at line 126 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mMaxSize, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeOldestItem().

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::insert().

◆ checkLRUMaxSize()

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

Definition at line 137 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mMaxSize, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeOldestItem().

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::setMaxSize().

◆ clear()

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

Definition at line 288 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clearSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap.

◆ clearSize()

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

Definition at line 151 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeSize().

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clear(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::~lru_map().

◆ end()

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

Definition at line 278 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList.

◆ find()

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

Definition at line 243 of file lru_map.hxx.

References i, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap.

◆ insert() [1/2]

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

Definition at line 217 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::addSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemInsert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemUpdate(), i, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeSize().

◆ insert() [2/2]

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

Definition at line 190 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::addSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemInsert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemUpdate(), i, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeSize().

◆ remove_if()

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

Definition at line 260 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeSize().

◆ removeOldestItem()

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

Definition at line 102 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeSize().

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemInsert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemUpdate(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUMaxSize().

◆ removeSize()

template<typename Key , typename Value , class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class ValueSize = void>
void o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeSize ( const Value &  value)
inlineprivate

Definition at line 91 of file lru_map.hxx.

References value.

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clearSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::insert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::remove_if(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeOldestItem().

◆ setMaxSize()

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

Definition at line 183 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUMaxSize(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mMaxSize.

◆ size()

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

Definition at line 280 of file lru_map.hxx.

References o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruList, and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::mLruMap.

Member Data Documentation

◆ mLruList

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

Definition at line 80 of file lru_map.hxx.

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::begin(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemInsert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemUpdate(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clear(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clearSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::end(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::find(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::insert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::remove_if(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeOldestItem(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::size(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::~lru_map().

◆ mLruMap

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

Definition at line 81 of file lru_map.hxx.

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemInsert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUMaxSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::clear(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::find(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::insert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::remove_if(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::removeOldestItem(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::size(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::~lru_map().

◆ mMaxSize

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

Definition at line 82 of file lru_map.hxx.

Referenced by o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemInsert(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUItemUpdate(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::checkLRUMaxSize(), o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::lru_map(), and o3tl::lru_map< Key, Value, KeyHash, KeyEqual, ValueSize >::setMaxSize().

The documentation for this class was generated from the following file:
Generated on Sun Jul 30 2023 04:39:38 for LibreOffice Module o3tl (master) by doxygen 1.9.3