#include <ClpMap.h>

Collaboration diagram for ClpMap< Key, Value, MemoryUsedBy >:

Classes
class	Entry
	the keeper of cache entry Key, Value, and caching-related entry metadata More...

Public Types
using	key_type = Key

using	mapped_type = Value

using	Ttl = int
	maximum desired entry caching duration (a.k.a. TTL), in seconds

using	Entries = std::list< Entry, PoolingAllocator< Entry > >
	Entries in LRU order.

using	EntriesIterator = typename Entries::iterator

using	ConstEntriesIterator = typename Entries::const_iterator

Public Member Functions
	ClpMap (const uint64_t capacity)

	ClpMap (uint64_t capacity, Ttl defaultTtl)

	~ClpMap ()=default

	ClpMap (const ClpMap &)=delete

ClpMap &	operator= (const ClpMap &)=delete

const Value *	get (const Key &)

bool	add (const Key &, const Value &, Ttl)

bool	add (const Key &key, const Value &v)
	Copy the given value into the map (with the given key and default TTL)

void	del (const Key &)
	Remove the corresponding entry (if any)

void	setMemLimit (uint64_t newLimit)
	Reset the memory capacity for this map, purging if needed.

uint64_t	memLimit () const
	The memory capacity for the map.

uint64_t	freeMem () const
	The free space of the map.

uint64_t	memoryUsed () const
	The current (approximate) memory usage of the map.

size_t	entries () const
	The number of currently stored entries, including expired ones.

ConstEntriesIterator	cbegin () const

ConstEntriesIterator	cend () const

ConstEntriesIterator	begin () const
	range-based `for` loop support;

ConstEntriesIterator	end () const

Private Types
using	IndexItem = std::pair< const Key, EntriesIterator >

using	Index = std::unordered_map< Key, EntriesIterator, std::hash< Key >, std::equal_to< Key >, PoolingAllocator< IndexItem > >
	key:entry_position mapping for fast entry lookups by key

using	IndexIterator = typename Index::iterator

Private Member Functions
void	trim (uint64_t wantSpace)
	purges entries to make free memory large enough to fit wantSpace bytes

void	erase (const IndexIterator &)
	removes the cached entry (identified by its index) from the map

IndexIterator	find (const Key &)

Static Private Member Functions
static std::optional< uint64_t >	MemoryCountedFor (const Key &, const Value &)

Private Attributes
Entries	entries_
	cached entries, including expired ones, in LRU order

Index	index_
	entries_ positions indexed by the entry key

Ttl	defaultTtl_ = std::numeric_limits<Ttl>::max()
	entry TTL to use if none provided to add()

uint64_t	memLimit_ = 0
	the maximum memory we are allowed to use for all cached entries

uint64_t	memUsed_ = 0
	the total amount of memory we currently use for all cached entries

Detailed Description

template<class Key, class Value, uint64_t MemoryUsedBy = DefaultMemoryUsage>
class ClpMap< Key, Value, MemoryUsedBy >

An in-memory associative container enforcing three primary caching policies:

Capacity: The memory used by cached entries has a configurable limit;
Lifetime: Entries are hidden (and may be deleted) after their TTL expires;
Priority: Capacity victims are purged in LRU order. Individual cache entry operations have average constant-time complexity.

Value must meet STL requirements of Erasable and EmplaceConstructible. Key must come with std::hash<Key> and std::equal_to<Key> instantiations. Key::length() must return the number of memory bytes in use by the key. MemoryUsedBy() must return the number of memory bytes in use by the value.

Definition at line 40 of file ClpMap.h.

Member Typedef Documentation

◆ ConstEntriesIterator

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::ConstEntriesIterator = typename Entries::const_iterator

Definition at line 68 of file ClpMap.h.

◆ Entries

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::Entries = std::list<Entry, PoolingAllocator<Entry> >

Definition at line 66 of file ClpMap.h.

◆ EntriesIterator

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::EntriesIterator = typename Entries::iterator

Definition at line 67 of file ClpMap.h.

◆ Index

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::Index = std::unordered_map<Key, EntriesIterator, std::hash<Key>, std::equal_to<Key>, PoolingAllocator<IndexItem> >

private

Definition at line 123 of file ClpMap.h.

◆ IndexItem

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::IndexItem = std::pair<const Key, EntriesIterator>

private

Definition at line 121 of file ClpMap.h.

◆ IndexIterator

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::IndexIterator = typename Index::iterator

private

Definition at line 124 of file ClpMap.h.

◆ key_type

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::key_type = Key

Definition at line 43 of file ClpMap.h.

◆ mapped_type

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::mapped_type = Value

Definition at line 44 of file ClpMap.h.

◆ Ttl

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

using ClpMap< Key, Value, MemoryUsedBy >::Ttl = int

Definition at line 47 of file ClpMap.h.

Constructor & Destructor Documentation

◆ ClpMap() [1/3]

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ClpMap< Key, Value, MemoryUsedBy >::ClpMap ( const uint64_t capacity )

inlineexplicit

Definition at line 70 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::setMemLimit().

◆ ClpMap() [2/3]

template<class Key , class Value , uint64_t MemoryUsedBy>

ClpMap< Key, Value, MemoryUsedBy >::ClpMap	(	uint64_t	capacity,
		Ttl	defaultTtl
	)

Definition at line 149 of file ClpMap.h.

References assert, and ClpMap< Key, Value, MemoryUsedBy >::setMemLimit().

◆ ~ClpMap()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ClpMap< Key, Value, MemoryUsedBy >::~ClpMap ( )

default

◆ ClpMap() [3/3]

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ClpMap< Key, Value, MemoryUsedBy >::ClpMap ( const ClpMap< Key, Value, MemoryUsedBy > & )

delete

Member Function Documentation

◆ add() [1/2]

template<class Key , class Value , uint64_t MemoryUsedBy>

bool ClpMap< Key, Value, MemoryUsedBy >::add	(	const Key &	key,
		const Value &	v,
		Ttl	ttl
	)

Copy the given value into the map (with the given key and TTL)

Return values

true	the value was successfully copied into the map
false	caching was rejected (the map remains unchanged)

Definition at line 220 of file ClpMap.h.

References addedEntry(), and assert.

Referenced by TestClpMap::addOneEntry(), TestClpMap::addOneEntry(), TestClpMap::addSequenceOfEntriesToMap(), TestClpMap::testEntryCounter(), TestClpMap::testNegativeTtl(), and TestClpMap::testPutGetDelete().

◆ add() [2/2]

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

bool ClpMap< Key, Value, MemoryUsedBy >::add	(	const Key &	key,
		const Value &	v
	)

inline

Definition at line 91 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::add(), and ClpMap< Key, Value, MemoryUsedBy >::defaultTtl_.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::add().

◆ begin()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ConstEntriesIterator ClpMap< Key, Value, MemoryUsedBy >::begin ( ) const

inline

See also: cbegin()

Definition at line 117 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::cbegin().

◆ cbegin()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ConstEntriesIterator ClpMap< Key, Value, MemoryUsedBy >::cbegin ( ) const

inline

Read-only traversal of all cached entries in LRU order, least recently used entry first. Stored expired entries (if any) are included. Any map modification may invalidate these iterators and their derivatives.

Definition at line 114 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::entries_.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::begin(), and TestClpMap::testClassicLoopTraversal().

◆ cend()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ConstEntriesIterator ClpMap< Key, Value, MemoryUsedBy >::cend ( ) const

inline

Definition at line 115 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::entries_.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::end(), and TestClpMap::testClassicLoopTraversal().

◆ del()

template<class Key , class Value , uint64_t MemoryUsedBy>

void ClpMap< Key, Value, MemoryUsedBy >::del ( const Key & key )

Definition at line 268 of file ClpMap.h.

Referenced by TestClpMap::testMisses(), and TestClpMap::testPutGetDelete().

◆ end()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ConstEntriesIterator ClpMap< Key, Value, MemoryUsedBy >::end ( ) const

inline

Definition at line 118 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::cend().

◆ entries()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

size_t ClpMap< Key, Value, MemoryUsedBy >::entries ( ) const

inline

Definition at line 109 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::entries_.

Referenced by TestClpMap::testConstructor(), TestClpMap::testEntryCounter(), TestClpMap::testMemoryLimit(), and TestClpMap::testMisses().

◆ erase()

template<class Key , class Value , uint64_t MemoryUsedBy>

void ClpMap< Key, Value, MemoryUsedBy >::erase ( const IndexIterator & i )

private

Definition at line 252 of file ClpMap.h.

References assert.

◆ find()

template<class Key , class Value , uint64_t MemoryUsedBy>

ClpMap< Key, Value, MemoryUsedBy >::IndexIterator ClpMap< Key, Value, MemoryUsedBy >::find ( const Key & key )

private

Returns: the index position of an entry identified by its key (or end())

Definition at line 168 of file ClpMap.h.

◆ freeMem()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

uint64_t ClpMap< Key, Value, MemoryUsedBy >::freeMem ( ) const

inline

Definition at line 103 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::memLimit(), and ClpMap< Key, Value, MemoryUsedBy >::memoryUsed().

Referenced by TestClpMap::testConstructor().

◆ get()

template<class Key , class Value , uint64_t MemoryUsedBy>

const Value * ClpMap< Key, Value, MemoryUsedBy >::get ( const Key & key )

Returns: a pointer to a fresh cached value (or nil) The underlying value is owned by the map, so the pointer may be invalidated by any non-constant method call, including another get(). Also moves the found entry to the end of the purging queue.

Definition at line 188 of file ClpMap.h.

Referenced by TestClpMap::addOneEntry(), TestClpMap::addOneEntry(), TestClpMap::testMisses(), TestClpMap::testNegativeTtl(), TestClpMap::testPurgeIsLru(), TestClpMap::testPutGetDelete(), TestClpMap::testReplaceEntryWithShorterTtl(), TestClpMap::testTtlExpiration(), and TestClpMap::testZeroTtl().

◆ memLimit()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

uint64_t ClpMap< Key, Value, MemoryUsedBy >::memLimit ( ) const

inline

Definition at line 100 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::memLimit_.

Referenced by TestClpMap::fillMapWithEntries(), ClpMap< Key, Value, MemoryUsedBy >::freeMem(), and TestClpMap::testConstructor().

◆ MemoryCountedFor()

template<class Key , class Value , uint64_t MemoryUsedBy>

std::optional< uint64_t > ClpMap< Key, Value, MemoryUsedBy >::MemoryCountedFor	(	const Key &	k,
		const Value &	v
	)

staticprivate

Definition at line 200 of file ClpMap.h.

◆ memoryUsed()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

uint64_t ClpMap< Key, Value, MemoryUsedBy >::memoryUsed ( ) const

inline

Definition at line 106 of file ClpMap.h.

References ClpMap< Key, Value, MemoryUsedBy >::memUsed_.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::freeMem(), TestClpMap::testConstructor(), and TestClpMap::testMemoryLimit().

◆ operator=()

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

ClpMap & ClpMap< Key, Value, MemoryUsedBy >::operator= ( const ClpMap< Key, Value, MemoryUsedBy > & )

delete

◆ setMemLimit()

template<class Key , class Value , uint64_t MemoryUsedBy>

void ClpMap< Key, Value, MemoryUsedBy >::setMemLimit ( uint64_t newLimit )

Definition at line 158 of file ClpMap.h.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::ClpMap(), ClpMap< Key, Value, MemoryUsedBy >::ClpMap(), and TestClpMap::testMemoryLimit().

◆ trim()

template<class Key , class Value , uint64_t MemoryUsedBy>

void ClpMap< Key, Value, MemoryUsedBy >::trim ( uint64_t wantSpace )

private

Definition at line 278 of file ClpMap.h.

References assert.

Member Data Documentation

◆ defaultTtl_

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

Ttl ClpMap< Key, Value, MemoryUsedBy >::defaultTtl_ = std::numeric_limits<Ttl>::max()

private

Definition at line 139 of file ClpMap.h.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::add().

◆ entries_

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

Entries ClpMap< Key, Value, MemoryUsedBy >::entries_

private

Definition at line 133 of file ClpMap.h.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::cbegin(), ClpMap< Key, Value, MemoryUsedBy >::cend(), and ClpMap< Key, Value, MemoryUsedBy >::entries().

◆ index_

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

Index ClpMap< Key, Value, MemoryUsedBy >::index_

private

Definition at line 136 of file ClpMap.h.

◆ memLimit_

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

uint64_t ClpMap< Key, Value, MemoryUsedBy >::memLimit_ = 0

private

Definition at line 142 of file ClpMap.h.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::memLimit().

◆ memUsed_

template<class Key , class Value , uint64_t MemoryUsedBy = DefaultMemoryUsage>

uint64_t ClpMap< Key, Value, MemoryUsedBy >::memUsed_ = 0

private

Definition at line 145 of file ClpMap.h.

Referenced by ClpMap< Key, Value, MemoryUsedBy >::memoryUsed().

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

squid/src/base/ClpMap.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ConstEntriesIterator

◆ Entries

◆ EntriesIterator

◆ Index

◆ IndexItem

◆ IndexIterator

◆ key_type

◆ mapped_type

◆ Ttl

Constructor & Destructor Documentation

◆ ClpMap() [1/3]

◆ ClpMap() [2/3]

◆ ~ClpMap()

◆ ClpMap() [3/3]

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ begin()

◆ cbegin()

◆ cend()

◆ del()

◆ end()

◆ entries()

◆ erase()

◆ find()

◆ freeMem()

◆ get()

◆ memLimit()

◆ MemoryCountedFor()

◆ memoryUsed()

◆ operator=()

◆ setMemLimit()

◆ trim()

Member Data Documentation

◆ defaultTtl_

◆ entries_

◆ index_

◆ memLimit_

◆ memUsed_