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);