proxygen: folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual

#include <EvictingCacheMap.h>

Classes
class	iterator_base

struct	KeyHasher

struct	KeyValueEqual

struct	Node

Public Types
typedef std::function< void(TKey, TValue &&)>	PruneHookCall

typedef iterator_base< TPair, typename NodeList::iterator >	iterator

typedef iterator_base< const TPair, typename NodeList::const_iterator >	const_iterator

typedef iterator_base< TPair, typename NodeList::reverse_iterator >	reverse_iterator

typedef iterator_base< const TPair, typename NodeList::const_reverse_iterator >	const_reverse_iterator

using	key_type = TKey

using	mapped_type = TValue

using	hasher = THash

Public Member Functions
	EvictingCacheMap (std::size_t maxSize, std::size_t clearSize=1, const THash &keyHash=THash(), const TKeyEqual &keyEqual=TKeyEqual())

	EvictingCacheMap (const EvictingCacheMap &)=delete

EvictingCacheMap &	operator= (const EvictingCacheMap &)=delete

	EvictingCacheMap (EvictingCacheMap &&)=default

EvictingCacheMap &	operator= (EvictingCacheMap &&)=default

	~EvictingCacheMap ()

void	setMaxSize (size_t maxSize, PruneHookCall pruneHook=nullptr)

size_t	getMaxSize () const

void	setClearSize (size_t clearSize)

bool	exists (const TKey &key) const

TValue &	get (const TKey &key)

iterator	find (const TKey &key)

const TValue &	getWithoutPromotion (const TKey &key) const

TValue &	getWithoutPromotion (const TKey &key)

const_iterator	findWithoutPromotion (const TKey &key) const

iterator	findWithoutPromotion (const TKey &key)

bool	erase (const TKey &key)

void	set (const TKey &key, TValue value, bool promote=true, PruneHookCall pruneHook=nullptr)

std::size_t	size () const

bool	empty () const

void	clear (PruneHookCall pruneHook=nullptr)

void	setPruneHook (PruneHookCall pruneHook)

void	prune (std::size_t pruneSize, PruneHookCall pruneHook=nullptr)

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

const_iterator	cbegin () const

const_iterator	cend () const

reverse_iterator	rbegin ()

reverse_iterator	rend ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	rend () const

const_reverse_iterator	crbegin () const

const_reverse_iterator	crend () const

Private Types
typedef boost::intrusive::link_mode< boost::intrusive::safe_link >	link_mode

typedef boost::intrusive::unordered_set< Node, boost::intrusive::hash< KeyHasher >, boost::intrusive::equal< KeyValueEqual > >	NodeMap

typedef boost::intrusive::list< Node >	NodeList

typedef std::pair< const TKey, TValue >	TPair

Private Member Functions
NodeMap::iterator	findInIndex (const TKey &key)

NodeMap::const_iterator	findInIndex (const TKey &key) const

void	pruneWithFailSafeOption (std::size_t pruneSize, PruneHookCall pruneHook, bool failSafe)

Private Attributes
PruneHookCall	pruneHook_

std::size_t	nIndexBuckets_

std::unique_ptr< typename NodeMap::bucket_type[]>	indexBuckets_

NodeMap::bucket_traits	indexTraits_

THash	keyHash_

TKeyEqual	keyEqual_

NodeMap	index_

NodeList	lru_

std::size_t	maxSize_

std::size_t	clearSize_

Static Private Attributes
static const std::size_t	kMinNumIndexBuckets = 100

Detailed Description

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>
class folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >

A general purpose LRU evicting cache. Designed to support constant time set/get operations. It maintains a doubly linked list of items that are threaded through an index (a hash map). The access ordered is maintained on the list by moving an element to the front of list on a get. New elements are added to the front of the list. The index size is set to half the capacity (setting capacity to 0 is a special case. see notes at the end of this section). So assuming uniform distribution of keys, set/get are both constant time operations.

On reaching capacity limit, clearSize_ LRU items are evicted at a time. If a callback is specified with setPruneHook, it is invoked for each eviction.

This is NOT a thread-safe implementation.

Configurability: capacity of the cache, number of items to evict, eviction callback and the hasher to hash the keys can all be supplied by the caller.

If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure layout is as below. N1 .. N6 is a list threaded through the hash. Assuming, each the number of nodes hashed to each index key is bounded, the following operations run in constant time. i) get computes the index key, walks the list of elements hashed to the key and moves it to the front of the list, if found. ii) set inserts a new node into the list and places the same node on to the list of elements hashing to the corresponding index key. ii) prune deletes nodes from the end of the list as well from the index.

+-—+ +-—+ +-—+ | H1 | <-> | N1 | <-> | N5 | +-—+ +-—+ +-—+ ^ ^ ^ | ___/ \ | / \ |_ /________ ___ / | \ / | \ v v v +-—+ +-—+ +-—+ +-—+ | H2 | <-> | N4 | <-> | N2 | <-> | N6 | +-—+ +-—+ +-—+ +-—+ . ^ ^ . | | . | | . | _____| . | / v v +-—+ +-—+ | Hi | <-> | N3 | +-—+ +-—+

N.B 1 : Changing the capacity with setMaxSize does not change the index size and it could end up in too many elements indexed to the same slot in index. The set/get performance will get worse in this case. So it is best to avoid resizing.

N.B 2 : Setting capacity to 0, using setMaxSize or initialization, turns off evictions based on sizeof the cache making it an INFINITE size cache unless evictions of LRU items are triggered by calling prune() by clients (using their own eviction criteria).

Definition at line 98 of file EvictingCacheMap.h.

Member Typedef Documentation

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef iterator_base<const TPair, typename NodeList::const_iterator> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::const_iterator

Definition at line 135 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef iterator_base<const TPair, typename NodeList::const_reverse_iterator> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::const_reverse_iterator

Definition at line 139 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

using folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::hasher = THash

Definition at line 144 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef iterator_base<TPair, typename NodeList::iterator> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::iterator

Definition at line 133 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

using folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::key_type = TKey

Definition at line 142 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef boost::intrusive::link_mode<boost::intrusive::safe_link> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::link_mode

private

Definition at line 103 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

using folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::mapped_type = TValue

Definition at line 143 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef boost::intrusive::list<Node> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::NodeList

private

Definition at line 110 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef boost::intrusive::unordered_set< Node, boost::intrusive::hash<KeyHasher>, boost::intrusive::equal<KeyValueEqual> > folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::NodeMap

private

Definition at line 109 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef std::function<void(TKey, TValue&&)> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::PruneHookCall

Definition at line 114 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef iterator_base<TPair, typename NodeList::reverse_iterator> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::reverse_iterator

Definition at line 137 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

typedef std::pair<const TKey, TValue> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::TPair

private

Definition at line 111 of file EvictingCacheMap.h.

Constructor & Destructor Documentation

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::EvictingCacheMap	(	std::size_t	maxSize,
		std::size_t	clearSize = `1`,
		const THash &	keyHash = `THash()`,
		const TKeyEqual &	keyEqual = `TKeyEqual()`
	)

inlineexplicit

Construct a EvictingCacheMap

Parameters

maxSize	maximum size of the cache map. Once the map size exceeds maxSize, the map will begin to evict.
clearSize	the number of elements to clear at a time when the eviction size is reached.

Definition at line 153 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::EvictingCacheMap().

       : nIndexBuckets_(std::max(maxSize / 2, std::size_t(kMinNumIndexBuckets))),
         indexBuckets_(new typename NodeMap::bucket_type[nIndexBuckets_]),
         indexTraits_(indexBuckets_.get(), nIndexBuckets_),
         keyHash_(keyHash),
         keyEqual_(keyEqual),
         index_(indexTraits_, keyHash_, keyEqual_),
         maxSize_(maxSize),
         clearSize_(clearSize) {}

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::EvictingCacheMap ( const EvictingCacheMap< TKey, TValue, THash, TKeyEqual > & )

delete

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::EvictingCacheMap ( EvictingCacheMap< TKey, TValue, THash, TKeyEqual > && )

default

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::~EvictingCacheMap ( )

inline

Definition at line 172 of file EvictingCacheMap.h.

                       {
     setPruneHook(nullptr);
     // ignore any potential exceptions from pruneHook_
     pruneWithFailSafeOption(size(), nullptr, true);
   }

Member Function Documentation

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::begin ( )

inline

Definition at line 385 of file EvictingCacheMap.h.

Referenced by TEST().

                    {
     return iterator(lru_.begin());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::begin ( ) const

inline

Definition at line 391 of file EvictingCacheMap.h.

                                {
     return const_iterator(lru_.begin());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::cbegin ( ) const

inline

Definition at line 398 of file EvictingCacheMap.h.

                                 {
     return const_iterator(lru_.cbegin());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::cend ( ) const

inline

Definition at line 401 of file EvictingCacheMap.h.

                               {
     return const_iterator(lru_.cend());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::clear ( PruneHookCall pruneHook = nullptr )

inline

Definition at line 354 of file EvictingCacheMap.h.

Referenced by wangle::LocalSSLSessionCache::~LocalSSLSessionCache().

                                                 {
     prune(size(), pruneHook);
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_reverse_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::crbegin ( ) const

inline

Definition at line 419 of file EvictingCacheMap.h.

                                          {
     return const_reverse_iterator(lru_.crbegin());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_reverse_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::crend ( ) const

inline

Definition at line 422 of file EvictingCacheMap.h.

                                        {
     return const_reverse_iterator(lru_.crend());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

bool folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::empty ( ) const

inline

Typical empty function

Returns: true if empty, false otherwise

Definition at line 350 of file EvictingCacheMap.h.

Referenced by TEST().

                      {
     return index_.empty();
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::end ( )

inline

Definition at line 388 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::find(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::findWithoutPromotion(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::get(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::getWithoutPromotion(), wangle::ShardedLocalSSLSessionCache::lookupSession(), wangle::ShardedLocalSSLSessionCache::storeSession(), and TEST().

                  {
     return iterator(lru_.end());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::end ( ) const

inline

Definition at line 394 of file EvictingCacheMap.h.

                              {
     return const_iterator(lru_.end());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

bool folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::erase ( const TKey & key )

inline

Erase the key-value pair associated with key if it exists.

Parameters

key	key associated with the value

Returns: true if the key existed and was erased, else false

Definition at line 293 of file EvictingCacheMap.h.

Referenced by TEST().

                               {
     auto it = findInIndex(key);
     if (it == index_.end()) {
       return false;
     }
     auto node = &(*it);
     std::unique_ptr<Node> nptr(node);
     lru_.erase(lru_.iterator_to(*node));
     index_.erase(it);
     return true;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

bool folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::exists ( const TKey & key ) const

inline

Check for existence of a specific key in the map. This operation has no effect on LRU order.

Parameters

key	key to search for

Returns: true if exists, false otherwise

Definition at line 215 of file EvictingCacheMap.h.

Referenced by TEST().

                                      {
     return findInIndex(key) != index_.end();
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::find ( const TKey & key )

inline

Get the iterator associated with a specific key. This function always promotes a found value to the head of the LRU.

Parameters

key	key to associate with value

Returns: the iterator of the object (a std::pair of const TKey, TValue) or end() if it does not exist

Definition at line 241 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::get(), and TEST().

                                  {
     auto it = findInIndex(key);
     if (it == index_.end()) {
       return end();
     }
     lru_.erase(lru_.iterator_to(*it));
     lru_.push_front(*it);
     return iterator(lru_.iterator_to(*it));
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

NodeMap::iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::findInIndex ( const TKey & key )

inlineprivate

Get the iterator in in the index associated with a specific key. This is merely a search in the index and does not promote the object.

Parameters

key	key to associate with value

Returns: the NodeMap::iterator to the Node containing the object (a std::pair of const TKey, TValue) or index_.end() if it does not exist

Definition at line 466 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::erase(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::exists(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::find(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::findWithoutPromotion(), and folly::EvictingCacheMap< std::string, SSL_SESSION * >::set().

                                                         {
     return index_.find(key, KeyHasher(keyHash_), KeyValueEqual(keyEqual_));
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

NodeMap::const_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::findInIndex ( const TKey & key ) const

inlineprivate

Definition at line 470 of file EvictingCacheMap.h.

                                                                     {
     return index_.find(key, KeyHasher(keyHash_), KeyValueEqual(keyEqual_));
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::findWithoutPromotion ( const TKey & key ) const

inline

Get the iterator associated with a specific key. This function never promotes a found value to the head of the LRU.

Parameters

key	key to associate with value

Returns: the iterator of the object (a std::pair of const TKey, TValue) or end() if it does not exist

Definition at line 278 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::getWithoutPromotion(), and TEST().

                                                              {
     auto it = findInIndex(key);
     return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::findWithoutPromotion ( const TKey & key )

inline

Definition at line 283 of file EvictingCacheMap.h.

                                                  {
     auto it = findInIndex(key);
     return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

TValue& folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::get ( const TKey & key )

inline

Get the value associated with a specific key. This function always promotes a found value to the head of the LRU.

Parameters

key	key associated with the value

Returns: the value if it exists

Exceptions

std::out_of_range exception of the key does not exist

Definition at line 226 of file EvictingCacheMap.h.

Referenced by TEST().

                                {
     auto it = find(key);
     if (it == end()) {
       throw_exception<std::out_of_range>("Key does not exist");
     }
     return it->second;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

size_t folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::getMaxSize ( ) const

inline

Definition at line 201 of file EvictingCacheMap.h.

                             {
     return maxSize_;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const TValue& folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::getWithoutPromotion ( const TKey & key ) const

inline

Get the value associated with a specific key. This function never promotes a found value to the head of the LRU.

Parameters

key	key associated with the value

Returns: the value if it exists

Exceptions

std::out_of_range exception of the key does not exist

Definition at line 258 of file EvictingCacheMap.h.

Referenced by TEST().

                                                            {
     auto it = findWithoutPromotion(key);
     if (it == end()) {
       throw_exception<std::out_of_range>("Key does not exist");
     }
     return it->second;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

TValue& folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::getWithoutPromotion ( const TKey & key )

inline

Definition at line 266 of file EvictingCacheMap.h.

                                                {
     auto const& cThis = *this;
     return const_cast<TValue&>(cThis.getWithoutPromotion(key));
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

EvictingCacheMap& folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::operator= ( const EvictingCacheMap< TKey, TValue, THash, TKeyEqual > & )

delete

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::EvictingCacheMap().

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

EvictingCacheMap& folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::operator= ( EvictingCacheMap< TKey, TValue, THash, TKeyEqual > && )

default

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::prune	(	std::size_t	pruneSize,
		PruneHookCall	pruneHook = `nullptr`
	)

inline

Prune the minimum of pruneSize and size() from the back of the LRU. Will throw if pruneHook throws.

Parameters

pruneSize	minimum number of elements to prune
pruneHook	a custom pruneHook function

Definition at line 379 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::clear(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::set(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::setMaxSize(), and TEST().

                                                                      {
     // do not swallow exceptions for prunes not triggered from destructor
     pruneWithFailSafeOption(pruneSize, pruneHook, false);
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::pruneWithFailSafeOption	(	std::size_t	pruneSize,
		PruneHookCall	pruneHook,
		bool	failSafe
	)

inlineprivate

Prune the minimum of pruneSize and size() from the back of the LRU.

Parameters

pruneSize	minimum number of elements to prune
pruneHook	a custom pruneHook function
failSafe	true if exceptions are to ignored, false by default

Definition at line 480 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::prune(), and folly::EvictingCacheMap< std::string, SSL_SESSION * >::~EvictingCacheMap().

                      {
     auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
 
     for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
       auto* node = &(*lru_.rbegin());
       std::unique_ptr<Node> nptr(node);
 
       lru_.erase(lru_.iterator_to(*node));
       index_.erase(index_.iterator_to(*node));
       if (ph) {
         try {
           ph(node->pr.first, std::move(node->pr.second));
         } catch (...) {
           if (!failSafe) {
             throw;
           }
         }
       }
     }
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

reverse_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::rbegin ( )

inline

Definition at line 405 of file EvictingCacheMap.h.

Referenced by TEST().

                             {
     return reverse_iterator(lru_.rbegin());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_reverse_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::rbegin ( ) const

inline

Definition at line 412 of file EvictingCacheMap.h.

                                         {
     return const_reverse_iterator(lru_.rbegin());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

reverse_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::rend ( )

inline

Definition at line 408 of file EvictingCacheMap.h.

Referenced by TEST().

                           {
     return reverse_iterator(lru_.rend());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const_reverse_iterator folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::rend ( ) const

inline

Definition at line 415 of file EvictingCacheMap.h.

                                       {
     return const_reverse_iterator(lru_.rend());
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::set	(	const TKey &	key,
		TValue	value,
		bool	promote = `true`,
		PruneHookCall	pruneHook = `nullptr`
	)

inline

Set a key-value pair in the dictionary

Parameters

key	key to associate with value
value	value to associate with the key
promote	boolean flag indicating whether or not to move something to the front of an LRU. This only really matters if you're setting a value that already exists.
pruneHook	callback to use on eviction (if it occurs).

Definition at line 314 of file EvictingCacheMap.h.

Referenced by TEST().

                                          {
     auto it = findInIndex(key);
     if (it != index_.end()) {
       it->pr.second = std::move(value);
       if (promote) {
         lru_.erase(lru_.iterator_to(*it));
         lru_.push_front(*it);
       }
     } else {
       auto node = new Node(key, std::move(value));
       index_.insert(*node);
       lru_.push_front(*node);
 
       // no evictions if maxSize_ is 0 i.e. unlimited capacity
       if (maxSize_ > 0 && size() > maxSize_) {
         prune(clearSize_, pruneHook);
       }
     }
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::setClearSize ( size_t clearSize )

inline

Definition at line 205 of file EvictingCacheMap.h.

Referenced by TEST().

                                       {
     clearSize_ = clearSize;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::setMaxSize	(	size_t	maxSize,
		PruneHookCall	pruneHook = `nullptr`
	)

inline

Adjust the max size of EvictingCacheMap. Note that this does not update nIndexBuckets_ accordingly. This API can cause performance to get very bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.

Calling this function with an arugment of 0 removes the limit on the cache size and elements are not evicted unless clients explictly call prune.

If you intend to resize dynamically using this, then picking an index size that works well and initializing with corresponding maxSize is the only reasonable option.

Parameters

maxSize	new maximum size of the cache map.
pruneHook	callback to use on eviction.

Definition at line 193 of file EvictingCacheMap.h.

Referenced by TEST().

                                                                      {
     if (maxSize != 0 && maxSize < size()) {
       // Prune the excess elements with our new constraints.
       prune(std::max(size() - maxSize, clearSize_), pruneHook);
     }
     maxSize_ = maxSize;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

void folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::setPruneHook ( PruneHookCall pruneHook )

inline

Set the prune hook, which is the function invoked on the key and value on each eviction. Will throw If the pruneHook throws, unless the EvictingCacheMap object is being destroyed in which case it will be ignored.

Parameters

pruneHook	new callback to use on eviction.
promote	boolean flag indicating whether or not to move something to the front of an LRU.

Returns: the iterator of the object (a std::pair of const TKey, TValue) or end() if it does not exist

Definition at line 369 of file EvictingCacheMap.h.

Referenced by wangle::LocalSSLSessionCache::LocalSSLSessionCache(), TEST(), and folly::EvictingCacheMap< std::string, SSL_SESSION * >::~EvictingCacheMap().

                                              {
     pruneHook_ = pruneHook;
   }

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

std::size_t folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::size ( ) const

inline

Get the number of elements in the dictionary

Returns: the size of the dictionary

Definition at line 342 of file EvictingCacheMap.h.

                          {
     return index_.size();
   }

Member Data Documentation

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

std::size_t folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::clearSize_

private

Definition at line 514 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::set(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::setClearSize(), and folly::EvictingCacheMap< std::string, SSL_SESSION * >::setMaxSize().

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

NodeMap folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::index_

private

Definition at line 511 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

std::unique_ptr<typename NodeMap::bucket_type[]> folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::indexBuckets_

private

Definition at line 507 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

NodeMap::bucket_traits folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::indexTraits_

private

Definition at line 508 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

TKeyEqual folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::keyEqual_

private

Definition at line 510 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::findInIndex().

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

THash folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::keyHash_

private

Definition at line 509 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::findInIndex().

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

const std::size_t folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::kMinNumIndexBuckets = 100

staticprivate

Definition at line 504 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

NodeList folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::lru_

private

Definition at line 512 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

std::size_t folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::maxSize_

private

Definition at line 513 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::getMaxSize(), folly::EvictingCacheMap< std::string, SSL_SESSION * >::set(), and folly::EvictingCacheMap< std::string, SSL_SESSION * >::setMaxSize().

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

std::size_t folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::nIndexBuckets_

private

Definition at line 506 of file EvictingCacheMap.h.

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>

PruneHookCall folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >::pruneHook_

private

Definition at line 505 of file EvictingCacheMap.h.

Referenced by folly::EvictingCacheMap< std::string, SSL_SESSION * >::pruneWithFailSafeOption(), and folly::EvictingCacheMap< std::string, SSL_SESSION * >::setPruneHook().

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

proxygen/folly/folly/container/EvictingCacheMap.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>> class folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class TKey, class TValue, class THash = std::hash<TKey>, class TKeyEqual = std::equal_to<TKey>>
class folly::EvictingCacheMap< TKey, TValue, THash, TKeyEqual >