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