mru_cache.hpp

Go to the documentation of this file.

#ifndef GENESIS_UTILS_CONTAINERS_MRU_CACHE_H_
#define GENESIS_UTILS_CONTAINERS_MRU_CACHE_H_

/*
    Genesis - A toolkit for working with phylogenetic data.
    Copyright (C) 2014-2020 Lucas Czech and HITS gGmbH

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

    Contact:
    Lucas Czech <lucas.czech@h-its.org>
    Exelixis Lab, Heidelberg Institute for Theoretical Studies
    Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
*/

#include <cassert>
#include <functional>
#include <list>
#include <mutex>
#include <stdexcept>
#include <unordered_map>
#include <utility>

namespace genesis {
namespace utils {

// =================================================================================================
//     MRU Cache
// =================================================================================================

template< typename Key, typename T >
class MruCache
{
public:

    // -------------------------------------------------------------------------
    //     Member Types
    // -------------------------------------------------------------------------

    using key_type        = Key;
    using mapped_type     = T;
    using value_type      = std::pair<const key_type, mapped_type>;

    using       iterator  = typename std::list< value_type >::iterator;
    using const_iterator  = typename std::list< value_type >::const_iterator;

    using size_type       = size_t;

    // -------------------------------------------------------------------------
    //     Constructor and Rule of Five
    // -------------------------------------------------------------------------

    MruCache() = default;

    explicit MruCache( size_t capacity )
        : capacity_( capacity )
    {}

    ~MruCache()
    {
        // Need to call the release_function. Make it easy, just call clear.
        clear();
    }

    MruCache( MruCache const& ) = default;
    MruCache( MruCache&& )      = default;

    MruCache& operator= ( MruCache const& ) = default;
    MruCache& operator= ( MruCache&& )      = default;

    // -------------------------------------------------------------------------
    //     Iterators
    // -------------------------------------------------------------------------

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

    const_iterator begin() const
    {
        return cache_.cbegin();
    }

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

    const_iterator end() const
    {
        return cache_.cend();
    }

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

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

    // -------------------------------------------------------------------------
    //     Properties
    // -------------------------------------------------------------------------

    size_type size() const
    {
        assert( lookup_.size() == cache_.size() );
        return lookup_.size();
    }

    size_type capacity() const
    {
        assert( capacity_ == 0 || lookup_.size() <= capacity_ );
        return capacity_;
    }

    bool empty() const
    {
        return lookup_.empty();
    }

    // -------------------------------------------------------------------------
    //     Element Access
    // -------------------------------------------------------------------------

    mapped_type& fetch( key_type const& key )
    {
        // Use the lookup map to check whether the element is in the cache.
        auto const lit = lookup_.find( key );

        // Found it! Move it to the front and return its mapped element.
        if( lit != lookup_.end() ) {
            return promote_and_get_( lit->second );
        }

        // If we are here, the element was not found.
        // Add the element to the cache and lookup. Throws if the load function is empty.
        // Also, if loading fails with an exception, nothing happens to the container.
        assert( lookup_.count( key ) == 0 );
        cache_.push_front({ key, load_function( key ) });
        lookup_[ key ] = cache_.begin();
        assert( cache_.size() == lookup_.size() );

        // Make sure that we stay within capacity.
        shrink_();

        // Finally, return the element.
        assert( ! cache_.empty() );
        return cache_.begin()->second;
    }

    mapped_type fetch_copy( key_type const& key )
    {
        // First, check if the elemt is there. If so, simply return it.
        {
            // Lock access to everything.
            std::lock_guard<std::mutex> lock( mutex_ );

            // Use the lookup map to check whether the element is in the cache.
            auto const lit = lookup_.find( key );

            // Found it! Move it to the front and return its mapped element.
            if( lit != lookup_.end() ) {
                // LOG_DBG << "Found.";
                return promote_and_get_( lit->second );
            }
        }

        // If we are here, the element is not in the cache. Load it into a dummy list,
        // without locking, so that loading can happen in parallel.
        std::list< value_type > tmp_list;
        tmp_list.push_front({ key, load_function( key ) });

        // Now, store it if needed.
        {
            // Lock access to everything.
            std::lock_guard<std::mutex> lock( mutex_ );

            // Check whether the element was put into the cache in the meantime (by another thread).
            auto const lit = lookup_.find( key );

            // Found it! Move it to the front and return its mapped element.
            // In that case, we do not use tmp_list, but discard the element in there.
            if( lit != lookup_.end() ) {
                // LOG_DBG << "Wasted.";
                return promote_and_get_( lit->second );
            }
            // LOG_DBG << "Loaded.";

            // If we are here, the element was not found.
            // Add the element to the cache and lookup.
            assert( lookup_.count( key ) == 0 );
            assert( tmp_list.size() == 1 );
            cache_.splice( cache_.begin(), tmp_list, tmp_list.begin() );
            lookup_[ key ] = cache_.begin();
            assert( cache_.size() == lookup_.size() );

            // Make sure that we stay within capacity.
            shrink_();

            // Finally, return the element.
            assert( ! cache_.empty() );
            return cache_.begin()->second;
        }
    }

    bool contains( key_type const& key )
    {
        return lookup_.count( key ) > 0;
    }

    void touch( key_type const& key )
    {
        (void) fetch_copy( key );
    }

    // -------------------------------------------------------------------------
    //     Modifiers
    // -------------------------------------------------------------------------

    void capacity( size_t value )
    {
        // Lock access to everything. It would be a weird use case where this function is called
        // while also fetching copies of elements in a different thread, but still,
        // we need to protect this.
        std::lock_guard<std::mutex> lock( mutex_ );

        capacity_ = value;
        shrink_();
        assert( capacity_ == 0 || size() <= capacity_ );
    }

    void clear()
    {
        // Lock access to everything.
        std::lock_guard<std::mutex> lock( mutex_ );

        if( release_function ) {
            for( auto& elem : cache_ ) {
                release_function( elem.first, elem.second );
            }
        }
        cache_.clear();
        lookup_.clear();
    }

    // -------------------------------------------------------------------------
    //     Implementation Functions
    // -------------------------------------------------------------------------

private:

    void shrink_()
    {
        // Capacity/target size of 0 means limitless. No shrinking.
        if( capacity_ == 0 ) {
            return;
        }

        // Remove last elements from cache and lookup if needed.
        while( size() > capacity_ ) {

            // This needs to be maintained.
            assert( lookup_.size() == cache_.size() );

            // If we are here, size > capacity > 0. Hence, size > 1.
            assert( cache_.size() > 1 );

            auto& last = cache_.back();
            if( release_function ) {
                release_function( last.first, last.second );
            }
            lookup_.erase( last.first );
            cache_.pop_back();
        }

        // Check invariant and result.
        assert( lookup_.size() == cache_.size() );
        assert( lookup_.size() <= capacity() );
    }

    mapped_type& promote_and_get_( iterator const& cache_it )
    {
        // The function is internally called only if we found an iterator.
        // This can of course only happen if there are elements in the cache.
        assert( ! cache_.empty() );

        // Only move if it is not already at the front.
        if( cache_it != cache_.begin() ) {
            cache_.splice( cache_.begin(), cache_, cache_it );
        }

        // Return the element.
        return cache_it->second;
    }

    // -------------------------------------------------------------------------
    //     Data Members
    // -------------------------------------------------------------------------

public:

    std::function< mapped_type( key_type const& )> load_function;

    std::function< void( key_type const&, mapped_type& )> release_function;

private:

    size_type capacity_ = 0;

    std::list< value_type > cache_;

    std::unordered_map< key_type, iterator > lookup_;

    std::mutex mutex_;

};

} // namespace utils
} // namespace genesis

#endif // include guard