8 files changed, 605 insertions, 21 deletions

diff --git a/chrome/browser/history/history_types.h b/chrome/browser/history/history_types.h
index c967374..02023f1 100644
--- a/chrome/browser/history/history_types.h
+++ b/chrome/browser/history/history_types.h
@@ -518,6 +518,17 @@ struct KeywordSearchTermVisit {
   std::wstring term;
 };
 
+// MostVisitedURL --------------------------------------------------------------
+
+// Holds the per-URL information of the most visited query.
+struct MostVisitedURL {
+  GURL url;
+  GURL favicon_url;
+  std::wstring title;
+
+  RedirectList redirects;
+};
+
 }  // history
 
 #endif  // CHROME_BROWSER_HISTORY_HISTORY_TYPES_H__
diff --git a/chrome/browser/history/top_sites.cc b/chrome/browser/history/top_sites.cc
new file mode 100644
index 0000000..48a1751
--- /dev/null
+++ b/chrome/browser/history/top_sites.cc
@@ -0,0 +1,170 @@
+// Copyright (c) 2009 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 "chrome/browser/history/top_sites.h"
+
+#include "base/gfx/jpeg_codec.h"
+#include "base/logging.h"
+#include "third_party/skia/include/core/SkBitmap.h"
+
+namespace history {
+
+TopSites::TopSites() {
+}
+
+TopSites::~TopSites() {
+}
+
+bool TopSites::Init() {
+  // TODO(brettw) read the database here.
+  return true;
+}
+
+bool TopSites::SetPageThumbnail(const GURL& url,
+                                const SkBitmap& thumbnail,
+                                const ThumbnailScore& score) {
+  AutoLock lock(lock_);
+
+  std::map<GURL, size_t>::iterator found = canonical_urls_.find(url);
+  if (found == canonical_urls_.end())
+    return false;  // This URL is not known to us.
+  MostVisitedURL& most_visited = top_sites_[found->second];
+  Images& image = top_images_[most_visited.url];
+
+  // When comparing the thumbnail scores, we need to take into account the
+  // redirect hops, which are not generated when the thumbnail is becuase the
+  // redirects weren't known. We fill that in here since we know the redirects.
+  ThumbnailScore new_score_with_redirects(score);
+  new_score_with_redirects.redirect_hops_from_dest =
+      GetRedirectDistanceForURL(most_visited, url);
+
+  if (!ShouldReplaceThumbnailWith(image.thumbnail_score,
+                                  new_score_with_redirects))
+    return false;  // The one we already have is better.
+
+  image.thumbnail = new RefCountedBytes;
+  SkAutoLockPixels thumbnail_lock(thumbnail);
+  bool encoded = JPEGCodec::Encode(
+      reinterpret_cast<unsigned char*>(thumbnail.getAddr32(0, 0)),
+      JPEGCodec::FORMAT_BGRA, thumbnail.width(),
+      thumbnail.height(),
+      static_cast<int>(thumbnail.rowBytes()), 90,
+      &image.thumbnail->data);
+  if (!encoded)
+    return false;
+  image.thumbnail_score = new_score_with_redirects;
+
+  return true;
+}
+
+void TopSites::StoreMostVisited(std::vector<MostVisitedURL>* most_visited) {
+  lock_.AssertAcquired();
+  // TODO(brettw) filter for blacklist!
+
+  if (!top_sites_.empty()) {
+    std::vector<size_t> added;
+    std::vector<size_t> deleted;
+    std::vector<size_t> moved;
+    DiffMostVisited(top_sites_, *most_visited, &added, &deleted, &moved);
+
+    // Delete all the thumbnails associated with URLs that were deleted.
+    for (size_t i = 0; i < deleted.size(); i++) {
+      std::map<GURL, Images>::iterator found =
+          top_images_.find(top_sites_[deleted[i]].url);
+      if (found != top_images_.end())
+        top_images_.erase(found);
+    }
+
+    // TODO(brettw) write the new data to disk.
+  }
+
+  // Take ownership of the most visited data.
+  top_sites_.clear();
+  top_sites_.swap(*most_visited);
+
+  // Save the redirect information for quickly mapping to the canonical URLs.
+  canonical_urls_.clear();
+  for (size_t i = 0; i < top_sites_.size(); i++)
+    StoreRedirectChain(top_sites_[i].redirects, i);
+}
+
+void TopSites::StoreRedirectChain(const RedirectList& redirects,
+                                  size_t destination) {
+  lock_.AssertAcquired();
+
+  if (redirects.empty()) {
+    NOTREACHED();
+    return;
+  }
+
+  // We shouldn't get any duplicates.
+  DCHECK(canonical_urls_.find(redirects[0]) == canonical_urls_.end());
+
+  // Map all the redirected URLs to the destination.
+  for (size_t i = 0; i < redirects.size(); i++)
+    canonical_urls_[redirects[i]] = destination;
+}
+
+GURL TopSites::GetCanonicalURL(const GURL& url) const {
+  lock_.AssertAcquired();
+
+  std::map<GURL, size_t>::const_iterator found = canonical_urls_.find(url);
+  if (found == canonical_urls_.end())
+    return GURL();  // Don't know anything about this URL.
+  return top_sites_[found->second].url;
+}
+
+// static
+int TopSites::GetRedirectDistanceForURL(const MostVisitedURL& most_visited,
+                                        const GURL& url) {
+  for (size_t i = 0; i < most_visited.redirects.size(); i++) {
+    if (most_visited.redirects[i] == url)
+      return static_cast<int>(most_visited.redirects.size() - i - 1);
+  }
+  NOTREACHED() << "URL should always be found.";
+  return 0;
+}
+
+// static
+void TopSites::DiffMostVisited(const std::vector<MostVisitedURL>& old_list,
+                               const std::vector<MostVisitedURL>& new_list,
+                               std::vector<size_t>* added_urls,
+                               std::vector<size_t>* deleted_urls,
+                               std::vector<size_t>* moved_urls) {
+  added_urls->clear();
+  deleted_urls->clear();
+  moved_urls->clear();
+
+  // Add all the old URLs for quick lookup. This maps URLs to the corresponding
+  // index in the input.
+  std::map<GURL, size_t> all_old_urls;
+  for (size_t i = 0; i < old_list.size(); i++)
+    all_old_urls[old_list[i].url] = i;
+
+  // Check all the URLs in the new set to see which ones are new or just moved.
+  // When we find a match in the old set, we'll reset its index to our special
+  // marker. This allows us to quickly identify the deleted ones in a later
+  // pass.
+  const size_t kAlreadyFoundMarker = static_cast<size_t>(-1);
+  for (size_t i = 0; i < new_list.size(); i++) {
+    std::map<GURL, size_t>::iterator found = all_old_urls.find(new_list[i].url);
+    if (found == all_old_urls.end()) {
+      added_urls->push_back(i);
+    } else {
+      if (found->second != i)
+        moved_urls->push_back(i);
+      found->second = kAlreadyFoundMarker;
+    }
+  }
+
+  // Any member without the special marker in the all_old_urls list means that
+  // there wasn't a "new" URL that mapped to it, so it was deleted.
+  for (std::map<GURL, size_t>::const_iterator i = all_old_urls.begin();
+       i != all_old_urls.end(); ++i) {
+    if (i->second != kAlreadyFoundMarker)
+      deleted_urls->push_back(i->second);
+  }
+}
+
+}  // namespace history
diff --git a/chrome/browser/history/top_sites.h b/chrome/browser/history/top_sites.h
new file mode 100644
index 0000000..93fad64
--- /dev/null
+++ b/chrome/browser/history/top_sites.h
@@ -0,0 +1,130 @@
+// Copyright (c) 2009 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_BROWSER_HISTORY_TOP_SITES_H_
+#define CHROME_BROWSER_HISTORY_TOP_SITES_H_
+
+#include <map>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/lock.h"
+#include "base/ref_counted.h"
+#include "chrome/browser/history/history_types.h"
+#include "chrome/common/ref_counted_util.h"
+#include "chrome/common/thumbnail_score.h"
+#include "googleurl/src/gurl.h"
+
+class SkBitmap;
+struct ThumbnailScore;
+
+namespace history {
+
+class TopSitesBackend;
+class TopSitesTest;
+
+// Stores the data for the top "most visited" sites. This includes a cache of
+// the most visited data from history, as well as the corresponding thumbnails
+// of those sites.
+//
+// This class IS threadsafe. It is designed to be used from the UI thread of
+// the browser (where history requests must be kicked off and received from)
+// and from the I/O thread (where new tab page requests come in). Handling the
+// new tab page requests on the I/O thread without proxying to the UI thread is
+// a nontrivial performance win, especially when the browser is starting and
+// the UI thread is busy.
+class TopSites : public base::RefCountedThreadSafe<TopSites> {
+ public:
+  TopSites();
+  ~TopSites();
+
+  // Initializes this component, returning true on success.
+  bool Init();
+
+  // Sets the given thumbnail for the given URL. Returns true if the thumbnail
+  // was updated. False means either the URL wasn't known to us, or we felt
+  // that our current thumbnail was superior to the given one.
+  bool SetPageThumbnail(const GURL& url,
+                        const SkBitmap& thumbnail,
+                        const ThumbnailScore& score);
+
+  //TODO(brettw) write this.
+  //bool GetPageThumbnail(const GURL& url, RefCountedBytes** data) const;
+
+ private:
+  friend class TopSitesTest;
+
+  struct Images {
+    scoped_refptr<RefCountedBytes> thumbnail;
+    ThumbnailScore thumbnail_score;
+
+    // TODO(brettw) this will eventually store the favicon.
+    //scoped_refptr<RefCountedBytes> favicon;
+  };
+
+  // Saves the set of the top URLs visited by this user. The 0th item is the
+  // most popular.
+  //
+  // DANGER! This will clear all data from the input argument.
+  void StoreMostVisited(std::vector<MostVisitedURL>* most_visited);
+
+  // Saves the given set of redirects. The redirects are in order of the
+  // given vector, so [0] -> [1] -> [2].
+  void StoreRedirectChain(const RedirectList& redirects,
+                          size_t destination);
+
+  // Each item in the most visited view can redirect elsewhere. This returns
+  // the canonical URL one identifying the site if the given URL does appear
+  // in the "top sites" list.
+  //
+  // If the given URL is not in the top sites, this will return an empty GURL.
+  GURL GetCanonicalURL(const GURL& url) const;
+
+  // Finds the given URL in the redirect chain for the given TopSite, and
+  // returns the distance from the destination in hops that the given URL is.
+  // The URL is assumed to be in the list. The destination is 0.
+  static int GetRedirectDistanceForURL(const MostVisitedURL& most_visited,
+                                       const GURL& url);
+
+  // Generates the diff of things that happened between "old" and "new."
+  //
+  // The URLs that are in "new" but not "old" will be have their index into
+  // "new" put in |added_urls|. The URLs that are in "old" but not "new" will
+  // have their index into "old" put into |deleted_urls|.
+  //
+  // URLs appearing in both old and new lists but having different indices will
+  // have their index into "new" be put into |moved_urls|.
+  static void DiffMostVisited(const std::vector<MostVisitedURL>& old_list,
+                              const std::vector<MostVisitedURL>& new_list,
+                              std::vector<size_t>* added_urls,
+                              std::vector<size_t>* deleted_urls,
+                              std::vector<size_t>* moved_urls);
+
+  mutable Lock lock_;
+
+  // The cached version of the top sites. The 0th item in this vector is the
+  // #1 site.
+  std::vector<MostVisitedURL> top_sites_;
+
+  // The images corresponding to the top_sites. This is indexed by the URL of
+  // the top site, so this doesn't have to be shuffled around when the ordering
+  // changes of the top sites. Some top_sites_ entries may not have images.
+  std::map<GURL, Images> top_images_;
+
+  // Generated from the redirects to and from the most visited pages, this
+  // maps the redirects to the index into top_sites_ that contains it.
+  std::map<GURL, size_t> canonical_urls_;
+
+  // TODO(brettw) use the blacklist.
+  //std::set<GURL> blacklist_;
+
+  DISALLOW_COPY_AND_ASSIGN(TopSites);
+};
+
+}  // namespace history
+
+#endif  // CHROME_BROWSER_HISTORY_TOP_SITES_H_
+
diff --git a/chrome/browser/history/top_sites_unittest.cc b/chrome/browser/history/top_sites_unittest.cc
new file mode 100644
index 0000000..676261a
--- /dev/null
+++ b/chrome/browser/history/top_sites_unittest.cc
@@ -0,0 +1,187 @@
+// Copyright (c) 2009 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 "chrome/browser/history/top_sites.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "third_party/skia/include/core/SkBitmap.h"
+
+namespace history {
+
+class TopSitesTest : public testing::Test {
+ public:
+  TopSitesTest() : top_sites_(new TopSites) {
+  }
+  ~TopSitesTest() {
+  }
+
+  TopSites& top_sites() { return *top_sites_; }
+
+  virtual void SetUp() {
+  }
+
+  virtual void TearDown() {
+  }
+
+  // Wrappers that allow private TopSites functions to be called from the
+  // individual tests without making them all be friends.
+  GURL GetCanonicalURL(const GURL& url) const {
+    AutoLock lock(top_sites_->lock_);  // The function asserts it's in the lock.
+    return top_sites_->GetCanonicalURL(url);
+  }
+
+  void StoreMostVisited(std::vector<MostVisitedURL>* urls) {
+    AutoLock lock(top_sites_->lock_);  // The function asserts it's in the lock.
+    top_sites_->StoreMostVisited(urls);
+  }
+
+  static void DiffMostVisited(const std::vector<MostVisitedURL>& old_list,
+                              const std::vector<MostVisitedURL>& new_list,
+                              std::vector<size_t>* added_urls,
+                              std::vector<size_t>* deleted_urls,
+                              std::vector<size_t>* moved_urls)  {
+    TopSites::DiffMostVisited(old_list, new_list,
+                              added_urls, deleted_urls, moved_urls);
+  }
+
+ private:
+  scoped_refptr<TopSites> top_sites_;
+
+  DISALLOW_COPY_AND_ASSIGN(TopSitesTest);
+};
+
+// Helper function for appending a URL to a vector of "most visited" URLs,
+// using the default values for everything but the URL.
+static void AppendMostVisitedURL(std::vector<MostVisitedURL>* list,
+                                 const GURL& url) {
+  MostVisitedURL mv;
+  mv.url = url;
+  mv.redirects.push_back(url);
+  list->push_back(mv);
+}
+
+// Same as AppendMostVisitedURL except that it adds a redirect from the first
+// URL to the second.
+static void AppendMostVisitedURLWithRedirect(
+    std::vector<MostVisitedURL>* list,
+    const GURL& redirect_source, const GURL& redirect_dest) {
+  MostVisitedURL mv;
+  mv.url = redirect_dest;
+  mv.redirects.push_back(redirect_source);
+  mv.redirects.push_back(redirect_dest);
+  list->push_back(mv);
+}
+
+TEST_F(TopSitesTest, GetCanonicalURL) {
+  // Have two chains:
+  //   google.com -> www.google.com
+  //   news.google.com (no redirects)
+  GURL news("http://news.google.com/");
+  GURL source("http://google.com/");
+  GURL dest("http://www.google.com/");
+
+  std::vector<MostVisitedURL> most_visited;
+  AppendMostVisitedURLWithRedirect(&most_visited, source, dest);
+  AppendMostVisitedURL(&most_visited, news);
+  StoreMostVisited(&most_visited);
+
+  // Random URLs not in the database shouldn't be reported as being in there.
+  GURL result = GetCanonicalURL(GURL("http://fark.com/"));
+  EXPECT_TRUE(result.is_empty());
+
+  // Easy case, there are no redirects and the exact URL is stored.
+  result = GetCanonicalURL(news);
+  EXPECT_EQ(news, result);
+
+  // The URL in question is the source URL in a redirect list.
+  result = GetCanonicalURL(source);
+  EXPECT_EQ(dest, result);
+
+  // The URL in question is the destination of a redirect.
+  result = GetCanonicalURL(dest);
+  EXPECT_EQ(dest, result);
+}
+
+TEST_F(TopSitesTest, DiffMostVisited) {
+  GURL stays_the_same("http://staysthesame/");
+  GURL gets_added_1("http://getsadded1/");
+  GURL gets_added_2("http://getsadded2/");
+  GURL gets_deleted_1("http://getsdeleted2/");
+  GURL gets_moved_1("http://getsmoved1/");
+
+  std::vector<MostVisitedURL> old_list;
+  AppendMostVisitedURL(&old_list, stays_the_same);  // 0  (unchanged)
+  AppendMostVisitedURL(&old_list, gets_deleted_1);  // 1  (deleted)
+  AppendMostVisitedURL(&old_list, gets_moved_1);    // 2  (moved to 3)
+
+  std::vector<MostVisitedURL> new_list;
+  AppendMostVisitedURL(&new_list, stays_the_same);  // 0  (unchanged)
+  AppendMostVisitedURL(&new_list, gets_added_1);    // 1  (added)
+  AppendMostVisitedURL(&new_list, gets_added_2);    // 2  (added)
+  AppendMostVisitedURL(&new_list, gets_moved_1);    // 3  (moved from 2)
+
+  std::vector<size_t> added;
+  std::vector<size_t> deleted;
+  std::vector<size_t> moved;
+  DiffMostVisited(old_list, new_list, &added, &deleted, &moved);
+
+  ASSERT_EQ(2u, added.size());
+  ASSERT_EQ(1u, deleted.size());
+  ASSERT_EQ(1u, moved.size());
+
+  // There should be 2 URLs added, we don't assume what order they're in inside
+  // the result vector.
+  EXPECT_TRUE(added[0] == 1 || added[1] == 1);
+  EXPECT_TRUE(added[0] == 2 || added[1] == 2);
+
+  EXPECT_EQ(1u, deleted[0]);
+  EXPECT_EQ(3u, moved[0]);
+}
+
+TEST_F(TopSitesTest, SetPageThumbnail) {
+  GURL url1a("http://google.com/");
+  GURL url1b("http://www.google.com/");
+  GURL url2("http://images.google.com/");
+  GURL nonexistant_url("http://news.google.com/");
+
+  std::vector<MostVisitedURL> list;
+  AppendMostVisitedURL(&list, url2);
+
+  MostVisitedURL mv;
+  mv.url = url1b;
+  mv.redirects.push_back(url1a);
+  mv.redirects.push_back(url1b);
+  list.push_back(mv);
+
+  // Save our most visited data containing that one site.
+  StoreMostVisited(&list);
+
+  // Create a dummy thumbnail.
+  SkBitmap thumbnail;
+  thumbnail.setConfig(SkBitmap::kARGB_8888_Config, 4, 4);
+  thumbnail.allocPixels();
+
+  base::Time now = base::Time::Now();
+  ThumbnailScore low_score(1.0, true, true, now);
+  ThumbnailScore medium_score(0.5, true, true, now);
+  ThumbnailScore high_score(0.0, true, true, now);
+
+  // Setting the thumbnail for nonexistant pages should fail.
+  EXPECT_FALSE(top_sites().SetPageThumbnail(nonexistant_url,
+                                            thumbnail, medium_score));
+
+  // Setting the thumbnail for url2 should succeed, lower scores shouldn't
+  // replace it, higher scores should.
+  EXPECT_TRUE(top_sites().SetPageThumbnail(url2, thumbnail, medium_score));
+  EXPECT_FALSE(top_sites().SetPageThumbnail(url2, thumbnail, low_score));
+  EXPECT_TRUE(top_sites().SetPageThumbnail(url2, thumbnail, high_score));
+
+  // Set on the redirect source should succeed. It should be replacable by
+  // the same score on the redirect destination, which in turn should not
+  // be replaced by the source again.
+  EXPECT_TRUE(top_sites().SetPageThumbnail(url1a, thumbnail, medium_score));
+  EXPECT_TRUE(top_sites().SetPageThumbnail(url1b, thumbnail, medium_score));
+  EXPECT_FALSE(top_sites().SetPageThumbnail(url1a, thumbnail, medium_score));
+}
+
+}  // namespace history
diff --git a/chrome/chrome.gyp b/chrome/chrome.gyp
index 1ac712d..cae4673 100755
--- a/chrome/chrome.gyp
+++ b/chrome/chrome.gyp
@@ -1528,6 +1528,7 @@
         'browser/history/text_database_manager.h',
         'browser/history/thumbnail_database.cc',
         'browser/history/thumbnail_database.h',
+        'browser/history/top_sites.cc',
         'browser/history/url_database.cc',
         'browser/history/url_database.h',
         'browser/history/visit_database.cc',
@@ -4318,6 +4319,7 @@
         'browser/history/text_database_manager_unittest.cc',
         'browser/history/text_database_unittest.cc',
         'browser/history/thumbnail_database_unittest.cc',
+        'browser/history/top_sites_unittest.cc',
         'browser/thumbnail_store_unittest.cc',
         'browser/history/url_database_unittest.cc',
         'browser/history/visit_database_unittest.cc',
@@ -4423,6 +4425,7 @@
         'common/pref_service_unittest.cc',
         'common/property_bag_unittest.cc',
         'common/resource_dispatcher_unittest.cc',
+        'common/thumbnail_score_unittest.cc',
         'common/time_format_unittest.cc',
         'common/worker_thread_ticker_unittest.cc',
         'common/zip_unittest.cc',
diff --git a/chrome/common/thumbnail_score.cc b/chrome/common/thumbnail_score.cc
index 339b7e0..dc7856d 100644
--- a/chrome/common/thumbnail_score.cc
+++ b/chrome/common/thumbnail_score.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2009 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.
 
@@ -35,14 +35,16 @@ ThumbnailScore::ThumbnailScore()
     : boring_score(1.0),
       good_clipping(false),
       at_top(false),
-      time_at_snapshot(Time::Now()) {
+      time_at_snapshot(Time::Now()),
+      redirect_hops_from_dest(0) {
 }
 
 ThumbnailScore::ThumbnailScore(double score, bool clipping, bool top)
     : boring_score(score),
       good_clipping(clipping),
       at_top(top),
-      time_at_snapshot(Time::Now()) {
+      time_at_snapshot(Time::Now()),
+      redirect_hops_from_dest(0) {
 }
 
 ThumbnailScore::ThumbnailScore(double score, bool clipping, bool top,
@@ -50,7 +52,8 @@ ThumbnailScore::ThumbnailScore(double score, bool clipping, bool top,
     : boring_score(score),
       good_clipping(clipping),
       at_top(top),
-      time_at_snapshot(time) {
+      time_at_snapshot(time),
+      redirect_hops_from_dest(0) {
 }
 
 ThumbnailScore::~ThumbnailScore() {
@@ -63,7 +66,8 @@ bool ThumbnailScore::Equals(const ThumbnailScore& rhs) const {
   return boring_score == rhs.boring_score &&
       good_clipping == rhs.good_clipping &&
       at_top == rhs.at_top &&
-      time_at_snapshot.ToTimeT() == rhs.time_at_snapshot.ToTimeT();
+      time_at_snapshot.ToTimeT() == rhs.time_at_snapshot.ToTimeT() &&
+      redirect_hops_from_dest == rhs.redirect_hops_from_dest;
 }
 
 bool ShouldReplaceThumbnailWith(const ThumbnailScore& current,
@@ -77,22 +81,32 @@ bool ShouldReplaceThumbnailWith(const ThumbnailScore& current,
     return replacement.boring_score <
         ThumbnailScore::kThumbnailMaximumBoringness;
   } else if (replacement_type == current_type) {
-    if (replacement.boring_score < current.boring_score) {
-      // If we have a thumbnail that's straight up less boring, use it.
-      return true;
-    }
+    // It's much easier to do the scaling below when we're dealing with "higher
+    // is better." Then we can decrease the score by dividing by a fraction.
+    const double kThumbnailMinimumInterestingness =
+        1.0 - ThumbnailScore::kThumbnailMaximumBoringness;
+    double current_interesting_score = 1.0 - current.boring_score;
+    double replacement_interesting_score = 1.0 - replacement.boring_score;
+
+    // Degrade the score of each thumbnail to account for how many redirects
+    // they are away from the destination. 1/(x+1) gives a scaling factor of
+    // one for x = 0, and asymptotically approaches 0 for larger values of x.
+    current_interesting_score *=
+        1.0 / (current.redirect_hops_from_dest + 1);
+    replacement_interesting_score *=
+        1.0 / (replacement.redirect_hops_from_dest + 1);
 
-    // Slowly degrade the boring score of the current thumbnail
-    // so we take thumbnails which are slightly less good:
-    TimeDelta since_last_thumbnail =
+    // Degrade the score and prefer the newer one based on how long apart the
+    // two thumbnails were taken. This means we'll eventually replace an old
+    // good one with a new worse one assuming enough time has passed.
+    TimeDelta time_between_thumbnails =
         replacement.time_at_snapshot - current.time_at_snapshot;
-    double degraded_boring_score = current.boring_score +
-        (since_last_thumbnail.InHours() *
-         ThumbnailScore::kThumbnailDegradePerHour);
+    current_interesting_score -= time_between_thumbnails.InHours() *
+         ThumbnailScore::kThumbnailDegradePerHour;
 
-    if (degraded_boring_score > ThumbnailScore::kThumbnailMaximumBoringness)
-      degraded_boring_score = ThumbnailScore::kThumbnailMaximumBoringness;
-    if (replacement.boring_score < degraded_boring_score)
+    if (current_interesting_score < kThumbnailMinimumInterestingness)
+      current_interesting_score = kThumbnailMinimumInterestingness;
+    if (replacement_interesting_score > current_interesting_score)
       return true;
   }
 
diff --git a/chrome/common/thumbnail_score.h b/chrome/common/thumbnail_score.h
index 530f87e..c1ebb81 100644
--- a/chrome/common/thumbnail_score.h
+++ b/chrome/common/thumbnail_score.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2009 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.
 
@@ -9,8 +9,9 @@
 
 // A set of metadata about a Thumbnail.
 struct ThumbnailScore {
-  // Initializes the ThumbnailScore to the absolute worst possible
-  // values except for time, which is set to Now().
+  // Initializes the ThumbnailScore to the absolute worst possible values
+  // except for time, which is set to Now(), and redirect_hops_from_dest which
+  // is set to 0.
   ThumbnailScore();
 
   // Builds a ThumbnailScore with the passed in values, and sets the
@@ -48,6 +49,20 @@ struct ThumbnailScore {
   // sure thumbnails are kept fresh.
   base::Time time_at_snapshot;
 
+  // The number of hops from the final destination page that this thumbnail was
+  // taken at. When a thumbnail is taken, this will always be the redirect
+  // destination (value of 0).
+  //
+  // For the most visited view, we'll sometimes get thumbnails for URLs in the
+  // middle of a redirect chain. In this case, the top sites component will set
+  // this value so the distance from the destination can be taken into account
+  // by the comparison function.
+  //
+  // If "http://google.com/" redirected to "http://www.google.com/", then
+  // a thumbnail for the first would have a redirect hop of 1, and the second
+  // would have a redirect hop of 0.
+  int redirect_hops_from_dest;
+
   // How bad a thumbnail needs to be before we completely ignore it.
   static const double kThumbnailMaximumBoringness;
 
diff --git a/chrome/common/thumbnail_score_unittest.cc b/chrome/common/thumbnail_score_unittest.cc
new file mode 100644
index 0000000..14d79dd
--- /dev/null
+++ b/chrome/common/thumbnail_score_unittest.cc
@@ -0,0 +1,54 @@
+// Copyright (c) 2009 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 "chrome/common/thumbnail_score.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+// Tests that the different types of thumbnails are compared properly.
+TEST(ThumbnailScoreTest, ShouldReplaceThumbnailWithType) {
+  base::Time now = base::Time::Now();
+
+  ThumbnailScore nothing_good(0.5, false, false, now);
+  ThumbnailScore not_at_top(0.5, false, true, now);
+  ThumbnailScore bad_clipping(0.5, true, false, now);
+  ThumbnailScore life_is_awesome(0.5, true, true, now);
+
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(nothing_good, not_at_top));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(nothing_good, bad_clipping));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(nothing_good, life_is_awesome));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(not_at_top, bad_clipping));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(not_at_top, life_is_awesome));
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(bad_clipping, life_is_awesome));
+}
+
+// Tests that we'll replace old thumbnails will crappier but newer ones.
+TEST(ThumbnailScoreTest, ShouldReplaceThumbnailWithTime) {
+  // Use a really long time for the difference so we aren't sensitive to the
+  // degrading schedule.
+  base::Time now = base::Time::Now();
+  base::Time last_year = now - base::TimeDelta::FromDays(365);
+
+  ThumbnailScore oldie_but_goodie(0.1, true, true, last_year);
+  ThumbnailScore newie_but_crappie(0.9, true, true, now);
+
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(oldie_but_goodie, newie_but_crappie));
+}
+
+// Having many redirects should age the thumbnail.
+TEST(ThumbnailScoreTest, RedirectCount) {
+  base::Time now = base::Time::Now();
+
+  ThumbnailScore no_redirects(0.5, true, true, now);
+  no_redirects.redirect_hops_from_dest = 0;
+  ThumbnailScore some_redirects(0.5, true, true, now);
+  some_redirects.redirect_hops_from_dest = 1;
+
+  EXPECT_TRUE(ShouldReplaceThumbnailWith(some_redirects, no_redirects));
+
+  // This one has a lot of redirects but a better score. It should still be
+  // rejected.
+  ThumbnailScore lotsa_redirects(0.4, true, true, now);
+  lotsa_redirects.redirect_hops_from_dest = 4;
+  EXPECT_FALSE(ShouldReplaceThumbnailWith(no_redirects, lotsa_redirects));
+}