Cache.h

Go to the documentation of this file.

/*
 * LSST Data Management System
 * See COPYRIGHT file at the top of the source tree.
 *
 * This product includes software developed by the
 * LSST Project (http://www.lsst.org/).
 *
 * 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 LSST License Statement and
 * the GNU General Public License along with this program.  If not,
 * see <http://www.lsstcorp.org/LegalNotices/>.
 */
#ifndef LSST_UTILS_CACHE_H
#define LSST_UTILS_CACHE_H

#include <vector>
#include <utility>  // std::pair

#include "boost/multi_index_container.hpp"
#include "boost/multi_index/sequenced_index.hpp"
#include "boost/multi_index/hashed_index.hpp"
#include "boost/multi_index/composite_key.hpp"
#include "boost/multi_index/member.hpp"
#include "boost/format.hpp"

#include "lsst/pex/exceptions.h"
#include "lsst/utils/CacheFwd.h"

//#define LSST_CACHE_DEBUG 1  // Define this variable to instrument for debugging


#ifdef LSST_CACHE_DEBUG
#include <iostream>
#include <fstream>
#include <typeinfo>
#include "lsst/utils/Demangle.h"
#endif

namespace lsst {
namespace utils {

template <typename Key, typename Value, typename KeyHash, typename KeyPred>
class Cache {
  public:
    Cache(std::size_t maxElements=0) : _maxElements(maxElements) {
        _container.template get<Hash>().reserve(maxElements);
#ifdef LSST_CACHE_DEBUG
        _debuggingEnabled = false;
        _hits = 0;
        _total = 0;
        _requests.reserve(maxElements);
#endif
    }

    // Defaulted stuff
    Cache(Cache const &) = default;
    Cache(Cache &&) = default;
    Cache & operator=(Cache const &) = default;
    Cache & operator=(Cache &&) = default;

#ifdef LSST_CACHE_DEBUG
    ~Cache();
#else
    ~Cache() = default;
#endif

    template <typename Generator>
    Value operator()(Key const& key, Generator func);

    /* Lookup a value
     *
     * If the key is in the cache, it will be promoted to the
     * most recently used value.
     *
     * @throws lsst::pex::exceptions::NotFoundError  If key is not in the
     * cache.
     *
     * @exceptsafe Basic exception safety: exceptions will leave the
     * system in a valid but unpredictable state.
     */
    Value operator[](Key const& key);

    void add(Key const& key, Value const& value);

    std::size_t size() const { return _container.size(); }

    std::vector<Key> keys() const;

    bool contains(Key const& key) { return _lookup(key).second; }

    std::size_t capacity() const { return _maxElements; }

    void reserve(std::size_t maxElements) { _maxElements = maxElements; _trim(); }

    void flush();

#ifdef LSST_CACHE_DEBUG
    void enableDebugging() { _debuggingEnabled = true; }
#endif

  private:

    // Trim the cache to size
    void _trim() {
        if (capacity() == 0) return;  // Allowed to grow without limit
        while (size() > capacity()) {
            _container.template get<Sequence>().pop_back();
        }
    }

    // Element in the multi_index container
    typedef std::pair<Key, Value> Element;

    // Tags for multi_index container
    struct Sequence {};
    struct Hash {};

    // The multi_index container
    typedef boost::multi_index_container<
                Element,
                boost::multi_index::indexed_by<
                    boost::multi_index::sequenced<boost::multi_index::tag<Sequence>>,
                    boost::multi_index::hashed_unique<
                        boost::multi_index::tag<Hash>,
                        boost::multi_index::member<Element, Key, &Element::first>,
                            KeyHash>>> Container;

    // Lookup key in the container
    //
    // Returns the iterator and whether there's anything there.
    //
    // If the key exists, updates the cache to make that key the most recent.
    std::pair<typename Container::template index<Hash>::type::iterator, bool> _lookup(Key const& key) {
        auto const& hashContainer = _container.template get<Hash>();
        auto it = hashContainer.find(key);
        bool found = (it != hashContainer.end());
        if (found) {
            _container.relocate(_container.template get<Sequence>().begin(),
                                _container.template project<Sequence>(it));
        }
#ifdef LSST_CACHE_DEBUG
        if (_debuggingEnabled) {
            _requests.push_back(key);
            ++_total;
            if (found) ++_hits;
        }
#endif
        return std::make_pair(it, found);
    }

    // Add a key-value pair that are not already present
    void _addNew(Key const& key, Value const& value) {
        _container.template get<Sequence>().emplace_front(key, value);
        _trim();
    }

    std::size_t _maxElements;  // Maximum number of elements; 0 means infinite
    Container _container;  // Container of key,value pairs
#ifdef LSST_CACHE_DEBUG
    bool _debuggingEnabled;
    mutable std::size_t _hits, _total;  // Statistics of cache hits
    mutable std::vector<Key> _requests;  // Cache requests
    static std::size_t getId() {
        static std::size_t _id = 0;  // Identifier
        return _id++;
    }
#endif
};

// Definitions

template <typename Key, typename Value, typename KeyHash, typename KeyPred>
template <typename Generator>
Value Cache<Key, Value, KeyHash, KeyPred>::operator()(
    Key const& key,
    Generator func
) {
    auto result = _lookup(key);
    if (result.second) {
        return result.first->second;
    }
    Value value = func(key);
    _addNew(key, value);
    return value;
}

template <typename Key, typename Value, typename KeyHash, typename KeyPred>
Value Cache<Key, Value, KeyHash, KeyPred>::operator[](Key const& key) {
    auto result = _lookup(key);
    if (result.second) {
        return result.first->second;
    }
    throw LSST_EXCEPT(pex::exceptions::NotFoundError,
                      (boost::format("Unable to find key: %s") % key).str());
}

template <typename Key, typename Value, typename KeyHash, typename KeyPred>
void Cache<Key, Value, KeyHash, KeyPred>::add(Key const& key, Value const& value) {
    auto result = _lookup(key);
    if (!result.second) {
        _addNew(key, value);
    }
}

template <typename Key, typename Value, typename KeyHash, typename KeyPred>
std::vector<Key> Cache<Key, Value, KeyHash, KeyPred>::keys() const {
    std::vector<Key> result;
    result.reserve(size());
    for (auto & keyValue : _container.template get<Sequence>()) {
        result.push_back(keyValue.first);
    }
    return result;
}

template <typename Key, typename Value, typename KeyHash, typename KeyPred>
void Cache<Key, Value, KeyHash, KeyPred>::flush() {
    while (size() > 0) {
        _container.template get<Sequence>().pop_back();
    }
}

#ifdef LSST_CACHE_DEBUG
template <typename Key, typename Value, typename KeyHash, typename KeyPred>
Cache<Key, Value, KeyHash, KeyPred>::~Cache() {
    if (!_debuggingEnabled) {
        return;
    }
    std::string filename = (boost::format("lsst-cache-%s-%d.dat") %
                            demangleType(typeid(*this).name()) % getId()).str();
    std::ofstream file(filename);
    for (auto const& key : _requests) {
        file << key << "\n";
    }
    file.close();
    std::cerr << "Wrote cache requests to " << filename << ": " << _hits << "/" << _total << " hits";
    std::cerr << std::endl;
}
#endif

}} // namespace lsst::utils


#endif // ifndef LSST_UTILS_CACHE_H