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 <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 {

[palmer, 2013/03/21 22:58:04]

This seems large and inefficient. The contract described in the documentation
could be implemented with a thin wrapper around a std::vector<T>, as far as I
can tell. Dumb linear search doesn't really get bad until max_cache_size gets
bigger than this class' callers intend, as far as I understand. Do we intend to
store more than, say, 100 items in this cache?

[Shishir, 2013/03/21 23:38:41]

The class did start off being a wrapper over a list and evolved to use the
MRUCache which as brett pointed out did much of what we need. Give that we will
be storing 100 elements at max, and the extra memory is a map with 100 ints and
iterators, is it very inefficient? Are we really worried about the memory
overhead here?

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