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. 37 template <typename T> 38 class 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 84 template <typename T> 85 InstantRestrictedIDCache<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 92 template <typename T> 93 InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() { 94 } 95 96 template <typename T> 97 void 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 113 template <typename T> 114 void 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 142 template <typename T> 143 void 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 152 template <typename T> 153 bool 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
