cc/tiles/tiling_set_eviction_queue.cc

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