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 <deque>
+#include <map>
+#include <utility>
+#include <vector>
+
+#include "base/gtest_prod_util.h"
+#include "base/logging.h"
+#include "base/stl_util.h"
+#include "chrome/common/instant_types.h"
+#include "content/public/common/page_transition_types.h"

[dhollowa, 2013/03/14 00:02:43]

Needed?

[Shishir, 2013/03/14 19:53:03]

Done.

+#include "googleurl/src/gurl.h"
+
+// In InstantExtended, iframes are used to display objects which can only be

[dhollowa, 2013/03/14 00:02:43]

Not only iframes, but Most Visited information.  It would be good also to note
that these iframes are used to display the Instant suggestions.

[Shishir, 2013/03/14 19:53:03]

Even the Most visited Items is moving to iframes shortly.

[dhollowa, 2013/03/14 23:40:00]

Ya, but the MV items will still have IDs for the thumbnail urls, no?  The
iframes won't have src=chrome://... right?  So they'll still need
thumbnails/favicons of the form src=chrome-search://thumb/<id>, correct?

+// referred 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.
+//
+// This "cache" class is used for assigning restricted IDs to objects, storing
+// the last N items and retreiving them using the IDs when necessary. Objects
+// can also be added which already have IDs assigned, but the caller has to

[dhollowa, 2013/03/14 00:02:43]

"but the caller has to ensure that the IDs do not repeat."  This is not
super-clear.  How would I do this as a caller?  Especially when the core purpose
of this class is to assign/generate IDs for me?

[Shishir, 2013/03/14 19:53:03]

Done.

+// ensure that the IDs do not repeat. In case IDs are repeated, the last added
+// object with the ID will be returned.
+
+// T needs to be copyable.
+template <typename T>
+class InstantRestrictedIDCache {
+ public:
+  typedef std::pair<InstantRestrictedID, T> RestrictedIDItemPair;
+
+  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 std::vector<T>& items);
+
+  // Adds items to the cache using the supplied restricted IDs. May delete

[dhollowa, 2013/03/14 00:02:43]

The "May delete..." aspect of this has me a bit worried.  Are we relying on the
size of the cache and probabilistic behavior to avoid the race of using a stale
ID before the new data has fully propagated?

This seems pretty central to the reason-for-existence of this cache so should be
documented at the top.

[Shishir, 2013/03/14 19:53:03]

Yes the cache is to avoid races. Added comment to top.

+  // older items from the cache.
+  void AddItemsWithRestrictedID(const std::vector<RestrictedIDItemPair>& items);
+
+  // Returns the last set of items added to the cache either via |AddItems| or
+  // |AddItemsWithRestrictedId|.
+  void GetCurrentItems(std::vector<RestrictedIDItemPair>* 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,

[dhollowa, 2013/03/14 00:02:43]

This searches ALL items, not just "current" items, correct?  Please add a note
to that effect.

[Shishir, 2013/03/14 19:53:03]

Isnt this explained because we say "in the cache"?

[dhollowa, 2013/03/14 23:40:00]

Ok.

+                               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);
+
+  // Will drop items from |cache_| if its size is greater than
+  // |max_cache_size_|.
+  void MaybeDropItemsFromCache();
+
+  std::deque<RestrictedIDItemPair*> cache_;
+  STLElementDeleter<std::deque<RestrictedIDItemPair*> > cache_deleter_;
+  std::map<InstantRestrictedID, RestrictedIDItemPair*> restricted_id_item_map_;
+  InstantRestrictedID last_restricted_id_;
+  size_t last_addition_size_;  // The number of items added last.
+  const size_t max_cache_size_;
+
+  DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache);
+};
+
+template <typename T>
+InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size)
+    : cache_deleter_(&cache_),
+      last_restricted_id_(0),
+      last_addition_size_(0),
+      max_cache_size_(max_cache_size) {
+  DCHECK(max_cache_size_);
+}
+
+template <typename T>
+InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() {
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::AddItems(const std::vector<T>& items) {
+  for (typename std::vector<T>::const_iterator it = items.begin();
+       it != items.end(); ++it) {
+    RestrictedIDItemPair* to_add = new RestrictedIDItemPair(
+        ++last_restricted_id_, *it);
+    cache_.push_back(to_add);
+    restricted_id_item_map_[last_restricted_id_] = to_add;
+  }
+  last_addition_size_ = items.size();
+  MaybeDropItemsFromCache();
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID(
+    const std::vector<RestrictedIDItemPair>& items) {
+  for (typename std::vector<RestrictedIDItemPair>::const_iterator it =

[palmer, 2013/03/13 23:50:37]

NIT: I might make a more friendly-looking typedef for
std::vector<RestrictedIDItemPair>::const_iterator.

[Shishir, 2013/03/14 19:53:03]

Done.

+          items.begin(); it != items.end(); ++it) {
+    RestrictedIDItemPair* to_add = new RestrictedIDItemPair(*it);
+    cache_.push_back(to_add);
+    restricted_id_item_map_[it->first] = to_add;
+    last_restricted_id_ = std::max(it->first, last_restricted_id_);
+  }
+  last_addition_size_ = items.size();
+  MaybeDropItemsFromCache();
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::GetCurrentItems(
+    std::vector<RestrictedIDItemPair>* items) const {
+  items->clear();
+
+  if (last_addition_size_ == 0)
+    return;
+
+  int start = std::max(0, static_cast<int>(cache_.size() -
+                                           last_addition_size_));
+  for (int i = start; i < static_cast<int>(cache_.size()); ++i) {

[palmer, 2013/03/13 23:50:37]

static_cast is a sign that |start| and |i| should be size_t. :) And above too,
in the call to std::max.

[Shishir, 2013/03/14 19:53:03]

Like my comment from base/basictypes, we should be using ints in loops.

+    items->push_back(*(cache_[i]));
+  }
+}
+
+template <typename T>
+bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
+    InstantRestrictedID restricted_id,
+    T* item) const {
+  DCHECK(item);
+
+  typename std::map<InstantRestrictedID, RestrictedIDItemPair*>::const_iterator

[palmer, 2013/03/13 23:50:37]

NIT: Consider a friendly typedef here too.

[Shishir, 2013/03/14 19:53:03]

Done.

+      iter = restricted_id_item_map_.find(restricted_id);
+  if (iter == restricted_id_item_map_.end())
+    return false;
+
+  *item = iter->second->second;
+  return true;
+}
+
+template <typename T>
+void InstantRestrictedIDCache<T>::MaybeDropItemsFromCache() {
+  while (cache_.size() > max_cache_size_) {
+    RestrictedIDItemPair* to_erase = cache_.front();
+
+    typename std::map<InstantRestrictedID, RestrictedIDItemPair*>::iterator
+        iter = restricted_id_item_map_.find(to_erase->first);
+    if (iter != restricted_id_item_map_.end() && iter->second == to_erase)
+      restricted_id_item_map_.erase(to_erase->first);
+
+    cache_.pop_front();
+    delete to_erase;
+  }
+}
+
+#endif  // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_