text: // Copyright (c) 2018 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #ifndef QUICHE_QUIC_CORE_QUIC_LRU_CACHE_H_
  #define QUICHE_QUIC_CORE_QUIC_LRU_CACHE_H_
  
  #include <memory>
  
  #include "quiche/quic/platform/api/quic_export.h"
  #include "quiche/quic/platform/api/quic_flag_utils.h"
  #include "quiche/quic/platform/api/quic_flags.h"
  #include "quiche/quic/platform/api/quic_logging.h"
  #include "quiche/common/quiche_linked_hash_map.h"
  
  namespace quic {
  
  // A LRU cache that maps from type Key to Value* in QUIC.
  // This cache CANNOT be shared by multiple threads (even with locks) because
  // Value* returned by Lookup() can be invalid if the entry is evicted by other
  // threads.
  template <class K, class V, class Hash = std::hash<K>,
            class Eq = std::equal_to<K>>
  class QUIC_NO_EXPORT QuicLRUCache {
   private:
    using HashMapType =
        typename quiche::QuicheLinkedHashMap<K, std::unique_ptr<V>, Hash, Eq>;
  
   public:
    // The iterator, if valid, points to std::pair<K, std::unique_ptr<V>>.
    using iterator = typename HashMapType::iterator;
    using const_iterator = typename HashMapType::const_iterator;
    using reverse_iterator = typename HashMapType::reverse_iterator;
    using const_reverse_iterator = typename HashMapType::const_reverse_iterator;
  
    explicit QuicLRUCache(size_t capacity) : capacity_(capacity) {}
    QuicLRUCache(const QuicLRUCache&) = delete;
    QuicLRUCache& operator=(const QuicLRUCache&) = delete;
  
    iterator begin() { return cache_.begin(); }
    const_iterator begin() const { return cache_.begin(); }
  
    iterator end() { return cache_.end(); }
    const_iterator end() const { return cache_.end(); }
  
    reverse_iterator rbegin() { return cache_.rbegin(); }
    const_reverse_iterator rbegin() const { return cache_.rbegin(); }
  
    reverse_iterator rend() { return cache_.rend(); }
    const_reverse_iterator rend() const { return cache_.rend(); }
  
    // Inserts one unit of |key|, |value| pair to the cache. Cache takes ownership
    // of inserted |value|.
    void Insert(const K& key, std::unique_ptr<V> value) {
      auto it = cache_.find(key);
      if (it != cache_.end()) {
        cache_.erase(it);
      }
      cache_.emplace(key, std::move(value));
  
      if (cache_.size() > capacity_) {
        cache_.pop_front();
      }
      QUICHE_DCHECK_LE(cache_.size(), capacity_);
    }
  
    iterator Lookup(const K& key) {
      auto iter = cache_.find(key);
      if (iter == cache_.end()) {
        return iter;
      }
  
      std::unique_ptr<V> value = std::move(iter->second);
      cache_.erase(iter);
      auto result = cache_.emplace(key, std::move(value));
      QUICHE_DCHECK(result.second);
      return result.first;
    }
  
    iterator Erase(iterator iter) { return cache_.erase(iter); }
  
    // Removes all entries from the cache.
    void Clear() { cache_.clear(); }
  
    // Returns maximum size of the cache.
    size_t MaxSize() const { return capacity_; }
  
    // Returns current size of the cache.
    size_t Size() const { return cache_.size(); }
  
   private:
    quiche::QuicheLinkedHashMap<K, std::unique_ptr<V>, Hash, Eq> cache_;
    const size_t capacity_;
  };
  
  }  // namespace quic
  
  #endif  // QUICHE_QUIC_CORE_QUIC_LRU_CACHE_H_
  