// Copyright 2018 The Fuchsia 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 LIB_ESCHER_UTIL_HASH_CACHE_H_
#define LIB_ESCHER_UTIL_HASH_CACHE_H_

#include <limits>

#include "lib/escher/util/hash.h"
#include "lib/escher/util/hash_map.h"
#include "lib/escher/util/intrusive_list.h"
#include "lib/escher/util/object_pool.h"

#ifndef NDEBUG
#include "lib/fxl/logging.h"
#endif

namespace escher {

// Base class for items that can be cached in a HashCache.
//
// TODO(SCN-696): A fancier implementation would make these fields private.
// Until then, we trust Escher clients to not frob them.
template <typename T>
struct HashCacheItem : public IntrusiveListItem<T> {
 public:
  void set_hash(Hash hash) { hash_ = hash; }
  void set_ring_index(size_t ring_index) { ring_index_ = ring_index; }
  Hash hash() { return hash_; }
  size_t ring_index() const { return ring_index_; }

 private:
  // The hash is stored so that the item can be found in the map when it is
  // found in the ring-to-be-evicted.
  Hash hash_ = {0};

  // Remembers the frame that the item was last used.  If it is used in a
  // different frame, it is moved into that frame's eviction ring.  If it was
  // previously used in the same frame, it doesn't need to move.
  size_t ring_index_ = 0;
};

// Wraps the provided ObjectPool policy so that HashCache clients can focus on
// the domain-specific functionality of cached items, without thinking about
// the HashCache-internal fields of those items.
template <typename T, typename BasePolicyT>
class HashCacheObjectPoolPolicy : public BasePolicyT {
 public:
  template <typename... Args>
  HashCacheObjectPoolPolicy(Args&&... args)
      : BasePolicyT(std::forward<Args>(args)...) {}

  inline void DestroyPoolObject(T* ptr) {
#ifndef NDEBUG
    FXL_DCHECK(ptr->prev == nullptr);
    FXL_DCHECK(ptr->next == nullptr);
    FXL_DCHECK(ptr->list == nullptr);
#endif
    ptr->set_hash({0});
    ptr->set_ring_index(std::numeric_limits<size_t>::max());
    this->BasePolicyT::DestroyPoolObject(ptr);
  }
};

// Provides a frame-based cache that evicts items that haven't been used for
// |FramesUntilEviction| frames.  In other words:
// - if FramesUntilEviction == 0, there is no frame-to-frame caching; items are
//   evicted even if they were used in the previous frame.
// - if FramesUntilEviction == 1, items are evicted if they were not used in the
//   previous frame, otherwise they remain in the cache.
// - if FramesUntilEviction == 2, items are evicted if two frames pass without
//   the resource being used.
// - and so on...
//
// Clients are responsible for not using the cached object after it has been
// evicted from the cache.  The recommended way to do this is to re-request
// cached objects every frame (or even more often).
template <typename T, typename ObjectPoolPolicyT = DefaultObjectPoolPolicy<T>,
          uint32_t FramesUntilEviction = 3>
class HashCache {
 public:
  template <typename... Args>
  HashCache(Args&&... args) : object_pool_(std::forward<Args>(args)...) {}
  ~HashCache() { Clear(); }

  void Clear() {
    for (size_t i = 0; i <= FramesUntilEviction; ++i) {
      ClearRing(i);
    }
    hash_map_.clear();

    object_pool_.Clear();

    cache_hits_ = 0;
    cache_misses_ = 0;
  }

  void BeginFrame() {
    index_ = (index_ + 1) % (FramesUntilEviction + 1);
    ClearRing(index_);
  }

  std::pair<T*, bool> Obtain(Hash hash) {
    auto it = hash_map_.find(hash);
    if (it != hash_map_.end()) {
      // Item was already cached.
      ++cache_hits_;

      T* item = it->second;
      FXL_DCHECK(item->hash() == hash);

      // Move item to the current frame's ring, to prevent it from being flushed
      // from the cache.
      if (item->ring_index() != index_) {
        rings_[index_].MoveToFront(rings_[item->ring_index()], item);
        item->set_ring_index(index_);
      }

      return {item, true};
    } else {
      // The item was not found in the cache, so a new one must be allocated.
      ++cache_misses_;

      T* item = object_pool_.Allocate();
      item->set_hash(hash);
      item->set_ring_index(index_);

      hash_map_.insert(it, std::make_pair(hash, item));
      rings_[index_].InsertFront(item);

      return {item, false};
    }
  }

  size_t cache_hits() const { return cache_hits_; }
  size_t cache_misses() const { return cache_misses_; }

  using ObjectPoolPolicyType = HashCacheObjectPoolPolicy<T, ObjectPoolPolicyT>;
  using ObjectPoolType = ObjectPool<T, ObjectPoolPolicyType>;
  const ObjectPoolType& object_pool() const { return object_pool_; }

 private:
  void ClearRing(size_t ring_index) {
    FXL_DCHECK(ring_index <= FramesUntilEviction);
    auto& ring = rings_[ring_index];
    while (auto item = ring.PopFront()) {
      hash_map_.erase(item->hash());
      object_pool_.Free(item);
    }
    FXL_DCHECK(ring.IsEmpty());
  }

  IntrusiveList<T> rings_[FramesUntilEviction + 1];
  ObjectPoolType object_pool_;
  unsigned index_ = 0;

  HashMap<Hash, T*> hash_map_;
  size_t cache_hits_ = 0;
  size_t cache_misses_ = 0;
};

}  // namespace escher

#endif  // LIB_ESCHER_UTIL_HASH_CACHE_H_