Loading...
Searching...
No Matches
lru.hh
Go to the documentation of this file.
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
#ifndef DUNE_COMMON_LRU_HH
#define DUNE_COMMON_LRU_HH
#include <list>
#include <utility>
#include <map>
#include <memory>
#include <dune/common/exceptions.hh>
namespace Dune {
namespace {
/*
hide the default traits in an empty namespace
*/
template <typename Key, typename Tp,
typename Alloc = std::allocator<Tp> >
struct _lru_default_traits
{
typedef Key key_type;
typedef Alloc allocator;
typedef std::list< std::pair<Key, Tp> > list_type;
typedef typename list_type::iterator iterator;
typedef typename std::less<key_type> cmp;
typedef std::map< key_type, iterator, cmp,
typename std::allocator_traits<allocator>::template rebind_alloc<std::pair<const key_type, iterator> > > map_type;
};
} // end empty namespace
template <typename Key, typename Tp,
typename Traits = _lru_default_traits<Key, Tp> >
class lru
{
typedef typename Traits::list_type list_type;
typedef typename Traits::map_type map_type;
typedef typename Traits::allocator allocator;
typedef typename map_type::iterator map_iterator;
typedef typename map_type::const_iterator const_map_iterator;
public:
typedef typename Traits::key_type key_type;
typedef typename allocator::value_type value_type;
using pointer = typename allocator::value_type*;
using const_pointer = typename allocator::value_type const*;
using const_reference = typename allocator::value_type const&;
using reference = typename allocator::value_type&;
typedef typename allocator::size_type size_type;
typedef typename list_type::iterator iterator;
typedef typename list_type::const_iterator const_iterator;
reference front()
{
return _data.front().second;
}
const_reference front() const
{
return _data.front().second;
}
reference back()
{
return _data.back().second;
}
const_reference back ([[maybe_unused]] int i) const
{
return _data.back().second;
}
void pop_front()
{
key_type k = _data.front().first;
_data.pop_front();
_index.erase(k);
}
void pop_back()
{
key_type k = _data.back().first;
_data.pop_back();
_index.erase(k);
}
iterator find (const key_type & key)
{
const map_iterator it = _index.find(key);
if (it == _index.end()) return _data.end();
return it->second;
}
const_iterator find (const key_type & key) const
{
const map_iterator it = _index.find(key);
if (it == _index.end()) return _data.end();
return it->second;
}
reference insert (const key_type & key, const_reference data)
{
std::pair<key_type, value_type> x(key, data);
/* insert item as mru */
iterator it = _data.insert(_data.begin(), x);
/* store index */
_index.insert(std::make_pair(key,it));
return it->second;
}
reference insert (const key_type & key)
{
return touch (key);
}
reference touch (const key_type & key)
{
/* query _index for iterator */
map_iterator it = _index.find(key);
if (it == _index.end())
DUNE_THROW(Dune::RangeError,
"Failed to touch key " << key << ", it is not in the lru container");
/* update _data
move it to the front
*/
_data.splice(_data.begin(), _data, it->second);
return it->second->second;
}
size_type size() const
{
return _data.size();
}
void resize(size_type new_size)
{
assert(new_size <= size());
while (new_size < size())
pop_back();
}
void clear()
{
_data.clear();
_index.clear();
}
private:
list_type _data;
map_type _index;
};
} // namespace Dune
#endif // DUNE_COMMON_LRU_HH
exceptions.hh
A few common exception classes.
DUNE_THROW
#define DUNE_THROW(E,...)
Definition exceptions.hh:314
Dune
Dune namespace
Definition alignedallocator.hh:13
Dune::RangeError
Default exception class for range errors.
Definition exceptions.hh:348
Dune::lru
LRU Cache Container.
Definition lru.hh:52
Dune::lru::pop_back
void pop_back()
Removes the last element.
Definition lru.hh:119
Dune::lru::find
iterator find(const key_type &key)
Finds the element whose key is k.
Definition lru.hh:131
Dune::lru::insert
reference insert(const key_type &key)
mark data associated with key as most recent
Definition lru.hh:175
Dune::lru::const_iterator
list_type::const_iterator const_iterator
Definition lru.hh:68
Dune::lru::resize
void resize(size_type new_size)
ensure a maximum size of the container
Definition lru.hh:213
Dune::lru::size_type
allocator::size_type size_type
Definition lru.hh:66
Dune::lru::iterator
list_type::iterator iterator
Definition lru.hh:67
Dune::lru::value_type
allocator::value_type value_type
Definition lru.hh:61
Dune::lru::front
const_reference front() const
Definition lru.hh:83
Dune::lru::const_pointer
typename allocator::value_type const * const_pointer
Definition lru.hh:63
Dune::lru::size
size_type size() const
Retrieve number of entries in the container.
Definition lru.hh:202
Dune::lru::reference
typename allocator::value_type & reference
Definition lru.hh:65
Dune::lru::back
reference back()
Definition lru.hh:92
Dune::lru::pop_front
void pop_front()
Removes the first element.
Definition lru.hh:110
Dune::lru::front
reference front()
Definition lru.hh:74
Dune::lru::clear
void clear()
Definition lru.hh:224
Dune::lru::touch
reference touch(const key_type &key)
mark data associated with key as most recent
Definition lru.hh:185
Dune::lru::insert
reference insert(const key_type &key, const_reference data)
Insert a value into the container.
Definition lru.hh:161
Dune::lru::pointer
typename allocator::value_type * pointer
Definition lru.hh:62
Dune::lru::find
const_iterator find(const key_type &key) const
Finds the element whose key is k.
Definition lru.hh:143
Dune::lru::const_reference
typename allocator::value_type const & const_reference
Definition lru.hh:64
Dune::lru::key_type
Traits::key_type key_type
Definition lru.hh:60
Dune::lru::back
const_reference back(int i) const
Definition lru.hh:101