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