InstantExtended: Adding InstantRestrictedIDCache for caching and looking up restricted IDs.

In InstantExtended, cross origin 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 and cached for a while so that the SearchBox API can
fetch the object info based on the ID. The reason to use a cache of N items as
against just the last set of results is that there may be race conditions
between the internal state of the SearchBox and the data being displayed.

This CL introduces a template class InstantRestrictedIDCache that can be used
to generate the restricted IDs for objects, cache them and fetch objects based
on the IDs.


BUG=181870

Review URL: https://chromiumcodereview.appspot.com/12498002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@190052 0039d316-1c4b-4281-b951-d872f2087c98

18 files changed, 758 insertions, 317 deletions

diff --git a/chrome/browser/search/instant_io_context.cc b/chrome/browser/search/instant_io_context.cc
index ad813ea..ba1dc3f 100644
--- a/chrome/browser/search/instant_io_context.cc
+++ b/chrome/browser/search/instant_io_context.cc
@@ -35,7 +35,8 @@ InstantIOContext* GetDataForRequest(const net::URLRequest* request) {
 
 const char InstantIOContext::kInstantIOContextKeyName[] = "instant_io_context";
 
-InstantIOContext::InstantIOContext() {
+InstantIOContext::InstantIOContext()
+    : most_visited_item_cache_(kMaxInstantMostVisitedItemCacheSize) {
   // The InstantIOContext is created on the UI thread but is accessed
   // on the IO thread.
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
@@ -75,29 +76,13 @@ void InstantIOContext::ClearInstantProcessesOnIO(
 }
 
 // static
-void InstantIOContext::AddMostVisitedItemIDOnIO(
+void InstantIOContext::AddMostVisitedItemsOnIO(
     scoped_refptr<InstantIOContext> instant_io_context,
-    uint64 most_visited_item_id, const GURL& url) {
+    std::vector<InstantMostVisitedItemIDPair> items) {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO));
-  instant_io_context->most_visited_item_id_to_url_map_[most_visited_item_id] =
-      url;
+  instant_io_context->most_visited_item_cache_.AddItemsWithRestrictedID(items);
 }
 
-// static
-void InstantIOContext::DeleteMostVisitedURLsOnIO(
-    scoped_refptr<InstantIOContext> instant_io_context,
-    std::vector<uint64> deleted_ids, bool all_history) {
-  if (all_history) {
-    instant_io_context->most_visited_item_id_to_url_map_.clear();
-    return;
-  }
-
-  for (size_t i = 0; i < deleted_ids.size(); ++i) {
-    instant_io_context->most_visited_item_id_to_url_map_.erase(
-        instant_io_context->most_visited_item_id_to_url_map_.find(
-            deleted_ids[i]));
-  }
-}
 
 // static
 bool InstantIOContext::ShouldServiceRequest(const net::URLRequest* request) {
@@ -119,9 +104,9 @@ bool InstantIOContext::ShouldServiceRequest(const net::URLRequest* request) {
 }
 
 // static
-bool InstantIOContext::GetURLForMostVisitedItemId(
+bool InstantIOContext::GetURLForMostVisitedItemID(
     const net::URLRequest* request,
-    uint64 most_visited_item_id,
+    InstantRestrictedID most_visited_item_id,
     GURL* url) {
   InstantIOContext* instant_io_context = GetDataForRequest(request);
   if (!instant_io_context) {
@@ -129,7 +114,7 @@ bool InstantIOContext::GetURLForMostVisitedItemId(
     return false;
   }
 
-  return instant_io_context->GetURLForMostVisitedItemId(most_visited_item_id,
+  return instant_io_context->GetURLForMostVisitedItemID(most_visited_item_id,
                                                         url);
 }
 
@@ -138,14 +123,16 @@ bool InstantIOContext::IsInstantProcess(int process_id) const {
   return process_ids_.count(process_id) != 0;
 }
 
-bool InstantIOContext::GetURLForMostVisitedItemId(uint64 most_visited_item_id,
-                                                  GURL* url) {
-  std::map<uint64, GURL>::iterator it =
-      most_visited_item_id_to_url_map_.find(most_visited_item_id);
-  if (it != most_visited_item_id_to_url_map_.end()) {
-    *url = it->second;
+bool InstantIOContext::GetURLForMostVisitedItemID(
+    InstantRestrictedID most_visited_item_id,
+    GURL* url) const {
+  InstantMostVisitedItem item;
+  if (most_visited_item_cache_.GetItemWithRestrictedID(most_visited_item_id,
+                                                       &item)) {
+    *url = item.url;
     return true;
   }
+
   *url = GURL();
   return false;
 }
diff --git a/chrome/browser/search/instant_io_context.h b/chrome/browser/search/instant_io_context.h
index c9357b6..d061fa88 100644
--- a/chrome/browser/search/instant_io_context.h
+++ b/chrome/browser/search/instant_io_context.h
@@ -11,6 +11,7 @@
 
 #include "base/basictypes.h"
 #include "base/memory/ref_counted.h"
+#include "chrome/common/instant_restricted_id_cache.h"
 
 class GURL;
 
@@ -51,26 +52,20 @@ class InstantIOContext : public base::RefCountedThreadSafe<InstantIOContext> {
       scoped_refptr<InstantIOContext> instant_io_context);
 
   // Associates the |most_visited_item_id| with the |url|.
-  static void AddMostVisitedItemIDOnIO(
+  static void AddMostVisitedItemsOnIO(
       scoped_refptr<InstantIOContext> instant_io_context,
-      uint64 most_visited_item_id, const GURL& url);
-
-  // Deletes the Most Visited item IDs contained in |deleted_ids| from the url
-  // mapping.  If |all_history| is true, then ignores |deleted_ids| and
-  // deletes all mappings.
-  static void DeleteMostVisitedURLsOnIO(
-      scoped_refptr<InstantIOContext> instant_io_context,
-      std::vector<uint64> deleted_ids, bool all_history);
+      std::vector<InstantMostVisitedItemIDPair> items);
 
   // Determine if this chrome-search: request is coming from an Instant render
   // process.
   static bool ShouldServiceRequest(const net::URLRequest* request);
 
-  // Returns true if the |most_visited_item_id| is known, and |url| is set.
-  // Returns false otherwise.
-  static bool GetURLForMostVisitedItemId(
+  // If there is a mapping for the |most_visited_item_id|, sets |url| and
+  // returns true.
+  static bool GetURLForMostVisitedItemID(
       const net::URLRequest* request,
-      uint64 most_visited_item_id, GURL* url);
+      InstantRestrictedID most_visited_item_id,
+      GURL* url);
 
  protected:
    virtual ~InstantIOContext();
@@ -82,17 +77,17 @@ class InstantIOContext : public base::RefCountedThreadSafe<InstantIOContext> {
   // |process_ids_|.
   bool IsInstantProcess(int process_id) const;
 
-  bool GetURLForMostVisitedItemId(uint64 most_visited_item_id, GURL* url);
+  bool GetURLForMostVisitedItemID(InstantRestrictedID most_visited_item_id,
+                                  GURL* url) const;
 
   // The process IDs associated with Instant processes.  Mirror of the process
   // IDs in InstantService.  Duplicated here for synchronous access on the IO
   // thread.
   std::set<int> process_ids_;
 
-  // The Most Visited item IDs map associated with Instant processes.  Mirror of
-  // the Most Visited item ID map in InstantService.  Duplicated here for
-  // synchronous access on the IO thread.
-  std::map<uint64, GURL> most_visited_item_id_to_url_map_;
+  // The Most Visited item cache. Mirror of the Most Visited item cache in
+  // InstantService. Duplicated here for synchronous access on the IO thread.
+  InstantRestrictedIDCache<InstantMostVisitedItem> most_visited_item_cache_;
 
   DISALLOW_COPY_AND_ASSIGN(InstantIOContext);
 };
diff --git a/chrome/browser/search/instant_service.cc b/chrome/browser/search/instant_service.cc
index 00e34b5..d4d1d4a 100644
--- a/chrome/browser/search/instant_service.cc
+++ b/chrome/browser/search/instant_service.cc
@@ -24,24 +24,9 @@
 
 using content::BrowserThread;
 
-namespace {
-
-// Copies deleted urls out of the history data structure |details| into a
-// straight vector of GURLs.
-void HistoryDetailsToDeletedURLs(const history::URLsDeletedDetails& details,
-                                 std::vector<GURL>* deleted_urls) {
-  for (history::URLRows::const_iterator it = details.rows.begin();
-       it != details.rows.end();
-       ++it) {
-    deleted_urls->push_back(it->url());
-  }
-}
-
-}  // namespace
-
 InstantService::InstantService(Profile* profile)
     : profile_(profile),
-      last_most_visited_item_id_(0) {
+      most_visited_item_cache_(kMaxInstantMostVisitedItemCacheSize) {
   // Stub for unit tests.
   if (!BrowserThread::CurrentlyOn(BrowserThread::UI))
     return;
@@ -49,9 +34,6 @@ InstantService::InstantService(Profile* profile)
   registrar_.Add(this,
                  content::NOTIFICATION_RENDERER_PROCESS_TERMINATED,
                  content::NotificationService::AllSources());
-  registrar_.Add(this,
-                 chrome::NOTIFICATION_HISTORY_URLS_DELETED,
-                 content::NotificationService::AllSources());
 
   instant_io_context_ = new InstantIOContext();
 
@@ -84,11 +66,12 @@ const std::string InstantService::MaybeTranslateInstantPathOnUI(
   if (!instant_service)
     return path;
 
-  uint64 most_visited_item_id = 0;
-  if (base::StringToUint64(path, &most_visited_item_id)) {
-    GURL url;
-    if (instant_service->GetURLForMostVisitedItemId(most_visited_item_id, &url))
-      return url.spec();
+  InstantRestrictedID restricted_id = 0;
+  DCHECK_EQ(sizeof(InstantRestrictedID), sizeof(int));
+  if (base::StringToInt(path, &restricted_id)) {
+    InstantMostVisitedItem item;
+    if (instant_service->GetMostVisitedItemForID(restricted_id, &item))
+      return item.url.spec();
   }
   return path;
 }
@@ -96,13 +79,16 @@ const std::string InstantService::MaybeTranslateInstantPathOnUI(
 const std::string InstantService::MaybeTranslateInstantPathOnIO(
     const net::URLRequest* request, const std::string& path) {
   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::IO));
-  uint64 most_visited_item_id = 0;
-  if (base::StringToUint64(path, &most_visited_item_id)) {
+
+  InstantRestrictedID restricted_id = 0;
+  DCHECK_EQ(sizeof(InstantRestrictedID), sizeof(int));
+  if (base::StringToInt(path, &restricted_id)) {
     GURL url;
-    if (InstantIOContext::GetURLForMostVisitedItemId(request,
-                                                     most_visited_item_id,
-                                                     &url))
+    if (InstantIOContext::GetURLForMostVisitedItemID(request,
+                                                     restricted_id,
+                                                     &url)) {
       return url.spec();
+    }
   }
   return path;
 }
@@ -113,8 +99,8 @@ bool InstantService::IsInstantPath(const GURL& url) {
   std::string path = url.path().substr(1);
 
   // Check that path is of Most Visited item ID form.
-  uint64 dummy = 0;
-  return base::StringToUint64(path, &dummy);
+  InstantRestrictedID dummy = 0;
+  return base::StringToInt(path, &dummy);
 }
 
 void InstantService::AddInstantProcess(int process_id) {
@@ -132,48 +118,32 @@ bool InstantService::IsInstantProcess(int process_id) const {
   return process_ids_.find(process_id) != process_ids_.end();
 }
 
-uint64 InstantService::AddURL(const GURL& url) {
-  uint64 id = 0;
-  if (GetMostVisitedItemIDForURL(url, &id))
-    return id;
-
-  last_most_visited_item_id_++;
-  most_visited_item_id_to_url_map_[last_most_visited_item_id_] = url;
-  url_to_most_visited_item_id_map_[url] = last_most_visited_item_id_;
+void InstantService::AddMostVisitedItems(
+    const std::vector<InstantMostVisitedItem>& items) {
+  most_visited_item_cache_.AddItems(items);
 
+  // Post task to the IO thread to copy the data.
   if (instant_io_context_) {
+    std::vector<InstantMostVisitedItemIDPair> items;
+    most_visited_item_cache_.GetCurrentItems(&items);
     BrowserThread::PostTask(
         BrowserThread::IO, FROM_HERE,
-        base::Bind(&InstantIOContext::AddMostVisitedItemIDOnIO,
-                   instant_io_context_, last_most_visited_item_id_, url));
+        base::Bind(&InstantIOContext::AddMostVisitedItemsOnIO,
+                   instant_io_context_,
+                   items));
   }
-
-  return last_most_visited_item_id_;
 }
 
-bool InstantService::GetMostVisitedItemIDForURL(
-    const GURL& url,
-    uint64 *most_visited_item_id) {
-  std::map<GURL, uint64>::iterator it =
-      url_to_most_visited_item_id_map_.find(url);
-  if (it != url_to_most_visited_item_id_map_.end()) {
-    *most_visited_item_id = it->second;
-    return true;
-  }
-  *most_visited_item_id = 0;
-  return false;
+void InstantService::GetCurrentMostVisitedItems(
+    std::vector<InstantMostVisitedItemIDPair>* items) const {
+  most_visited_item_cache_.GetCurrentItems(items);
 }
 
-bool InstantService::GetURLForMostVisitedItemId(uint64 most_visited_item_id,
-                                                GURL* url) {
-  std::map<uint64, GURL>::iterator it =
-      most_visited_item_id_to_url_map_.find(most_visited_item_id);
-  if (it != most_visited_item_id_to_url_map_.end()) {
-    *url = it->second;
-    return true;
-  }
-  *url = GURL();
-  return false;
+bool InstantService::GetMostVisitedItemForID(
+    InstantRestrictedID most_visited_item_id,
+    InstantMostVisitedItem* item) const {
+  return most_visited_item_cache_.GetItemWithRestrictedID(
+      most_visited_item_id, item);
 }
 
 void InstantService::Shutdown() {
@@ -205,45 +175,7 @@ void InstantService::Observe(int type,
       }
       break;
     }
-    case chrome::NOTIFICATION_HISTORY_URLS_DELETED: {
-      content::Details<history::URLsDeletedDetails> det(details);
-      std::vector<GURL> deleted_urls;
-      HistoryDetailsToDeletedURLs(*det.ptr(), &deleted_urls);
-
-      std::vector<uint64> deleted_ids;
-      if (det->all_history) {
-        url_to_most_visited_item_id_map_.clear();
-        most_visited_item_id_to_url_map_.clear();
-      } else {
-        DeleteHistoryURLs(deleted_urls, &deleted_ids);
-      }
-
-      if (instant_io_context_) {
-        BrowserThread::PostTask(
-            BrowserThread::IO, FROM_HERE,
-            base::Bind(&InstantIOContext::DeleteMostVisitedURLsOnIO,
-                       instant_io_context_, deleted_ids, det->all_history));
-      }
-      break;
-    }
     default:
       NOTREACHED() << "Unexpected notification type in InstantService.";
   }
 }
-
-void InstantService::DeleteHistoryURLs(const std::vector<GURL>& deleted_urls,
-                                       std::vector<uint64>* deleted_ids) {
-  for (std::vector<GURL>::const_iterator it = deleted_urls.begin();
-       it != deleted_urls.end();
-       ++it) {
-    std::map<GURL, uint64>::iterator item =
-        url_to_most_visited_item_id_map_.find(*it);
-    if (item != url_to_most_visited_item_id_map_.end()) {
-      uint64 most_visited_item_id = item->second;
-      url_to_most_visited_item_id_map_.erase(item);
-      most_visited_item_id_to_url_map_.erase(
-          most_visited_item_id_to_url_map_.find(most_visited_item_id));
-      deleted_ids->push_back(most_visited_item_id);
-    }
-  }
-}
diff --git a/chrome/browser/search/instant_service.h b/chrome/browser/search/instant_service.h
index d1c84ca..14738fc 100644
--- a/chrome/browser/search/instant_service.h
+++ b/chrome/browser/search/instant_service.h
@@ -13,6 +13,7 @@
 #include "base/compiler_specific.h"
 #include "base/memory/ref_counted.h"
 #include "chrome/browser/profiles/profile_keyed_service.h"
+#include "chrome/common/instant_restricted_id_cache.h"
 #include "content/public/browser/notification_observer.h"
 #include "content/public/browser/notification_registrar.h"
 
@@ -55,18 +56,22 @@ class InstantService : public ProfileKeyedService,
   }
 #endif
 
-  // If |url| is known the existing Most Visited item ID is returned.  Otherwise
-  // a new Most Visited item ID is associated with the |url| and returned.
-  uint64 AddURL(const GURL& url);
+  // Most visited item API.
 
-  // If there is a mapping for the |url|, sets |most_visited_item_id| and
-  // returns true.
-  bool GetMostVisitedItemIDForURL(const GURL& url,
-                                  uint64* most_visited_item_id);
+  // Adds |items| to the |most_visited_item_cache_| assigning restricted IDs in
+  // the process.
+  void AddMostVisitedItems(const std::vector<InstantMostVisitedItem>& items);
 
-  // If there is a mapping for the |most_visited_item_id|, sets |url| and
-  // returns true.
-  bool GetURLForMostVisitedItemId(uint64 most_visited_item_id, GURL* url);
+  // Returns the last added InstantMostVisitedItems. After the call to
+  // |AddMostVisitedItems|, the caller should call this to get the items with
+  // the assigned IDs.
+  void GetCurrentMostVisitedItems(
+      std::vector<InstantMostVisitedItemIDPair>* items) const;
+
+  // If the |most_visited_item_id| is found in the cache, sets the |item| to it
+  // and returns true.
+  bool GetMostVisitedItemForID(InstantRestrictedID most_visited_item_id,
+                               InstantMostVisitedItem* item) const;
 
  private:
   // Overridden from ProfileKeyedService:
@@ -77,22 +82,13 @@ class InstantService : public ProfileKeyedService,
                        const content::NotificationSource& source,
                        const content::NotificationDetails& details) OVERRIDE;
 
-  // Removes entries of each url in |deleted_urls| from the ID maps.  Or all
-  // IDs if |all_history| is true.  |deleted_ids| is filled with the newly
-  // deleted Most Visited item IDs.
-  void DeleteHistoryURLs(const std::vector<GURL>& deleted_urls,
-                         std::vector<uint64>* deleted_ids);
-
   Profile* const profile_;
 
   // The process ids associated with Instant processes.
   std::set<int> process_ids_;
 
-  // A mapping of Most Visited IDs to URLs.  Used to hide Most Visited and
-  // Favicon URLs from the Instant search provider.
-  uint64 last_most_visited_item_id_;
-  std::map<uint64, GURL> most_visited_item_id_to_url_map_;
-  std::map<GURL, uint64> url_to_most_visited_item_id_map_;
+  // A cache of the InstantMostVisitedItems sent to the Instant Pages.
+  InstantRestrictedIDCache<InstantMostVisitedItem> most_visited_item_cache_;
 
   content::NotificationRegistrar registrar_;
 
diff --git a/chrome/browser/ui/search/instant_controller.cc b/chrome/browser/ui/search/instant_controller.cc
index f2fb1f6..ef28101 100644
--- a/chrome/browser/ui/search/instant_controller.cc
+++ b/chrome/browser/ui/search/instant_controller.cc
@@ -199,23 +199,20 @@ void EnsureSearchTermsAreSet(content::WebContents* contents,
       NavigationEntryUpdated();
 }
 
-bool GetURLForMostVisitedItemId(Profile* profile,
-                                uint64 most_visited_item_id,
+bool GetURLForMostVisitedItemID(Profile* profile,
+                                InstantRestrictedID most_visited_item_id,
                                 GURL* url) {
   InstantService* instant_service =
       InstantServiceFactory::GetForProfile(profile);
   if (!instant_service)
     return false;
-  return instant_service->GetURLForMostVisitedItemId(most_visited_item_id, url);
-}
 
-// Creates a new restriced id if one is not found.
-size_t GetMostVisitedItemIDForURL(Profile* profile, const GURL& url) {
-  InstantService* instant_service =
-      InstantServiceFactory::GetForProfile(profile);
-  if (!instant_service)
-    return 0;
-  return instant_service->AddURL(url);
+  InstantMostVisitedItem item;
+  if (!instant_service->GetMostVisitedItemForID(most_visited_item_id, &item))
+    return false;
+
+  *url = item.url;
+  return true;
 }
 
 }  // namespace
@@ -942,24 +939,26 @@ void InstantController::ClearDebugEvents() {
   debug_events_.clear();
 }
 
-void InstantController::DeleteMostVisitedItem(uint64 most_visited_item_id) {
+void InstantController::DeleteMostVisitedItem(
+    InstantRestrictedID most_visited_item_id) {
   history::TopSites* top_sites = browser_->profile()->GetTopSites();
   if (!top_sites)
     return;
 
   GURL url;
-  if (GetURLForMostVisitedItemId(browser_->profile(),
+  if (GetURLForMostVisitedItemID(browser_->profile(),
                                  most_visited_item_id, &url))
     top_sites->AddBlacklistedURL(url);
 }
 
-void InstantController::UndoMostVisitedDeletion(uint64 most_visited_item_id) {
+void InstantController::UndoMostVisitedDeletion(
+    InstantRestrictedID most_visited_item_id) {
   history::TopSites* top_sites = browser_->profile()->GetTopSites();
   if (!top_sites)
     return;
 
   GURL url;
-  if (GetURLForMostVisitedItemId(browser_->profile(),
+  if (GetURLForMostVisitedItemID(browser_->profile(),
                                  most_visited_item_id, &url))
     top_sites->RemoveBlacklistedURL(url);
 }
@@ -1517,23 +1516,29 @@ void InstantController::RequestMostVisitedItems() {
 
 void InstantController::OnMostVisitedItemsReceived(
     const history::MostVisitedURLList& data) {
+  InstantService* instant_service =
+      InstantServiceFactory::GetForProfile(browser_->profile());
+  if (!instant_service)
+    return;
+
   std::vector<InstantMostVisitedItem> most_visited_items;
   for (size_t i = 0; i < data.size(); i++) {
     const history::MostVisitedURL& url = data[i];
-
     InstantMostVisitedItem item;
-    item.most_visited_item_id = GetMostVisitedItemIDForURL(browser_->profile(),
-                                                           url.url);
     item.url = url.url;
     item.title = url.title;
-
     most_visited_items.push_back(item);
   }
-  SendMostVisitedItems(most_visited_items);
+
+  instant_service->AddMostVisitedItems(most_visited_items);
+
+  std::vector<InstantMostVisitedItemIDPair> items_with_ids;
+  instant_service->GetCurrentMostVisitedItems(&items_with_ids);
+  SendMostVisitedItems(items_with_ids);
 }
 
 void InstantController::SendMostVisitedItems(
-    const std::vector<InstantMostVisitedItem>& items) {
+    const std::vector<InstantMostVisitedItemIDPair>& items) {
   if (overlay_)
     overlay_->SendMostVisitedItems(items);
   if (ntp_)
diff --git a/chrome/browser/ui/search/instant_controller.h b/chrome/browser/ui/search/instant_controller.h
index 4c5ceb5..b10331b 100644
--- a/chrome/browser/ui/search/instant_controller.h
+++ b/chrome/browser/ui/search/instant_controller.h
@@ -256,11 +256,13 @@ class InstantController : public InstantPage::Delegate,
 
   // Invoked by the InstantLoader when the Instant page wants to delete a
   // Most Visited item.
-  virtual void DeleteMostVisitedItem(uint64 most_visited_item_id) OVERRIDE;
+  virtual void DeleteMostVisitedItem(InstantRestrictedID most_visited_item_id)
+      OVERRIDE;
 
   // Invoked by the InstantLoader when the Instant page wants to undo a
   // Most Visited deletion.
-  virtual void UndoMostVisitedDeletion(uint64 most_visited_item_id) OVERRIDE;
+  virtual void UndoMostVisitedDeletion(InstantRestrictedID most_visited_item_id)
+      OVERRIDE;
 
   // Invoked by the InstantLoader when the Instant page wants to undo all
   // Most Visited deletions.
@@ -352,7 +354,8 @@ class InstantController : public InstantPage::Delegate,
 
   // Sends a collection of MostVisitedItems to the renderer process via
   // the appropriate InstantPage subclass.
-  void SendMostVisitedItems(const std::vector<InstantMostVisitedItem>& items);
+  void SendMostVisitedItems(
+      const std::vector<InstantMostVisitedItemIDPair>& items);
 
   // If possible, tries to mutate |suggestion| to a valid suggestion. Returns
   // true if successful. (Note that |suggestion| may be modified even if this
diff --git a/chrome/browser/ui/search/instant_extended_browsertest.cc b/chrome/browser/ui/search/instant_extended_browsertest.cc
index 03f0a59..c8d6b29 100644
--- a/chrome/browser/ui/search/instant_extended_browsertest.cc
+++ b/chrome/browser/ui/search/instant_extended_browsertest.cc
@@ -1258,7 +1258,7 @@ IN_PROC_BROWSER_TEST_F(InstantExtendedTest, RestrictedItemReadback) {
   EXPECT_EQ(kQueryString, result);
 
   // Set the query text to the first restricted autocomplete item.
-  int rid = 0;
+  int rid = 1;
   stream.str(std::string());
   stream << "apiHandle.setRestrictedValue(" << rid << ")";
   EXPECT_TRUE(ExecuteScript(stream.str()));
diff --git a/chrome/browser/ui/search/instant_page.cc b/chrome/browser/ui/search/instant_page.cc
index f87dc36..3b0c7da 100644
--- a/chrome/browser/ui/search/instant_page.cc
+++ b/chrome/browser/ui/search/instant_page.cc
@@ -95,7 +95,7 @@ void InstantPage::KeyCaptureChanged(bool is_key_capture_enabled) {
 }
 
 void InstantPage::SendMostVisitedItems(
-    const std::vector<InstantMostVisitedItem>& items) {
+    const std::vector<InstantMostVisitedItemIDPair>& items) {
   Send(new ChromeViewMsg_SearchBoxMostVisitedItemsChanged(routing_id(), items));
 }
 
@@ -269,12 +269,12 @@ void InstantPage::OnSearchBoxNavigate(int page_id,
   }
 }
 
-void InstantPage::OnDeleteMostVisitedItem(uint64 most_visited_item_id) {
-  delegate_->DeleteMostVisitedItem(most_visited_item_id);
+void InstantPage::OnDeleteMostVisitedItem(InstantRestrictedID restricted_id) {
+  delegate_->DeleteMostVisitedItem(restricted_id);
 }
 
-void InstantPage::OnUndoMostVisitedDeletion(uint64 most_visited_item_id) {
-  delegate_->UndoMostVisitedDeletion(most_visited_item_id);
+void InstantPage::OnUndoMostVisitedDeletion(InstantRestrictedID restricted_id) {
+  delegate_->UndoMostVisitedDeletion(restricted_id);
 }
 
 void InstantPage::OnUndoAllMostVisitedDeletions() {
diff --git a/chrome/browser/ui/search/instant_page.h b/chrome/browser/ui/search/instant_page.h
index 8ddaf0a..78e3259 100644
--- a/chrome/browser/ui/search/instant_page.h
+++ b/chrome/browser/ui/search/instant_page.h
@@ -89,10 +89,12 @@ class InstantPage : public content::WebContentsObserver {
                                WindowOpenDisposition disposition) = 0;
 
     // Called when the SearchBox wants to delete a Most Visited item.
-    virtual void DeleteMostVisitedItem(uint64 most_visited_item_id) = 0;
+    virtual void DeleteMostVisitedItem(
+        InstantRestrictedID most_visited_item_id) = 0;
 
     // Called when the SearchBox wants to undo a Most Visited deletion.
-    virtual void UndoMostVisitedDeletion(uint64 most_visited_item_id) = 0;
+    virtual void UndoMostVisitedDeletion(
+        InstantRestrictedID most_visited_item_id) = 0;
 
     // Called when the SearchBox wants to undo all Most Visited deletions.
     virtual void UndoAllMostVisitedDeletions() = 0;
@@ -170,7 +172,8 @@ class InstantPage : public content::WebContentsObserver {
   void KeyCaptureChanged(bool is_key_capture_enabled);
 
   // Tells the page about new Most Visited data.
-  void SendMostVisitedItems(const std::vector<InstantMostVisitedItem>& items);
+  void SendMostVisitedItems(
+      const std::vector<InstantMostVisitedItemIDPair>& items);
 
  protected:
   explicit InstantPage(Delegate* delegate);
@@ -226,8 +229,8 @@ class InstantPage : public content::WebContentsObserver {
                            const GURL& url,
                            content::PageTransition transition,
                            WindowOpenDisposition disposition);
-  void OnDeleteMostVisitedItem(uint64 most_visited_item_id);
-  void OnUndoMostVisitedDeletion(uint64 most_visited_item_id);
+  void OnDeleteMostVisitedItem(InstantRestrictedID most_visited_item_id);
+  void OnUndoMostVisitedDeletion(InstantRestrictedID most_visited_item_id);
   void OnUndoAllMostVisitedDeletions();
 
   Delegate* const delegate_;
diff --git a/chrome/chrome_common.gypi b/chrome/chrome_common.gypi
index 95d9282..b69293d 100644
--- a/chrome/chrome_common.gypi
+++ b/chrome/chrome_common.gypi
@@ -285,6 +285,7 @@
         'common/external_ipc_fuzzer.cc',
         'common/icon_with_badge_image_source.cc',
         'common/icon_with_badge_image_source.h',
+        'common/instant_restricted_id_cache.h',
         'common/instant_types.cc',
         'common/instant_types.h',
         'common/json_schema/json_schema_constants.cc',
diff --git a/chrome/chrome_tests_unit.gypi b/chrome/chrome_tests_unit.gypi
index 57e5d0d..81026cc 100644
--- a/chrome/chrome_tests_unit.gypi
+++ b/chrome/chrome_tests_unit.gypi
@@ -1560,6 +1560,7 @@
         'common/extensions/user_script_unittest.cc',
         'common/extensions/value_counter_unittest.cc',
         'common/extensions/api/extension_api_unittest.cc',
+        'common/instant_restricted_id_cache_unittest.cc',
         'common/json_schema/json_schema_validator_unittest.cc',
         'common/json_schema/json_schema_validator_unittest_base.cc',
         'common/json_schema/json_schema_validator_unittest_base.h',
diff --git a/chrome/common/instant_restricted_id_cache.h b/chrome/common/instant_restricted_id_cache.h
new file mode 100644
index 0000000..66ae060
--- /dev/null
+++ b/chrome/common/instant_restricted_id_cache.h
@@ -0,0 +1,149 @@
+// 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 {
+ 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::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::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_
diff --git a/chrome/common/instant_restricted_id_cache_unittest.cc b/chrome/common/instant_restricted_id_cache_unittest.cc
new file mode 100644
index 0000000..57f1f26
--- /dev/null
+++ b/chrome/common/instant_restricted_id_cache_unittest.cc
@@ -0,0 +1,348 @@
+// 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.
+
+#include <string>
+#include <utility>
+#include <vector>
+#include "chrome/common/instant_restricted_id_cache.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+struct TestData {
+  TestData() {}
+  explicit TestData(const std::string& i_value) : value(i_value) {}
+
+  bool operator==(const TestData& rhs) const {
+    return rhs.value == value;
+  }
+
+  std::string value;
+};
+
+// For printing failures nicely.
+void PrintTo(const TestData& data, std::ostream* os) {
+  *os << data.value;
+}
+
+}  // namespace
+
+typedef testing::Test InstantRestrictedIDCacheTest;
+typedef InstantRestrictedIDCache<TestData>::ItemIDPair ItemIDPair;
+
+TEST_F(InstantRestrictedIDCacheTest, AutoIDGeneration) {
+  InstantRestrictedIDCache<TestData> cache(7);
+  EXPECT_EQ(0u, cache.cache_.size());
+  EXPECT_EQ(0, cache.last_restricted_id_);
+
+  // Check first addition.
+  std::vector<TestData> input1;
+  input1.push_back(TestData("A"));
+  input1.push_back(TestData("B"));
+  input1.push_back(TestData("C"));
+  cache.AddItems(input1);
+  EXPECT_EQ(3u, cache.cache_.size());
+  EXPECT_EQ(3, cache.last_restricted_id_);
+
+  std::vector<ItemIDPair> output;
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(3u, output.size());
+  for (int i = 0; i < 3; ++i) {
+    EXPECT_EQ(i + 1, output[i].first);
+    EXPECT_EQ(input1[i], output[i].second);
+  }
+
+  TestData t;
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_EQ(input1[2], t);
+
+  // Add more items, no overflow.
+  std::vector<TestData> input2;
+  input2.push_back(TestData("D"));
+  input2.push_back(TestData("E"));
+  cache.AddItems(input2);
+  EXPECT_EQ(5u, cache.cache_.size());
+  EXPECT_EQ(5, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(2u, output.size());
+  for (int i = 0; i < 2; ++i) {
+    EXPECT_EQ(i + 4, output[i].first);
+    EXPECT_EQ(input2[i], output[i].second);
+  }
+
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_EQ(input1[2], t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
+  EXPECT_EQ(input2[1], t);
+
+  // Add another set, overflows.
+  std::vector<TestData> input3;
+  input3.push_back(TestData("F"));
+  input3.push_back(TestData("G"));
+  input3.push_back(TestData("H"));
+  input3.push_back(TestData("I"));
+  cache.AddItems(input3);
+  EXPECT_EQ(7u, cache.cache_.size());
+  EXPECT_EQ(9, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(4u, output.size());
+  for (int i = 0; i < 3; ++i) {
+    EXPECT_EQ(i + 6, output[i].first);
+    EXPECT_EQ(input3[i], output[i].second);
+  }
+
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t));
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_EQ(input1[2], t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
+  EXPECT_EQ(input2[1], t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
+  EXPECT_EQ(input3[1], t);
+}
+
+TEST_F(InstantRestrictedIDCacheTest, ManualIDGeneration) {
+  InstantRestrictedIDCache<TestData> cache(5);
+  EXPECT_EQ(0u, cache.cache_.size());
+  EXPECT_EQ(0, cache.last_restricted_id_);
+
+  // Check first addition.
+  std::vector<ItemIDPair> input1;
+  input1.push_back(std::make_pair(1, TestData("A")));
+  input1.push_back(std::make_pair(2, TestData("B")));
+  input1.push_back(std::make_pair(4, TestData("C")));
+  cache.AddItemsWithRestrictedID(input1);
+  EXPECT_EQ(3u, cache.cache_.size());
+  EXPECT_EQ(4, cache.last_restricted_id_);
+
+  std::vector<ItemIDPair> output;
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(3u, output.size());
+  for (int i = 0; i < 3; ++i) {
+    EXPECT_EQ(input1[i].first, output[i].first);
+    EXPECT_EQ(input1[i].second, output[i].second);
+  }
+
+  TestData t;
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_EQ(input1[2].second, t);
+
+
+  // Add more items, one with same rid, no overflow.
+  std::vector<ItemIDPair> input2;
+  input2.push_back(std::make_pair(4, TestData("D")));
+  input2.push_back(std::make_pair(7, TestData("E")));
+  cache.AddItemsWithRestrictedID(input2);
+  EXPECT_EQ(4u, cache.cache_.size());
+  EXPECT_EQ(7, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(2u, output.size());
+  for (int i = 0; i < 2; ++i) {
+    EXPECT_EQ(input2[i].first, output[i].first);
+    EXPECT_EQ(input2[i].second, output[i].second);
+  }
+
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t));
+  EXPECT_EQ(input1[1].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_EQ(input2[0].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
+  EXPECT_EQ(input2[1].second, t);
+
+  // Add another set, duplicate rids, overflows.
+  std::vector<ItemIDPair> input3;
+  input3.push_back(std::make_pair(1, TestData("F")));
+  input3.push_back(std::make_pair(6, TestData("G")));
+  input3.push_back(std::make_pair(9, TestData("H")));
+  cache.AddItemsWithRestrictedID(input3);
+  EXPECT_EQ(5u, cache.cache_.size());
+  EXPECT_EQ(9, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(3u, output.size());
+  for (int i = 0; i < 3; ++i) {
+    EXPECT_EQ(input3[i].first, output[i].first);
+    EXPECT_EQ(input3[i].second, output[i].second);
+  }
+
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t));
+  EXPECT_EQ(input3[0].second, t);
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_EQ(input2[0].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
+  EXPECT_EQ(input2[1].second, t);
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(8, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(9, &t));
+  EXPECT_EQ(input3[2].second, t);
+}
+
+TEST_F(InstantRestrictedIDCacheTest, CrazyIDGeneration) {
+  InstantRestrictedIDCache<TestData> cache(4);
+  EXPECT_EQ(0u, cache.cache_.size());
+  EXPECT_EQ(0, cache.last_restricted_id_);
+
+  // Check first addition.
+  std::vector<ItemIDPair> input1;
+  input1.push_back(std::make_pair(0, TestData("A")));
+  input1.push_back(std::make_pair(kint32max, TestData("B")));
+  input1.push_back(std::make_pair(-100, TestData("C")));
+  cache.AddItemsWithRestrictedID(input1);
+  EXPECT_EQ(3u, cache.cache_.size());
+  EXPECT_EQ(kint32max, cache.last_restricted_id_);
+
+  std::vector<ItemIDPair> output;
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(3u, output.size());
+  for (int i = 0; i < 3; ++i) {
+    EXPECT_EQ(input1[i].first, output[i].first);
+    EXPECT_EQ(input1[i].second, output[i].second);
+  }
+
+  TestData t;
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32max, &t));
+  EXPECT_EQ(input1[1].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(-100, &t));
+  EXPECT_EQ(input1[2].second, t);
+
+  // Add more items, one with same rid, no overflow.
+  std::vector<ItemIDPair> input2;
+  input2.push_back(std::make_pair(kint32min, TestData("D")));
+  input2.push_back(std::make_pair(7, TestData("E")));
+  cache.AddItemsWithRestrictedID(input2);
+  EXPECT_EQ(4u, cache.cache_.size());
+  EXPECT_EQ(kint32max, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(2u, output.size());
+  for (int i = 0; i < 2; ++i) {
+    EXPECT_EQ(input2[i].first, output[i].first);
+    EXPECT_EQ(input2[i].second, output[i].second);
+  }
+
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(0, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32max, &t));
+  EXPECT_EQ(input1[1].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32min, &t));
+  EXPECT_EQ(input2[0].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
+  EXPECT_EQ(input2[1].second, t);
+
+  // Add an item without RID. last_restricted_id_ will overflow.
+  std::vector<TestData> input3;
+  input3.push_back(TestData("F"));
+  input3.push_back(TestData("G"));
+  cache.AddItems(input3);
+  EXPECT_EQ(4u, cache.cache_.size());
+  EXPECT_EQ(kint32min + 1, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(2u, output.size());
+  for (int i = 0; i < 2; ++i) {
+    EXPECT_EQ(kint32min + i, output[i].first);
+    EXPECT_EQ(input3[i], output[i].second);
+  }
+
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32min, &t));
+  EXPECT_EQ(input3[0], t);
+}
+
+TEST_F(InstantRestrictedIDCacheTest, MixIDGeneration) {
+  InstantRestrictedIDCache<TestData> cache(5);
+  EXPECT_EQ(0u, cache.cache_.size());
+  EXPECT_EQ(0, cache.last_restricted_id_);
+
+  // Add some items with manually assigned ids.
+  std::vector<ItemIDPair> input1;
+  input1.push_back(std::make_pair(1, TestData("A")));
+  input1.push_back(std::make_pair(2, TestData("B")));
+  input1.push_back(std::make_pair(4, TestData("C")));
+  cache.AddItemsWithRestrictedID(input1);
+  EXPECT_EQ(3u, cache.cache_.size());
+  EXPECT_EQ(4, cache.last_restricted_id_);
+
+  std::vector<ItemIDPair> output;
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(3u, output.size());
+  for (int i = 0; i < 3; ++i) {
+    EXPECT_EQ(input1[i].first, output[i].first);
+    EXPECT_EQ(input1[i].second, output[i].second);
+  }
+
+  TestData t;
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_EQ(input1[2].second, t);
+
+  // Add items with auto id generation.
+  std::vector<TestData> input2;
+  input2.push_back(TestData("D"));
+  input2.push_back(TestData("E"));
+  cache.AddItems(input2);
+  EXPECT_EQ(5u, cache.cache_.size());
+  EXPECT_EQ(6, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(2u, output.size());
+  for (int i = 0; i < 2; ++i) {
+    EXPECT_EQ(i + 5, output[i].first);
+    EXPECT_EQ(input2[i], output[i].second);
+  }
+
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t));
+  EXPECT_EQ(input1[1].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_EQ(input1[2].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
+  EXPECT_EQ(input2[0], t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t));
+  EXPECT_EQ(input2[1], t);
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(7, &t));
+
+  // Add manually assigned ids again.
+  std::vector<ItemIDPair> input3;
+  input3.push_back(std::make_pair(1, TestData("F")));
+  input3.push_back(std::make_pair(5, TestData("G")));
+  input3.push_back(std::make_pair(7, TestData("H")));
+  cache.AddItemsWithRestrictedID(input3);
+  EXPECT_EQ(5u, cache.cache_.size());
+  EXPECT_EQ(7, cache.last_restricted_id_);
+
+  output.clear();
+  cache.GetCurrentItems(&output);
+  EXPECT_EQ(3u, output.size());
+  for (int i = 0; i < 2; ++i) {
+    EXPECT_EQ(input3[i].first, output[i].first);
+    EXPECT_EQ(input3[i].second, output[i].second);
+  }
+
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t));
+  EXPECT_EQ(input3[0].second, t);
+  EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
+  EXPECT_EQ(input1[2].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
+  EXPECT_EQ(input3[1].second, t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t));
+  EXPECT_EQ(input2[1], t);
+  EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
+  EXPECT_EQ(input3[2].second, t);
+}
diff --git a/chrome/common/instant_types.h b/chrome/common/instant_types.h
index 9f646ba..880aef7 100644
--- a/chrome/common/instant_types.h
+++ b/chrome/common/instant_types.h
@@ -6,11 +6,19 @@
 #define CHROME_COMMON_INSTANT_TYPES_H_
 
 #include <string>
+#include <utility>
 
 #include "base/string16.h"
 #include "content/public/common/page_transition_types.h"
 #include "googleurl/src/gurl.h"
 
+// ID used by Instant code to refer to objects (e.g. Autocomplete results, Most
+// Visited items) that the Instant page needs access to.
+typedef int InstantRestrictedID;
+
+// The size of the InstantMostVisitedItem cache.
+const size_t kMaxInstantMostVisitedItemCacheSize = 100;
+
 // Ways that the Instant suggested text is autocompleted into the omnibox.
 enum InstantCompleteBehavior {
   // Autocomplete the suggestion immediately.
@@ -81,6 +89,10 @@ struct InstantAutocompleteResult {
   int relevance;
 };
 
+// An InstantAutocompleteResult along with its assigned restricted ID.
+typedef std::pair<InstantRestrictedID, InstantAutocompleteResult>
+    InstantAutocompleteResultIDPair;
+
 // How to interpret the size (height or width) of the Instant overlay (preview).
 enum InstantSizeUnits {
   // As an absolute number of pixels.
@@ -143,11 +155,6 @@ struct ThemeBackgroundInfo {
 };
 
 struct InstantMostVisitedItem {
-  InstantMostVisitedItem() : most_visited_item_id(0) {}
-
-  // A private identifier used on the browser side when retrieving assets.
-  uint64 most_visited_item_id;
-
   // The URL of the Most Visited item.
   GURL url;
 
@@ -156,4 +163,8 @@ struct InstantMostVisitedItem {
   string16 title;
 };
 
+// An InstantMostVisitedItem along with its assigned restricted ID.
+typedef std::pair<InstantRestrictedID, InstantMostVisitedItem>
+    InstantMostVisitedItemIDPair;
+
 #endif  // CHROME_COMMON_INSTANT_TYPES_H_
diff --git a/chrome/common/render_messages.h b/chrome/common/render_messages.h
index 39e1077..845e682 100644
--- a/chrome/common/render_messages.h
+++ b/chrome/common/render_messages.h
@@ -167,7 +167,6 @@ IPC_STRUCT_TRAITS_BEGIN(InstantAutocompleteResult)
 IPC_STRUCT_TRAITS_END()
 
 IPC_STRUCT_TRAITS_BEGIN(InstantMostVisitedItem)
-  IPC_STRUCT_TRAITS_MEMBER(most_visited_item_id)
   IPC_STRUCT_TRAITS_MEMBER(url)
   IPC_STRUCT_TRAITS_MEMBER(title)
 IPC_STRUCT_TRAITS_END()
@@ -347,13 +346,13 @@ IPC_MESSAGE_ROUTED1(ChromeViewMsg_SearchBoxGrantChromeSearchAccessFromOrigin,
                     GURL /* origin_url */)
 
 IPC_MESSAGE_ROUTED1(ChromeViewMsg_SearchBoxMostVisitedItemsChanged,
-                    std::vector<InstantMostVisitedItem> /* items */)
+                    std::vector<InstantMostVisitedItemIDPair> /* items */)
 
 IPC_MESSAGE_ROUTED1(ChromeViewHostMsg_SearchBoxDeleteMostVisitedItem,
-                    uint64 /* most_visited_item_id */)
+                    InstantRestrictedID /* most_visited_item_id */)
 
 IPC_MESSAGE_ROUTED1(ChromeViewHostMsg_SearchBoxUndoMostVisitedDeletion,
-                    uint64 /* most_visited_item_id */)
+                    InstantRestrictedID /* most_visited_item_id */)
 
 IPC_MESSAGE_ROUTED0(ChromeViewHostMsg_SearchBoxUndoAllMostVisitedDeletions)
 
diff --git a/chrome/renderer/searchbox/searchbox.cc b/chrome/renderer/searchbox/searchbox.cc
index 348e894..6171847 100644
--- a/chrome/renderer/searchbox/searchbox.cc
+++ b/chrome/renderer/searchbox/searchbox.cc
@@ -12,18 +12,23 @@
 #include "third_party/WebKit/Source/WebKit/chromium/public/WebSecurityPolicy.h"
 #include "third_party/WebKit/Source/WebKit/chromium/public/WebView.h"
 
+namespace {
+// Size of the results cache.
+const size_t kMaxInstantAutocompleteResultItemCacheSize = 100;
+}
+
 SearchBox::SearchBox(content::RenderView* render_view)
     : content::RenderViewObserver(render_view),
       content::RenderViewObserverTracker<SearchBox>(render_view),
       verbatim_(false),
       selection_start_(0),
       selection_end_(0),
-      results_base_(0),
       start_margin_(0),
-      last_results_base_(0),
       is_key_capture_enabled_(false),
       display_instant_results_(false),
-      omnibox_font_size_(0) {
+      omnibox_font_size_(0),
+      autocomplete_results_cache_(kMaxInstantAutocompleteResultItemCacheSize),
+      most_visited_items_cache_(kMaxInstantMostVisitedItemCacheSize) {
 }
 
 SearchBox::~SearchBox() {
@@ -75,12 +80,14 @@ void SearchBox::NavigateToURL(const GURL& url,
       url, transition, disposition));
 }
 
-void SearchBox::DeleteMostVisitedItem(uint64 most_visited_item_id) {
+void SearchBox::DeleteMostVisitedItem(
+    InstantRestrictedID most_visited_item_id) {
   render_view()->Send(new ChromeViewHostMsg_SearchBoxDeleteMostVisitedItem(
       render_view()->GetRoutingID(), most_visited_item_id));
 }
 
-void SearchBox::UndoMostVisitedDeletion(uint64 most_visited_item_id) {
+void SearchBox::UndoMostVisitedDeletion(
+    InstantRestrictedID most_visited_item_id) {
   render_view()->Send(new ChromeViewHostMsg_SearchBoxUndoMostVisitedDeletion(
       render_view()->GetRoutingID(), most_visited_item_id));
 }
@@ -115,24 +122,16 @@ gfx::Rect SearchBox::GetPopupBounds() const {
                    static_cast<int>(popup_bounds_.height() / zoom));
 }
 
-const std::vector<InstantAutocompleteResult>&
-    SearchBox::GetAutocompleteResults() {
-  // Remember the last requested autocomplete_results to account for race
-  // conditions between autocomplete providers returning new data and the user
-  // clicking on a suggestion.
-  last_autocomplete_results_ = autocomplete_results_;
-  last_results_base_ = results_base_;
-  return autocomplete_results_;
+void SearchBox::GetAutocompleteResults(
+    std::vector<InstantAutocompleteResultIDPair>* results) const {
+  autocomplete_results_cache_.GetCurrentItems(results);
 }
 
-const InstantAutocompleteResult* SearchBox::GetAutocompleteResultWithId(
-    size_t autocomplete_result_id) const {
-  if (autocomplete_result_id < last_results_base_ ||
-      autocomplete_result_id >=
-          last_results_base_ + last_autocomplete_results_.size())
-    return NULL;
-  return &last_autocomplete_results_[
-      autocomplete_result_id - last_results_base_];
+bool SearchBox::GetAutocompleteResultWithID(
+    InstantRestrictedID autocomplete_result_id,
+    InstantAutocompleteResult* result) const {
+  return autocomplete_results_cache_.GetItemWithRestrictedID(
+      autocomplete_result_id, result);
 }
 
 const ThemeBackgroundInfo& SearchBox::GetThemeBackgroundInfo() {
@@ -257,8 +256,7 @@ void SearchBox::OnDetermineIfPageSupportsInstant() {
 
 void SearchBox::OnAutocompleteResults(
     const std::vector<InstantAutocompleteResult>& results) {
-  results_base_ += autocomplete_results_.size();
-  autocomplete_results_ = results;
+  autocomplete_results_cache_.AddItems(results);
   if (render_view()->GetWebView() && render_view()->GetWebView()->mainFrame()) {
     DVLOG(1) << render_view() << " OnAutocompleteResults";
     extensions_v8::SearchBoxExtension::DispatchAutocompleteResults(
@@ -348,10 +346,8 @@ void SearchBox::Reset() {
   verbatim_ = false;
   selection_start_ = 0;
   selection_end_ = 0;
-  results_base_ = 0;
   popup_bounds_ = gfx::Rect();
   start_margin_ = 0;
-  autocomplete_results_.clear();
   is_key_capture_enabled_ = false;
   theme_info_ = ThemeBackgroundInfo();
   // Don't reset display_instant_results_ to prevent clearing it on committed
@@ -362,8 +358,8 @@ void SearchBox::Reset() {
 }
 
 void SearchBox::OnMostVisitedChanged(
-    const std::vector<InstantMostVisitedItem>& items) {
-  most_visited_items_ = items;
+    const std::vector<InstantMostVisitedItemIDPair>& items) {
+  most_visited_items_cache_.AddItemsWithRestrictedID(items);
 
   if (render_view()->GetWebView() && render_view()->GetWebView()->mainFrame()) {
     extensions_v8::SearchBoxExtension::DispatchMostVisitedChanged(
@@ -371,7 +367,14 @@ void SearchBox::OnMostVisitedChanged(
   }
 }
 
-const std::vector<InstantMostVisitedItem>&
-SearchBox::GetMostVisitedItems() const {
-  return most_visited_items_;
+void SearchBox::GetMostVisitedItems(
+    std::vector<InstantMostVisitedItemIDPair>* items) const {
+  return most_visited_items_cache_.GetCurrentItems(items);
+}
+
+bool SearchBox::GetMostVisitedItemWithID(
+    InstantRestrictedID most_visited_item_id,
+    InstantMostVisitedItem* item) const {
+  return most_visited_items_cache_.GetItemWithRestrictedID(most_visited_item_id,
+                                                           item);
 }
diff --git a/chrome/renderer/searchbox/searchbox.h b/chrome/renderer/searchbox/searchbox.h
index 1243318..173df10 100644
--- a/chrome/renderer/searchbox/searchbox.h
+++ b/chrome/renderer/searchbox/searchbox.h
@@ -9,6 +9,7 @@
 
 #include "base/basictypes.h"
 #include "base/string16.h"
+#include "chrome/common/instant_restricted_id_cache.h"
 #include "chrome/common/instant_types.h"
 #include "chrome/common/search_types.h"
 #include "content/public/common/page_transition_types.h"
@@ -51,16 +52,6 @@ class SearchBox : public content::RenderViewObserver,
                      content::PageTransition transition,
                      WindowOpenDisposition disposition);
 
-  // Sends ChromeViewHostMsg_SearchBoxDeleteMostVisitedItem to the browser.
-  void DeleteMostVisitedItem(uint64 most_visited_item_id);
-
-  // Sends ChromeViewHostMsg_SearchBoxUndoMostVisitedDeletion to the browser.
-  void UndoMostVisitedDeletion(uint64 most_visited_item_id);
-
-  // Sends ChromeViewHostMsg_SearchBoxUndoAllMostVisitedDeletions to the
-  // browser.
-  void UndoAllMostVisitedDeletions();
-
   // Shows any attached bars.
   void ShowBars();
 
@@ -72,7 +63,6 @@ class SearchBox : public content::RenderViewObserver,
   bool verbatim() const { return verbatim_; }
   size_t selection_start() const { return selection_start_; }
   size_t selection_end() const { return selection_end_; }
-  int results_base() const { return results_base_; }
   bool is_key_capture_enabled() const { return is_key_capture_enabled_; }
   bool display_instant_results() const { return display_instant_results_; }
   const string16& omnibox_font() const { return omnibox_font_; }
@@ -85,14 +75,39 @@ class SearchBox : public content::RenderViewObserver,
   // Returns the bounds of the omnibox popup in screen coordinates.
   gfx::Rect GetPopupBounds() const;
 
-  const std::vector<InstantAutocompleteResult>& GetAutocompleteResults();
-  // Searchbox retains ownership of this object.
-  const InstantAutocompleteResult*
-      GetAutocompleteResultWithId(size_t autocomplete_result_id) const;
   const ThemeBackgroundInfo& GetThemeBackgroundInfo();
 
-  // Most Visited items.
-  const std::vector<InstantMostVisitedItem>& GetMostVisitedItems() const;
+  // --- Autocomplete result APIs.
+
+  // Returns the most recent InstantAutocompleteResults sent by the browser.
+  void GetAutocompleteResults(
+      std::vector<InstantAutocompleteResultIDPair>* results) const;
+
+  // If the |autocomplete_result_id| is found in the cache, sets |item| to it
+  // and returns true.
+  bool GetAutocompleteResultWithID(InstantRestrictedID autocomplete_result_id,
+                                   InstantAutocompleteResult* result) const;
+
+  // --- Most Visited items APIs.
+
+  // Returns the latest most visited items sent by the browser.
+  void GetMostVisitedItems(
+      std::vector<InstantMostVisitedItemIDPair>* items) const;
+
+  // If the |most_visited_item_id| is found in the cache, sets |item| to it
+  // and returns true.
+  bool GetMostVisitedItemWithID(InstantRestrictedID most_visited_item_id,
+                                InstantMostVisitedItem* item) const;
+
+  // Sends ChromeViewHostMsg_SearchBoxDeleteMostVisitedItem to the browser.
+  void DeleteMostVisitedItem(InstantRestrictedID most_visited_item_id);
+
+  // Sends ChromeViewHostMsg_SearchBoxUndoMostVisitedDeletion to the browser.
+  void UndoMostVisitedDeletion(InstantRestrictedID most_visited_item_id);
+
+  // Sends ChromeViewHostMsg_SearchBoxUndoAllMostVisitedDeletions to the
+  // browser.
+  void UndoAllMostVisitedDeletions();
 
  private:
   // Overridden from content::RenderViewObserver:
@@ -120,7 +135,8 @@ class SearchBox : public content::RenderViewObserver,
   void OnFontInformationReceived(const string16& omnibox_font,
                                  size_t omnibox_font_size);
   void OnGrantChromeSearchAccessFromOrigin(const GURL& origin_url);
-  void OnMostVisitedChanged(const std::vector<InstantMostVisitedItem>& items);
+  void OnMostVisitedChanged(
+      const std::vector<InstantMostVisitedItemIDPair>& items);
 
   // Returns the current zoom factor of the render view or 1 on failure.
   double GetZoom() const;
@@ -132,18 +148,16 @@ class SearchBox : public content::RenderViewObserver,
   bool verbatim_;
   size_t selection_start_;
   size_t selection_end_;
-  size_t results_base_;
   int start_margin_;
   gfx::Rect popup_bounds_;
-  std::vector<InstantAutocompleteResult> autocomplete_results_;
-  size_t last_results_base_;
-  std::vector<InstantAutocompleteResult> last_autocomplete_results_;
   bool is_key_capture_enabled_;
   ThemeBackgroundInfo theme_info_;
   bool display_instant_results_;
   string16 omnibox_font_;
   size_t omnibox_font_size_;
-  std::vector<InstantMostVisitedItem> most_visited_items_;
+  InstantRestrictedIDCache<InstantAutocompleteResult>
+      autocomplete_results_cache_;
+  InstantRestrictedIDCache<InstantMostVisitedItem> most_visited_items_cache_;
 
   DISALLOW_COPY_AND_ASSIGN(SearchBox);
 };
diff --git a/chrome/renderer/searchbox/searchbox_extension.cc b/chrome/renderer/searchbox/searchbox_extension.cc
index 7606a19..524ae54 100644
--- a/chrome/renderer/searchbox/searchbox_extension.cc
+++ b/chrome/renderer/searchbox/searchbox_extension.cc
@@ -79,16 +79,6 @@ v8::Handle<v8::String> GenerateFaviconURL(uint64 most_visited_item_id) {
                          base::Uint64ToString(most_visited_item_id).c_str()));
 }
 
-const GURL MostVisitedItemIDToURL(
-    const std::vector<InstantMostVisitedItem>& most_visited_items,
-    uint64 most_visited_item_id) {
-  for (size_t i = 0; i < most_visited_items.size(); ++i) {
-    if (most_visited_items[i].most_visited_item_id == most_visited_item_id)
-      return most_visited_items[i].url;
-  }
-  return GURL();
-}
-
 }  // namespace
 
 namespace extensions_v8 {
@@ -573,25 +563,25 @@ v8::Handle<v8::Value> SearchBoxExtensionWrapper::GetAutocompleteResults(
   if (!render_view) return v8::Undefined();
 
   DVLOG(1) << render_view << " GetAutocompleteResults";
-  const std::vector<InstantAutocompleteResult>& results =
-      SearchBox::Get(render_view)->GetAutocompleteResults();
-  size_t results_base = SearchBox::Get(render_view)->results_base();
+  std::vector<InstantAutocompleteResultIDPair> results;
+  SearchBox::Get(render_view)->GetAutocompleteResults(&results);
 
   v8::Handle<v8::Array> results_array = v8::Array::New(results.size());
   for (size_t i = 0; i < results.size(); ++i) {
     v8::Handle<v8::Object> result = v8::Object::New();
     result->Set(v8::String::New("provider"),
-                UTF16ToV8String(results[i].provider));
-    result->Set(v8::String::New("type"), UTF16ToV8String(results[i].type));
+                UTF16ToV8String(results[i].second.provider));
+    result->Set(v8::String::New("type"),
+                UTF16ToV8String(results[i].second.type));
     result->Set(v8::String::New("contents"),
-                UTF16ToV8String(results[i].description));
+                UTF16ToV8String(results[i].second.description));
     result->Set(v8::String::New("destination_url"),
-                UTF16ToV8String(results[i].destination_url));
-    result->Set(v8::String::New("rid"), v8::Uint32::New(results_base + i));
+                UTF16ToV8String(results[i].second.destination_url));
+    result->Set(v8::String::New("rid"), v8::Uint32::New(results[i].first));
 
     v8::Handle<v8::Object> ranking_data = v8::Object::New();
     ranking_data->Set(v8::String::New("relevance"),
-                      v8::Int32::New(results[i].relevance));
+                      v8::Int32::New(results[i].second.relevance));
     result->Set(v8::String::New("rankingData"), ranking_data);
 
     results_array->Set(i, result);
@@ -750,11 +740,11 @@ v8::Handle<v8::Value> SearchBoxExtensionWrapper::NavigateSearchBox(
   GURL destination_url;
   content::PageTransition transition = content::PAGE_TRANSITION_TYPED;
   if (args[0]->IsNumber()) {
-    const InstantAutocompleteResult* result = SearchBox::Get(render_view)->
-        GetAutocompleteResultWithId(args[0]->Uint32Value());
-    if (result) {
-      destination_url = GURL(result->destination_url);
-      transition = result->transition;
+    InstantAutocompleteResult result;
+    if (SearchBox::Get(render_view)->GetAutocompleteResultWithID(
+            args[0]->IntegerValue(), &result)) {
+      destination_url = GURL(result.destination_url);
+      transition = result.transition;
     }
   } else {
     // Resolve the URL.
@@ -787,12 +777,13 @@ v8::Handle<v8::Value> SearchBoxExtensionWrapper::NavigateNewTabPage(
   if (!render_view || !args.Length()) return v8::Undefined();
 
   GURL destination_url;
-  content::PageTransition transition = content::PAGE_TRANSITION_TYPED;
+  content::PageTransition transition = content::PAGE_TRANSITION_AUTO_BOOKMARK;
   if (args[0]->IsNumber()) {
-    destination_url = MostVisitedItemIDToURL(
-        SearchBox::Get(render_view)->GetMostVisitedItems(),
-        args[0]->Uint32Value());
-    transition = content::PAGE_TRANSITION_AUTO_BOOKMARK;
+    InstantMostVisitedItem item;
+    if (SearchBox::Get(render_view)->GetMostVisitedItemWithID(
+            args[0]->IntegerValue(), &item)) {
+      destination_url = item.url;
+    }
   } else {
     destination_url = GURL(V8ValueToUTF16(args[0]));
   }
@@ -903,12 +894,14 @@ v8::Handle<v8::Value>
   if (!render_view || !args.Length()) return v8::Undefined();
 
   DVLOG(1) << render_view << " SetSuggestionFromAutocompleteResult";
-  const InstantAutocompleteResult* result = SearchBox::Get(render_view)->
-      GetAutocompleteResultWithId(args[0]->Uint32Value());
-  if (!result) return v8::Undefined();
+  InstantAutocompleteResult result;
+  if (!SearchBox::Get(render_view)->GetAutocompleteResultWithID(
+          args[0]->IntegerValue(), &result)) {
+    return v8::Undefined();
+  }
 
   // We only support selecting autocomplete results that are URLs.
-  string16 text = result->destination_url;
+  string16 text = result.destination_url;
   InstantCompleteBehavior behavior = INSTANT_COMPLETE_NOW;
   InstantSuggestionType type = INSTANT_SUGGESTION_URL;
 
@@ -951,12 +944,14 @@ v8::Handle<v8::Value>
   if (!render_view || !args.Length()) return v8::Undefined();
 
   DVLOG(1) << render_view << " SetQueryFromAutocompleteResult";
-  const InstantAutocompleteResult* result = SearchBox::Get(render_view)->
-      GetAutocompleteResultWithId(args[0]->Uint32Value());
-  if (!result) return v8::Undefined();
+  InstantAutocompleteResult result;
+  if (!SearchBox::Get(render_view)->GetAutocompleteResultWithID(
+          args[0]->IntegerValue(), &result)) {
+    return v8::Undefined();
+  }
 
   // We only support selecting autocomplete results that are URLs.
-  string16 text = result->destination_url;
+  string16 text = result.destination_url;
   InstantCompleteBehavior behavior = INSTANT_COMPLETE_REPLACE;
   // TODO(jered): Distinguish between history URLs and search provider
   // navsuggest URLs so that we can do proper accounting on history URLs.
@@ -1003,8 +998,8 @@ v8::Handle<v8::Value> SearchBoxExtensionWrapper::GetMostVisitedItems(
 
   const SearchBox* search_box = SearchBox::Get(render_view);
 
-  const std::vector<InstantMostVisitedItem>& instant_mv_items =
-      search_box->GetMostVisitedItems();
+  std::vector<InstantMostVisitedItemIDPair> instant_mv_items;
+  search_box->GetMostVisitedItems(&instant_mv_items);
   v8::Handle<v8::Array> v8_mv_items = v8::Array::New(instant_mv_items.size());
   for (size_t i = 0; i < instant_mv_items.size(); ++i) {
     // We set the "dir" attribute of the title, so that in RTL locales, a LTR
@@ -1018,27 +1013,26 @@ v8::Handle<v8::Value> SearchBoxExtensionWrapper::GetMostVisitedItems(
     // http://yahoo.com is "Yahoo!". In RTL locales, in the New Tab page, the
     // title will be rendered as "!Yahoo" if its "dir" attribute is not set to
     // "ltr".
+    const InstantMostVisitedItem& mv_item = instant_mv_items[i].second;
     std::string direction;
-    if (base::i18n::StringContainsStrongRTLChars(instant_mv_items[i].title))
+    if (base::i18n::StringContainsStrongRTLChars(mv_item.title))
       direction = kRTLHtmlTextDirection;
     else
       direction = kLTRHtmlTextDirection;
 
-    string16 title = instant_mv_items[i].title;
+    string16 title = mv_item.title;
     if (title.empty())
-      title = UTF8ToUTF16(instant_mv_items[i].url.spec());
+      title = UTF8ToUTF16(mv_item.url.spec());
 
+    InstantRestrictedID restricted_id = instant_mv_items[i].first;
     v8::Handle<v8::Object> item = v8::Object::New();
-    item->Set(v8::String::New("rid"),
-              v8::Int32::New(instant_mv_items[i].most_visited_item_id));
+    item->Set(v8::String::New("rid"), v8::Int32::New(restricted_id));
     item->Set(v8::String::New("thumbnailUrl"),
-              GenerateThumbnailURL(instant_mv_items[i].most_visited_item_id));
+              GenerateThumbnailURL(restricted_id));
     item->Set(v8::String::New("faviconUrl"),
-              GenerateFaviconURL(instant_mv_items[i].most_visited_item_id));
-    item->Set(v8::String::New("title"),
-              UTF16ToV8String(title));
-    item->Set(v8::String::New("domain"),
-              UTF8ToV8String(instant_mv_items[i].url.host()));
+              GenerateFaviconURL(restricted_id));
+    item->Set(v8::String::New("title"), UTF16ToV8String(title));
+    item->Set(v8::String::New("domain"), UTF8ToV8String(mv_item.url.host()));
     item->Set(v8::String::New("direction"), UTF8ToV8String(direction));
 
     v8_mv_items->Set(i, item);