A toolkit for working with phylogenetic data.
v0.24.0
mru_cache.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_CONTAINERS_MRU_CACHE_H_
2 #define GENESIS_UTILS_CONTAINERS_MRU_CACHE_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2020 Lucas Czech and HITS gGmbH
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
34 #include <cassert>
35 #include <functional>
36 #include <list>
37 #include <mutex>
38 #include <stdexcept>
39 #include <unordered_map>
40 #include <utility>
41 
42 namespace genesis {
43 namespace utils {
44 
45 // =================================================================================================
46 // MRU Cache
47 // =================================================================================================
48 
99 template< typename Key, typename T >
100 class MruCache
101 {
102 public:
103 
104  // -------------------------------------------------------------------------
105  // Member Types
106  // -------------------------------------------------------------------------
107 
108  using key_type = Key;
109  using mapped_type = T;
110  using value_type = std::pair<const key_type, mapped_type>;
111 
112  using iterator = typename std::list< value_type >::iterator;
113  using const_iterator = typename std::list< value_type >::const_iterator;
114 
115  using size_type = size_t;
116 
117  // -------------------------------------------------------------------------
118  // Constructor and Rule of Five
119  // -------------------------------------------------------------------------
120 
127  MruCache() = default;
128 
135  explicit MruCache( size_t capacity )
136  : capacity_( capacity )
137  {}
138 
140  {
141  // Need to call the release_function. Make it easy, just call clear.
142  clear();
143  }
144 
145  MruCache( MruCache const& ) = default;
146  MruCache( MruCache&& ) = default;
147 
148  MruCache& operator= ( MruCache const& ) = default;
149  MruCache& operator= ( MruCache&& ) = default;
150 
151  // -------------------------------------------------------------------------
152  // Iterators
153  // -------------------------------------------------------------------------
154 
159  {
160  return cache_.begin();
161  }
162 
167  {
168  return cache_.cbegin();
169  }
170 
176  {
177  return cache_.end();
178  }
179 
185  {
186  return cache_.cend();
187  }
188 
193  {
194  return cache_.cbegin();
195  }
196 
201  {
202  return cache_.cend();
203  }
204 
205  // -------------------------------------------------------------------------
206  // Properties
207  // -------------------------------------------------------------------------
208 
212  size_type size() const
213  {
214  assert( lookup_.size() == cache_.size() );
215  return lookup_.size();
216  }
217 
224  {
225  assert( capacity_ == 0 || lookup_.size() <= capacity_ );
226  return capacity_;
227  }
228 
232  bool empty() const
233  {
234  return lookup_.empty();
235  }
236 
237  // -------------------------------------------------------------------------
238  // Element Access
239  // -------------------------------------------------------------------------
240 
263  mapped_type& fetch( key_type const& key )
264  {
265  // Use the lookup map to check whether the element is in the cache.
266  auto const lit = lookup_.find( key );
267 
268  // Found it! Move it to the front and return its mapped element.
269  if( lit != lookup_.end() ) {
270  return promote_and_get_( lit->second );
271  }
272 
273  // If we are here, the element was not found.
274  // Add the element to the cache and lookup. Throws if the load function is empty.
275  // Also, if loading fails with an exception, nothing happens to the container.
276  assert( lookup_.count( key ) == 0 );
277  cache_.push_front({ key, load_function( key ) });
278  lookup_[ key ] = cache_.begin();
279  assert( cache_.size() == lookup_.size() );
280 
281  // Make sure that we stay within capacity.
282  shrink_();
283 
284  // Finally, return the element.
285  assert( ! cache_.empty() );
286  return cache_.begin()->second;
287  }
288 
328  {
329  // First, check if the elemt is there. If so, simply return it.
330  {
331  // Lock access to everything.
332  std::lock_guard<std::mutex> lock( mutex_ );
333 
334  // Use the lookup map to check whether the element is in the cache.
335  auto const lit = lookup_.find( key );
336 
337  // Found it! Move it to the front and return its mapped element.
338  if( lit != lookup_.end() ) {
339  // LOG_DBG << "Found.";
340  return promote_and_get_( lit->second );
341  }
342  }
343 
344  // If we are here, the element is not in the cache. Load it into a dummy list,
345  // without locking, so that loading can happen in parallel.
346  std::list< value_type > tmp_list;
347  tmp_list.push_front({ key, load_function( key ) });
348 
349  // Now, store it if needed.
350  {
351  // Lock access to everything.
352  std::lock_guard<std::mutex> lock( mutex_ );
353 
354  // Check whether the element was put into the cache in the meantime (by another thread).
355  auto const lit = lookup_.find( key );
356 
357  // Found it! Move it to the front and return its mapped element.
358  // In that case, we do not use tmp_list, but discard the element in there.
359  if( lit != lookup_.end() ) {
360  // LOG_DBG << "Wasted.";
361  return promote_and_get_( lit->second );
362  }
363  // LOG_DBG << "Loaded.";
364 
365  // If we are here, the element was not found.
366  // Add the element to the cache and lookup.
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() );
372 
373  // Make sure that we stay within capacity.
374  shrink_();
375 
376  // Finally, return the element.
377  assert( ! cache_.empty() );
378  return cache_.begin()->second;
379  }
380  }
381 
387  bool contains( key_type const& key )
388  {
389  return lookup_.count( key ) > 0;
390  }
391 
403  void touch( key_type const& key )
404  {
405  (void) fetch_copy( key );
406  }
407 
408  // -------------------------------------------------------------------------
409  // Modifiers
410  // -------------------------------------------------------------------------
411 
417  void capacity( size_t value )
418  {
419  // Lock access to everything. It would be a weird use case where this function is called
420  // while also fetching copies of elements in a different thread, but still,
421  // we need to protect this.
422  std::lock_guard<std::mutex> lock( mutex_ );
423 
424  capacity_ = value;
425  shrink_();
426  assert( capacity_ == 0 || size() <= capacity_ );
427  }
428 
432  void clear()
433  {
434  // Lock access to everything.
435  std::lock_guard<std::mutex> lock( mutex_ );
436 
437  if( release_function ) {
438  for( auto& elem : cache_ ) {
439  release_function( elem.first, elem.second );
440  }
441  }
442  cache_.clear();
443  lookup_.clear();
444  }
445 
446  // -------------------------------------------------------------------------
447  // Implementation Functions
448  // -------------------------------------------------------------------------
449 
450 private:
451 
455  void shrink_()
456  {
457  // Capacity/target size of 0 means limitless. No shrinking.
458  if( capacity_ == 0 ) {
459  return;
460  }
461 
462  // Remove last elements from cache and lookup if needed.
463  while( size() > capacity_ ) {
464 
465  // This needs to be maintained.
466  assert( lookup_.size() == cache_.size() );
467 
468  // If we are here, size > capacity > 0. Hence, size > 1.
469  assert( cache_.size() > 1 );
470 
471  auto& last = cache_.back();
472  if( release_function ) {
473  release_function( last.first, last.second );
474  }
475  lookup_.erase( last.first );
476  cache_.pop_back();
477  }
478 
479  // Check invariant and result.
480  assert( lookup_.size() == cache_.size() );
481  assert( lookup_.size() <= capacity() );
482  }
483 
488  mapped_type& promote_and_get_( iterator const& cache_it )
489  {
490  // The function is internally called only if we found an iterator.
491  // This can of course only happen if there are elements in the cache.
492  assert( ! cache_.empty() );
493 
494  // Only move if it is not already at the front.
495  if( cache_it != cache_.begin() ) {
496  cache_.splice( cache_.begin(), cache_, cache_it );
497  }
498 
499  // Return the element.
500  return cache_it->second;
501  }
502 
503  // -------------------------------------------------------------------------
504  // Data Members
505  // -------------------------------------------------------------------------
506 
507 public:
508 
515  std::function< mapped_type( key_type const& )> load_function;
516 
525  std::function< void( key_type const&, mapped_type& )> release_function;
526 
527 private:
528 
535  size_type capacity_ = 0;
536 
542  std::list< value_type > cache_;
543 
550  std::unordered_map< key_type, iterator > lookup_;
551 
555  std::mutex mutex_;
556 
557 };
558 
559 } // namespace utils
560 } // namespace genesis
561 
562 #endif // include guard
bool empty() const
Return whether the cache is currently empty, that is, has no elements loaded.
Definition: mru_cache.hpp:232
MruCache(size_t capacity)
Construct a cache with a given capacity.
Definition: mru_cache.hpp:135
mapped_type fetch_copy(key_type const &key)
Get an element by copy.
Definition: mru_cache.hpp:327
MruCache()=default
Default constructor. Uses a capacity() of 0, that is, limitless.
void capacity(size_t value)
Set the capacity of the cache, i.e., its maximal size.
Definition: mru_cache.hpp:417
const_iterator cend()
Get a const iterator to past-the-end of the cache, that is, one element after the least recently used...
Definition: mru_cache.hpp:200
bool contains(key_type const &key)
Return whether an element is currently in the cache.
Definition: mru_cache.hpp:387
Container namespace for all symbols of genesis in order to keep them separate when used as a library...
size_type capacity() const
Return the currently set capacity of the cache, i.e., its maximal size.
Definition: mru_cache.hpp:223
Most Recently Used Cache.
Definition: mru_cache.hpp:100
typename std::list< value_type >::iterator iterator
Definition: mru_cache.hpp:112
const_iterator cbegin()
Get a const iterator to the begin of the cache, that is, the most recently used element.
Definition: mru_cache.hpp:192
void touch(key_type const &key)
Bring an element to the front, and load it if needed.
Definition: mru_cache.hpp:403
const_iterator begin() const
Get a const iterator to the begin of the cache, that is, the most recently used element.
Definition: mru_cache.hpp:166
iterator begin()
Get an iterator to the begin of the cache, that is, the most recently used element.
Definition: mru_cache.hpp:158
mapped_type & fetch(key_type const &key)
Get an element.
Definition: mru_cache.hpp:263
size_type size() const
Get the current count of elements being loaded in the cache.
Definition: mru_cache.hpp:212
MruCache & operator=(MruCache const &)=default
iterator end()
Get an iterator to past-the-end of the cache, that is, one element after the least recently used one...
Definition: mru_cache.hpp:175
std::function< void(key_type const &, mapped_type &)> release_function
Function to be called when an element is removed from the cache.
Definition: mru_cache.hpp:525
void clear()
Clear the cache.
Definition: mru_cache.hpp:432
const_iterator end() const
Get a const iterator to past-the-end of the cache, that is, one element after the least recently used...
Definition: mru_cache.hpp:184
std::pair< const key_type, mapped_type > value_type
Definition: mru_cache.hpp:110
typename std::list< value_type >::const_iterator const_iterator
Definition: mru_cache.hpp:113
std::function< mapped_type(key_type const &)> load_function
Function to load an element into the cache if it is being fetched but not there yet.
Definition: mru_cache.hpp:515