Kstars

trixelcache.h
1 /*
2  SPDX-FileCopyrightText: 2001 Jason Harris <[email protected]>
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 
58 template <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 */
170  size_t current_usage()
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 };
size_t current_usage()
Definition: trixelcache.h:170
content & data()
Definition: trixelcache.h:76
void clear() noexcept
Clear the cache without changing it's size.
Definition: trixelcache.h:187
void reset()
resets the element to the empty state
Definition: trixelcache.h:93
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...
Definition: trixelcache.h:108
element & operator[](const size_t index) noexcept
Retrieve an element at index.
Definition: trixelcache.h:118
std::list< size_t > primed_indices()
Definition: trixelcache.h:177
void prune(size_t keep=0) noexcept
Remove excess elements from the cache The capacity can be temporarily readjusted to keep.
Definition: trixelcache.h:131
void set_size(const size_t size)
Reset the cache size to size.
Definition: trixelcache.h:155
bool noop() const
Definition: trixelcache.h:184
size_t size() const
Definition: trixelcache.h:167
A container to hold cache elements.
Definition: trixelcache.h:69
A simple integer indexed elastically cached wrapper around std::vector to hold container types conten...
Definition: trixelcache.h:59
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Sun Oct 1 2023 04:02:45 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.