chromium/base/containers/lru_cache.h

// Copyright 2011 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// This file contains a template for a Least Recently Used cache that allows
// constant-time access to items, but easy identification of the
// least-recently-used items for removal. Variations exist to support use as a
// Map (`base::LRUCache`), HashMap (`base::HashingLRUCache`), Set
// (`base::LRUCacheSet`), or HashSet (`base::HashingLRUCacheSet`). These are
// implemented as aliases of `base::internal::LRUCacheBase`, defined at the
// bottom of this file.
//
// The key object (which is identical to the value, in the Set variations) will
// be stored twice, so it should support efficient copying.

#ifndef BASE_CONTAINERS_LRU_CACHE_H_
#define BASE_CONTAINERS_LRU_CACHE_H_

#include <stddef.h>

#include <algorithm>
#include <concepts>
#include <functional>
#include <list>
#include <map>
#include <type_traits>
#include <unordered_map>
#include <utility>

#include "base/check.h"

namespace base {
namespace trace_event::internal {

template <class LruCacheType>
size_t DoEstimateMemoryUsageForLruCache(const LruCacheType&);

}  // namespace trace_event::internal

namespace internal {

struct GetKeyFromKVPair { … };

// Base class for the LRU cache specializations defined below.
template <class ValueType, class GetKeyFromValue, class KeyIndexTemplate>
class LRUCacheBase { … };

template <class KeyType, class KeyCompare>
struct LRUCacheKeyIndex { … };

template <class KeyType, class KeyHash, class KeyEqual>
struct HashingLRUCacheKeyIndex { … };

}  // namespace internal

// Implements an LRU cache of `ValueType`, where each value can be uniquely
// referenced by `KeyType`. Entries can be iterated in order of
// least-recently-used to most-recently-used by iterating from `rbegin()` to
// `rend()`, where a "use" is defined as a call to `Put(k, v)` or `Get(k)`.
LRUCache;

// Implements an LRU cache of `ValueType`, where each value can be uniquely
// referenced by `KeyType`, and `KeyType` may be hashed for O(1) insertion,
// removal, and lookup. Entries can be iterated in order of least-recently-used
// to most-recently-used by iterating from `rbegin()` to `rend()`, where a "use"
// is defined as a call to `Put(k, v)` or `Get(k)`.
HashingLRUCache;

// Implements an LRU cache of `ValueType`, where each value is unique. Entries
// can be iterated in order of least-recently-used to most-recently-used by
// iterating from `rbegin()` to `rend()`, where a "use" is defined as a call to
// `Put(v)` or `Get(v)`.
LRUCacheSet;

// Implements an LRU cache of `ValueType`, where is value is unique, and may be
// hashed for O(1) insertion, removal, and lookup. Entries can be iterated in
// order of least-recently-used to most-recently-used by iterating from
// `rbegin()` to `rend()`, where a "use" is defined as a call to `Put(v)` or
// `Get(v)`.
HashingLRUCacheSet;

}  // namespace base

#endif  // BASE_CONTAINERS_LRU_CACHE_H_