Home | History | Annotate | Download | only in history 
      1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "chrome/browser/history/top_sites.h"
      6 
      7 #include <algorithm>
      8 #include <set>
      9 
     10 #include "base/command_line.h"
     11 #include "base/logging.h"
     12 #include "base/md5.h"
     13 #include "base/string_util.h"
     14 #include "base/utf_string_conversions.h"
     15 #include "base/values.h"
     16 #include "chrome/browser/history/history_backend.h"
     17 #include "chrome/browser/history/history_notifications.h"
     18 #include "chrome/browser/history/page_usage_data.h"
     19 #include "chrome/browser/history/top_sites_backend.h"
     20 #include "chrome/browser/history/top_sites_cache.h"
     21 #include "chrome/browser/prefs/pref_service.h"
     22 #include "chrome/browser/prefs/scoped_user_pref_update.h"
     23 #include "chrome/browser/profiles/profile.h"
     24 #include "chrome/browser/ui/webui/most_visited_handler.h"
     25 #include "chrome/common/chrome_switches.h"
     26 #include "chrome/common/pref_names.h"
     27 #include "chrome/common/thumbnail_score.h"
     28 #include "content/browser/browser_thread.h"
     29 #include "content/browser/tab_contents/navigation_controller.h"
     30 #include "content/browser/tab_contents/navigation_entry.h"
     31 #include "content/common/notification_service.h"
     32 #include "grit/chromium_strings.h"
     33 #include "grit/generated_resources.h"
     34 #include "grit/locale_settings.h"
     35 #include "third_party/skia/include/core/SkBitmap.h"
     36 #include "ui/base/l10n/l10n_util.h"
     37 #include "ui/gfx/codec/jpeg_codec.h"
     38 
     39 namespace history {
     40 
     41 // How many top sites to store in the cache.
     42 static const size_t kTopSitesNumber = 20;
     43 
     44 // Max number of temporary images we'll cache. See comment above
     45 // temp_images_ for details.
     46 static const size_t kMaxTempTopImages = 8;
     47 
     48 static const size_t kTopSitesShown = 8;
     49 static const int kDaysOfHistory = 90;
     50 // Time from startup to first HistoryService query.
     51 static const int64 kUpdateIntervalSecs = 15;
     52 // Intervals between requests to HistoryService.
     53 static const int64 kMinUpdateIntervalMinutes = 1;
     54 static const int64 kMaxUpdateIntervalMinutes = 60;
     55 
     56 // IDs of the sites we force into top sites.
     57 static const int kPrepopulatePageIDs[] =
     58     { IDS_CHROME_WELCOME_URL, IDS_THEMES_GALLERY_URL };
     59 
     60 // Favicons of the sites we force into top sites.
     61 static const char kPrepopulateFaviconURLs[][54] =
     62     { "chrome://theme/IDR_NEWTAB_CHROME_WELCOME_PAGE_FAVICON",
     63       "chrome://theme/IDR_NEWTAB_THEMES_GALLERY_FAVICON" };
     64 
     65 static const int kPrepopulateTitleIDs[] =
     66     { IDS_NEW_TAB_CHROME_WELCOME_PAGE_TITLE,
     67       IDS_NEW_TAB_THEMES_GALLERY_PAGE_TITLE };
     68 
     69 namespace {
     70 
     71 // HistoryDBTask used during migration of thumbnails from history to top sites.
     72 // When run on the history thread it collects the top sites and the
     73 // corresponding thumbnails. When run back on the ui thread it calls into
     74 // TopSites::FinishHistoryMigration.
     75 class LoadThumbnailsFromHistoryTask : public HistoryDBTask {
     76  public:
     77   LoadThumbnailsFromHistoryTask(TopSites* top_sites,
     78                                 int result_count)
     79       : top_sites_(top_sites),
     80         result_count_(result_count) {
     81     // l10n_util isn't thread safe, so cache for use on the db thread.
     82     ignore_urls_.insert(l10n_util::GetStringUTF8(IDS_CHROME_WELCOME_URL));
     83     ignore_urls_.insert(l10n_util::GetStringUTF8(IDS_THEMES_GALLERY_URL));
     84   }
     85 
     86   virtual bool RunOnDBThread(history::HistoryBackend* backend,
     87                              history::HistoryDatabase* db) {
     88     // Get the most visited urls.
     89     backend->QueryMostVisitedURLsImpl(result_count_,
     90                                       kDaysOfHistory,
     91                                       &data_.most_visited);
     92 
     93     // And fetch the thumbnails.
     94     for (size_t i = 0; i < data_.most_visited.size(); ++i) {
     95       const GURL& url = data_.most_visited[i].url;
     96       if (ShouldFetchThumbnailFor(url)) {
     97         scoped_refptr<RefCountedBytes> data;
     98         backend->GetPageThumbnailDirectly(url, &data);
     99         data_.url_to_thumbnail_map[url] = data;
    100       }
    101     }
    102     return true;
    103   }
    104 
    105   virtual void DoneRunOnMainThread() {
    106     top_sites_->FinishHistoryMigration(data_);
    107   }
    108 
    109  private:
    110   bool ShouldFetchThumbnailFor(const GURL& url) {
    111     return ignore_urls_.find(url.spec()) == ignore_urls_.end();
    112   }
    113 
    114   // Set of URLs we don't load thumbnails for. This is created on the UI thread
    115   // and used on the history thread.
    116   std::set<std::string> ignore_urls_;
    117 
    118   scoped_refptr<TopSites> top_sites_;
    119 
    120   // Number of results to request from history.
    121   const int result_count_;
    122 
    123   ThumbnailMigration data_;
    124 
    125   DISALLOW_COPY_AND_ASSIGN(LoadThumbnailsFromHistoryTask);
    126 };
    127 
    128 }  // namespace
    129 
    130 TopSites::TopSites(Profile* profile)
    131     : backend_(NULL),
    132       cache_(new TopSitesCache()),
    133       thread_safe_cache_(new TopSitesCache()),
    134       profile_(profile),
    135       last_num_urls_changed_(0),
    136       blacklist_(NULL),
    137       pinned_urls_(NULL),
    138       history_state_(HISTORY_LOADING),
    139       top_sites_state_(TOP_SITES_LOADING),
    140       loaded_(false) {
    141   if (!profile_)
    142     return;
    143 
    144   if (NotificationService::current()) {
    145     registrar_.Add(this, NotificationType::HISTORY_URLS_DELETED,
    146                    Source<Profile>(profile_));
    147     registrar_.Add(this, NotificationType::NAV_ENTRY_COMMITTED,
    148                    NotificationService::AllSources());
    149   }
    150 
    151   // We create update objects here to be sure that dictionaries are created
    152   // in the user preferences.
    153   DictionaryPrefUpdate(profile_->GetPrefs(),
    154                        prefs::kNTPMostVisitedURLsBlacklist).Get();
    155   DictionaryPrefUpdate(profile_->GetPrefs(),
    156                        prefs::kNTPMostVisitedPinnedURLs).Get();
    157 
    158   // Now the dictionaries are guaranteed to exist and we can cache pointers
    159   // to them.
    160   blacklist_ =
    161       profile_->GetPrefs()->GetDictionary(prefs::kNTPMostVisitedURLsBlacklist);
    162   pinned_urls_ =
    163       profile_->GetPrefs()->GetDictionary(prefs::kNTPMostVisitedPinnedURLs);
    164 }
    165 
    166 void TopSites::Init(const FilePath& db_name) {
    167   // Create the backend here, rather than in the constructor, so that
    168   // unit tests that do not need the backend can run without a problem.
    169   backend_ = new TopSitesBackend;
    170   backend_->Init(db_name);
    171   backend_->GetMostVisitedThumbnails(
    172       &cancelable_consumer_,
    173       NewCallback(this, &TopSites::OnGotMostVisitedThumbnails));
    174 
    175   // History may have already finished loading by the time we're created.
    176   HistoryService* history = profile_->GetHistoryServiceWithoutCreating();
    177   if (history && history->backend_loaded()) {
    178     if (history->needs_top_sites_migration())
    179       MigrateFromHistory();
    180     else
    181       history_state_ = HISTORY_LOADED;
    182   }
    183 }
    184 
    185 bool TopSites::SetPageThumbnail(const GURL& url,
    186                                 const SkBitmap& thumbnail,
    187                                 const ThumbnailScore& score) {
    188   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    189 
    190   if (!loaded_) {
    191     // TODO(sky): I need to cache these and apply them after the load
    192     // completes.
    193     return false;
    194   }
    195 
    196   bool add_temp_thumbnail = false;
    197   if (!IsKnownURL(url)) {
    198     if (!IsFull()) {
    199       add_temp_thumbnail = true;
    200     } else {
    201       return false;  // This URL is not known to us.
    202     }
    203   }
    204 
    205   if (!HistoryService::CanAddURL(url))
    206     return false;  // It's not a real webpage.
    207 
    208   scoped_refptr<RefCountedBytes> thumbnail_data;
    209   if (!EncodeBitmap(thumbnail, &thumbnail_data))
    210     return false;
    211 
    212   if (add_temp_thumbnail) {
    213     // Always remove the existing entry and then add it back. That way if we end
    214     // up with too many temp thumbnails we'll prune the oldest first.
    215     RemoveTemporaryThumbnailByURL(url);
    216     AddTemporaryThumbnail(url, thumbnail_data, score);
    217     return true;
    218   }
    219 
    220   return SetPageThumbnailEncoded(url, thumbnail_data, score);
    221 }
    222 
    223 void TopSites::GetMostVisitedURLs(CancelableRequestConsumer* consumer,
    224                                   GetTopSitesCallback* callback) {
    225   // WARNING: this may be invoked on any thread.
    226   scoped_refptr<CancelableRequest<GetTopSitesCallback> > request(
    227       new CancelableRequest<GetTopSitesCallback>(callback));
    228   // This ensures cancellation of requests when either the consumer or the
    229   // provider is deleted. Deletion of requests is also guaranteed.
    230   AddRequest(request, consumer);
    231   MostVisitedURLList filtered_urls;
    232   {
    233     base::AutoLock lock(lock_);
    234     if (!loaded_) {
    235       // A request came in before we finished loading. Put the request in
    236       // pending_callbacks_ and we'll notify it when we finish loading.
    237       pending_callbacks_.insert(request);
    238       return;
    239     }
    240 
    241     filtered_urls = thread_safe_cache_->top_sites();
    242   }
    243   request->ForwardResult(GetTopSitesCallback::TupleType(filtered_urls));
    244 }
    245 
    246 bool TopSites::GetPageThumbnail(const GURL& url,
    247                                 scoped_refptr<RefCountedBytes>* bytes) {
    248   // WARNING: this may be invoked on any thread.
    249   base::AutoLock lock(lock_);
    250   return thread_safe_cache_->GetPageThumbnail(url, bytes);
    251 }
    252 
    253 bool TopSites::GetPageThumbnailScore(const GURL& url,
    254                                      ThumbnailScore* score) {
    255   // WARNING: this may be invoked on any thread.
    256   base::AutoLock lock(lock_);
    257   return thread_safe_cache_->GetPageThumbnailScore(url, score);
    258 }
    259 
    260 bool TopSites::GetTemporaryPageThumbnailScore(const GURL& url,
    261                                               ThumbnailScore* score) {
    262   for (TempImages::iterator i = temp_images_.begin(); i != temp_images_.end();
    263        ++i) {
    264     if (i->first == url) {
    265       *score = i->second.thumbnail_score;
    266       return true;
    267     }
    268   }
    269   return false;
    270 }
    271 
    272 
    273 // Returns the index of |url| in |urls|, or -1 if not found.
    274 static int IndexOf(const MostVisitedURLList& urls, const GURL& url) {
    275   for (size_t i = 0; i < urls.size(); i++) {
    276     if (urls[i].url == url)
    277       return i;
    278   }
    279   return -1;
    280 }
    281 
    282 void TopSites::MigrateFromHistory() {
    283   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    284   DCHECK_EQ(history_state_, HISTORY_LOADING);
    285 
    286   history_state_ = HISTORY_MIGRATING;
    287   profile_->GetHistoryService(Profile::EXPLICIT_ACCESS)->ScheduleDBTask(
    288       new LoadThumbnailsFromHistoryTask(
    289           this,
    290           num_results_to_request_from_history()),
    291       &cancelable_consumer_);
    292   MigratePinnedURLs();
    293 }
    294 
    295 void TopSites::FinishHistoryMigration(const ThumbnailMigration& data) {
    296   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    297   DCHECK_EQ(history_state_, HISTORY_MIGRATING);
    298 
    299   history_state_ = HISTORY_LOADED;
    300 
    301   SetTopSites(data.most_visited);
    302 
    303   for (size_t i = 0; i < data.most_visited.size(); ++i) {
    304     URLToThumbnailMap::const_iterator image_i =
    305         data.url_to_thumbnail_map.find(data.most_visited[i].url);
    306     if (image_i != data.url_to_thumbnail_map.end()) {
    307       SetPageThumbnailEncoded(data.most_visited[i].url,
    308                               image_i->second,
    309                               ThumbnailScore());
    310     }
    311   }
    312 
    313   MoveStateToLoaded();
    314 
    315   ResetThreadSafeImageCache();
    316 
    317   // We've scheduled all the thumbnails and top sites to be written to the top
    318   // sites db, but it hasn't happened yet. Schedule a request on the db thread
    319   // that notifies us when done. When done we'll know everything was written and
    320   // we can tell history to finish its part of migration.
    321   backend_->DoEmptyRequest(
    322       &cancelable_consumer_,
    323       NewCallback(this, &TopSites::OnHistoryMigrationWrittenToDisk));
    324 }
    325 
    326 void TopSites::HistoryLoaded() {
    327   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    328   DCHECK_NE(history_state_, HISTORY_LOADED);
    329 
    330   if (history_state_ != HISTORY_MIGRATING) {
    331     // No migration from history is needed.
    332     history_state_ = HISTORY_LOADED;
    333     if (top_sites_state_ == TOP_SITES_LOADED_WAITING_FOR_HISTORY) {
    334       // TopSites thought it needed migration, but it really didn't. This
    335       // typically happens the first time a profile is run with Top Sites
    336       // enabled
    337       SetTopSites(MostVisitedURLList());
    338       MoveStateToLoaded();
    339     }
    340   }
    341 }
    342 
    343 bool TopSites::HasBlacklistedItems() const {
    344   return !blacklist_->empty();
    345 }
    346 
    347 void TopSites::AddBlacklistedURL(const GURL& url) {
    348   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    349 
    350   RemovePinnedURL(url);
    351   Value* dummy = Value::CreateNullValue();
    352   {
    353     DictionaryPrefUpdate update(profile_->GetPrefs(),
    354                                 prefs::kNTPMostVisitedURLsBlacklist);
    355     DictionaryValue* blacklist = update.Get();
    356     blacklist->SetWithoutPathExpansion(GetURLHash(url), dummy);
    357   }
    358 
    359   ResetThreadSafeCache();
    360 }
    361 
    362 void TopSites::RemoveBlacklistedURL(const GURL& url) {
    363   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    364   {
    365     DictionaryPrefUpdate update(profile_->GetPrefs(),
    366                                 prefs::kNTPMostVisitedURLsBlacklist);
    367     DictionaryValue* blacklist = update.Get();
    368     blacklist->RemoveWithoutPathExpansion(GetURLHash(url), NULL);
    369   }
    370   ResetThreadSafeCache();
    371 }
    372 
    373 bool TopSites::IsBlacklisted(const GURL& url) {
    374   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    375   return blacklist_->HasKey(GetURLHash(url));
    376 }
    377 
    378 void TopSites::ClearBlacklistedURLs() {
    379   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    380   {
    381     DictionaryPrefUpdate update(profile_->GetPrefs(),
    382                                 prefs::kNTPMostVisitedURLsBlacklist);
    383     DictionaryValue* blacklist = update.Get();
    384     blacklist->Clear();
    385   }
    386   ResetThreadSafeCache();
    387 }
    388 
    389 void TopSites::AddPinnedURL(const GURL& url, size_t pinned_index) {
    390   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    391 
    392   GURL old;
    393   if (GetPinnedURLAtIndex(pinned_index, &old))
    394     RemovePinnedURL(old);
    395 
    396   if (IsURLPinned(url))
    397     RemovePinnedURL(url);
    398 
    399   Value* index = Value::CreateIntegerValue(pinned_index);
    400 
    401   {
    402     DictionaryPrefUpdate update(profile_->GetPrefs(),
    403                                 prefs::kNTPMostVisitedPinnedURLs);
    404     DictionaryValue* pinned_urls = update.Get();
    405     pinned_urls->SetWithoutPathExpansion(GetURLString(url), index);
    406   }
    407 
    408   ResetThreadSafeCache();
    409 }
    410 
    411 bool TopSites::IsURLPinned(const GURL& url) {
    412   int tmp;
    413   return pinned_urls_->GetIntegerWithoutPathExpansion(GetURLString(url), &tmp);
    414 }
    415 
    416 void TopSites::RemovePinnedURL(const GURL& url) {
    417   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    418 
    419   {
    420     DictionaryPrefUpdate update(profile_->GetPrefs(),
    421                                 prefs::kNTPMostVisitedPinnedURLs);
    422     DictionaryValue* pinned_urls = update.Get();
    423     pinned_urls->RemoveWithoutPathExpansion(GetURLString(url), NULL);
    424   }
    425 
    426   ResetThreadSafeCache();
    427 }
    428 
    429 bool TopSites::GetPinnedURLAtIndex(size_t index, GURL* url) {
    430   for (DictionaryValue::key_iterator it = pinned_urls_->begin_keys();
    431        it != pinned_urls_->end_keys(); ++it) {
    432     int current_index;
    433     if (pinned_urls_->GetIntegerWithoutPathExpansion(*it, &current_index)) {
    434       if (static_cast<size_t>(current_index) == index) {
    435         *url = GURL(*it);
    436         return true;
    437       }
    438     }
    439   }
    440   return false;
    441 }
    442 
    443 void TopSites::Shutdown() {
    444   profile_ = NULL;
    445   // Cancel all requests so that the service doesn't callback to us after we've
    446   // invoked Shutdown (this could happen if we have a pending request and
    447   // Shutdown is invoked).
    448   cancelable_consumer_.CancelAllRequests();
    449   backend_->Shutdown();
    450 }
    451 
    452 // static
    453 void TopSites::DiffMostVisited(const MostVisitedURLList& old_list,
    454                                const MostVisitedURLList& new_list,
    455                                TopSitesDelta* delta) {
    456   // Add all the old URLs for quick lookup. This maps URLs to the corresponding
    457   // index in the input.
    458   std::map<GURL, size_t> all_old_urls;
    459   for (size_t i = 0; i < old_list.size(); i++)
    460     all_old_urls[old_list[i].url] = i;
    461 
    462   // Check all the URLs in the new set to see which ones are new or just moved.
    463   // When we find a match in the old set, we'll reset its index to our special
    464   // marker. This allows us to quickly identify the deleted ones in a later
    465   // pass.
    466   const size_t kAlreadyFoundMarker = static_cast<size_t>(-1);
    467   for (size_t i = 0; i < new_list.size(); i++) {
    468     std::map<GURL, size_t>::iterator found = all_old_urls.find(new_list[i].url);
    469     if (found == all_old_urls.end()) {
    470       MostVisitedURLWithRank added;
    471       added.url = new_list[i];
    472       added.rank = i;
    473       delta->added.push_back(added);
    474     } else {
    475       if (found->second != i) {
    476         MostVisitedURLWithRank moved;
    477         moved.url = new_list[i];
    478         moved.rank = i;
    479         delta->moved.push_back(moved);
    480       }
    481       found->second = kAlreadyFoundMarker;
    482     }
    483   }
    484 
    485   // Any member without the special marker in the all_old_urls list means that
    486   // there wasn't a "new" URL that mapped to it, so it was deleted.
    487   for (std::map<GURL, size_t>::const_iterator i = all_old_urls.begin();
    488        i != all_old_urls.end(); ++i) {
    489     if (i->second != kAlreadyFoundMarker)
    490       delta->deleted.push_back(old_list[i->second]);
    491   }
    492 }
    493 
    494 CancelableRequestProvider::Handle TopSites::StartQueryForMostVisited() {
    495   DCHECK(loaded_);
    496   if (!profile_)
    497     return 0;
    498 
    499   HistoryService* hs = profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
    500   // |hs| may be null during unit tests.
    501   if (hs) {
    502     return hs->QueryMostVisitedURLs(
    503         num_results_to_request_from_history(),
    504         kDaysOfHistory,
    505         &cancelable_consumer_,
    506         NewCallback(this, &TopSites::OnTopSitesAvailableFromHistory));
    507   }
    508   return 0;
    509 }
    510 
    511 bool TopSites::IsKnownURL(const GURL& url) {
    512   return loaded_ && cache_->IsKnownURL(url);
    513 }
    514 
    515 bool TopSites::IsFull() {
    516   return loaded_ && cache_->top_sites().size() >= kTopSitesNumber;
    517 }
    518 
    519 TopSites::~TopSites() {
    520 }
    521 
    522 bool TopSites::SetPageThumbnailNoDB(const GURL& url,
    523                                     const RefCountedBytes* thumbnail_data,
    524                                     const ThumbnailScore& score) {
    525   // This should only be invoked when we know about the url.
    526   DCHECK(cache_->IsKnownURL(url));
    527 
    528   const MostVisitedURL& most_visited =
    529       cache_->top_sites()[cache_->GetURLIndex(url)];
    530   Images* image = cache_->GetImage(url);
    531 
    532   // When comparing the thumbnail scores, we need to take into account the
    533   // redirect hops, which are not generated when the thumbnail is because the
    534   // redirects weren't known. We fill that in here since we know the redirects.
    535   ThumbnailScore new_score_with_redirects(score);
    536   new_score_with_redirects.redirect_hops_from_dest =
    537       GetRedirectDistanceForURL(most_visited, url);
    538 
    539   if (!ShouldReplaceThumbnailWith(image->thumbnail_score,
    540                                   new_score_with_redirects) &&
    541       image->thumbnail.get())
    542     return false;  // The one we already have is better.
    543 
    544   image->thumbnail = const_cast<RefCountedBytes*>(thumbnail_data);
    545   image->thumbnail_score = new_score_with_redirects;
    546 
    547   ResetThreadSafeImageCache();
    548   return true;
    549 }
    550 
    551 bool TopSites::SetPageThumbnailEncoded(const GURL& url,
    552                                        const RefCountedBytes* thumbnail,
    553                                        const ThumbnailScore& score) {
    554   if (!SetPageThumbnailNoDB(url, thumbnail, score))
    555     return false;
    556 
    557   // Update the database.
    558   if (!cache_->IsKnownURL(url))
    559     return false;
    560 
    561   size_t index = cache_->GetURLIndex(url);
    562   const MostVisitedURL& most_visited = cache_->top_sites()[index];
    563   backend_->SetPageThumbnail(most_visited,
    564                              index,
    565                              *(cache_->GetImage(most_visited.url)));
    566   return true;
    567 }
    568 
    569 // static
    570 bool TopSites::EncodeBitmap(const SkBitmap& bitmap,
    571                             scoped_refptr<RefCountedBytes>* bytes) {
    572   *bytes = new RefCountedBytes();
    573   SkAutoLockPixels bitmap_lock(bitmap);
    574   std::vector<unsigned char> data;
    575   if (!gfx::JPEGCodec::Encode(
    576           reinterpret_cast<unsigned char*>(bitmap.getAddr32(0, 0)),
    577           gfx::JPEGCodec::FORMAT_BGRA, bitmap.width(),
    578           bitmap.height(),
    579           static_cast<int>(bitmap.rowBytes()), 90,
    580           &data)) {
    581     return false;
    582   }
    583   // As we're going to cache this data, make sure the vector is only as big as
    584   // it needs to be.
    585   (*bytes)->data = data;
    586   return true;
    587 }
    588 
    589 void TopSites::RemoveTemporaryThumbnailByURL(const GURL& url) {
    590   for (TempImages::iterator i = temp_images_.begin(); i != temp_images_.end();
    591        ++i) {
    592     if (i->first == url) {
    593       temp_images_.erase(i);
    594       return;
    595     }
    596   }
    597 }
    598 
    599 void TopSites::AddTemporaryThumbnail(const GURL& url,
    600                                      const RefCountedBytes* thumbnail,
    601                                      const ThumbnailScore& score) {
    602   if (temp_images_.size() == kMaxTempTopImages)
    603     temp_images_.erase(temp_images_.begin());
    604 
    605   TempImage image;
    606   image.first = url;
    607   image.second.thumbnail = const_cast<RefCountedBytes*>(thumbnail);
    608   image.second.thumbnail_score = score;
    609   temp_images_.push_back(image);
    610 }
    611 
    612 void TopSites::TimerFired() {
    613   StartQueryForMostVisited();
    614 }
    615 
    616 // static
    617 int TopSites::GetRedirectDistanceForURL(const MostVisitedURL& most_visited,
    618                                         const GURL& url) {
    619   for (size_t i = 0; i < most_visited.redirects.size(); i++) {
    620     if (most_visited.redirects[i] == url)
    621       return static_cast<int>(most_visited.redirects.size() - i - 1);
    622   }
    623   NOTREACHED() << "URL should always be found.";
    624   return 0;
    625 }
    626 
    627 // static
    628 MostVisitedURLList TopSites::GetPrepopulatePages() {
    629   MostVisitedURLList urls;
    630   urls.resize(arraysize(kPrepopulatePageIDs));
    631   for (size_t i = 0; i < arraysize(kPrepopulatePageIDs); ++i) {
    632     MostVisitedURL& url = urls[i];
    633     url.url = GURL(l10n_util::GetStringUTF8(kPrepopulatePageIDs[i]));
    634     url.redirects.push_back(url.url);
    635     url.favicon_url = GURL(kPrepopulateFaviconURLs[i]);
    636     url.title = l10n_util::GetStringUTF16(kPrepopulateTitleIDs[i]);
    637   }
    638   return urls;
    639 }
    640 
    641 // static
    642 bool TopSites::AddPrepopulatedPages(MostVisitedURLList* urls) {
    643   bool added = false;
    644   MostVisitedURLList prepopulate_urls = GetPrepopulatePages();
    645   for (size_t i = 0; i < prepopulate_urls.size(); ++i) {
    646     if (urls->size() < kTopSitesNumber &&
    647         IndexOf(*urls, prepopulate_urls[i].url) == -1) {
    648       urls->push_back(prepopulate_urls[i]);
    649       added = true;
    650     }
    651   }
    652   return added;
    653 }
    654 
    655 void TopSites::MigratePinnedURLs() {
    656   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    657 
    658   std::map<GURL, size_t> tmp_map;
    659   for (DictionaryValue::key_iterator it = pinned_urls_->begin_keys();
    660        it != pinned_urls_->end_keys(); ++it) {
    661     Value* value;
    662     if (!pinned_urls_->GetWithoutPathExpansion(*it, &value))
    663       continue;
    664 
    665     if (value->IsType(DictionaryValue::TYPE_DICTIONARY)) {
    666       DictionaryValue* dict = static_cast<DictionaryValue*>(value);
    667       std::string url_string;
    668       int index;
    669       if (dict->GetString("url", &url_string) &&
    670           dict->GetInteger("index", &index))
    671         tmp_map[GURL(url_string)] = index;
    672     }
    673   }
    674 
    675   {
    676     DictionaryPrefUpdate update(profile_->GetPrefs(),
    677                                 prefs::kNTPMostVisitedPinnedURLs);
    678     DictionaryValue* pinned_urls = update.Get();
    679     pinned_urls->Clear();
    680   }
    681 
    682   for (std::map<GURL, size_t>::iterator it = tmp_map.begin();
    683        it != tmp_map.end(); ++it)
    684     AddPinnedURL(it->first, it->second);
    685 }
    686 
    687 void TopSites::ApplyBlacklistAndPinnedURLs(const MostVisitedURLList& urls,
    688                                            MostVisitedURLList* out) {
    689   MostVisitedURLList urls_copy;
    690   for (size_t i = 0; i < urls.size(); i++) {
    691     if (!IsBlacklisted(urls[i].url))
    692       urls_copy.push_back(urls[i]);
    693   }
    694 
    695   for (size_t pinned_index = 0; pinned_index < kTopSitesShown; pinned_index++) {
    696     GURL url;
    697     bool found = GetPinnedURLAtIndex(pinned_index, &url);
    698     if (!found)
    699       continue;
    700 
    701     DCHECK(!url.is_empty());
    702     int cur_index = IndexOf(urls_copy, url);
    703     MostVisitedURL tmp;
    704     if (cur_index < 0) {
    705       // Pinned URL not in urls.
    706       tmp.url = url;
    707     } else {
    708       tmp = urls_copy[cur_index];
    709       urls_copy.erase(urls_copy.begin() + cur_index);
    710     }
    711     if (pinned_index > out->size())
    712       out->resize(pinned_index);  // Add empty URLs as fillers.
    713     out->insert(out->begin() + pinned_index, tmp);
    714   }
    715 
    716   // Add non-pinned URLs in the empty spots.
    717   size_t current_url = 0;  // Index into the remaining URLs in urls_copy.
    718   for (size_t i = 0; i < kTopSitesShown && current_url < urls_copy.size();
    719        i++) {
    720     if (i == out->size()) {
    721       out->push_back(urls_copy[current_url]);
    722       current_url++;
    723     } else if (i < out->size()) {
    724       if ((*out)[i].url.is_empty()) {
    725         // Replace the filler
    726         (*out)[i] = urls_copy[current_url];
    727         current_url++;
    728       }
    729     } else {
    730       NOTREACHED();
    731     }
    732   }
    733 }
    734 
    735 std::string TopSites::GetURLString(const GURL& url) {
    736   return cache_->GetCanonicalURL(url).spec();
    737 }
    738 
    739 std::string TopSites::GetURLHash(const GURL& url) {
    740   // We don't use canonical URLs here to be able to blacklist only one of
    741   // the two 'duplicate' sites, e.g. 'gmail.com' and 'mail.google.com'.
    742   return MD5String(url.spec());
    743 }
    744 
    745 base::TimeDelta TopSites::GetUpdateDelay() {
    746   if (cache_->top_sites().size() <= arraysize(kPrepopulateTitleIDs))
    747     return base::TimeDelta::FromSeconds(30);
    748 
    749   int64 range = kMaxUpdateIntervalMinutes - kMinUpdateIntervalMinutes;
    750   int64 minutes = kMaxUpdateIntervalMinutes -
    751       last_num_urls_changed_ * range / cache_->top_sites().size();
    752   return base::TimeDelta::FromMinutes(minutes);
    753 }
    754 
    755 // static
    756 void TopSites::ProcessPendingCallbacks(
    757     const PendingCallbackSet& pending_callbacks,
    758     const MostVisitedURLList& urls) {
    759   PendingCallbackSet::const_iterator i;
    760   for (i = pending_callbacks.begin();
    761        i != pending_callbacks.end(); ++i) {
    762     scoped_refptr<CancelableRequest<GetTopSitesCallback> > request = *i;
    763     if (!request->canceled())
    764       request->ForwardResult(GetTopSitesCallback::TupleType(urls));
    765   }
    766 }
    767 
    768 void TopSites::Observe(NotificationType type,
    769                        const NotificationSource& source,
    770                        const NotificationDetails& details) {
    771   if (!loaded_)
    772     return;
    773 
    774   if (type == NotificationType::HISTORY_URLS_DELETED) {
    775     Details<history::URLsDeletedDetails> deleted_details(details);
    776     if (deleted_details->all_history) {
    777       SetTopSites(MostVisitedURLList());
    778       backend_->ResetDatabase();
    779     } else {
    780       std::set<size_t> indices_to_delete;  // Indices into top_sites_.
    781       for (std::set<GURL>::iterator i = deleted_details->urls.begin();
    782            i != deleted_details->urls.end(); ++i) {
    783         if (cache_->IsKnownURL(*i))
    784           indices_to_delete.insert(cache_->GetURLIndex(*i));
    785       }
    786 
    787       if (indices_to_delete.empty())
    788         return;
    789 
    790       MostVisitedURLList new_top_sites(cache_->top_sites());
    791       for (std::set<size_t>::reverse_iterator i = indices_to_delete.rbegin();
    792            i != indices_to_delete.rend(); i++) {
    793         size_t index = *i;
    794         RemovePinnedURL(new_top_sites[index].url);
    795         new_top_sites.erase(new_top_sites.begin() + index);
    796       }
    797       SetTopSites(new_top_sites);
    798     }
    799     StartQueryForMostVisited();
    800   } else if (type == NotificationType::NAV_ENTRY_COMMITTED) {
    801     if (!IsFull()) {
    802       NavigationController::LoadCommittedDetails* load_details =
    803           Details<NavigationController::LoadCommittedDetails>(details).ptr();
    804       if (!load_details)
    805         return;
    806       const GURL& url = load_details->entry->url();
    807       if (!cache_->IsKnownURL(url) && HistoryService::CanAddURL(url)) {
    808         // To avoid slamming history we throttle requests when the url updates.
    809         // To do otherwise negatively impacts perf tests.
    810         RestartQueryForTopSitesTimer(GetUpdateDelay());
    811       }
    812     }
    813   }
    814 }
    815 
    816 void TopSites::SetTopSites(const MostVisitedURLList& new_top_sites) {
    817   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    818 
    819   MostVisitedURLList top_sites(new_top_sites);
    820   AddPrepopulatedPages(&top_sites);
    821 
    822   TopSitesDelta delta;
    823   DiffMostVisited(cache_->top_sites(), top_sites, &delta);
    824   if (!delta.deleted.empty() || !delta.added.empty() || !delta.moved.empty())
    825     backend_->UpdateTopSites(delta);
    826 
    827   last_num_urls_changed_ = delta.added.size() + delta.moved.size();
    828 
    829   // We always do the following steps (setting top sites in cache, and resetting
    830   // thread safe cache ...) as this method is invoked during startup at which
    831   // point the caches haven't been updated yet.
    832   cache_->SetTopSites(top_sites);
    833 
    834   // See if we have any tmp thumbnails for the new sites.
    835   if (!temp_images_.empty()) {
    836     for (size_t i = 0; i < top_sites.size(); ++i) {
    837       const MostVisitedURL& mv = top_sites[i];
    838       GURL canonical_url = cache_->GetCanonicalURL(mv.url);
    839       // At the time we get the thumbnail redirects aren't known, so we have to
    840       // iterate through all the images.
    841       for (TempImages::iterator it = temp_images_.begin();
    842            it != temp_images_.end(); ++it) {
    843         if (canonical_url == cache_->GetCanonicalURL(it->first)) {
    844           SetPageThumbnailEncoded(mv.url,
    845                                   it->second.thumbnail,
    846                                   it->second.thumbnail_score);
    847           temp_images_.erase(it);
    848           break;
    849         }
    850       }
    851     }
    852   }
    853 
    854   if (top_sites.size() >= kTopSitesNumber)
    855     temp_images_.clear();
    856 
    857   ResetThreadSafeCache();
    858   ResetThreadSafeImageCache();
    859 
    860   // Restart the timer that queries history for top sites. This is done to
    861   // ensure we stay in sync with history.
    862   RestartQueryForTopSitesTimer(GetUpdateDelay());
    863 }
    864 
    865 int TopSites::num_results_to_request_from_history() const {
    866   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    867 
    868   return kTopSitesNumber + blacklist_->size();
    869 }
    870 
    871 void TopSites::MoveStateToLoaded() {
    872   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    873 
    874   MostVisitedURLList filtered_urls;
    875   PendingCallbackSet pending_callbacks;
    876   {
    877     base::AutoLock lock(lock_);
    878 
    879     if (loaded_)
    880       return;  // Don't do anything if we're already loaded.
    881     loaded_ = true;
    882 
    883     // Now that we're loaded we can service the queued up callbacks. Copy them
    884     // here and service them outside the lock.
    885     if (!pending_callbacks_.empty()) {
    886       filtered_urls = thread_safe_cache_->top_sites();
    887       pending_callbacks.swap(pending_callbacks_);
    888     }
    889   }
    890 
    891   ProcessPendingCallbacks(pending_callbacks, filtered_urls);
    892 
    893   NotificationService::current()->Notify(NotificationType::TOP_SITES_LOADED,
    894                                          Source<Profile>(profile_),
    895                                          Details<TopSites>(this));
    896 }
    897 
    898 void TopSites::ResetThreadSafeCache() {
    899   base::AutoLock lock(lock_);
    900   MostVisitedURLList cached;
    901   ApplyBlacklistAndPinnedURLs(cache_->top_sites(), &cached);
    902   thread_safe_cache_->SetTopSites(cached);
    903 }
    904 
    905 void TopSites::ResetThreadSafeImageCache() {
    906   base::AutoLock lock(lock_);
    907   thread_safe_cache_->SetThumbnails(cache_->images());
    908   thread_safe_cache_->RemoveUnreferencedThumbnails();
    909 }
    910 
    911 void TopSites::RestartQueryForTopSitesTimer(base::TimeDelta delta) {
    912   if (timer_.IsRunning() && ((timer_start_time_ + timer_.GetCurrentDelay()) <
    913                              (base::TimeTicks::Now() + delta))) {
    914     return;
    915   }
    916 
    917   timer_start_time_ = base::TimeTicks::Now();
    918   timer_.Stop();
    919   timer_.Start(delta, this, &TopSites::TimerFired);
    920 }
    921 
    922 void TopSites::OnHistoryMigrationWrittenToDisk(TopSitesBackend::Handle handle) {
    923   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    924 
    925   if (!profile_)
    926     return;
    927 
    928   HistoryService* history =
    929       profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
    930   if (history)
    931     history->OnTopSitesReady();
    932 }
    933 
    934 void TopSites::OnGotMostVisitedThumbnails(
    935     CancelableRequestProvider::Handle handle,
    936     scoped_refptr<MostVisitedThumbnails> data,
    937     bool may_need_history_migration) {
    938   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
    939   DCHECK_EQ(top_sites_state_, TOP_SITES_LOADING);
    940 
    941   if (!may_need_history_migration) {
    942     top_sites_state_ = TOP_SITES_LOADED;
    943 
    944     // Set the top sites directly in the cache so that SetTopSites diffs
    945     // correctly.
    946     cache_->SetTopSites(data->most_visited);
    947     SetTopSites(data->most_visited);
    948     cache_->SetThumbnails(data->url_to_images_map);
    949 
    950     ResetThreadSafeImageCache();
    951 
    952     MoveStateToLoaded();
    953 
    954     // Start a timer that refreshes top sites from history.
    955     RestartQueryForTopSitesTimer(
    956         base::TimeDelta::FromSeconds(kUpdateIntervalSecs));
    957   } else {
    958     // The top sites file didn't exist or is the wrong version. We need to wait
    959     // for history to finish loading to know if we really needed to migrate.
    960     if (history_state_ == HISTORY_LOADED) {
    961       top_sites_state_ = TOP_SITES_LOADED;
    962       SetTopSites(MostVisitedURLList());
    963       MoveStateToLoaded();
    964     } else {
    965       top_sites_state_ = TOP_SITES_LOADED_WAITING_FOR_HISTORY;
    966       // Ask for history just in case it hasn't been loaded yet. When history
    967       // finishes loading we'll do migration and/or move to loaded.
    968       profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
    969     }
    970   }
    971 }
    972 
    973 void TopSites::OnTopSitesAvailableFromHistory(
    974     CancelableRequestProvider::Handle handle,
    975     MostVisitedURLList pages) {
    976   SetTopSites(pages);
    977 
    978   // Used only in testing.
    979   NotificationService::current()->Notify(
    980       NotificationType::TOP_SITES_UPDATED,
    981       Source<TopSites>(this),
    982       Details<CancelableRequestProvider::Handle>(&handle));
    983 }
    984 
    985 }  // namespace history
    986