1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
// SPDX-License-Identifier: GPL-2.0-or-later
/** @file
* An abstract gadget that implements a finite cache for a factory.
*/
/*
* 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 {
/**
* A cached_map<Tk, Tv> is designed for use by a factory that takes as input keys of type Tk and
* produces objects of type std::unique_ptr<Tv> in response. It allows such a factory to remember
* a finite number of previously constructed objects for later re-use.
*
* Upon constructing an object v for key k for the first time, calling
*
* my_ptr = my_cached_map.add(k, std::move(v));
*
* will add it to the cache, returning a std::shared_ptr<Tv> by which it can now be accessed.
*
* To re-use an object that might be in the cache, use
*
* my_ptr = my_cached_map.lookup(k)
*
* When all copies of the shared_ptr my_ptr have expired, the object is marked as unused. However
* it is not immediately deleted. As further objects are marked as unused, the oldest unused
* objects are gradually deleted, with their number never exceeding the value max_cache_size.
*
* Note that the cache must not be destroyed while any shared pointers to any of its objects are
* still active. This is in accord with its expected usage; if the factory loads objects from an
* external library, then it should be safe to destroy the cache just before the library is
* unloaded, as the objects should no longer be in use at that point anyway.
*/
template <typename Tk, typename Tv, typename Hash = std::hash<Tk>, typename Compare = std::equal_to<Tk>>
class cached_map
{
public:
/**
* Construct an empty cached_map.
*
* The optional max_cache_size argument specifies the maximum number of unused elements which
* will be kept in memory.
*/
cached_map(std::size_t max_cache_size = 32) : max_cache_size(max_cache_size) {}
/**
* Given a key and a unique_ptr to a value, inserts them into the map, or discards them if the
* key is already present.
*
* Returns a non-null shared_ptr to the new value in the map corresponding to key.
*/
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);
}
/**
* Look up a key in the map.
*
* Returns a shared pointer to the corresponding value, or null if the key is not present.
*/
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
|
