1 #ifndef GENESIS_UTILS_CONTAINERS_MRU_CACHE_H_
2 #define GENESIS_UTILS_CONTAINERS_MRU_CACHE_H_
39 #include <unordered_map>
99 template<
typename Key,
typename T >
112 using iterator =
typename std::list< value_type >::iterator;
160 return cache_.begin();
168 return cache_.cbegin();
186 return cache_.cend();
194 return cache_.cbegin();
202 return cache_.cend();
214 assert( lookup_.size() == cache_.size() );
215 return lookup_.size();
225 assert( capacity_ == 0 || lookup_.size() <= capacity_ );
234 return lookup_.empty();
266 auto const lit = lookup_.find( key );
269 if( lit != lookup_.end() ) {
270 return promote_and_get_( lit->second );
276 assert( lookup_.count( key ) == 0 );
278 lookup_[ key ] = cache_.begin();
279 assert( cache_.size() == lookup_.size() );
285 assert( ! cache_.empty() );
286 return cache_.begin()->second;
332 std::lock_guard<std::mutex> lock( mutex_ );
335 auto const lit = lookup_.find( key );
338 if( lit != lookup_.end() ) {
340 return promote_and_get_( lit->second );
346 std::list< value_type > tmp_list;
352 std::lock_guard<std::mutex> lock( mutex_ );
355 auto const lit = lookup_.find( key );
359 if( lit != lookup_.end() ) {
361 return promote_and_get_( lit->second );
367 assert( lookup_.count( key ) == 0 );
368 assert( tmp_list.size() == 1 );
369 cache_.splice( cache_.begin(), tmp_list, tmp_list.begin() );
370 lookup_[ key ] = cache_.begin();
371 assert( cache_.size() == lookup_.size() );
377 assert( ! cache_.empty() );
378 return cache_.begin()->second;
389 return lookup_.count( key ) > 0;
422 std::lock_guard<std::mutex> lock( mutex_ );
426 assert( capacity_ == 0 ||
size() <= capacity_ );
435 std::lock_guard<std::mutex> lock( mutex_ );
438 for(
auto& elem : cache_ ) {
458 if( capacity_ == 0 ) {
463 while(
size() > capacity_ ) {
466 assert( lookup_.size() == cache_.size() );
469 assert( cache_.size() > 1 );
471 auto& last = cache_.back();
475 lookup_.erase( last.first );
480 assert( lookup_.size() == cache_.size() );
481 assert( lookup_.size() <=
capacity() );
492 assert( ! cache_.empty() );
495 if( cache_it != cache_.begin() ) {
496 cache_.splice( cache_.begin(), cache_, cache_it );
500 return cache_it->second;
542 std::list< value_type > cache_;
550 std::unordered_map< key_type, iterator > lookup_;
562 #endif // include guard