InstantExtended: Adding InstantRestrictedIDCache.

chrome/common/instant_restricted_id_cache.h

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..66ae060a754be541c57df73a9230ad069c903ab8
--- /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_