1 /* 2 * Copyright (C) 2021 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <list> 20 #include <sstream> 21 #include <unordered_map> 22 23 namespace android::mediametrics { 24 25 /** 26 * LruSet keeps a set of the last "Size" elements added or accessed. 27 * 28 * (Lru stands for least-recently-used eviction policy). 29 * 30 * Runs in O(1) time for add, remove, and check. Internally implemented 31 * with an unordered_map and a list. In order to remove elements, 32 * a list iterator is stored in the unordered_map 33 * (noting that std::list::erase() contractually 34 * does not affect iterators other than the one erased). 35 */ 36 37 template <typename T> 38 class LruSet { 39 const size_t mMaxSize; 40 std::list<T> mAccessOrder; // front is the most recent, back is the oldest. 41 // item T with its access order iterator. 42 std::unordered_map<T, typename std::list<T>::iterator> mMap; 43 44 public: 45 /** 46 * Constructs a LruSet which checks whether the element was 47 * accessed or added recently. 48 * 49 * The parameter maxSize is used to cap growth of LruSet; 50 * eviction is based on least recently used LRU. 51 * If maxSize is zero, the LruSet contains no elements 52 * and check() always returns false. 53 * 54 * \param maxSize the maximum number of elements that are tracked. 55 */ LruSet(size_t maxSize)56 explicit LruSet(size_t maxSize) : mMaxSize(maxSize) {} 57 58 /** 59 * Returns the number of entries in the LruSet. 60 * 61 * This is a number between 0 and maxSize. 62 */ size()63 size_t size() const { 64 return mMap.size(); 65 } 66 67 /** Clears the container contents. */ clear()68 void clear() { 69 mMap.clear(); 70 mAccessOrder.clear(); 71 } 72 73 /** Returns a string dump of the last n entries. */ dump(size_t n)74 std::string dump(size_t n) const { 75 std::stringstream ss; 76 auto it = mAccessOrder.cbegin(); 77 for (size_t i = 0; i < n && it != mAccessOrder.cend(); ++i) { 78 ss << *it++ << "\n"; 79 } 80 return ss.str(); 81 } 82 83 /** Adds a new item to the set. */ add(const T & t)84 void add(const T& t) { 85 if (mMaxSize == 0) return; 86 auto it = mMap.find(t); 87 if (it != mMap.end()) { // already exists. 88 mAccessOrder.erase(it->second); // move-to-front on the chronologically ordered list. 89 } else if (mAccessOrder.size() >= mMaxSize) { 90 const T last = mAccessOrder.back(); 91 mAccessOrder.pop_back(); 92 mMap.erase(last); 93 } 94 mAccessOrder.push_front(t); 95 mMap[t] = mAccessOrder.begin(); 96 } 97 98 /** 99 * Removes an item from the set. 100 * 101 * \param t item to be removed. 102 * \return false if the item doesn't exist. 103 */ remove(const T & t)104 bool remove(const T& t) { 105 auto it = mMap.find(t); 106 if (it == mMap.end()) return false; 107 mAccessOrder.erase(it->second); 108 mMap.erase(it); 109 return true; 110 } 111 112 /** Returns true if t is present (and moves the access order of t to the front). */ check(const T & t)113 bool check(const T& t) { // not const, as it adjusts the least-recently-used order. 114 auto it = mMap.find(t); 115 if (it == mMap.end()) return false; 116 mAccessOrder.erase(it->second); 117 mAccessOrder.push_front(it->first); 118 it->second = mAccessOrder.begin(); 119 return true; 120 } 121 }; 122 123 } // namespace android::mediametrics 124