Most visited thumbnails and favicons need id-based urls

chrome/browser/instant/instant_service.cc

Index: chrome/browser/instant/instant_service.cc
diff --git a/chrome/browser/instant/instant_service.cc b/chrome/browser/instant/instant_service.cc
index 3c8a6b2ba2c9c93b4ca5f714d27175e4ffca84e8..410622236770a17b1ef3c61eb11363521054eae6 100644
--- a/chrome/browser/instant/instant_service.cc
+++ b/chrome/browser/instant/instant_service.cc
@@ -4,7 +4,9 @@
 
 #include "chrome/browser/instant/instant_service.h"
 
+#include "base/strings/string_number_conversions.h"
 #include "chrome/browser/instant/instant_io_context.h"
+#include "chrome/browser/instant/instant_service_factory.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/browser/ui/webui/ntp/thumbnail_source.h"
 #include "chrome/common/chrome_notification_types.h"
@@ -13,11 +15,13 @@
 #include "content/public/browser/notification_types.h"
 #include "content/public/browser/render_process_host.h"
 #include "content/public/browser/url_data_source.h"
+#include "googleurl/src/gurl.h"
 
 using content::BrowserThread;
 
 InstantService::InstantService(Profile* profile)
-    : profile_(profile) {
+    : profile_(profile),
+      last_url_id_(0) {
   // Stub for unit tests.
   if (!BrowserThread::CurrentlyOn(BrowserThread::UI))
     return;
@@ -41,6 +45,34 @@ InstantService::InstantService(Profile* profile)
 InstantService::~InstantService() {
 }
 
+// static
+const std::string InstantService::MaybeTranslateInstantPath(
+    Profile* profile, const std::string& path) {
+  DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
+  InstantService* instant_service =
+      InstantServiceFactory::GetForProfile(profile);

[palmer, 2013/03/11 20:42:31]

Seems like you can make |profile| const?

[dhollowa, 2013/03/11 23:27:59]

Difficult.

+  if (!instant_service)
+    return path;
+
+  uint64 restricted_id = 0;
+  if (base::StringToUint64(path, &restricted_id)) {

[palmer, 2013/03/11 20:42:31]

I see. You should add this expectation to the documentation for this function in
the .h file.

[dhollowa, 2013/03/11 23:27:59]

Done.

+    GURL url;
+    if (instant_service->GetURLForRestrictedId(restricted_id, &url))
+      return url.spec();
+  }
+  return path;
+}
+
+// static
+bool InstantService::IsInstantPath(const GURL& url) {
+  // Strip leading slash.
+  std::string path = url.path().substr(1);
+
+  // Check that path is of restricted id form.
+  uint64 dummy = 0;
+  return base::StringToUint64(path, &dummy);
+}
+
 void InstantService::AddInstantProcess(int process_id) {
   process_ids_.insert(process_id);
 
@@ -56,6 +88,46 @@ 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 (GetRestrictedIDForURL(url, &id))
+    return id;
+
+  last_url_id_++;

[palmer, 2013/03/11 20:42:31]

Since incrementation is your ID creation discipline, you could make
id_to_url_map_ a vector and save some space. Also, this means you're never going
to really use up the uint64 space; you could probably use uint16 and do just as
well (again saving a tiny amount of space). In fact the maximum # of entries is
probably well below 2**16 - 1?

uint64 would make sense if you intended to generate the IDs randomly (for
example, as a way to avoid keeping last_url_id_ state).

[dhollowa, 2013/03/11 23:27:59]

It is a time/space trade-off yes.  I'd prefer to keep it as is since the savings
are minimal and the convenience is large not having to search linearly through
lists.

[palmer, 2013/03/11 23:47:18]

I'm only suggesting using a vector for id_to_url_map_; we'd still want to use a
map for the reverse mapping, precisely to avoid O(N) lookup. But a vector would
be a notable savings in both space and (micro-benchmarked) time (O(1) vs. (O(log
N) of std::map's balanced tree).

Since we had that thread about keeping Chrome's memory down, I thought I'd bring
it up. A map costs you significantly more memory per item than a vector; you
have to store the key (in a std::pair), and you have to store at least two
pointers per node (left and right children), and possibly tree balancing
overhead (like red vs. black status of each node).

Performance aside, I'm more concerned about the implied API contract of uint64 —
in this context, it seems to mean "almost a GUID", because it's so obvious that
we will never really have 2**64 - 1 URLs in this map. And yet it's not an
almost-GUID; the IDs are sequential. So, shrinking the size of the key removes
that potential confusion, plus it increases your memory savings even further.

+  id_to_url_map_.insert(std::make_pair(last_url_id_, url));

[palmer, 2013/03/11 20:42:31]

Why not use the usual map[key] = value syntax?

[dhollowa, 2013/03/11 23:27:59]

Done.  Much better, thanks.

+  url_to_id_map_.insert(std::make_pair(url, last_url_id_));
+
+  if (instant_io_context_) {
+    BrowserThread::PostTask(
+        BrowserThread::IO, FROM_HERE,
+        base::Bind(&InstantIOContext::AddRestrictedIDOnIO,
+                   instant_io_context_, last_url_id_, url));
+  }
+
+  return last_url_id_;
+}
+
+bool InstantService::GetRestrictedIDForURL(const GURL& url,
+                                           uint64 *restricted_id) {
+  std::map<GURL, uint64>::iterator it = url_to_id_map_.find(url);
+  if (it != url_to_id_map_.end()) {
+    *restricted_id = it->second;
+    return true;
+  }
+  *restricted_id = 0;
+  return false;
+}
+
+bool InstantService::GetURLForRestrictedId(uint64 restricted_id, GURL* url) {
+  std::map<uint64, GURL>::iterator it = id_to_url_map_.find(restricted_id);
+  if (it != id_to_url_map_.end()) {
+    *url = it->second;
+    return true;
+  }
+  *url = GURL();
+  return false;
+}
+
 void InstantService::Shutdown() {
   process_ids_.clear();