// Copyright 2013 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 CHROME_RENDERER_INSTANT_RESTRICTED_ID_CACHE_H_
#define CHROME_RENDERER_INSTANT_RESTRICTED_ID_CACHE_H_

#include <stddef.h>

#include <set>
#include <utility>
#include <vector>

#include "base/check_op.h"
#include "base/containers/lru_cache.h"
#include "base/gtest_prod_util.h"
#include "chrome/common/search/instant_types.h"

// In InstantExtended, iframes are used to display objects which can only be
// referenced by the Instant page using an ID (restricted ID). These IDs need to
// be unique and cached for a while so that the SearchBox API can fetch the
// object info based on the ID when required by the Instant page. The reason to
// use a cache of N items as against just the last set of results is that there
// may be race conditions - e.g. the user clicks on a result being shown but the
// result set has internally changed but not yet been displayed.
//
// The cache can be used in two modes:
//
// 1. To store items and assign restricted IDs to them. The cache will store
//    a max of |max_cache_size_| items and assign them unique IDs.
//
// 2. To store items that already have restricted IDs assigned to them (e.g.
//    from another instance of the cache). The cache will then not generate IDs
//    and does not make any guarantees of the uniqueness of the IDs. If multiple
//    items are inserted with the same ID, the cache will return the last
//    inserted item in GetItemWithRestrictedID() call.

// T needs to be copyable.
template <typename T>
class InstantRestrictedIDCache {
 public:
  typedef std::pair<InstantRestrictedID, T> ItemIDPair;
  typedef std::vector<T> ItemVector;
  typedef std::vector<ItemIDPair> ItemIDVector;

  explicit InstantRestrictedIDCache(size_t max_cache_size);

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

  ~InstantRestrictedIDCache();

  // Adds items to the cache, assigning restricted IDs in the process. May
  // delete older items from the cache. |items.size()| has to be less than max
  // cache size.
  void AddItems(const ItemVector& items);

  // Adds items to the cache using the supplied restricted IDs. May delete
  // older items from the cache. No two entries in |items| should have the same
  // InstantRestrictedID. |items.size()| has to be less than max cache size.
  void AddItemsWithRestrictedID(const ItemIDVector& items);

  // Returns the last set of items added to the cache either via AddItems() or
  // AddItemsWithRestrictedID().
  void GetCurrentItems(ItemIDVector* items) const;

  // Returns true if the |restricted_id| is present in the cache and if so,
  // returns a copy of the item.
  bool GetItemWithRestrictedID(InstantRestrictedID restricted_id,
                               T* item) const;

 private:
  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AutoIDGeneration);
  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, CrazyIDGeneration);
  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration);
  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration);
  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AddEmptySet);
  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest,
                           AddItemsWithRestrictedID);

  typedef base::LRUCache<InstantRestrictedID, T> CacheImpl;

  mutable CacheImpl cache_;
  typename CacheImpl::reverse_iterator last_add_start_;
  InstantRestrictedID last_restricted_id_;
};

template <typename T>
InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size)
    : cache_(max_cache_size),
      last_add_start_(cache_.rend()),
      last_restricted_id_(0) {
  DCHECK(max_cache_size);
}

template <typename T>
InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() {
}

template <typename T>
void InstantRestrictedIDCache<T>::AddItems(const ItemVector& items) {
  DCHECK_LE(items.size(), cache_.max_size());

  if (items.empty()) {
    last_add_start_ = cache_.rend();
    return;
  }

  for (size_t i = 0; i < items.size(); ++i) {
    InstantRestrictedID id = ++last_restricted_id_;
    cache_.Put(id, items[i]);
    if (i == 0)
      last_add_start_ = --cache_.rend();
  }
}

template <typename T>
void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID(
    const ItemIDVector& items) {
  DCHECK_LE(items.size(), cache_.max_size());

  if (items.empty()) {
    last_add_start_ = cache_.rend();
    return;
  }

  std::set<InstantRestrictedID> ids_added;
  for (size_t i = 0; i < items.size(); ++i) {
    const ItemIDPair& item_id = items[i];

    DCHECK(ids_added.find(item_id.first) == ids_added.end());
    ids_added.insert(item_id.first);

    cache_.Put(item_id.first, item_id.second);
    last_restricted_id_ = std::max(item_id.first, last_restricted_id_);
  }

  // cache_.Put() can invalidate the iterator |last_add_start_| is pointing to.
  // Therefore, update |last_add_start_| after adding all the items to the
  // |cache_|.
  last_add_start_ = cache_.rend();
  for (size_t i = 0; i < items.size(); ++i)
    --last_add_start_;
}

template <typename T>
void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const {
  items->clear();

  for (typename CacheImpl::reverse_iterator it = last_add_start_;
       it != cache_.rend(); ++it) {
    items->push_back(std::make_pair(it->first, it->second));
  }
}

template <typename T>
bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
    InstantRestrictedID restricted_id,
    T* item) const {
  DCHECK(item);

  typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id);
  if (cache_it == cache_.end())
    return false;
  *item = cache_it->second;
  return true;
}

#endif  // CHROME_RENDERER_INSTANT_RESTRICTED_ID_CACHE_H_