gd/common/lru_cache.h

/*
 * Copyright 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <functional>
#include <iterator>
#include <list>
#include <mutex>
#include <optional>
#include <thread>
#include <unordered_map>

#include "common/list_map.h"
#include "os/log.h"

namespace bluetooth {
namespace common {

// An LRU map-cache the evict the oldest item when reaching capacity
//
// Usage:
//   - keys are sorted from warmest to coldest
//   - iterating through the cache won't warm up keys
//   - operations on iterators won't warm up keys
//   - find(), contains(), insert_or_assign() will warm up the key
//   - insert_or_assign() will evict coldest key when cache reaches capacity
//   - NOT THREAD SAFE
//
// Performance:
//   - Key look-up and modification is O(1)
//   - Memory consumption is:
//     O(2*capacity*sizeof(K) + capacity*(sizeof(nullptr)+sizeof(V)))
//
// Template:
//   - Key key type
//   - T value type
// */
template <typename Key, typename T>
class LruCache {
 public:
  using value_type = typename ListMap<Key, T>::value_type;
  // different from c++17 node_type on purpose as we want node to be copyable
  using node_type = typename ListMap<Key, T>::node_type;
  using iterator = typename ListMap<Key, T>::iterator;
  using const_iterator = typename ListMap<Key, T>::const_iterator;

  // Constructor a LRU cache with |capacity|
  explicit LruCache(size_t capacity) : capacity_(capacity) {
    ASSERT_LOG(capacity_ != 0, "Unable to have 0 LRU Cache capacity");
  }

  // for move
  LruCache(LruCache&& other) noexcept = default;
  LruCache& operator=(LruCache&& other) noexcept = default;

  // copy-constructor
  // iterators in key_map_ cannot be copied directly
  LruCache(const LruCache& other) : capacity_(other.capacity_), list_map_(other.list_map_) {}

  // copy-assignment
  // iterators in key_map_ cannot be copied directly
  LruCache& operator=(const LruCache& other) {
    if (&other == this) {
      return *this;
    }
    capacity_ = other.capacity_;
    list_map_ = other.list_map_;
    return *this;
  }

  // comparison operators
  bool operator==(const LruCache& rhs) const {
    return capacity_ == rhs.capacity_ && list_map_ == rhs.list_map_;
  }
  bool operator!=(const LruCache& rhs) const {
    return !(*this == rhs);
  }

  ~LruCache() {
    clear();
  }

  // Clear the cache
  void clear() {
    list_map_.clear();
  }

  // Find the value of a key, and move the key to the head of cache, if there is one. Return iterator to value if key
  // exists, end() if not. Iterator might be invalidated when removed or evicted. Const version.
  //
  // LRU: Will warm up key
  // LRU: Access to returned iterator won't move key in LRU
  const_iterator find(const Key& key) const {
    return const_cast<LruCache*>(this)->find(key);
  }

  // Find the value of a key, and move the key to the head of cache, if there is one. Return iterator to value if key
  // exists, end() if not. Iterator might be invalidated when removed or evicted
  //
  // LRU: Will warm up key
  // LRU: Access to returned iterator won't move key in LRU
  iterator find(const Key& key) {
    auto iter = list_map_.find(key);
    if (iter == list_map_.end()) {
      return end();
    }
    // move to front
    list_map_.splice(list_map_.begin(), list_map_, iter);
    return iter;
  }

  // Check if key exist in the cache. Return true if key exist in cache, false, if not
  //
  // LRU: Will warm up key
  bool contains(const Key& key) const {
    return find(key) != list_map_.end();
  }

  // Put a key-value pair to the head of cache, evict the oldest key if cache is at capacity. Eviction is based on key
  // ONLY. Hence, updating a key will not evict the oldest key. Return evicted value if old value was evicted,
  // std::nullopt if not. The return value will be evaluated to true in a boolean context if a value is contained by
  // std::optional, false otherwise.
  //
  // LRU: Will warm up key
  std::optional<node_type> insert_or_assign(const Key& key, T value) {
    if (contains(key)) {
      // contains() calls find() that moved the node to the head
      list_map_.begin()->second = std::move(value);
      return std::nullopt;
    }
    // remove tail if at capacity
    std::optional<node_type> evicted_node = std::nullopt;
    if (list_map_.size() == capacity_) {
      evicted_node = list_map_.extract(std::prev(list_map_.end())->first);
    }
    // insert new one to front of list
    list_map_.insert_or_assign(list_map_.begin(), key, std::move(value));
    return evicted_node;
  }

  // Put a key-value pair to the head of cache, evict the oldest key if cache is at capacity. Eviction is based on key
  // ONLY. Hence, updating a key will not evict the oldest key. This method tries to construct the value in-place. If
  // the key already exist, this method only update the value. Return inserted iterator, whether insertion happens, and
  // evicted value if old value was evicted or std::nullopt
  //
  // LRU: Will warm up key
  template <class... Args>
  std::tuple<iterator, bool, std::optional<node_type>> try_emplace(const Key& key, Args&&... args) {
    if (contains(key)) {
      // contains() calls find() that moved the node to the head
      return std::make_tuple(end(), false, std::nullopt);
    }
    // remove tail if at capacity
    std::optional<node_type> evicted_node = std::nullopt;
    if (list_map_.size() == capacity_) {
      evicted_node = list_map_.extract(std::prev(list_map_.end())->first);
    }
    // insert new one to front of list
    auto pair = list_map_.try_emplace(list_map_.begin(), key, std::forward<Args>(args)...);
    return std::make_tuple(pair.first, pair.second, std::move(evicted_node));
  }

  // Delete a key from cache, return removed value if old value was evicted, std::nullopt if not. The return value will
  // be evaluated to true in a boolean context if a value is contained by std::optional, false otherwise.
  inline std::optional<node_type> extract(const Key& key) {
    return list_map_.extract(key);
  }

  /// Remove an iterator pointed item from the lru cache and return the iterator immediately after the erased item
  iterator erase(const_iterator iter) {
    return list_map_.erase(iter);
  }

  // Return size of the cache
  inline size_t size() const {
    return list_map_.size();
  }

  // Iterator interface for begin
  inline iterator begin() {
    return list_map_.begin();
  }

  // Return iterator interface for begin, const
  inline const_iterator begin() const {
    return list_map_.begin();
  }

  // Return iterator interface for end
  inline iterator end() {
    return list_map_.end();
  }

  // Iterator interface for end, const
  inline const_iterator end() const {
    return list_map_.end();
  }

 private:
  size_t capacity_;
  ListMap<Key, T> list_map_;
};

}  // namespace common
}  // namespace bluetooth