A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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-2018 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 
95 template< typename Key, typename T >
96 class MruCache
97 {
98 public:
99 
100  // -------------------------------------------------------------------------
101  // Member Types
102  // -------------------------------------------------------------------------
103 
104  using key_type = Key;
105  using mapped_type = T;
106  using value_type = std::pair<const key_type, mapped_type>;
107 
108  using iterator = typename std::list< value_type >::iterator;
109  using const_iterator = typename std::list< value_type >::const_iterator;
110 
111  using size_type = size_t;
112 
113  // -------------------------------------------------------------------------
114  // Constructor and Rule of Five
115  // -------------------------------------------------------------------------
116 
123  MruCache() = default;
124 
131  MruCache( size_t capacity )
132  : capacity_( capacity )
133  {}
134 
136  {
137  // Need to call the release_function. Make it easy, just call clear.
138  clear();
139  }
140 
141  MruCache( MruCache const& ) = default;
142  MruCache( MruCache&& ) = default;
143 
144  MruCache& operator= ( MruCache const& ) = default;
145  MruCache& operator= ( MruCache&& ) = default;
146 
147  // -------------------------------------------------------------------------
148  // Iterators
149  // -------------------------------------------------------------------------
150 
155  {
156  return cache_.begin();
157  }
158 
163  {
164  return cache_.cbegin();
165  }
166 
172  {
173  return cache_.end();
174  }
175 
181  {
182  return cache_.cend();
183  }
184 
189  {
190  return cache_.cbegin();
191  }
192 
197  {
198  return cache_.cend();
199  }
200 
201  // -------------------------------------------------------------------------
202  // Properties
203  // -------------------------------------------------------------------------
204 
208  size_type size() const
209  {
210  assert( lookup_.size() == cache_.size() );
211  return lookup_.size();
212  }
213 
220  {
221  assert( capacity_ == 0 || lookup_.size() <= capacity_ );
222  return capacity_;
223  }
224 
228  bool empty() const
229  {
230  return lookup_.empty();
231  }
232 
233  // -------------------------------------------------------------------------
234  // Element Access
235  // -------------------------------------------------------------------------
236 
259  mapped_type& fetch( key_type const& key )
260  {
261  // Use the lookup map to check whether the element is in the cache.
262  auto const lit = lookup_.find( key );
263 
264  // Found it! Move it to the front and return its mapped element.
265  if( lit != lookup_.end() ) {
266  return promote_and_get_( lit->second );
267  }
268 
269  // If we are here, the element was not found.
270  // Add the element to the cache and lookup. Throws if the load function is empty.
271  // Also, if loading fails with an exception, nothing happens to the container.
272  assert( lookup_.count( key ) == 0 );
273  cache_.push_front({ key, load_function( key ) });
274  lookup_[ key ] = cache_.begin();
275  assert( cache_.size() == lookup_.size() );
276 
277  // Make sure that we stay within capacity.
278  shrink_();
279 
280  // Finally, return the element.
281  assert( cache_.size() > 0 );
282  return cache_.begin()->second;
283  }
284 
324  {
325  // First, check if the elemt is there. If so, simply return it.
326  {
327  // Lock access to everything.
328  std::lock_guard<std::mutex> lock( mutex_ );
329 
330  // Use the lookup map to check whether the element is in the cache.
331  auto const lit = lookup_.find( key );
332 
333  // Found it! Move it to the front and return its mapped element.
334  if( lit != lookup_.end() ) {
335  // LOG_DBG << "Found.";
336  return promote_and_get_( lit->second );
337  }
338  }
339 
340  // If we are here, the element is not in the cache. Load it into a dummy list,
341  // without locking, so that loading can happen in parallel.
342  std::list< value_type > tmp_list;
343  tmp_list.push_front({ key, load_function( key ) });
344 
345  // Now, store it if needed.
346  {
347  // Lock access to everything.
348  std::lock_guard<std::mutex> lock( mutex_ );
349 
350  // Check whether the element was put into the cache in the meantime (by another thread).
351  auto const lit = lookup_.find( key );
352 
353  // Found it! Move it to the front and return its mapped element.
354  // In that case, we do not use tmp_list, but discard the element in there.
355  if( lit != lookup_.end() ) {
356  // LOG_DBG << "Wasted.";
357  return promote_and_get_( lit->second );
358  }
359  // LOG_DBG << "Loaded.";
360 
361  // If we are here, the element was not found.
362  // Add the element to the cache and lookup.
363  assert( lookup_.count( key ) == 0 );
364  assert( tmp_list.size() == 1 );
365  cache_.splice( cache_.begin(), tmp_list, tmp_list.begin() );
366  lookup_[ key ] = cache_.begin();
367  assert( cache_.size() == lookup_.size() );
368 
369  // Make sure that we stay within capacity.
370  shrink_();
371 
372  // Finally, return the element.
373  assert( cache_.size() > 0 );
374  return cache_.begin()->second;
375  }
376  }
377 
383  bool contains( key_type const& key )
384  {
385  return lookup_.count( key ) > 0;
386  }
387 
399  void touch( key_type const& key )
400  {
401  (void) fetch_copy( key );
402  }
403 
404  // -------------------------------------------------------------------------
405  // Modifiers
406  // -------------------------------------------------------------------------
407 
413  void capacity( size_t value )
414  {
415  // Lock access to everything. It would be a weird use case where this function is called
416  // while also fetching copies of elements in a different thread, but still,
417  // we need do protect this.
418  std::lock_guard<std::mutex> lock( mutex_ );
419 
420  capacity_ = value;
421  shrink_();
422  assert( capacity_ == 0 || size() <= capacity_ );
423  }
424 
428  void clear()
429  {
430  // Lock access to everything.
431  std::lock_guard<std::mutex> lock( mutex_ );
432 
433  if( release_function ) {
434  for( auto& elem : cache_ ) {
435  release_function( elem.first, elem.second );
436  }
437  }
438  cache_.clear();
439  lookup_.clear();
440  }
441 
442  // -------------------------------------------------------------------------
443  // Implementation Functions
444  // -------------------------------------------------------------------------
445 
446 private:
447 
451  void shrink_()
452  {
453  // Capacity/target size of 0 means limitless. No shrinking.
454  if( capacity_ == 0 ) {
455  return;
456  }
457 
458  // Remove last elements from cache and lookup if needed.
459  while( size() > capacity_ ) {
460 
461  // This needs to be maintained.
462  assert( lookup_.size() == cache_.size() );
463 
464  // If we are here, size > capacity_ > 0
465  assert( cache_.size() > 1 );
466 
467  auto& last = cache_.back();
468  if( release_function ) {
469  release_function( last.first, last.second );
470  }
471  lookup_.erase( last.first );
472  cache_.pop_back();
473  }
474 
475  // Check invariant and result.
476  assert( lookup_.size() == cache_.size() );
477  assert( lookup_.size() <= capacity() );
478  }
479 
484  mapped_type& promote_and_get_( iterator const& cache_it )
485  {
486  assert( cache_.size() > 0 );
487 
488  // Only move if it is not already at the front.
489  if( cache_it != cache_.begin() ) {
490  cache_.splice( cache_.begin(), cache_, cache_it );
491  }
492 
493  // Return the element.
494  return cache_it->second;
495  }
496 
497  // -------------------------------------------------------------------------
498  // Data Members
499  // -------------------------------------------------------------------------
500 
501 public:
502 
509  std::function< mapped_type( key_type const& )> load_function;
510 
519  std::function< void( key_type const&, mapped_type& )> release_function;
520 
521 private:
522 
529  size_type capacity_ = 0;
530 
536  std::list< value_type > cache_;
537 
544  std::unordered_map< key_type, iterator > lookup_;
545 
549  std::mutex mutex_;
550 
551 };
552 
553 } // namespace utils
554 } // namespace genesis
555 
556 #endif // include guard
MruCache(size_t capacity)
Construct a cache with a given capacity.
Definition: mru_cache.hpp:131
mapped_type fetch_copy(key_type const &key)
Get an element by copy.
Definition: mru_cache.hpp:323
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:413
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:196
bool contains(key_type const &key)
Return whether an element is currently in the cache.
Definition: mru_cache.hpp:383
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:162
size_type size() const
Get the current count of elements being loaded in the cache.
Definition: mru_cache.hpp:208
Most Recently Used Cache.
Definition: mru_cache.hpp:96
typename std::list< value_type >::iterator iterator
Definition: mru_cache.hpp:108
const_iterator cbegin()
Get a const iterator to the begin of the cache, that is, the most recently used element.
Definition: mru_cache.hpp:188
void touch(key_type const &key)
Bring an element to the front, and load it if needed.
Definition: mru_cache.hpp:399
bool empty() const
Return whether the cache is currently empty, that is, has no elements loaded.
Definition: mru_cache.hpp:228
iterator begin()
Get an iterator to the begin of the cache, that is, the most recently used element.
Definition: mru_cache.hpp:154
mapped_type & fetch(key_type const &key)
Get an element.
Definition: mru_cache.hpp:259
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:171
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:519
void clear()
Clear the cache.
Definition: mru_cache.hpp:428
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:180
std::pair< const key_type, mapped_type > value_type
Definition: mru_cache.hpp:106
size_type capacity() const
Return the currently set capacity of the cache, i.e., its maximal size.
Definition: mru_cache.hpp:219
typename std::list< value_type >::const_iterator const_iterator
Definition: mru_cache.hpp:109
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:509