File indexing completed on 2024-04-14 08:33:58

0001 /*
0002    SPDX-FileCopyrightText: 2020 Milian Wolff <mail@milianw.org>
0003 
0004    SPDX-License-Identifier: LGPL-2.0-or-later
0005 */
0006 
0007 #pragma once
0008 
0009 #include <algorithm>
0010 #include <vector>
0011 
0012 template<typename Key, typename Value>
0013 class LRUCache
0014 {
0015 public:
0016     struct Entry {
0017         Key key;
0018         Value value;
0019         bool operator==(const Key &rhs) const
0020         {
0021             return key == rhs;
0022         }
0023     };
0024     using Entries = std::vector<Entry>;
0025     using value_type = typename Entries::value_type;
0026     using size_type = typename Entries::size_type;
0027     using difference_type = typename Entries::difference_type;
0028     // only const access
0029     using reference = typename Entries::const_reference;
0030     using const_reference = typename Entries::const_reference;
0031     using pointer = typename Entries::const_pointer;
0032     using iterator = typename Entries::const_iterator;
0033     using const_iterator = typename Entries::const_iterator;
0034 
0035     void setMaxEntries(int maxEntries)
0036     {
0037         mMaxEntries = maxEntries;
0038     }
0039 
0040     std::size_t size() const
0041     {
0042         return mEntries.size();
0043     }
0044 
0045     const_iterator begin() const
0046     {
0047         return mEntries.begin();
0048     }
0049 
0050     const_iterator end() const
0051     {
0052         return std::next(mEntries.begin(), size());
0053     }
0054 
0055     const_iterator find(const Key &key)
0056     {
0057         // using non-const iterators here since we will re-insert when we find
0058         const auto begin = mEntries.begin();
0059         const auto end = std::next(mEntries.begin(), size());
0060         auto it = std::find(begin, end, key);
0061         if (it == begin || it == end) { // not found or already the last recently used one
0062             return it;
0063         }
0064 
0065         // rotate to mark entry as last recently used one
0066         std::rotate(begin, it, it + 1);
0067         return mEntries.cbegin();
0068     }
0069 
0070     void insert(Key key, Value value)
0071     {
0072         auto entriesSize = size();
0073         if (mMaxEntries == -1 || (entriesSize < static_cast<size_t>(mMaxEntries))) {
0074             // open up a new slot
0075             ++entriesSize;
0076             mEntries.resize(entriesSize);
0077         }
0078 
0079         // right shift to make space at the front
0080         std::rotate(mEntries.begin(), std::next(mEntries.begin(), entriesSize - 1), std::next(mEntries.begin(), entriesSize));
0081 
0082         // insert up front
0083         mEntries.front() = {std::move(key), std::move(value)};
0084     }
0085 
0086     bool remove(const Key &key)
0087     {
0088         const auto begin = mEntries.begin();
0089         const auto end = std::next(mEntries.begin(), size());
0090         auto it = std::find(begin, end, key);
0091         if (it == end) { // not found or already the last recently used one
0092             return false;
0093         }
0094 
0095         std::move(std::next(it), end, it);
0096         mEntries.resize(size() - 1);
0097         return true;
0098     }
0099 
0100     void clear()
0101     {
0102         mEntries.clear();
0103     }
0104 
0105 private:
0106     Entries mEntries;
0107     int mMaxEntries = -1;
0108 };