Kstars

trixelcache.h
1/*
2 SPDX-FileCopyrightText: 2001 Jason Harris <jharris@30doradus.org>
3 SPDX-FileCopyrightText: 2021 Valentin Boettcher <hiro at protagon.space; @hiro98:tchncs.de>
4
5 SPDX-License-Identifier: GPL-2.0-or-later
6*/
7
8#pragma once
9#include <algorithm>
10#include <cstddef>
11#include <stdexcept>
12#include <vector>
13#include <list>
14
15/**
16 * \brief A simple integer indexed elastically cached wrapper around
17 * std::vector to hold container types `content` which are cheap to
18 * construct empty and provide a default constructor, as well as `[]`,
19 * `size` and `swap` members (think `std::vector` and `std::list`). The
20 * caching mechanism will be short-circuited if the cache size equals the
21 * data size.
22 *
23 * The container is resized to a given data_size by default
24 * initializing its elements. The elements are stored as
25 * `TrixelCache::element` objects and retrieved by index and LRU
26 * cached on the fly. To test if a given element is cached (or not
27 * empty) the `TrixelCache::element::is_set()` can be queried. Setting
28 * an element works by just assigning it with the new data. The data
29 * from an element can be retrieved through the
30 * `TrixelCache::element::data()` member. Modifying the data through
31 * that reference is allowed.
32 *
33 * Setting an element is done by assigning it the new data.
34 *
35 * When it is convenient `TrixelCache::prune()` may be called, which
36 * clears the least recently used elements (by default initializing them)
37 * until the number of elements does not exceed the cache size. This is
38 * expensive relative to setting an elment which has almost no cost.
39 *
40 * \tparam content The content type to use. Most likely a QList,
41 * `std::vector or std::list.`
42 *
43 * \todo Use `std::optional` when C++17 is adopted in kstars.
44 *
45 * ### Example
46 *
47 * ~~~~~~~~{cpp}
48 * TrixelCache<std::vector<int>> cache(100, 10);
49 * auto& element = chache[0];
50 *
51 * if(!elmenent.is_set())
52 * elment = std::vector<int> {1, 2, 3, 4};
53 *
54 * std::cout << cache[0].data(); // {1, 2, 3, 4}
55 * ~~~~~~~~
56 */
57
58template <typename content>
60{
61 public:
62 /**
63 * @brief A container to hold cache elements.
64 *
65 * The holds the data and the information if the data has been set
66 * already. To this end, the assignment operator has been
67 * overloaded.
68 */
69 class element
70 {
71 public:
72 /** @return wether the element contains a cached object */
73 bool is_set() { return _set; }
74
75 /** @return the data held by element */
76 content &data() { return _data; }
77
78 element &operator=(const content &rhs)
79 {
80 _data = rhs;
81 _set = true;
82 return *this;
83 }
84
85 element &operator=(content &&rhs)
86 {
87 _data.swap(rhs);
88 _set = true;
89 return *this;
90 }
91
92 /** resets the element to the empty state */
93 void reset()
94 {
95 content().swap(_data);
96 _set = false;
97 };
98
99 private:
100 bool _set{ false };
101 content _data;
102 };
103
104 /**
105 * Constructs a cache with \p data_size default constructed elements
106 * with an elastic ceiling capacity of \p cache_size.
107 */
108 TrixelCache(const size_t data_size, const size_t cache_size)
109 : _cache_size{ cache_size }, _noop{ cache_size == data_size }
110 {
111 if (_cache_size > data_size)
112 throw std::range_error("cache_size cannot exceet data_size");
113
114 _data.resize(data_size);
115 };
116
117 /** Retrieve an element at \p index. */
118 element &operator[](const size_t index) noexcept
119 {
120 if (!_noop)
121 add_index(index);
122
123 return _data[index];
124 }
125
126 /**
127 * Remove excess elements from the cache
128 * The capacity can be temporarily readjusted to \p keep.
129 * \p keep must be greater than the cache size to be of effect.
130 */
131 void prune(size_t keep = 0) noexcept
132 {
133 if (_noop)
134 return;
135
136 remove_dublicate_indices();
137 const int delta =
138 _used_indices.size() - (keep > _cache_size ? keep : _cache_size);
139
140 if (delta <= 0)
141 return;
142
143 auto begin = _used_indices.begin();
144 std::advance(begin, delta);
145
146 std::for_each(begin, _used_indices.end(),
147 [&](size_t index) { _data[index].reset(); });
148
149 _used_indices = {};
150 }
151
152 /**
153 * Reset the cache size to \p size. This does clear the cache.
154 */
155 void set_size(const size_t size)
156 {
157 if (size > _data.size())
158 throw std::range_error("cache_size cannot exceet data_size");
159
160 clear();
161
162 _cache_size = size;
163 _noop = (_cache_size == _data.size());
164 }
165
166 /** @return the size of the cache */
167 size_t size() const { return _cache_size; };
168
169 /** @return the number of set elements in the cache, slow */
171 {
172 remove_dublicate_indices();
173 return _used_indices.size();
174 };
175
176 /** @return a list of currently primed indices, slow */
177 std::list<size_t> primed_indices()
178 {
179 remove_dublicate_indices();
180 return _used_indices;
181 };
182
183 /** @return wether the cache is just a wrapped vector */
184 bool noop() const { return _noop; }
185
186 /** Clear the cache without changing it's size. */
187 void clear() noexcept
188 {
189 auto size = _data.size();
190 std::vector<element>().swap(_data);
191 _data.resize(size);
192 _used_indices.clear();
193 }
194
195 private:
196 size_t _cache_size;
197 bool _noop;
198 std::vector<element> _data;
199 std::list<size_t> _used_indices;
200
201 /** Add an index to the lru caching list */
202 void add_index(const size_t index) { _used_indices.push_front(index); }
203
204 void remove_dublicate_indices()
205 {
206 std::vector<bool> found(_data.size(), false);
207 _used_indices.remove_if([&](size_t index) {
208 if (found[index])
209 return true;
210
211 found[index] = true;
212 return false;
213 });
214 };
215};
A container to hold cache elements.
Definition trixelcache.h:70
void reset()
resets the element to the empty state
Definition trixelcache.h:93
A simple integer indexed elastically cached wrapper around std::vector to hold container types conten...
Definition trixelcache.h:60
void prune(size_t keep=0) noexcept
Remove excess elements from the cache The capacity can be temporarily readjusted to keep.
TrixelCache(const size_t data_size, const size_t cache_size)
Constructs a cache with data_size default constructed elements with an elastic ceiling capacity of ca...
bool noop() const
size_t current_usage()
void set_size(const size_t size)
Reset the cache size to size.
element & operator[](const size_t index) noexcept
Retrieve an element at index.
void clear() noexcept
Clear the cache without changing it's size.
size_t size() const
std::list< size_t > primed_indices()
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Mon Nov 4 2024 16:38:42 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.