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..9a4e8a5b549499bb0f6d8cfda4fd16f25f2f4fab
--- /dev/null
+++ b/chrome/common/instant_restricted_id_cache.h
@@ -0,0 +1,171 @@
+// 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 "googleurl/src/gurl.h"
+
+// In InstantExtended, iframes are used to display objects which can only be
+// referred by the Instant page using an ID (restricted ID). These IDs need to

[sreeram, 2013/03/14 23:05:36]

referred by -> referred to by
or
referred by -> referenced by

[Shishir, 2013/03/15 17:31:15]

Done.

+// 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 aginst just the last set of results is that there

[sreeram, 2013/03/14 23:05:36]

aginst -> against

[Shishir, 2013/03/15 17:31:15]

Done.

+// 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 restrcited IDs to them. The cache will store

[sreeram, 2013/03/14 23:05:36]

restrcited -> restricted

[Shishir, 2013/03/15 17:31:15]

Done.

+//    a max of |max_cache_size_| items and assign them unique ids.

[sreeram, 2013/03/14 23:05:36]

ids -> IDs

[Shishir, 2013/03/15 17:31:15]

Done.

+//
+// 2. To store items that already have restrcited IDs assigned to them (like

[sreeram, 2013/03/14 23:05:36]

restrcited -> restricted
(like -> (e.g.,

[Shishir, 2013/03/15 17:31:15]

Sorry, new keyboard!

+//    from another instance of the cache). The cache will then not generate IDs
+//    and does not make any garantees of the uniqueness of the IDs. If multiple

[sreeram, 2013/03/14 23:05:36]

garantees -> guarantees

[Shishir, 2013/03/15 17:31:15]

Done.

+//    items are inserted with the same ID, the cahce

[sreeram, 2013/03/14 23:05:36]

cahce -> cache
... rest of the comment?

[Shishir, 2013/03/15 17:31:15]

Done.

+
+// 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/14 23:05:36]

|AddItems| -> AddItems()
|AddItemsWithRestrictedId| -> AddItemsWithRestrictedID()

(pipes are only for parameters and data members, not functions/methods or class
names.)

[Shishir, 2013/03/15 17:31:15]

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::map<InstantRestrictedID, ItemIDPair*> ItemIDMap;
+
+  // Will drop items from |cache_| if its size is greater than
+  // |max_cache_size_|.
+  void MaybeDropItemsFromCache();
+
+  std::deque<ItemIDPair*> cache_;

[sreeram, 2013/03/14 23:05:36]

std::list<ItemIDPair> seems like a better choice here.

[Shishir, 2013/03/15 17:31:15]

There was array access requirement when this CL started, which isnt present now.
Changed to list.

+  STLElementDeleter<std::deque<ItemIDPair*> > cache_deleter_;

[sreeram, 2013/03/14 23:05:36]

This doesn't seem necessary. If you want to ensure that stuff gets deleted, you
can do so in the destructor. No?

[Shishir, 2013/03/15 17:31:15]

Can do that too. But this is an equally good approach, NO?

+  std::map<InstantRestrictedID, ItemIDPair*> restricted_id_item_map_;

[sreeram, 2013/03/14 23:05:36]

ItemIDMap item_id_map_;

[Shishir, 2013/03/15 17:31:15]

Done.

+  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 ItemVector& items) {
+  for (typename ItemVector::const_iterator it = items.begin();
+       it != items.end(); ++it) {
+    ItemIDPair* to_add = new ItemIDPair(++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 ItemIDVector& items) {
+  for (typename ItemIDVector::const_iterator it = items.begin();
+       it != items.end(); ++it) {
+    ItemIDPair* to_add = new ItemIDPair(*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(ItemIDVector* 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) {
+    items->push_back(*(cache_[i]));
+  }
+}
+
+template <typename T>
+bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
+    InstantRestrictedID restricted_id,
+    T* item) const {
+  DCHECK(item);
+
+  typename ItemIDMap::const_iterator 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_) {
+    ItemIDPair* to_erase = cache_.front();
+
+    typename ItemIDMap::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_