File indexing completed on 2024-03-24 15:15:23

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 };