lru_cache.h

// Copyright (c) 2011 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.

// This file contains a template for a Least Recently Used cache that allows
// constant-time access to items using a key, but easy identification of the
// least-recently-used items for removal.  Each key can only be associated with
// one payload item at a time.
//
// The key object will be stored twice, so it should support efficient copying.
//
// NOTE: While all operations are O(1), this code is written for
// legibility rather than optimality. If future profiling identifies this as
// a bottleneck, there is room for smaller values of 1 in the O(1). :]

#ifndef BASE_CONTAINERS_LRU_CACHE_H_
#define BASE_CONTAINERS_LRU_CACHE_H_

#include <stddef.h>

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

#include "base/check.h"

namespace base {
namespace trace_event {
namespace internal {

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

}  // namespace internal
}  // namespace trace_event

// LRUCacheBase ----------------------------------------------------------------

// This template is used to standardize map type containers that can be used
// by LRUCacheBase. This level of indirection is necessary because of the way
// that template template params and default template params interact.
template <class KeyType, class ValueType, class CompareType>
struct LRUCacheStandardMap {
  using Type = std::map<KeyType, ValueType, CompareType>;
};

// Base class for the LRU cache specializations defined below.
template <class KeyType,
          class PayloadType,
          class HashOrCompareType,
          template <typename, typename, typename> class MapType =
              LRUCacheStandardMap>
class LRUCacheBase {
 public:
  // The payload of the list. This maintains a copy of the key so we can
  // efficiently delete things given an element of the list.
  using value_type = std::pair<KeyType, PayloadType>;

 private:
  using PayloadList = std::list<value_type>;
  using KeyIndex = typename MapType<KeyType,
                                    typename PayloadList::iterator,
                                    HashOrCompareType>::Type;

 public:
  using size_type = typename PayloadList::size_type;

  using iterator = typename PayloadList::iterator;
  using const_iterator = typename PayloadList::const_iterator;
  using reverse_iterator = typename PayloadList::reverse_iterator;
  using const_reverse_iterator = typename PayloadList::const_reverse_iterator;

  enum { NO_AUTO_EVICT = 0 };

  // The max_size is the size at which the cache will prune its members to when
  // a new item is inserted. If the caller wants to manage this itself (for
  // example, maybe it has special work to do when something is evicted), it
  // can pass NO_AUTO_EVICT to not restrict the cache size.
  explicit LRUCacheBase(size_type max_size) : max_size_(max_size) {}

  LRUCacheBase(const LRUCacheBase&) = delete;
  LRUCacheBase& operator=(const LRUCacheBase&) = delete;

  virtual ~LRUCacheBase() = default;

  size_type max_size() const { return max_size_; }

  // Inserts a payload item with the given key. If an existing item has
  // the same key, it is removed prior to insertion. An iterator indicating the
  // inserted item will be returned (this will always be the front of the list).
  //
  // The payload will be forwarded.
  template <typename Payload>
  iterator Put(const KeyType& key, Payload&& payload) {
    // Remove any existing payload with that key.
    typename KeyIndex::iterator index_iter = index_.find(key);
    if (index_iter != index_.end()) {
      // Erase the reference to it. The index reference will be replaced in the
      // code below.
      Erase(index_iter->second);
    } else if (max_size_ != NO_AUTO_EVICT) {
      // New item is being inserted which might make it larger than the maximum
      // size: kick the oldest thing out if necessary.
      ShrinkToSize(max_size_ - 1);
    }

    ordering_.emplace_front(key, std::forward<Payload>(payload));
    index_.emplace(key, ordering_.begin());
    return ordering_.begin();
  }

  // Retrieves the contents of the given key, or end() if not found. This method
  // has the side effect of moving the requested item to the front of the
  // recency list.
  iterator Get(const KeyType& key) {
    typename KeyIndex::iterator index_iter = index_.find(key);
    if (index_iter == index_.end())
      return end();
    typename PayloadList::iterator iter = index_iter->second;

    // Move the touched item to the front of the recency ordering.
    ordering_.splice(ordering_.begin(), ordering_, iter);
    return ordering_.begin();
  }

  // Retrieves the payload associated with a given key and returns it via
  // result without affecting the ordering (unlike Get()).
  iterator Peek(const KeyType& key) {
    typename KeyIndex::const_iterator index_iter = index_.find(key);
    if (index_iter == index_.end())
      return end();
    return index_iter->second;
  }

  const_iterator Peek(const KeyType& key) const {
    typename KeyIndex::const_iterator index_iter = index_.find(key);
    if (index_iter == index_.end())
      return end();
    return index_iter->second;
  }

  // Exchanges the contents of |this| by the contents of the |other|.
  void Swap(LRUCacheBase& other) {
    ordering_.swap(other.ordering_);
    index_.swap(other.index_);
    std::swap(max_size_, other.max_size_);
  }

  // Erases the item referenced by the given iterator. An iterator to the item
  // following it will be returned. The iterator must be valid.
  iterator Erase(iterator pos) {
    index_.erase(pos->first);
    return ordering_.erase(pos);
  }

  // LRUCache entries are often processed in reverse order, so we add this
  // convenience function (not typically defined by STL containers).
  reverse_iterator Erase(reverse_iterator pos) {
    // We have to actually give it the incremented iterator to delete, since
    // the forward iterator that base() returns is actually one past the item
    // being iterated over.
    return reverse_iterator(Erase((++pos).base()));
  }

  // Shrinks the cache so it only holds |new_size| items. If |new_size| is
  // bigger or equal to the current number of items, this will do nothing.
  void ShrinkToSize(size_type new_size) {
    for (size_type i = size(); i > new_size; i--)
      Erase(rbegin());
  }

  // Deletes everything from the cache.
  void Clear() {
    index_.clear();
    ordering_.clear();
  }

  // Returns the number of elements in the cache.
  size_type size() const {
    // We don't use ordering_.size() for the return value because
    // (as a linked list) it can be O(n).
    DCHECK(index_.size() == ordering_.size());
    return index_.size();
  }

  // Allows iteration over the list. Forward iteration starts with the most
  // recent item and works backwards.
  //
  // Note that since these iterators are actually iterators over a list, you
  // can keep them as you insert or delete things (as long as you don't delete
  // the one you are pointing to) and they will still be valid.
  iterator begin() { return ordering_.begin(); }
  const_iterator begin() const { return ordering_.begin(); }
  iterator end() { return ordering_.end(); }
  const_iterator end() const { return ordering_.end(); }

  reverse_iterator rbegin() { return ordering_.rbegin(); }
  const_reverse_iterator rbegin() const { return ordering_.rbegin(); }
  reverse_iterator rend() { return ordering_.rend(); }
  const_reverse_iterator rend() const { return ordering_.rend(); }

  bool empty() const { return ordering_.empty(); }

 private:
  template <class LruCacheType>
  friend size_t trace_event::internal::DoEstimateMemoryUsageForLruCache(
      const LruCacheType&);

  PayloadList ordering_;
  KeyIndex index_;

  size_type max_size_;
};

// LRUCache --------------------------------------------------------------------

// A container that does not do anything to free its data. Use this when storing
// value types (as opposed to pointers) in the list.
template <class KeyType,
          class PayloadType,
          class CompareType = std::less<KeyType>>
class LRUCache : public LRUCacheBase<KeyType, PayloadType, CompareType> {
 private:
  using ParentType = LRUCacheBase<KeyType, PayloadType, CompareType>;

 public:
  // See LRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
  explicit LRUCache(typename ParentType::size_type max_size)
      : ParentType(max_size) {}
  LRUCache(const LRUCache&) = delete;
  LRUCache& operator=(const LRUCache&) = delete;
  ~LRUCache() override = default;
};

// HashingLRUCache ------------------------------------------------------------

template <class KeyType, class ValueType, class HashType>
struct LRUCacheHashMap {
  using Type = std::unordered_map<KeyType, ValueType, HashType>;
};

// This class is similar to LRUCache, except that it uses std::unordered_map as
// the map type instead of std::map. Note that your KeyType must be hashable to
// use this cache or you need to provide a hashing class.
template <class KeyType, class PayloadType, class HashType = std::hash<KeyType>>
class HashingLRUCache
    : public LRUCacheBase<KeyType, PayloadType, HashType, LRUCacheHashMap> {
 private:
  using ParentType =
      LRUCacheBase<KeyType, PayloadType, HashType, LRUCacheHashMap>;

 public:
  // See LRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
  explicit HashingLRUCache(typename ParentType::size_type max_size)
      : ParentType(max_size) {}
  HashingLRUCache(const HashingLRUCache&) = delete;
  HashingLRUCache& operator=(const HashingLRUCache&) = delete;
  ~HashingLRUCache() override = default;
};

}  // namespace base

#endif  // BASE_CONTAINERS_LRU_CACHE_H_