LSST Applications 27.0.0,g0265f82a02+469cd937ee,g02d81e74bb+21ad69e7e1,g1470d8bcf6+cbe83ee85a,g2079a07aa2+e67c6346a6,g212a7c68fe+04a9158687,g2305ad1205+94392ce272,g295015adf3+81dd352a9d,g2bbee38e9b+469cd937ee,g337abbeb29+469cd937ee,g3939d97d7f+72a9f7b576,g487adcacf7+71499e7cba,g50ff169b8f+5929b3527e,g52b1c1532d+a6fc98d2e7,g591dd9f2cf+df404f777f,g5a732f18d5+be83d3ecdb,g64a986408d+21ad69e7e1,g858d7b2824+21ad69e7e1,g8a8a8dda67+a6fc98d2e7,g99cad8db69+f62e5b0af5,g9ddcbc5298+d4bad12328,ga1e77700b3+9c366c4306,ga8c6da7877+71e4819109,gb0e22166c9+25ba2f69a1,gb6a65358fc+469cd937ee,gbb8dafda3b+69d3c0e320,gc07e1c2157+a98bf949bb,gc120e1dc64+615ec43309,gc28159a63d+469cd937ee,gcf0d15dbbd+72a9f7b576,gdaeeff99f8+a38ce5ea23,ge6526c86ff+3a7c1ac5f1,ge79ae78c31+469cd937ee,gee10cc3b42+a6fc98d2e7,gf1cff7945b+21ad69e7e1,gfbcc870c63+9a11dc8c8f
LSST Data Management Base Package
Loading...
Searching...
No Matches
Cache.h
Go to the documentation of this file.
1/*
2 * LSST Data Management System
3 * See COPYRIGHT file at the top of the source tree.
4 *
5 * This product includes software developed by the
6 * LSST Project (http://www.lsst.org/).
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 LSST License Statement and
19 * the GNU General Public License along with this program. If not,
20 * see <http://www.lsstcorp.org/LegalNotices/>.
21 */
22#ifndef LSST_CPPUTILS_CACHE_H
23#define LSST_CPPUTILS_CACHE_H
24
25#include <vector>
26#include <optional>
27#include <utility> // std::pair
28
29#include "boost/multi_index_container.hpp"
30#include "boost/multi_index/sequenced_index.hpp"
31#include "boost/multi_index/hashed_index.hpp"
32#include "boost/multi_index/composite_key.hpp"
33#include "boost/multi_index/member.hpp"
34#include "boost/format.hpp"
35
36#include "lsst/pex/exceptions.h"
38
39//#define LSST_CACHE_DEBUG 1 // Define this variable to instrument for debugging
40
41
42#ifdef LSST_CACHE_DEBUG
43#include <iostream>
44#include <fstream>
45#include <typeinfo>
47#endif
48
49namespace lsst {
50namespace cpputils {
51
74template <typename Key, typename Value, typename KeyHash, typename KeyPred>
75class Cache {
76 public:
85 Cache(std::size_t maxElements=0) : _maxElements(maxElements) {
86 _container.template get<Hash>().reserve(maxElements);
87#ifdef LSST_CACHE_DEBUG
88 _debuggingEnabled = false;
89 _hits = 0;
90 _total = 0;
91 _requests.reserve(maxElements);
92#endif
93 }
94
95 // Defaulted stuff
96 Cache(Cache const &) = default;
97 Cache(Cache &&) = default;
98 Cache & operator=(Cache const &) = default;
99 Cache & operator=(Cache &&) = default;
100
102#ifdef LSST_CACHE_DEBUG
105 ~Cache();
106#else
107 ~Cache() = default;
108#endif
109
130 template <typename Generator>
131 Value operator()(Key const& key, Generator func);
132
133 /* Lookup a value
134 *
135 * If the key is in the cache, it will be promoted to the
136 * most recently used value.
137 *
138 * @throws lsst::pex::exceptions::NotFoundError If key is not in the
139 * cache.
140 *
141 * @exceptsafe Basic exception safety: exceptions will leave the
142 * system in a valid but unpredictable state.
143 */
144 Value operator[](Key const& key);
145
154 void add(Key const& key, Value const& value);
155
161 std::size_t size() const { return _container.size(); }
162
168 std::vector<Key> keys() const;
169
178 bool contains(Key const& key) { return _lookup(key).second; }
179
188 std::optional<Value> get(Key const& key) {
189 auto result = _lookup(key);
190 if (result.second) {
191 return std::optional<Value>(result.first->second);
192 } else {
193 return std::optional<Value>();
194 }
195 }
196
201 std::size_t capacity() const { return _maxElements; }
202
208 void reserve(std::size_t maxElements) { _maxElements = maxElements; _trim(); }
209
215 void flush();
216
217#ifdef LSST_CACHE_DEBUG
218 void enableDebugging() { _debuggingEnabled = true; }
219#endif
220
221 private:
222
223 // Trim the cache to size
224 void _trim() {
225 if (capacity() == 0) return; // Allowed to grow without limit
226 while (size() > capacity()) {
227 _container.template get<Sequence>().pop_back();
228 }
229 }
230
231 // Element in the multi_index container
232 typedef std::pair<Key, Value> Element;
233
234 // Tags for multi_index container
235 struct Sequence {};
236 struct Hash {};
237
238 // The multi_index container
239 typedef boost::multi_index_container<
240 Element,
241 boost::multi_index::indexed_by<
242 boost::multi_index::sequenced<boost::multi_index::tag<Sequence>>,
243 boost::multi_index::hashed_unique<
244 boost::multi_index::tag<Hash>,
245 boost::multi_index::member<Element, Key, &Element::first>,
246 KeyHash>>> Container;
247
248 // Lookup key in the container
249 //
250 // Returns the iterator and whether there's anything there.
251 //
252 // If the key exists, updates the cache to make that key the most recent.
254 auto const& hashContainer = _container.template get<Hash>();
255 auto it = hashContainer.find(key);
256 bool found = (it != hashContainer.end());
257 if (found) {
258 _container.relocate(_container.template get<Sequence>().begin(),
259 _container.template project<Sequence>(it));
260 }
261#ifdef LSST_CACHE_DEBUG
262 if (_debuggingEnabled) {
263 _requests.push_back(key);
264 ++_total;
265 if (found) ++_hits;
266 }
267#endif
268 return std::make_pair(it, found);
269 }
270
271 // Add a key-value pair that are not already present
272 void _addNew(Key const& key, Value const& value) {
273 _container.template get<Sequence>().emplace_front(key, value);
274 _trim();
275 }
276
277 std::size_t _maxElements; // Maximum number of elements; 0 means infinite
278 Container _container; // Container of key,value pairs
279#ifdef LSST_CACHE_DEBUG
280 bool _debuggingEnabled;
281 mutable std::size_t _hits, _total; // Statistics of cache hits
282 mutable std::vector<Key> _requests; // Cache requests
283 static std::size_t getId() {
284 static std::size_t _id = 0; // Identifier
285 return _id++;
286 }
287#endif
288};
289
290// Definitions
291
292template <typename Key, typename Value, typename KeyHash, typename KeyPred>
293template <typename Generator>
295 Key const& key,
296 Generator func
297) {
298 auto result = _lookup(key);
299 if (result.second) {
300 return result.first->second;
301 }
302 Value value = func(key);
303 _addNew(key, value);
304 return value;
305}
306
307template <typename Key, typename Value, typename KeyHash, typename KeyPred>
309 auto result = _lookup(key);
310 if (result.second) {
311 return result.first->second;
312 }
314 (boost::format("Unable to find key: %s") % key).str());
315}
316
317template <typename Key, typename Value, typename KeyHash, typename KeyPred>
318void Cache<Key, Value, KeyHash, KeyPred>::add(Key const& key, Value const& value) {
319 auto result = _lookup(key);
320 if (!result.second) {
321 _addNew(key, value);
322 }
323}
324
325template <typename Key, typename Value, typename KeyHash, typename KeyPred>
328 result.reserve(size());
329 for (auto & keyValue : _container.template get<Sequence>()) {
330 result.push_back(keyValue.first);
331 }
332 return result;
333}
334
335template <typename Key, typename Value, typename KeyHash, typename KeyPred>
337 while (size() > 0) {
338 _container.template get<Sequence>().pop_back();
339 }
340}
341
342#ifdef LSST_CACHE_DEBUG
343template <typename Key, typename Value, typename KeyHash, typename KeyPred>
345 if (!_debuggingEnabled) {
346 return;
347 }
348 std::string filename = (boost::format("lsst-cache-%s-%d.dat") %
349 demangleType(typeid(*this).name()) % getId()).str();
350 std::ofstream file(filename);
351 for (auto const& key : _requests) {
352 file << key << "\n";
353 }
354 file.close();
355 std::cerr << "Wrote cache requests to " << filename << ": " << _hits << "/" << _total << " hits";
357}
358#endif
359
360}
361namespace utils = cpputils;
362} // namespace lsst::cpputils
363
364
365#endif // ifndef LSST_CPPUTILS_CACHE_H
py::object result
Definition _schema.cc:429
#define LSST_EXCEPT(type,...)
Create an exception with a given type.
Definition Exception.h:48
Cache of most recently used values.
Definition Cache.h:75
std::vector< Key > keys() const
Return all keys in the cache, most recent first.
Definition Cache.h:326
std::size_t size() const
Return the number of values in the cache.
Definition Cache.h:161
Value operator()(Key const &key, Generator func)
Lookup or generate a value.
Definition Cache.h:294
bool contains(Key const &key)
Does the cache contain the key?
Definition Cache.h:178
Cache(Cache &&)=default
Cache(Cache const &)=default
std::size_t capacity() const
Return the capacity of the cache.
Definition Cache.h:201
void flush()
Empty the cache.
Definition Cache.h:336
void add(Key const &key, Value const &value)
Add a value to the cache.
Definition Cache.h:318
Cache(std::size_t maxElements=0)
Ctor.
Definition Cache.h:85
~Cache()=default
Dtor.
Cache & operator=(Cache &&)=default
Value operator[](Key const &key)
Definition Cache.h:308
std::optional< Value > get(Key const &key)
Return the cached value if it exists.
Definition Cache.h:188
void reserve(std::size_t maxElements)
Change the capacity of the cache.
Definition Cache.h:208
Cache & operator=(Cache const &)=default
Reports attempts to access elements using an invalid key.
Definition Runtime.h:151
T endl(T... args)
T make_pair(T... args)
std::string demangleType(std::string const _typeName)
Definition Demangle.cc:113
T reserve(T... args)