chrome/common/instant_restricted_id_cache.h

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
   6 #define CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
   7
   8 #include <set>
   9 #include <utility>
  10 #include <vector>
  11
  12 #include "base/containers/mru_cache.h"
  13 #include "base/gtest_prod_util.h"
  14 #include "base/logging.h"
  15 #include "chrome/common/instant_types.h"
  16
  17 // In InstantExtended, iframes are used to display objects which can only be
  18 // referenced by the Instant page using an ID (restricted ID). These IDs need to
  19 // be unique and cached for a while so that the SearchBox API can fetch the
  20 // object info based on the ID when required by the Instant page. The reason to
  21 // use a cache of N items as against just the last set of results is that there
  22 // may be race conditions - e.g. the user clicks on a result being shown but the
  23 // result set has internally changed but not yet been displayed.
  24 //
  25 // The cache can be used in two modes:
  26 //
  27 // 1. To store items and assign restricted IDs to them. The cache will store
  28 //    a max of |max_cache_size_| items and assign them unique IDs.
  29 //
  30 // 2. To store items that already have restricted IDs assigned to them (e.g.
  31 //    from another instance of the cache). The cache will then not generate IDs
  32 //    and does not make any guarantees of the uniqueness of the IDs. If multiple
  33 //    items are inserted with the same ID, the cache will return the last
  34 //    inserted item in GetItemWithRestrictedID() call.
  35
  36 // T needs to be copyable.
  37 template <typename T>
  38 class InstantRestrictedIDCache {
  39  public:
  40   typedef std::pair<InstantRestrictedID, T> ItemIDPair;
  41   typedef std::vector<T> ItemVector;
  42   typedef std::vector<ItemIDPair> ItemIDVector;
  43
  44   explicit InstantRestrictedIDCache(size_t max_cache_size);
  45   ~InstantRestrictedIDCache();
  46
  47   // Adds items to the cache, assigning restricted IDs in the process. May
  48   // delete older items from the cache. |items.size()| has to be less than max
  49   // cache size.
  50   void AddItems(const ItemVector& items);
  51
  52   // Adds items to the cache using the supplied restricted IDs. May delete
  53   // older items from the cache. No two entries in |items| should have the same
  54   // InstantRestrictedID. |items.size()| has to be less than max cache size.
  55   void AddItemsWithRestrictedID(const ItemIDVector& items);
  56
  57   // Returns the last set of items added to the cache either via AddItems() or
  58   // AddItemsWithRestrictedID().
  59   void GetCurrentItems(ItemIDVector* items) const;
  60
  61   // Returns true if the |restricted_id| is present in the cache and if so,
  62   // returns a copy of the item.
  63   bool GetItemWithRestrictedID(InstantRestrictedID restricted_id,
  64                                T* item) const;
  65
  66  private:
  67   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AutoIDGeneration);
  68   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, CrazyIDGeneration);
  69   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration);
  70   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration);
  71   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AddEmptySet);
  72   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest,
  73                            AddItemsWithRestrictedID);
  74
  75   typedef base::MRUCache<InstantRestrictedID, T> CacheImpl;
  76
  77   mutable CacheImpl cache_;
  78   typename CacheImpl::reverse_iterator last_add_start_;
  79   InstantRestrictedID last_restricted_id_;
  80
  81   DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache);
  82 };
  83
  84 template <typename T>
  85 InstantRestrictedIDCache<T>::InstantRestrictedIDCache(size_t max_cache_size)
  86     : cache_(max_cache_size),
  87       last_add_start_(cache_.rend()),
  88       last_restricted_id_(0) {
  89   DCHECK(max_cache_size);
  90 }
  91
  92 template <typename T>
  93 InstantRestrictedIDCache<T>::~InstantRestrictedIDCache() {
  94 }
  95
  96 template <typename T>
  97 void InstantRestrictedIDCache<T>::AddItems(const ItemVector& items) {
  98   DCHECK_LE(items.size(), cache_.max_size());
  99
 100   if (items.empty()) {
 101     last_add_start_ = cache_.rend();
 102     return;
 103   }
 104
 105   for (size_t i = 0; i < items.size(); ++i) {
 106     InstantRestrictedID id = ++last_restricted_id_;
 107     cache_.Put(id, items[i]);
 108     if (i == 0)
 109       last_add_start_ = --cache_.rend();
 110   }
 111 }
 112
 113 template <typename T>
 114 void InstantRestrictedIDCache<T>::AddItemsWithRestrictedID(
 115     const ItemIDVector& items) {
 116   DCHECK_LE(items.size(), cache_.max_size());
 117
 118   if (items.empty()) {
 119     last_add_start_ = cache_.rend();
 120     return;
 121   }
 122
 123   std::set<InstantRestrictedID> ids_added;
 124   for (size_t i = 0; i < items.size(); ++i) {
 125     const ItemIDPair& item_id = items[i];
 126
 127     DCHECK(ids_added.find(item_id.first) == ids_added.end());
 128     ids_added.insert(item_id.first);
 129
 130     cache_.Put(item_id.first, item_id.second);
 131     last_restricted_id_ = std::max(item_id.first, last_restricted_id_);
 132   }
 133
 134   // cache_.Put() can invalidate the iterator |last_add_start_| is pointing to.
 135   // Therefore, update |last_add_start_| after adding all the items to the
 136   // |cache_|.
 137   last_add_start_ = cache_.rend();
 138   for (size_t i = 0; i < items.size(); ++i)
 139     --last_add_start_;
 140 }
 141
 142 template <typename T>
 143 void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const {
 144   items->clear();
 145
 146   for (typename CacheImpl::reverse_iterator it = last_add_start_;
 147        it != cache_.rend(); ++it) {
 148     items->push_back(std::make_pair(it->first, it->second));
 149   }
 150 }
 151
 152 template <typename T>
 153 bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
 154     InstantRestrictedID restricted_id,
 155     T* item) const {
 156   DCHECK(item);
 157
 158   typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id);
 159   if (cache_it == cache_.end())
 160     return false;
 161   *item = cache_it->second;
 162   return true;
 163 }
 164
 165 #endif  // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_