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