blob: 3062768bc22980cdd2c1adb64f16cdab22d235d3 [file] [log] [blame]
// 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.
#include <stddef.h>
#include <set>
#include <utility>
#include <vector>
#include "base/containers/mru_cache.h"
#include "base/gtest_prod_util.h"
#include "base/logging.h"
#include "base/macros.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 {
typedef std::pair<InstantRestrictedID, T> ItemIDPair;
typedef std::vector<T> ItemVector;
typedef std::vector<ItemIDPair> ItemIDVector;
explicit InstantRestrictedIDCache(size_t max_cache_size);
// 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;
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);
typedef base::MRUCache<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_restricted_id_(0) {
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();
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();
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());
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)
template <typename T>
void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const {
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 {
typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id);
if (cache_it == cache_.end())
return false;
*item = cache_it->second;
return true;