InstantExtended: Adding InstantRestrictedIDCache for caching and looking up restricted IDs.

In InstantExtended, cross origin 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 and cached for a while so that the SearchBox API can
fetch the object info based on the ID. The reason to use a cache of N items as
against just the last set of results is that there may be race conditions
between the internal state of the SearchBox and the data being displayed.

This CL introduces a template class InstantRestrictedIDCache that can be used
to generate the restricted IDs for objects, cache them and fetch objects based
on the IDs.


BUG=181870

Review URL: https://chromiumcodereview.appspot.com/12498002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@190052 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 149 insertions, 0 deletions

diff --git a/chrome/common/instant_restricted_id_cache.h b/chrome/common/instant_restricted_id_cache.h
new file mode 100644
index 0000000..66ae060
--- /dev/null
+++ b/chrome/common/instant_restricted_id_cache.h
@@ -0,0 +1,149 @@
+// 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 <set>
+#include <utility>
+#include <vector>
+
+#include "base/containers/mru_cache.h"
+#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 restricted IDs assigned to them (e.g.
+//    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. |items.size()| has to be less than max
+  // cache size.
+  void AddItems(const ItemVector& items);
+
+  // Adds items to the cache using the supplied restricted IDs. May delete
+  // older items from the cache. No two entries in |items| should have the same
+  // InstantRestrictedID. |items.size()| has to be less than max cache size.
+  void AddItemsWithRestrictedID(const ItemIDVector& items);
+
+  // Returns the last set of items added to the cache either via AddItems() or
+  // AddItemsWithRestrictedID().
+  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, AutoIDGeneration);
+  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, CrazyIDGeneration);
+  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration);
+  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration);
+
+  typedef base::MRUCache<InstantRestrictedID, T> CacheImpl;
+
+  mutable CacheImpl cache_;
+  typename CacheImpl::reverse_iterator last_add_start_;
+  InstantRestrictedID last_restricted_id_;
+
+  DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache);
+};
+
+template <typename T>
+InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size)
+    : cache_(max_cache_size),
+      last_add_start_(cache_.rend()),
+      last_restricted_id_(0) {
+  DCHECK(max_cache_size);
+}
+
+template <typename T>
+InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() {
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::AddItems(const ItemVector& items) {
+  if (items.size() == 0 || items.size() > cache_.max_size())
+    return;
+
+  for (size_t i = 0; i < items.size(); ++i) {
+    InstantRestrictedID id = ++last_restricted_id_;
+    cache_.Put(id, items[i]);
+    if (i == 0)
+      last_add_start_ = --cache_.rend();
+  }
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID(
+    const ItemIDVector& items) {
+  if (items.size() == 0 || items.size() > cache_.max_size())
+    return;
+
+  std::set<InstantRestrictedID> ids_added;
+  for (size_t i = 0; i < items.size(); ++i) {
+    const ItemIDPair& item_id = items[i];
+
+    DCHECK(ids_added.find(item_id.first) == ids_added.end());
+    ids_added.insert(item_id.first);
+
+    cache_.Put(item_id.first, item_id.second);
+    if (i == 0)
+      last_add_start_ = --cache_.rend();
+    last_restricted_id_ = std::max(item_id.first, last_restricted_id_);
+  }
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const {
+  items->clear();
+
+  for (typename CacheImpl::reverse_iterator it = last_add_start_;
+       it != cache_.rend(); ++it) {
+    items->push_back(std::make_pair(it->first, it->second));
+  }
+}
+
+template <typename T>
+bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
+    InstantRestrictedID restricted_id,
+    T* item) const {
+  DCHECK(item);
+
+  typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id);
+  if (cache_it == cache_.end())
+    return false;
+  *item = cache_it->second;
+  return true;
+}
+
+#endif  // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_