ut::prefix_cache< CharType, Value > Class Template Reference

Bounded cache for prefix lookups with MRU/LRU recency tracking. More...

#include <ut0prefix_cache.h>

Classes
struct	Entry

Public Types
using	sequence = std::basic_string< CharType >
using	sequence_view = std::basic_string_view< CharType >

Public Member Functions
	prefix_cache (size_t capacity)
	Create a cache with at most capacity stored prefixes. More...
	prefix_cache (const prefix_cache &)=delete
prefix_cache &	operator= (const prefix_cache &)=delete
Value *	find_value_for_prefix_of (sequence_view &buffer)
	Find a cached value whose key is the longest prefix of buffer. More...
bool	insert (sequence_view prefix, Value value)
	Insert a new prefix/value pair as the most recently used entry. More...

Private Types
using	Map = std::map< sequence, Entry, std::greater<> >
using	It = typename Map::iterator
using	Lru_list = std::list< It >
using	Lru_it = typename Lru_list::iterator

Private Member Functions
It	try_find (sequence_view buffer)
void	move_to_front (It it)
void	link_new_mru (It it)
void	enforce_capacity ()

Static Private Member Functions
static bool	is_prefix (sequence_view key, sequence_view buffer)

Private Attributes
size_t	m_capacity
Map	m_map
Lru_list	m_lru

Detailed Description

template<typename CharType, typename Value>
class ut::prefix_cache< CharType, Value >

Bounded cache for prefix lookups with MRU/LRU recency tracking.

The main use case is in parsers, which consume a prefix of a buffer, to produce a value, where the length of the prefix is not know up-front without parsing. This solves the case in which callers need to map owned prefixes to values, probe whether a cached prefix matches the beginning of a buffer, and evict old entries when the cache reaches a fixed size. Standard containers alone are not enough, because they do not combine prefix lookup, stable owned keys, and LRU eviction in one reusable abstraction.

Important limitation of this class (met by the parser usecase) is that it can work only with prefix-free languages, i.e. that is it doesn't support adding two prefixes such that one is a proper prefix of another.

Member Typedef Documentation

It

template<typename CharType , typename Value >

using ut::prefix_cache< CharType, Value >::It = typename Map::iterator

private

Lru_it

template<typename CharType , typename Value >

using ut::prefix_cache< CharType, Value >::Lru_it = typename Lru_list::iterator

private

Lru_list

template<typename CharType , typename Value >

using ut::prefix_cache< CharType, Value >::Lru_list = std::list<It>

private

Map

template<typename CharType , typename Value >

using ut::prefix_cache< CharType, Value >::Map = std::map<sequence, Entry, std::greater<> >

private

sequence

template<typename CharType , typename Value >

using ut::prefix_cache< CharType, Value >::sequence = std::basic_string<CharType>

sequence_view

template<typename CharType , typename Value >

using ut::prefix_cache< CharType, Value >::sequence_view = std::basic_string_view<CharType>

Constructor & Destructor Documentation

prefix_cache() [1/2]

template<typename CharType , typename Value >

ut::prefix_cache< CharType, Value >::prefix_cache ( size_t  capacity )

inlineexplicit

Create a cache with at most capacity stored prefixes.

Parameters

[in]

capacity

The maximum number of entries kept after each insertion

prefix_cache() [2/2]

template<typename CharType , typename Value >

ut::prefix_cache< CharType, Value >::prefix_cache ( const prefix_cache< CharType, Value > &  )

delete

Member Function Documentation

enforce_capacity()

template<typename CharType , typename Value >

void ut::prefix_cache< CharType, Value >::enforce_capacity ( )

inlineprivate

find_value_for_prefix_of()

template<typename CharType , typename Value >

Value * ut::prefix_cache< CharType, Value >::find_value_for_prefix_of ( sequence_view &  buffer )

inline

Find a cached value whose key is the longest prefix of buffer.

If a match is found, the entry becomes most recently used and the buffer is trimmed to the leftover suffix.

Parameters

[in,out]

buffer

The input buffer. Trimmed to the leftover suffix on match. Otherwise kept intact.

Returns

The pointer to cached value or nullptr if no match. It is only safe to dereference it until next call to insert(..).

insert()

template<typename CharType , typename Value >

bool ut::prefix_cache< CharType, Value >::insert ( sequence_view  prefix, Value  value  )

inline

Insert a new prefix/value pair as the most recently used entry.

If prefix already exists, the cache is left unchanged. After a successful insertion, least recently used entries are evicted until the cache size is within capacity.

The caller must ensure that the language is prefix-free, i.e. that the prefix is not a proper prefix of any previously inserted one, nor vice-versa.

Invalidates pointers returned by find_value_for_prefix_of(..), as they might become evicted as a result of this call.

Parameters

[in]	prefix	key prefix.
[in]	value	value to store.

Returns

true if inserted, false if key already existed

is_prefix()

template<typename CharType , typename Value >

static bool ut::prefix_cache< CharType, Value >::is_prefix ( sequence_view  key, sequence_view  buffer  )

inlinestaticprivate

link_new_mru()

template<typename CharType , typename Value >

void ut::prefix_cache< CharType, Value >::link_new_mru ( It  it )

inlineprivate

move_to_front()

template<typename CharType , typename Value >

void ut::prefix_cache< CharType, Value >::move_to_front ( It  it )

inlineprivate

operator=()

template<typename CharType , typename Value >

prefix_cache & ut::prefix_cache< CharType, Value >::operator= ( const prefix_cache< CharType, Value > &  )

delete

try_find()

template<typename CharType , typename Value >

It ut::prefix_cache< CharType, Value >::try_find ( sequence_view  buffer )

inlineprivate

Member Data Documentation

m_capacity

template<typename CharType , typename Value >

size_t ut::prefix_cache< CharType, Value >::m_capacity

private

m_lru

template<typename CharType , typename Value >

Lru_list ut::prefix_cache< CharType, Value >::m_lru

private

m_map

template<typename CharType , typename Value >

Map ut::prefix_cache< CharType, Value >::m_map

private

---

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

• storage/innobase/include/ut0prefix_cache.h