1 // Copyright (c) 2018 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef QUICHE_QUIC_CORE_QUIC_LRU_CACHE_H_ 6 #define QUICHE_QUIC_CORE_QUIC_LRU_CACHE_H_ 7 8 #include <memory> 9 10 #include "quiche/quic/platform/api/quic_export.h" 11 #include "quiche/quic/platform/api/quic_flag_utils.h" 12 #include "quiche/quic/platform/api/quic_flags.h" 13 #include "quiche/quic/platform/api/quic_logging.h" 14 #include "quiche/common/quiche_linked_hash_map.h" 15 16 namespace quic { 17 18 // A LRU cache that maps from type Key to Value* in QUIC. 19 // This cache CANNOT be shared by multiple threads (even with locks) because 20 // Value* returned by Lookup() can be invalid if the entry is evicted by other 21 // threads. 22 template <class K, class V, class Hash = std::hash<K>, 23 class Eq = std::equal_to<K>> 24 class QUICHE_EXPORT QuicLRUCache { 25 private: 26 using HashMapType = 27 typename quiche::QuicheLinkedHashMap<K, std::unique_ptr<V>, Hash, Eq>; 28 29 public: 30 // The iterator, if valid, points to std::pair<K, std::unique_ptr<V>>. 31 using iterator = typename HashMapType::iterator; 32 using const_iterator = typename HashMapType::const_iterator; 33 using reverse_iterator = typename HashMapType::reverse_iterator; 34 using const_reverse_iterator = typename HashMapType::const_reverse_iterator; 35 QuicLRUCache(size_t capacity)36 explicit QuicLRUCache(size_t capacity) : capacity_(capacity) {} 37 QuicLRUCache(const QuicLRUCache&) = delete; 38 QuicLRUCache& operator=(const QuicLRUCache&) = delete; 39 begin()40 iterator begin() { return cache_.begin(); } begin()41 const_iterator begin() const { return cache_.begin(); } 42 end()43 iterator end() { return cache_.end(); } end()44 const_iterator end() const { return cache_.end(); } 45 rbegin()46 reverse_iterator rbegin() { return cache_.rbegin(); } rbegin()47 const_reverse_iterator rbegin() const { return cache_.rbegin(); } 48 rend()49 reverse_iterator rend() { return cache_.rend(); } rend()50 const_reverse_iterator rend() const { return cache_.rend(); } 51 52 // Inserts one unit of |key|, |value| pair to the cache. Cache takes ownership 53 // of inserted |value|. Insert(const K & key,std::unique_ptr<V> value)54 void Insert(const K& key, std::unique_ptr<V> value) { 55 auto it = cache_.find(key); 56 if (it != cache_.end()) { 57 cache_.erase(it); 58 } 59 cache_.emplace(key, std::move(value)); 60 61 if (cache_.size() > capacity_) { 62 cache_.pop_front(); 63 } 64 QUICHE_DCHECK_LE(cache_.size(), capacity_); 65 } 66 Lookup(const K & key)67 iterator Lookup(const K& key) { 68 auto iter = cache_.find(key); 69 if (iter == cache_.end()) { 70 return iter; 71 } 72 73 std::unique_ptr<V> value = std::move(iter->second); 74 cache_.erase(iter); 75 auto result = cache_.emplace(key, std::move(value)); 76 QUICHE_DCHECK(result.second); 77 return result.first; 78 } 79 Erase(iterator iter)80 iterator Erase(iterator iter) { return cache_.erase(iter); } 81 82 // Removes all entries from the cache. Clear()83 void Clear() { cache_.clear(); } 84 85 // Returns maximum size of the cache. MaxSize()86 size_t MaxSize() const { return capacity_; } 87 88 // Returns current size of the cache. Size()89 size_t Size() const { return cache_.size(); } 90 91 private: 92 quiche::QuicheLinkedHashMap<K, std::unique_ptr<V>, Hash, Eq> cache_; 93 const size_t capacity_; 94 }; 95 96 } // namespace quic 97 98 #endif // QUICHE_QUIC_CORE_QUIC_LRU_CACHE_H_ 99