Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(3301)

Unified Diff: chrome/common/instant_restricted_id_cache.h

Issue 12498002: InstantExtended: Adding InstantRestrictedIDCache. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Merging conflicts. Created 7 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
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_

Powered by Google App Engine
This is Rietveld 408576698