12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file. 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_ 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <set> 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <utility> 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <vector> 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/containers/mru_cache.h" 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/gtest_prod_util.h" 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/logging.h" 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "chrome/common/instant_types.h" 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// In InstantExtended, iframes are used to display objects which can only be 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// referenced by the Instant page using an ID (restricted ID). These IDs need to 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// be unique and cached for a while so that the SearchBox API can fetch the 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// object info based on the ID when required by the Instant page. The reason to 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// use a cache of N items as against just the last set of results is that there 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// may be race conditions - e.g. the user clicks on a result being shown but the 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// result set has internally changed but not yet been displayed. 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The cache can be used in two modes: 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 1. To store items and assign restricted IDs to them. The cache will store 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// a max of |max_cache_size_| items and assign them unique IDs. 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 2. To store items that already have restricted IDs assigned to them (e.g. 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// from another instance of the cache). The cache will then not generate IDs 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// and does not make any guarantees of the uniqueness of the IDs. If multiple 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// items are inserted with the same ID, the cache will return the last 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// inserted item in GetItemWithRestrictedID() call. 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// T needs to be copyable. 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class InstantRestrictedIDCache { 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public: 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::pair<InstantRestrictedID, T> ItemIDPair; 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<T> ItemVector; 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef std::vector<ItemIDPair> ItemIDVector; 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) explicit InstantRestrictedIDCache(size_t max_cache_size); 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~InstantRestrictedIDCache(); 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Adds items to the cache, assigning restricted IDs in the process. May 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // delete older items from the cache. |items.size()| has to be less than max 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // cache size. 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void AddItems(const ItemVector& items); 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Adds items to the cache using the supplied restricted IDs. May delete 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // older items from the cache. No two entries in |items| should have the same 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // InstantRestrictedID. |items.size()| has to be less than max cache size. 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void AddItemsWithRestrictedID(const ItemIDVector& items); 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns the last set of items added to the cache either via AddItems() or 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // AddItemsWithRestrictedID(). 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) void GetCurrentItems(ItemIDVector* items) const; 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Returns true if the |restricted_id| is present in the cache and if so, 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // returns a copy of the item. 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool GetItemWithRestrictedID(InstantRestrictedID restricted_id, 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* item) const; 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) private: 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AutoIDGeneration); 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, CrazyIDGeneration); 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration); 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration); 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AddEmptySet); 72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, 73868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) AddItemsWithRestrictedID); 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typedef base::MRUCache<InstantRestrictedID, T> CacheImpl; 762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) mutable CacheImpl cache_; 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename CacheImpl::reverse_iterator last_add_start_; 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InstantRestrictedID last_restricted_id_; 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache); 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size) 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) : cache_(max_cache_size), 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_add_start_(cache_.rend()), 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_restricted_id_(0) { 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(max_cache_size); 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() { 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void InstantRestrictedIDCache<T>::AddItems(const ItemVector& items) { 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_LE(items.size(), cache_.max_size()); 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (items.empty()) { 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_add_start_ = cache_.rend(); 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < items.size(); ++i) { 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InstantRestrictedID id = ++last_restricted_id_; 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cache_.Put(id, items[i]); 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (i == 0) 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_add_start_ = --cache_.rend(); 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID( 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const ItemIDVector& items) { 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK_LE(items.size(), cache_.max_size()); 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (items.empty()) { 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_add_start_ = cache_.rend(); 1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::set<InstantRestrictedID> ids_added; 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (size_t i = 0; i < items.size(); ++i) { 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const ItemIDPair& item_id = items[i]; 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(ids_added.find(item_id.first) == ids_added.end()); 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ids_added.insert(item_id.first); 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cache_.Put(item_id.first, item_id.second); 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) last_restricted_id_ = std::max(item_id.first, last_restricted_id_); 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 133868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 134868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // cache_.Put() can invalidate the iterator |last_add_start_| is pointing to. 135868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Therefore, update |last_add_start_| after adding all the items to the 136868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // |cache_|. 137868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) last_add_start_ = cache_.rend(); 138868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) for (size_t i = 0; i < items.size(); ++i) 139868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) --last_add_start_; 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const { 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) items->clear(); 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (typename CacheImpl::reverse_iterator it = last_add_start_; 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) it != cache_.rend(); ++it) { 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) items->push_back(std::make_pair(it->first, it->second)); 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template <typename T> 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID( 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) InstantRestrictedID restricted_id, 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T* item) const { 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) DCHECK(item); 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id); 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (cache_it == cache_.end()) 1602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 1612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) *item = cache_it->second; 1622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 1632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_ 166