File indexing completed on 2024-04-21 07:28:40
0001 /* 0002 SPDX-FileCopyrightText: 2001 Jason Harris <jharris@30doradus.org> 0003 SPDX-FileCopyrightText: 2021 Valentin Boettcher <hiro at protagon.space; @hiro98:tchncs.de> 0004 0005 SPDX-License-Identifier: GPL-2.0-or-later 0006 */ 0007 0008 #pragma once 0009 #include <algorithm> 0010 #include <cstddef> 0011 #include <stdexcept> 0012 #include <vector> 0013 #include <list> 0014 0015 /** 0016 * \brief A simple integer indexed elastically cached wrapper around 0017 * std::vector to hold container types `content` which are cheap to 0018 * construct empty and provide a default constructor, as well as `[]`, 0019 * `size` and `swap` members (think `std::vector` and `std::list`). The 0020 * caching mechanism will be short-circuited if the cache size equals the 0021 * data size. 0022 * 0023 * The container is resized to a given data_size by default 0024 * initializing its elements. The elements are stored as 0025 * `TrixelCache::element` objects and retrieved by index and LRU 0026 * cached on the fly. To test if a given element is cached (or not 0027 * empty) the `TrixelCache::element::is_set()` can be queried. Setting 0028 * an element works by just assigning it with the new data. The data 0029 * from an element can be retrieved through the 0030 * `TrixelCache::element::data()` member. Modifying the data through 0031 * that reference is allowed. 0032 * 0033 * Setting an element is done by assigning it the new data. 0034 * 0035 * When it is convenient `TrixelCache::prune()` may be called, which 0036 * clears the least recently used elements (by default initializing them) 0037 * until the number of elements does not exceed the cache size. This is 0038 * expensive relative to setting an elment which has almost no cost. 0039 * 0040 * \tparam content The content type to use. Most likely a QList, 0041 * `std::vector or std::list.` 0042 * 0043 * \todo Use `std::optional` when C++17 is adopted in kstars. 0044 * 0045 * ### Example 0046 * 0047 * ~~~~~~~~{cpp} 0048 * TrixelCache<std::vector<int>> cache(100, 10); 0049 * auto& element = chache[0]; 0050 * 0051 * if(!elmenent.is_set()) 0052 * elment = std::vector<int> {1, 2, 3, 4}; 0053 * 0054 * std::cout << cache[0].data(); // {1, 2, 3, 4} 0055 * ~~~~~~~~ 0056 */ 0057 0058 template <typename content> 0059 class TrixelCache 0060 { 0061 public: 0062 /** 0063 * @brief A container to hold cache elements. 0064 * 0065 * The holds the data and the information if the data has been set 0066 * already. To this end, the assignment operator has been 0067 * overloaded. 0068 */ 0069 class element 0070 { 0071 public: 0072 /** @return wether the element contains a cached object */ 0073 bool is_set() { return _set; } 0074 0075 /** @return the data held by element */ 0076 content &data() { return _data; } 0077 0078 element &operator=(const content &rhs) 0079 { 0080 _data = rhs; 0081 _set = true; 0082 return *this; 0083 } 0084 0085 element &operator=(content &&rhs) 0086 { 0087 _data.swap(rhs); 0088 _set = true; 0089 return *this; 0090 } 0091 0092 /** resets the element to the empty state */ 0093 void reset() 0094 { 0095 content().swap(_data); 0096 _set = false; 0097 }; 0098 0099 private: 0100 bool _set{ false }; 0101 content _data; 0102 }; 0103 0104 /** 0105 * Constructs a cache with \p data_size default constructed elements 0106 * with an elastic ceiling capacity of \p cache_size. 0107 */ 0108 TrixelCache(const size_t data_size, const size_t cache_size) 0109 : _cache_size{ cache_size }, _noop{ cache_size == data_size } 0110 { 0111 if (_cache_size > data_size) 0112 throw std::range_error("cache_size cannot exceet data_size"); 0113 0114 _data.resize(data_size); 0115 }; 0116 0117 /** Retrieve an element at \p index. */ 0118 element &operator[](const size_t index) noexcept 0119 { 0120 if (!_noop) 0121 add_index(index); 0122 0123 return _data[index]; 0124 } 0125 0126 /** 0127 * Remove excess elements from the cache 0128 * The capacity can be temporarily readjusted to \p keep. 0129 * \p keep must be greater than the cache size to be of effect. 0130 */ 0131 void prune(size_t keep = 0) noexcept 0132 { 0133 if (_noop) 0134 return; 0135 0136 remove_dublicate_indices(); 0137 const int delta = 0138 _used_indices.size() - (keep > _cache_size ? keep : _cache_size); 0139 0140 if (delta <= 0) 0141 return; 0142 0143 auto begin = _used_indices.begin(); 0144 std::advance(begin, delta); 0145 0146 std::for_each(begin, _used_indices.end(), 0147 [&](size_t index) { _data[index].reset(); }); 0148 0149 _used_indices = {}; 0150 } 0151 0152 /** 0153 * Reset the cache size to \p size. This does clear the cache. 0154 */ 0155 void set_size(const size_t size) 0156 { 0157 if (size > _data.size()) 0158 throw std::range_error("cache_size cannot exceet data_size"); 0159 0160 clear(); 0161 0162 _cache_size = size; 0163 _noop = (_cache_size == _data.size()); 0164 } 0165 0166 /** @return the size of the cache */ 0167 size_t size() const { return _cache_size; }; 0168 0169 /** @return the number of set elements in the cache, slow */ 0170 size_t current_usage() 0171 { 0172 remove_dublicate_indices(); 0173 return _used_indices.size(); 0174 }; 0175 0176 /** @return a list of currently primed indices, slow */ 0177 std::list<size_t> primed_indices() 0178 { 0179 remove_dublicate_indices(); 0180 return _used_indices; 0181 }; 0182 0183 /** @return wether the cache is just a wrapped vector */ 0184 bool noop() const { return _noop; } 0185 0186 /** Clear the cache without changing it's size. */ 0187 void clear() noexcept 0188 { 0189 auto size = _data.size(); 0190 std::vector<element>().swap(_data); 0191 _data.resize(size); 0192 _used_indices.clear(); 0193 } 0194 0195 private: 0196 size_t _cache_size; 0197 bool _noop; 0198 std::vector<element> _data; 0199 std::list<size_t> _used_indices; 0200 0201 /** Add an index to the lru caching list */ 0202 void add_index(const size_t index) { _used_indices.push_front(index); } 0203 0204 void remove_dublicate_indices() 0205 { 0206 std::vector<bool> found(_data.size(), false); 0207 _used_indices.remove_if([&](size_t index) { 0208 if (found[index]) 0209 return true; 0210 0211 found[index] = true; 0212 return false; 0213 }); 0214 }; 0215 };