InstantExtended: Adding InstantRestrictedIDCache.

chrome/common/instant_restricted_id_cache.h

+// 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 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.
+  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().
+  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, CrazyIDGeneration);
+  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_) {

[brettw, 2013/03/20 21:53:53]

I wonder if this could be done using an MRUCache to avoid writing so much custom
logic? base/containers/mru_cache.h. It seems that this class is just an MRUCache
with key autogeneration.

[Shishir, 2013/03/20 22:10:51]

This is not a strict MRU cache, but it definitely looks like it could be done on
top of the MRUCache (thanks to the peek method), but we would still have to
write custom code to deal with ID generation. All the functions except
MaybeDropItemsFromCache will still have to be implemented. We will have the
simplicity of not having a map and a list but we would have to maintain
additional data to support the use case for GetCurrentItems.

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