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