cc/resources/tiling_set_eviction_queue.cc

   1 // Copyright 2014 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 <utility>
   6
   7 #include "cc/resources/tiling_set_eviction_queue.h"
   8
   9 namespace cc {
  10
  11 TilingSetEvictionQueue::TilingSetEvictionQueue(
  12     PictureLayerTilingSet* tiling_set,
  13     bool skip_shared_out_of_order_tiles)
  14     : tree_(tiling_set->client()->GetTree()),
  15       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
  16       phase_(EVENTUALLY_RECT),
  17       current_tile_(nullptr) {
  18   // Early out if the layer has no tilings.
  19   if (!tiling_set->num_tilings())
  20     return;
  21   GenerateTilingOrder(tiling_set);
  22   eventually_iterator_ = EventuallyTilingIterator(
  23       &tilings_, tree_, skip_shared_out_of_order_tiles_);
  24   if (eventually_iterator_.done()) {
  25     AdvancePhase();
  26     return;
  27   }
  28   current_tile_ = *eventually_iterator_;
  29 }
  30
  31 TilingSetEvictionQueue::~TilingSetEvictionQueue() {
  32 }
  33
  34 void TilingSetEvictionQueue::GenerateTilingOrder(
  35     PictureLayerTilingSet* tiling_set) {
  36   tilings_.reserve(tiling_set->num_tilings());
  37   // Generate all of the tilings in the order described in the header comment
  38   // for this class.
  39   PictureLayerTilingSet::TilingRange range =
  40       tiling_set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES);
  41   for (int i = range.start; i < range.end; ++i) {
  42     PictureLayerTiling* tiling = tiling_set->tiling_at(i);
  43     if (tiling->has_tiles())
  44       tilings_.push_back(tiling);
  45   }
  46
  47   range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES);
  48   for (int i = range.end - 1; i >= range.start; --i) {
  49     PictureLayerTiling* tiling = tiling_set->tiling_at(i);
  50     if (tiling->has_tiles())
  51       tilings_.push_back(tiling);
  52   }
  53
  54   range = tiling_set->GetTilingRange(
  55       PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES);
  56   for (int i = range.end - 1; i >= range.start; --i) {
  57     PictureLayerTiling* tiling = tiling_set->tiling_at(i);
  58     if (tiling->has_tiles())
  59       tilings_.push_back(tiling);
  60   }
  61
  62   range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOW_RES);
  63   for (int i = range.start; i < range.end; ++i) {
  64     PictureLayerTiling* tiling = tiling_set->tiling_at(i);
  65     if (tiling->has_tiles())
  66       tilings_.push_back(tiling);
  67   }
  68
  69   range = tiling_set->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
  70   for (int i = range.start; i < range.end; ++i) {
  71     PictureLayerTiling* tiling = tiling_set->tiling_at(i);
  72     if (tiling->has_tiles())
  73       tilings_.push_back(tiling);
  74   }
  75   DCHECK_GE(tiling_set->num_tilings(), tilings_.size());
  76 }
  77
  78 void TilingSetEvictionQueue::AdvancePhase() {
  79   current_tile_ = nullptr;
  80   while (!current_tile_ &&
  81          phase_ != VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED) {
  82     phase_ = static_cast<Phase>(phase_ + 1);
  83     switch (phase_) {
  84       case EVENTUALLY_RECT:
  85         NOTREACHED();
  86         break;
  87       case SOON_BORDER_RECT:
  88         soon_iterator_ = SoonBorderTilingIterator(
  89             &tilings_, tree_, skip_shared_out_of_order_tiles_);
  90         if (!soon_iterator_.done())
  91           current_tile_ = *soon_iterator_;
  92         break;
  93       case SKEWPORT_RECT:
  94         skewport_iterator_ = SkewportTilingIterator(
  95             &tilings_, tree_, skip_shared_out_of_order_tiles_);
  96         if (!skewport_iterator_.done())
  97           current_tile_ = *skewport_iterator_;
  98         break;
  99       case PENDING_VISIBLE_RECT:
 100         pending_visible_iterator_ = PendingVisibleTilingIterator(
 101             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 102             false /* return required for activation tiles */);
 103         if (!pending_visible_iterator_.done())
 104           current_tile_ = *pending_visible_iterator_;
 105         break;
 106       case PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION:
 107         pending_visible_iterator_ = PendingVisibleTilingIterator(
 108             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 109             true /* return required for activation tiles */);
 110         if (!pending_visible_iterator_.done())
 111           current_tile_ = *pending_visible_iterator_;
 112         break;
 113       case VISIBLE_RECT_OCCLUDED:
 114         visible_iterator_ = VisibleTilingIterator(
 115             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 116             true /* return occluded tiles */,
 117             false /* return required for activation tiles */);
 118         if (!visible_iterator_.done())
 119           current_tile_ = *visible_iterator_;
 120         break;
 121       case VISIBLE_RECT_UNOCCLUDED:
 122         visible_iterator_ = VisibleTilingIterator(
 123             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 124             false /* return occluded tiles */,
 125             false /* return required for activation tiles */);
 126         if (!visible_iterator_.done())
 127           current_tile_ = *visible_iterator_;
 128         break;
 129       case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
 130         visible_iterator_ = VisibleTilingIterator(
 131             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 132             true /* return occluded tiles */,
 133             true /* return required for activation tiles */);
 134         if (!visible_iterator_.done())
 135           current_tile_ = *visible_iterator_;
 136         break;
 137       case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
 138         visible_iterator_ = VisibleTilingIterator(
 139             &tilings_, tree_, skip_shared_out_of_order_tiles_,
 140             false /* return occluded tiles */,
 141             true /* return required for activation tiles */);
 142         if (!visible_iterator_.done())
 143           current_tile_ = *visible_iterator_;
 144         break;
 145     }
 146   }
 147 }
 148
 149 bool TilingSetEvictionQueue::IsEmpty() const {
 150   return !current_tile_;
 151 }
 152
 153 Tile* TilingSetEvictionQueue::Top() {
 154   DCHECK(!IsEmpty());
 155   return current_tile_;
 156 }
 157
 158 const Tile* TilingSetEvictionQueue::Top() const {
 159   DCHECK(!IsEmpty());
 160   return current_tile_;
 161 }
 162
 163 void TilingSetEvictionQueue::Pop() {
 164   DCHECK(!IsEmpty());
 165   current_tile_ = nullptr;
 166   switch (phase_) {
 167     case EVENTUALLY_RECT:
 168       ++eventually_iterator_;
 169       if (!eventually_iterator_.done())
 170         current_tile_ = *eventually_iterator_;
 171       break;
 172     case SOON_BORDER_RECT:
 173       ++soon_iterator_;
 174       if (!soon_iterator_.done())
 175         current_tile_ = *soon_iterator_;
 176       break;
 177     case SKEWPORT_RECT:
 178       ++skewport_iterator_;
 179       if (!skewport_iterator_.done())
 180         current_tile_ = *skewport_iterator_;
 181       break;
 182     case PENDING_VISIBLE_RECT:
 183     case PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION:
 184       ++pending_visible_iterator_;
 185       if (!pending_visible_iterator_.done())
 186         current_tile_ = *pending_visible_iterator_;
 187       break;
 188     case VISIBLE_RECT_OCCLUDED:
 189     case VISIBLE_RECT_UNOCCLUDED:
 190     case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
 191     case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
 192       ++visible_iterator_;
 193       if (!visible_iterator_.done())
 194         current_tile_ = *visible_iterator_;
 195       break;
 196   }
 197   if (!current_tile_)
 198     AdvancePhase();
 199 }
 200
 201 // EvictionRectIterator
 202 TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator()
 203     : tile_(nullptr),
 204       tilings_(nullptr),
 205       tree_(ACTIVE_TREE),
 206       skip_shared_out_of_order_tiles_(false),
 207       tiling_index_(0) {
 208 }
 209
 210 TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator(
 211     std::vector<PictureLayerTiling*>* tilings,
 212     WhichTree tree,
 213     bool skip_shared_out_of_order_tiles,
 214     bool skip_pending_visible_rect)
 215     : tile_(nullptr),
 216       tilings_(tilings),
 217       tree_(tree),
 218       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
 219       skip_pending_visible_rect_(skip_pending_visible_rect),
 220       tiling_index_(0) {
 221 }
 222
 223 template <typename TilingIteratorType>
 224 bool TilingSetEvictionQueue::EvictionRectIterator::AdvanceToNextTile(
 225     TilingIteratorType* iterator) {
 226   bool found_tile = false;
 227   while (!found_tile) {
 228     ++(*iterator);
 229     if (!(*iterator)) {
 230       tile_ = nullptr;
 231       break;
 232     }
 233     found_tile = GetFirstTileAndCheckIfValid(iterator);
 234   }
 235   return found_tile;
 236 }
 237
 238 template <typename TilingIteratorType>
 239 bool TilingSetEvictionQueue::EvictionRectIterator::GetFirstTileAndCheckIfValid(
 240     TilingIteratorType* iterator) {
 241   PictureLayerTiling* tiling = (*tilings_)[tiling_index_];
 242   tile_ = tiling->TileAt(iterator->index_x(), iterator->index_y());
 243   // If there's nothing to evict, return false.
 244   if (!tile_ || !tile_->HasResource())
 245     return false;
 246   if (skip_pending_visible_rect_ &&
 247       tiling->pending_visible_rect().Intersects(tile_->content_rect())) {
 248     return false;
 249   }
 250   (*tilings_)[tiling_index_]->UpdateTileAndTwinPriority(tile_);
 251   // In other cases, the tile we got is a viable candidate, return true.
 252   return true;
 253 }
 254
 255 // EventuallyTilingIterator
 256 TilingSetEvictionQueue::EventuallyTilingIterator::EventuallyTilingIterator(
 257     std::vector<PictureLayerTiling*>* tilings,
 258     WhichTree tree,
 259     bool skip_shared_out_of_order_tiles)
 260     : EvictionRectIterator(tilings,
 261                            tree,
 262                            skip_shared_out_of_order_tiles,
 263                            true /* skip_pending_visible_rect */) {
 264   // Find the first tiling with a tile.
 265   while (tiling_index_ < tilings_->size()) {
 266     if (!(*tilings_)[tiling_index_]->has_eventually_rect_tiles()) {
 267       ++tiling_index_;
 268       continue;
 269     }
 270     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 271         (*tilings_)[tiling_index_]->tiling_data(),
 272         (*tilings_)[tiling_index_]->current_eventually_rect(),
 273         (*tilings_)[tiling_index_]->current_skewport_rect(),
 274         (*tilings_)[tiling_index_]->current_soon_border_rect());
 275     if (!iterator_) {
 276       ++tiling_index_;
 277       continue;
 278     }
 279     break;
 280   }
 281   if (tiling_index_ >= tilings_->size())
 282     return;
 283   if (!GetFirstTileAndCheckIfValid(&iterator_))
 284     ++(*this);
 285 }
 286
 287 TilingSetEvictionQueue::EventuallyTilingIterator&
 288     TilingSetEvictionQueue::EventuallyTilingIterator::
 289     operator++() {
 290   bool found_tile = AdvanceToNextTile(&iterator_);
 291   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 292     ++tiling_index_;
 293     if (!(*tilings_)[tiling_index_]->has_eventually_rect_tiles())
 294       continue;
 295     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 296         (*tilings_)[tiling_index_]->tiling_data(),
 297         (*tilings_)[tiling_index_]->current_eventually_rect(),
 298         (*tilings_)[tiling_index_]->current_skewport_rect(),
 299         (*tilings_)[tiling_index_]->current_soon_border_rect());
 300     if (!iterator_)
 301       continue;
 302     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 303     if (!found_tile)
 304       found_tile = AdvanceToNextTile(&iterator_);
 305   }
 306   return *this;
 307 }
 308
 309 // SoonBorderTilingIterator
 310 TilingSetEvictionQueue::SoonBorderTilingIterator::SoonBorderTilingIterator(
 311     std::vector<PictureLayerTiling*>* tilings,
 312     WhichTree tree,
 313     bool skip_shared_out_of_order_tiles)
 314     : EvictionRectIterator(tilings,
 315                            tree,
 316                            skip_shared_out_of_order_tiles,
 317                            true /* skip_pending_visible_rect */) {
 318   // Find the first tiling with a tile.
 319   while (tiling_index_ < tilings_->size()) {
 320     if (!(*tilings_)[tiling_index_]->has_soon_border_rect_tiles()) {
 321       ++tiling_index_;
 322       continue;
 323     }
 324     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 325         (*tilings_)[tiling_index_]->tiling_data(),
 326         (*tilings_)[tiling_index_]->current_soon_border_rect(),
 327         (*tilings_)[tiling_index_]->current_skewport_rect(),
 328         (*tilings_)[tiling_index_]->current_visible_rect());
 329     if (!iterator_) {
 330       ++tiling_index_;
 331       continue;
 332     }
 333     break;
 334   }
 335   if (tiling_index_ >= tilings_->size())
 336     return;
 337   if (!GetFirstTileAndCheckIfValid(&iterator_))
 338     ++(*this);
 339 }
 340
 341 TilingSetEvictionQueue::SoonBorderTilingIterator&
 342     TilingSetEvictionQueue::SoonBorderTilingIterator::
 343     operator++() {
 344   bool found_tile = AdvanceToNextTile(&iterator_);
 345   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 346     ++tiling_index_;
 347     if (!(*tilings_)[tiling_index_]->has_soon_border_rect_tiles())
 348       continue;
 349     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 350         (*tilings_)[tiling_index_]->tiling_data(),
 351         (*tilings_)[tiling_index_]->current_soon_border_rect(),
 352         (*tilings_)[tiling_index_]->current_skewport_rect(),
 353         (*tilings_)[tiling_index_]->current_visible_rect());
 354     if (!iterator_)
 355       continue;
 356     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 357     if (!found_tile)
 358       found_tile = AdvanceToNextTile(&iterator_);
 359   }
 360   return *this;
 361 }
 362
 363 // SkewportTilingIterator
 364 TilingSetEvictionQueue::SkewportTilingIterator::SkewportTilingIterator(
 365     std::vector<PictureLayerTiling*>* tilings,
 366     WhichTree tree,
 367     bool skip_shared_out_of_order_tiles)
 368     : EvictionRectIterator(tilings,
 369                            tree,
 370                            skip_shared_out_of_order_tiles,
 371                            true /* skip_pending_visible_rect */) {
 372   // Find the first tiling with a tile.
 373   while (tiling_index_ < tilings_->size()) {
 374     if (!(*tilings_)[tiling_index_]->has_skewport_rect_tiles()) {
 375       ++tiling_index_;
 376       continue;
 377     }
 378     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 379         (*tilings_)[tiling_index_]->tiling_data(),
 380         (*tilings_)[tiling_index_]->current_skewport_rect(),
 381         (*tilings_)[tiling_index_]->current_visible_rect(),
 382         (*tilings_)[tiling_index_]->current_visible_rect());
 383     if (!iterator_) {
 384       ++tiling_index_;
 385       continue;
 386     }
 387     break;
 388   }
 389   if (tiling_index_ >= tilings_->size())
 390     return;
 391   if (!GetFirstTileAndCheckIfValid(&iterator_))
 392     ++(*this);
 393 }
 394
 395 TilingSetEvictionQueue::SkewportTilingIterator&
 396     TilingSetEvictionQueue::SkewportTilingIterator::
 397     operator++() {
 398   bool found_tile = AdvanceToNextTile(&iterator_);
 399   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 400     ++tiling_index_;
 401     if (!(*tilings_)[tiling_index_]->has_skewport_rect_tiles())
 402       continue;
 403     iterator_ = TilingData::ReverseSpiralDifferenceIterator(
 404         (*tilings_)[tiling_index_]->tiling_data(),
 405         (*tilings_)[tiling_index_]->current_skewport_rect(),
 406         (*tilings_)[tiling_index_]->current_visible_rect(),
 407         (*tilings_)[tiling_index_]->current_visible_rect());
 408     if (!iterator_)
 409       continue;
 410     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 411     if (!found_tile)
 412       found_tile = AdvanceToNextTile(&iterator_);
 413   }
 414   return *this;
 415 }
 416
 417 // PendingVisibleIterator
 418 TilingSetEvictionQueue::PendingVisibleTilingIterator::
 419     PendingVisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 420                                  WhichTree tree,
 421                                  bool skip_shared_out_of_order_tiles,
 422                                  bool return_required_for_activation_tiles)
 423     : EvictionRectIterator(tilings,
 424                            tree,
 425                            skip_shared_out_of_order_tiles,
 426                            false /* skip_pending_visible_rect */),
 427       return_required_for_activation_tiles_(
 428           return_required_for_activation_tiles) {
 429   // Find the first tiling with a tile.
 430   while (tiling_index_ < tilings_->size()) {
 431     iterator_ = TilingData::DifferenceIterator(
 432         (*tilings_)[tiling_index_]->tiling_data(),
 433         (*tilings_)[tiling_index_]->pending_visible_rect(),
 434         (*tilings_)[tiling_index_]->current_visible_rect());
 435     if (!iterator_) {
 436       ++tiling_index_;
 437       continue;
 438     }
 439     break;
 440   }
 441   if (tiling_index_ >= tilings_->size())
 442     return;
 443   if (!GetFirstTileAndCheckIfValid(&iterator_)) {
 444     ++(*this);
 445     return;
 446   }
 447   if (!TileMatchesRequiredFlags(tile_)) {
 448     ++(*this);
 449     return;
 450   }
 451 }
 452
 453 TilingSetEvictionQueue::PendingVisibleTilingIterator&
 454     TilingSetEvictionQueue::PendingVisibleTilingIterator::
 455     operator++() {
 456   bool found_tile = AdvanceToNextTile(&iterator_);
 457   while (found_tile && !TileMatchesRequiredFlags(tile_))
 458     found_tile = AdvanceToNextTile(&iterator_);
 459
 460   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 461     ++tiling_index_;
 462     iterator_ = TilingData::DifferenceIterator(
 463         (*tilings_)[tiling_index_]->tiling_data(),
 464         (*tilings_)[tiling_index_]->pending_visible_rect(),
 465         (*tilings_)[tiling_index_]->current_visible_rect());
 466     if (!iterator_)
 467       continue;
 468     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 469     if (!found_tile)
 470       found_tile = AdvanceToNextTile(&iterator_);
 471     while (found_tile && !TileMatchesRequiredFlags(tile_))
 472       found_tile = AdvanceToNextTile(&iterator_);
 473   }
 474   return *this;
 475 }
 476
 477 bool TilingSetEvictionQueue::PendingVisibleTilingIterator::
 478     TileMatchesRequiredFlags(const Tile* tile) const {
 479   bool activation_flag_matches =
 480       tile->required_for_activation() == return_required_for_activation_tiles_;
 481   return activation_flag_matches;
 482 }
 483
 484 // VisibleTilingIterator
 485 TilingSetEvictionQueue::VisibleTilingIterator::VisibleTilingIterator(
 486     std::vector<PictureLayerTiling*>* tilings,
 487     WhichTree tree,
 488     bool skip_shared_out_of_order_tiles,
 489     bool return_occluded_tiles,
 490     bool return_required_for_activation_tiles)
 491     : EvictionRectIterator(tilings,
 492                            tree,
 493                            skip_shared_out_of_order_tiles,
 494                            false /* skip_pending_visible_rect */),
 495       return_occluded_tiles_(return_occluded_tiles),
 496       return_required_for_activation_tiles_(
 497           return_required_for_activation_tiles) {
 498   // Find the first tiling with a tile.
 499   while (tiling_index_ < tilings_->size()) {
 500     if (!(*tilings_)[tiling_index_]->has_visible_rect_tiles()) {
 501       ++tiling_index_;
 502       continue;
 503     }
 504     iterator_ = TilingData::Iterator(
 505         (*tilings_)[tiling_index_]->tiling_data(),
 506         (*tilings_)[tiling_index_]->current_visible_rect(), false);
 507     if (!iterator_) {
 508       ++tiling_index_;
 509       continue;
 510     }
 511     break;
 512   }
 513   if (tiling_index_ >= tilings_->size())
 514     return;
 515   if (!GetFirstTileAndCheckIfValid(&iterator_)) {
 516     ++(*this);
 517     return;
 518   }
 519   if (!TileMatchesRequiredFlags(tile_)) {
 520     ++(*this);
 521     return;
 522   }
 523 }
 524
 525 TilingSetEvictionQueue::VisibleTilingIterator&
 526     TilingSetEvictionQueue::VisibleTilingIterator::
 527     operator++() {
 528   bool found_tile = AdvanceToNextTile(&iterator_);
 529   while (found_tile && !TileMatchesRequiredFlags(tile_))
 530     found_tile = AdvanceToNextTile(&iterator_);
 531
 532   while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
 533     ++tiling_index_;
 534     if (!(*tilings_)[tiling_index_]->has_visible_rect_tiles())
 535       continue;
 536     iterator_ = TilingData::Iterator(
 537         (*tilings_)[tiling_index_]->tiling_data(),
 538         (*tilings_)[tiling_index_]->current_visible_rect(), false);
 539     if (!iterator_)
 540       continue;
 541     found_tile = GetFirstTileAndCheckIfValid(&iterator_);
 542     if (!found_tile)
 543       found_tile = AdvanceToNextTile(&iterator_);
 544     while (found_tile && !TileMatchesRequiredFlags(tile_))
 545       found_tile = AdvanceToNextTile(&iterator_);
 546   }
 547   return *this;
 548 }
 549
 550 bool TilingSetEvictionQueue::VisibleTilingIterator::TileMatchesRequiredFlags(
 551     const Tile* tile) const {
 552   bool activation_flag_matches =
 553       tile->required_for_activation() == return_required_for_activation_tiles_;
 554   bool occluded_flag_matches = tile->is_occluded() == return_occluded_tiles_;
 555   return activation_flag_matches && occluded_flag_matches;
 556 }
 557
 558 }  // namespace cc