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