cached_map.h

Go to the documentation of this file.

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Authors:
 *    PBS <pbs3141@gmail.com>
 *
 * Copyright (C) 2022 PBS
 *
 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
 */
#ifndef INKSCAPE_UTIL_CACHED_MAP_H
#define INKSCAPE_UTIL_CACHED_MAP_H
 
#include <unordered_map>
#include <deque>
#include <memory>
#include <algorithm>
 
namespace Inkscape {
namespace Util {
 
template <typename Tk, typename Tv, typename Hash = std::hash<Tk>, typename Compare = std::equal_to<Tk>>
class cached_map
{
public:
    cached_map(std::size_t max_cache_size = 32) : max_cache_size(max_cache_size) {}
 
    auto add(Tk key, std::unique_ptr<Tv> value)
    {
        auto ret = map.emplace(std::move(key), std::move(value));
        return get_view(ret.first->second);
    }
 
    auto lookup(Tk const &key) -> std::shared_ptr<Tv>
    {
        if (auto it = map.find(key); it != map.end()) {
            return get_view(it->second);
        } else {
            return {};
        }
    }
 
    void clear()
    {
        unused.clear();
        map.clear();
    }
 
private:
    struct Item
    {
        std::unique_ptr<Tv> value; // The unique_ptr owning the actual value.
        std::weak_ptr<Tv> view; // A non-owning shared_ptr view that is in use by the outside world.
        Item(decltype(value) value) : value(std::move(value)) {}
    };
 
    std::size_t const max_cache_size;
    std::unordered_map<Tk, Item, Hash, Compare> map;
    std::deque<Tv*> unused;
 
    auto get_view(Item &item)
    {
        if (auto view = item.view.lock()) {
            return view;
        } else {
            remove_unused(item.value.get());
            auto new_view = std::shared_ptr<Tv>(item.value.get(), [this] (Tv *value) {
                push_unused(value);
            });
            item.view = new_view;
            return new_view;
        }
    }
 
    void remove_unused(Tv *value)
    {
        auto it = std::find(unused.begin(), unused.end(), value);
        if (it != unused.end()) {
            unused.erase(it);
        }
    }
 
    void push_unused(Tv *value)
    {
        unused.emplace_back(value);
        if (unused.size() > max_cache_size) {
            pop_unused();
        }
    }
 
    void pop_unused()
    {
        auto value = unused.front();
        map.erase(std::find_if(map.begin(), map.end(), [value] (auto const &it) {
            return it.second.value.get() == value;
        }));
        unused.pop_front();
    }
};
 
} // namespace Util
} // namespace Inkscape
 
#endif // INKSCAPE_UTIL_CACHED_MAP_H