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..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 -> AddItemsWithRestrictedID

[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_