Index: chrome/common/instant_restricted_id_cache.h |
diff --git a/chrome/common/instant_restricted_id_cache.h b/chrome/common/instant_restricted_id_cache.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..1bf5e47355cd53b36535ff4ffd25cdbef97c67e4 |
--- /dev/null |
+++ b/chrome/common/instant_restricted_id_cache.h |
@@ -0,0 +1,169 @@ |
+// 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. |
+ |
+#ifndef CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_ |
+#define CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_ |
+ |
+#include <algorithm> |
+#include <list> |
+#include <map> |
+#include <utility> |
+#include <vector> |
+ |
+#include "base/gtest_prod_util.h" |
+#include "base/logging.h" |
+#include "chrome/common/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 restrcited IDs assigned to them (e.g. |
sreeram
2013/03/19 21:36:17
restrcited -> restricted
Shishir
2013/03/19 22:20:20
Done.
|
+// 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 { |
+ public: |
+ typedef std::pair<InstantRestrictedID, T> ItemIDPair; |
+ typedef std::vector<T> ItemVector; |
+ typedef std::vector<ItemIDPair> ItemIDVector; |
+ |
+ explicit InstantRestrictedIDCache(size_t max_cache_size); |
+ ~InstantRestrictedIDCache(); |
+ |
+ // Adds items to the cache, assigning restricted IDs in the process. May |
+ // delete older items from the cache. |
+ void AddItems(const ItemVector& items); |
+ |
+ // Adds items to the cache using the supplied restricted IDs. May delete |
+ // older items from the cache. |
+ void AddItemsWithRestrictedID(const ItemIDVector& items); |
+ |
+ // Returns the last set of items added to the cache either via AddItems() or |
+ // AddItemsWithRestrictedId(). |
sreeram
2013/03/19 21:36:17
AddItemsWithRestrictedId -> AddItemsWithRestricted
Shishir
2013/03/19 22:20:20
Done.
|
+ 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; |
+ |
+ private: |
+ FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AdditionOverflow); |
+ FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AutoIDGeneration); |
+ FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration); |
+ FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration); |
+ |
+ typedef std::list<ItemIDPair> ItemIDList; |
+ typedef std::map<InstantRestrictedID, typename ItemIDList::iterator> |
+ ItemIDMap; |
+ |
+ // Will drop items from |cache_| if its size is greater than |
+ // |max_cache_size_|. |
+ void MaybeDropItemsFromCache(); |
+ |
+ ItemIDList cache_; |
+ ItemIDMap item_id_map_; |
+ InstantRestrictedID last_restricted_id_; |
+ typename ItemIDList::iterator last_add_start_; |
+ const size_t max_cache_size_; |
+ |
+ DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache); |
+}; |
+ |
+template <typename T> |
+InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size) |
+ : last_restricted_id_(0), |
+ last_add_start_(cache_.begin()), |
+ max_cache_size_(max_cache_size) { |
+ DCHECK(max_cache_size_); |
+} |
+ |
+template <typename T> |
+InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() { |
+} |
+ |
+template <typename T> |
+void InstantRestrictedIDCache<T>::AddItems(const ItemVector& items) { |
+ for (size_t i = 0; i < items.size(); ++i) { |
+ typename ItemIDList::iterator iter = cache_.insert( |
+ cache_.end(), |
+ std::make_pair(++last_restricted_id_, items[i])); |
+ item_id_map_[last_restricted_id_] = iter; |
+ if (i == 0) |
+ last_add_start_ = iter; |
+ } |
+ |
+ MaybeDropItemsFromCache(); |
+} |
+ |
+template <typename T> |
+void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID( |
+ const ItemIDVector& items) { |
+ for (size_t i = 0; i < items.size(); ++i) { |
+ const ItemIDPair& item_id = items[i]; |
+ typename ItemIDList::iterator iter = cache_.insert(cache_.end(), item_id); |
+ item_id_map_[item_id.first] = iter; |
+ last_restricted_id_ = std::max(item_id.first, last_restricted_id_); |
+ if (i == 0) |
+ last_add_start_ = iter; |
+ } |
+ |
+ MaybeDropItemsFromCache(); |
+} |
+ |
+template <typename T> |
+void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const { |
+ items->clear(); |
+ |
+ for (typename ItemIDList::iterator it = last_add_start_; it != cache_.end(); |
+ ++it) { |
+ items->push_back(*it); |
+ } |
+} |
+ |
+template <typename T> |
+bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID( |
+ InstantRestrictedID restricted_id, |
+ T* item) const { |
+ DCHECK(item); |
+ |
+ typename ItemIDMap::const_iterator iter = item_id_map_.find(restricted_id); |
+ if (iter == item_id_map_.end()) |
+ return false; |
+ |
+ *item = (*(iter->second)).second; |
+ return true; |
+} |
+ |
+template <typename T> |
+void InstantRestrictedIDCache<T>::MaybeDropItemsFromCache() { |
+ while (cache_.size() > max_cache_size_) { |
+ typename ItemIDList::iterator begin = cache_.begin(); |
+ |
+ typename ItemIDMap::iterator iter = item_id_map_.find(begin->first); |
+ if (iter != item_id_map_.end() && iter->second == begin) |
+ item_id_map_.erase(begin->first); |
+ |
+ if (last_add_start_ == begin) |
+ ++last_add_start_; |
+ |
+ cache_.pop_front(); |
+ } |
+} |
+ |
+#endif // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_ |