1// Copyright 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
6#define CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
7
8#include <set>
9#include <utility>
10#include <vector>
11
12#include "base/containers/mru_cache.h"
13#include "base/gtest_prod_util.h"
14#include "base/logging.h"
15#include "chrome/common/instant_types.h"
16
17// In InstantExtended, iframes are used to display objects which can only be
18// referenced by the Instant page using an ID (restricted ID). These IDs need to
19// be unique and cached for a while so that the SearchBox API can fetch the
20// object info based on the ID when required by the Instant page. The reason to
21// use a cache of N items as against just the last set of results is that there
22// may be race conditions - e.g. the user clicks on a result being shown but the
23// result set has internally changed but not yet been displayed.
24//
25// The cache can be used in two modes:
26//
27// 1. To store items and assign restricted IDs to them. The cache will store
28//    a max of |max_cache_size_| items and assign them unique IDs.
29//
30// 2. To store items that already have restricted IDs assigned to them (e.g.
31//    from another instance of the cache). The cache will then not generate IDs
32//    and does not make any guarantees of the uniqueness of the IDs. If multiple
33//    items are inserted with the same ID, the cache will return the last
34//    inserted item in GetItemWithRestrictedID() call.
35
36// T needs to be copyable.
37template <typename T>
38class InstantRestrictedIDCache {
39 public:
40  typedef std::pair<InstantRestrictedID, T> ItemIDPair;
41  typedef std::vector<T> ItemVector;
42  typedef std::vector<ItemIDPair> ItemIDVector;
43
44  explicit InstantRestrictedIDCache(size_t max_cache_size);
45  ~InstantRestrictedIDCache();
46
47  // Adds items to the cache, assigning restricted IDs in the process. May
48  // delete older items from the cache. |items.size()| has to be less than max
49  // cache size.
50  void AddItems(const ItemVector& items);
51
52  // Adds items to the cache using the supplied restricted IDs. May delete
53  // older items from the cache. No two entries in |items| should have the same
54  // InstantRestrictedID. |items.size()| has to be less than max cache size.
55  void AddItemsWithRestrictedID(const ItemIDVector& items);
56
57  // Returns the last set of items added to the cache either via AddItems() or
58  // AddItemsWithRestrictedID().
59  void GetCurrentItems(ItemIDVector* items) const;
60
61  // Returns true if the |restricted_id| is present in the cache and if so,
62  // returns a copy of the item.
63  bool GetItemWithRestrictedID(InstantRestrictedID restricted_id,
64                               T* item) const;
65
66 private:
67  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AutoIDGeneration);
68  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, CrazyIDGeneration);
69  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration);
70  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration);
71  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AddEmptySet);
72  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest,
73                           AddItemsWithRestrictedID);
74
75  typedef base::MRUCache<InstantRestrictedID, T> CacheImpl;
76
77  mutable CacheImpl cache_;
78  typename CacheImpl::reverse_iterator last_add_start_;
79  InstantRestrictedID last_restricted_id_;
80
81  DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache);
82};
83
84template <typename T>
85InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size)
86    : cache_(max_cache_size),
87      last_add_start_(cache_.rend()),
88      last_restricted_id_(0) {
89  DCHECK(max_cache_size);
90}
91
92template <typename T>
93InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() {
94}
95
96template <typename T>
97void InstantRestrictedIDCache<T>::AddItems(const ItemVector& items) {
98  DCHECK_LE(items.size(), cache_.max_size());
99
100  if (items.empty()) {
101    last_add_start_ = cache_.rend();
102    return;
103  }
104
105  for (size_t i = 0; i < items.size(); ++i) {
106    InstantRestrictedID id = ++last_restricted_id_;
107    cache_.Put(id, items[i]);
108    if (i == 0)
109      last_add_start_ = --cache_.rend();
110  }
111}
112
113template <typename T>
114void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID(
115    const ItemIDVector& items) {
116  DCHECK_LE(items.size(), cache_.max_size());
117
118  if (items.empty()) {
119    last_add_start_ = cache_.rend();
120    return;
121  }
122
123  std::set<InstantRestrictedID> ids_added;
124  for (size_t i = 0; i < items.size(); ++i) {
125    const ItemIDPair& item_id = items[i];
126
127    DCHECK(ids_added.find(item_id.first) == ids_added.end());
128    ids_added.insert(item_id.first);
129
130    cache_.Put(item_id.first, item_id.second);
131    last_restricted_id_ = std::max(item_id.first, last_restricted_id_);
132  }
133
134  // cache_.Put() can invalidate the iterator |last_add_start_| is pointing to.
135  // Therefore, update |last_add_start_| after adding all the items to the
136  // |cache_|.
137  last_add_start_ = cache_.rend();
138  for (size_t i = 0; i < items.size(); ++i)
139    --last_add_start_;
140}
141
142template <typename T>
143void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const {
144  items->clear();
145
146  for (typename CacheImpl::reverse_iterator it = last_add_start_;
147       it != cache_.rend(); ++it) {
148    items->push_back(std::make_pair(it->first, it->second));
149  }
150}
151
152template <typename T>
153bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
154    InstantRestrictedID restricted_id,
155    T* item) const {
156  DCHECK(item);
157
158  typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id);
159  if (cache_it == cache_.end())
160    return false;
161  *item = cache_it->second;
162  return true;
163}
164
165#endif  // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
166