File indexing completed on 2023-11-26 08:17:50

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 <array>
0011 
0012 template<typename Key, typename Value, size_t N>
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::array<Entry, N>;
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     std::size_t size() const
0036     {
0037         return mNumEntries;
0038     }
0039 
0040     const_iterator begin() const
0041     {
0042         return mEntries.begin();
0043     }
0044 
0045     const_iterator end() const
0046     {
0047         return std::next(mEntries.begin(), mNumEntries);
0048     }
0049 
0050     const_iterator find(const Key &key)
0051     {
0052         // using non-const iterators here since we will re-insert when we find
0053         const auto begin = mEntries.begin();
0054         const auto end = std::next(mEntries.begin(), mNumEntries);
0055         auto it = std::find(begin, end, key);
0056         if (it == begin || it == end) { // not found or already the last recently used one
0057             return it;
0058         }
0059 
0060         // rotate to mark entry as last recently used one
0061         std::rotate(begin, it, it + 1);
0062         return mEntries.cbegin();
0063     }
0064 
0065     void insert(Key key, Value value)
0066     {
0067         if (mNumEntries < mEntries.size()) {
0068             // open up a new slot
0069             ++mNumEntries;
0070         }
0071 
0072         // right shift to make space at the front
0073         std::rotate(mEntries.begin(), std::next(mEntries.begin(), mNumEntries - 1), std::next(mEntries.begin(), mNumEntries));
0074 
0075         // insert up front
0076         mEntries.front() = {std::move(key), std::move(value)};
0077     }
0078 
0079     bool remove(const Key &key)
0080     {
0081         const auto begin = mEntries.begin();
0082         const auto end = std::next(mEntries.begin(), mNumEntries);
0083         auto it = std::find(begin, end, key);
0084         if (it == end) { // not found or already the last recently used one
0085             return false;
0086         }
0087 
0088         std::move(std::next(it), end, it);
0089         --mNumEntries;
0090         return true;
0091     }
0092 
0093     void clear()
0094     {
0095         mNumEntries = 0;
0096         Entries empty;
0097         mEntries.swap(empty);
0098     }
0099 
0100 private:
0101     Entries mEntries;
0102     std::size_t mNumEntries = 0;
0103 };