blob: da09e3192e991f1bf4bee73da5f08f43fa112f35 [file] [log] [blame]
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <stddef.h>
#include <utility>
#include "cc/tiles/tiling_set_eviction_queue.h"
namespace cc {
TilingSetEvictionQueue::TilingSetEvictionQueue(
PictureLayerTilingSet* tiling_set)
: tree_(tiling_set->tree()), phase_(EVENTUALLY_RECT) {
// Early out if the layer has no tilings.
if (!tiling_set->num_tilings())
return;
GenerateTilingOrder(tiling_set);
eventually_iterator_ = EventuallyTilingIterator(&tilings_, tree_);
if (eventually_iterator_.done()) {
AdvancePhase();
return;
}
current_tile_ = *eventually_iterator_;
}
TilingSetEvictionQueue::~TilingSetEvictionQueue() {
}
void TilingSetEvictionQueue::GenerateTilingOrder(
PictureLayerTilingSet* tiling_set) {
tilings_.reserve(tiling_set->num_tilings());
// Generate all of the tilings in the order described in the header comment
// for this class.
PictureLayerTilingSet::TilingRange range =
tiling_set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES);
for (size_t index = range.start; index < range.end; ++index) {
PictureLayerTiling* tiling = tiling_set->tiling_at(index);
if (tiling->has_tiles())
tilings_.push_back(tiling);
}
range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES);
for (size_t i = range.start; i < range.end; ++i) {
size_t index = range.start + (range.end - 1 - i);
PictureLayerTiling* tiling = tiling_set->tiling_at(index);
if (tiling->has_tiles())
tilings_.push_back(tiling);
}
range = tiling_set->GetTilingRange(
PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES);
for (size_t i = range.start; i < range.end; ++i) {
size_t index = range.start + (range.end - 1 - i);
PictureLayerTiling* tiling = tiling_set->tiling_at(index);
if (tiling->has_tiles())
tilings_.push_back(tiling);
}
range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOW_RES);
for (size_t index = range.start; index < range.end; ++index) {
PictureLayerTiling* tiling = tiling_set->tiling_at(index);
if (tiling->has_tiles())
tilings_.push_back(tiling);
}
range = tiling_set->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
for (size_t index = range.start; index < range.end; ++index) {
PictureLayerTiling* tiling = tiling_set->tiling_at(index);
if (tiling->has_tiles())
tilings_.push_back(tiling);
}
DCHECK_GE(tiling_set->num_tilings(), tilings_.size());
}
void TilingSetEvictionQueue::AdvancePhase() {
current_tile_ = PrioritizedTile();
while (!current_tile_.tile() &&
phase_ != VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED) {
phase_ = static_cast<Phase>(phase_ + 1);
switch (phase_) {
case EVENTUALLY_RECT:
NOTREACHED();
break;
case SOON_BORDER_RECT:
soon_iterator_ = SoonBorderTilingIterator(&tilings_, tree_);
if (!soon_iterator_.done())
current_tile_ = *soon_iterator_;
break;
case SKEWPORT_RECT:
skewport_iterator_ = SkewportTilingIterator(&tilings_, tree_);
if (!skewport_iterator_.done())
current_tile_ = *skewport_iterator_;
break;
case PENDING_VISIBLE_RECT:
pending_visible_iterator_ = PendingVisibleTilingIterator(
&tilings_, tree_, false /* return required for activation tiles */);
if (!pending_visible_iterator_.done())
current_tile_ = *pending_visible_iterator_;
break;
case PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION:
pending_visible_iterator_ = PendingVisibleTilingIterator(
&tilings_, tree_, true /* return required for activation tiles */);
if (!pending_visible_iterator_.done())
current_tile_ = *pending_visible_iterator_;
break;
case VISIBLE_RECT_OCCLUDED:
visible_iterator_ = VisibleTilingIterator(
&tilings_, tree_, true /* return occluded tiles */,
false /* return required for activation tiles */);
if (!visible_iterator_.done())
current_tile_ = *visible_iterator_;
break;
case VISIBLE_RECT_UNOCCLUDED:
visible_iterator_ = VisibleTilingIterator(
&tilings_, tree_, false /* return occluded tiles */,
false /* return required for activation tiles */);
if (!visible_iterator_.done())
current_tile_ = *visible_iterator_;
break;
case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
visible_iterator_ = VisibleTilingIterator(
&tilings_, tree_, true /* return occluded tiles */,
true /* return required for activation tiles */);
if (!visible_iterator_.done())
current_tile_ = *visible_iterator_;
break;
case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
visible_iterator_ = VisibleTilingIterator(
&tilings_, tree_, false /* return occluded tiles */,
true /* return required for activation tiles */);
if (!visible_iterator_.done())
current_tile_ = *visible_iterator_;
break;
}
}
}
bool TilingSetEvictionQueue::IsEmpty() const {
return !current_tile_.tile();
}
const PrioritizedTile& TilingSetEvictionQueue::Top() const {
DCHECK(!IsEmpty());
return current_tile_;
}
void TilingSetEvictionQueue::Pop() {
DCHECK(!IsEmpty());
current_tile_ = PrioritizedTile();
switch (phase_) {
case EVENTUALLY_RECT:
++eventually_iterator_;
if (!eventually_iterator_.done())
current_tile_ = *eventually_iterator_;
break;
case SOON_BORDER_RECT:
++soon_iterator_;
if (!soon_iterator_.done())
current_tile_ = *soon_iterator_;
break;
case SKEWPORT_RECT:
++skewport_iterator_;
if (!skewport_iterator_.done())
current_tile_ = *skewport_iterator_;
break;
case PENDING_VISIBLE_RECT:
case PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION:
++pending_visible_iterator_;
if (!pending_visible_iterator_.done())
current_tile_ = *pending_visible_iterator_;
break;
case VISIBLE_RECT_OCCLUDED:
case VISIBLE_RECT_UNOCCLUDED:
case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
++visible_iterator_;
if (!visible_iterator_.done())
current_tile_ = *visible_iterator_;
break;
}
if (!current_tile_.tile())
AdvancePhase();
}
// EvictionRectIterator
TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator()
: tilings_(nullptr), tree_(ACTIVE_TREE), tiling_index_(0) {
}
TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator(
std::vector<PictureLayerTiling*>* tilings,
WhichTree tree,
PictureLayerTiling::PriorityRectType priority_rect_type)
: tilings_(tilings),
tree_(tree),
priority_rect_type_(priority_rect_type),
tiling_index_(0) {
}
template <typename TilingIteratorType>
bool TilingSetEvictionQueue::EvictionRectIterator::AdvanceToNextTile(
TilingIteratorType* iterator) {
bool found_tile = false;
while (!found_tile) {
++(*iterator);
if (!(*iterator)) {
prioritized_tile_ = PrioritizedTile();
break;
}
found_tile = GetFirstTileAndCheckIfValid(iterator);
}
return found_tile;
}
template <typename TilingIteratorType>
bool TilingSetEvictionQueue::EvictionRectIterator::GetFirstTileAndCheckIfValid(
TilingIteratorType* iterator) {
PictureLayerTiling* tiling = (*tilings_)[tiling_index_];
Tile* tile = tiling->TileAt(iterator->index_x(), iterator->index_y());
prioritized_tile_ = PrioritizedTile();
// If there's nothing to evict, return false.
if (!tile || !tile->draw_info().has_resource())
return false;
// After the pending visible rect has been processed, we must return false
// for pending visible rect tiles as tiling iterators do not ignore those
// tiles.
if (priority_rect_type_ > PictureLayerTiling::PENDING_VISIBLE_RECT) {
gfx::Rect tile_rect = tiling->tiling_data()->TileBounds(
tile->tiling_i_index(), tile->tiling_j_index());
if (tiling->pending_visible_rect().Intersects(tile_rect))
return false;
}
prioritized_tile_ = (*tilings_)[tiling_index_]->MakePrioritizedTile(
tile, priority_rect_type_);
// In other cases, the tile we got is a viable candidate, return true.
return true;
}
// EventuallyTilingIterator
TilingSetEvictionQueue::EventuallyTilingIterator::EventuallyTilingIterator(
std::vector<PictureLayerTiling*>* tilings,
WhichTree tree)
: EvictionRectIterator(tilings, tree, PictureLayerTiling::EVENTUALLY_RECT) {
// Find the first tiling with a tile.
while (tiling_index_ < tilings_->size()) {
if (!(*tilings_)[tiling_index_]->has_eventually_rect_tiles()) {
++tiling_index_;
continue;
}
iterator_ = TilingData::ReverseSpiralDifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_eventually_rect(),
(*tilings_)[tiling_index_]->current_skewport_rect(),
(*tilings_)[tiling_index_]->current_soon_border_rect());
if (!iterator_) {
++tiling_index_;
continue;
}
break;
}
if (tiling_index_ >= tilings_->size())
return;
if (!GetFirstTileAndCheckIfValid(&iterator_))
++(*this);
}
TilingSetEvictionQueue::EventuallyTilingIterator&
TilingSetEvictionQueue::EventuallyTilingIterator::
operator++() {
bool found_tile = AdvanceToNextTile(&iterator_);
while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
++tiling_index_;
if (!(*tilings_)[tiling_index_]->has_eventually_rect_tiles())
continue;
iterator_ = TilingData::ReverseSpiralDifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_eventually_rect(),
(*tilings_)[tiling_index_]->current_skewport_rect(),
(*tilings_)[tiling_index_]->current_soon_border_rect());
if (!iterator_)
continue;
found_tile = GetFirstTileAndCheckIfValid(&iterator_);
if (!found_tile)
found_tile = AdvanceToNextTile(&iterator_);
}
return *this;
}
// SoonBorderTilingIterator
TilingSetEvictionQueue::SoonBorderTilingIterator::SoonBorderTilingIterator(
std::vector<PictureLayerTiling*>* tilings,
WhichTree tree)
: EvictionRectIterator(tilings,
tree,
PictureLayerTiling::SOON_BORDER_RECT) {
// Find the first tiling with a tile.
while (tiling_index_ < tilings_->size()) {
if (!(*tilings_)[tiling_index_]->has_soon_border_rect_tiles()) {
++tiling_index_;
continue;
}
iterator_ = TilingData::ReverseSpiralDifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_soon_border_rect(),
(*tilings_)[tiling_index_]->current_skewport_rect(),
(*tilings_)[tiling_index_]->current_visible_rect());
if (!iterator_) {
++tiling_index_;
continue;
}
break;
}
if (tiling_index_ >= tilings_->size())
return;
if (!GetFirstTileAndCheckIfValid(&iterator_))
++(*this);
}
TilingSetEvictionQueue::SoonBorderTilingIterator&
TilingSetEvictionQueue::SoonBorderTilingIterator::
operator++() {
bool found_tile = AdvanceToNextTile(&iterator_);
while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
++tiling_index_;
if (!(*tilings_)[tiling_index_]->has_soon_border_rect_tiles())
continue;
iterator_ = TilingData::ReverseSpiralDifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_soon_border_rect(),
(*tilings_)[tiling_index_]->current_skewport_rect(),
(*tilings_)[tiling_index_]->current_visible_rect());
if (!iterator_)
continue;
found_tile = GetFirstTileAndCheckIfValid(&iterator_);
if (!found_tile)
found_tile = AdvanceToNextTile(&iterator_);
}
return *this;
}
// SkewportTilingIterator
TilingSetEvictionQueue::SkewportTilingIterator::SkewportTilingIterator(
std::vector<PictureLayerTiling*>* tilings,
WhichTree tree)
: EvictionRectIterator(tilings, tree, PictureLayerTiling::SKEWPORT_RECT) {
// Find the first tiling with a tile.
while (tiling_index_ < tilings_->size()) {
if (!(*tilings_)[tiling_index_]->has_skewport_rect_tiles()) {
++tiling_index_;
continue;
}
iterator_ = TilingData::ReverseSpiralDifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_skewport_rect(),
(*tilings_)[tiling_index_]->current_visible_rect(),
(*tilings_)[tiling_index_]->current_visible_rect());
if (!iterator_) {
++tiling_index_;
continue;
}
break;
}
if (tiling_index_ >= tilings_->size())
return;
if (!GetFirstTileAndCheckIfValid(&iterator_))
++(*this);
}
TilingSetEvictionQueue::SkewportTilingIterator&
TilingSetEvictionQueue::SkewportTilingIterator::
operator++() {
bool found_tile = AdvanceToNextTile(&iterator_);
while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
++tiling_index_;
if (!(*tilings_)[tiling_index_]->has_skewport_rect_tiles())
continue;
iterator_ = TilingData::ReverseSpiralDifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_skewport_rect(),
(*tilings_)[tiling_index_]->current_visible_rect(),
(*tilings_)[tiling_index_]->current_visible_rect());
if (!iterator_)
continue;
found_tile = GetFirstTileAndCheckIfValid(&iterator_);
if (!found_tile)
found_tile = AdvanceToNextTile(&iterator_);
}
return *this;
}
// PendingVisibleIterator
TilingSetEvictionQueue::PendingVisibleTilingIterator::
PendingVisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
WhichTree tree,
bool return_required_for_activation_tiles)
: EvictionRectIterator(tilings,
tree,
PictureLayerTiling::PENDING_VISIBLE_RECT),
return_required_for_activation_tiles_(
return_required_for_activation_tiles) {
// Find the first tiling with a tile.
while (tiling_index_ < tilings_->size()) {
iterator_ = TilingData::DifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->pending_visible_rect(),
(*tilings_)[tiling_index_]->current_visible_rect());
if (!iterator_) {
++tiling_index_;
continue;
}
break;
}
if (tiling_index_ >= tilings_->size())
return;
if (!GetFirstTileAndCheckIfValid(&iterator_)) {
++(*this);
return;
}
if (!TileMatchesRequiredFlags(prioritized_tile_)) {
++(*this);
return;
}
}
TilingSetEvictionQueue::PendingVisibleTilingIterator&
TilingSetEvictionQueue::PendingVisibleTilingIterator::
operator++() {
bool found_tile = AdvanceToNextTile(&iterator_);
while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
found_tile = AdvanceToNextTile(&iterator_);
while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
++tiling_index_;
iterator_ = TilingData::DifferenceIterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->pending_visible_rect(),
(*tilings_)[tiling_index_]->current_visible_rect());
if (!iterator_)
continue;
found_tile = GetFirstTileAndCheckIfValid(&iterator_);
if (!found_tile)
found_tile = AdvanceToNextTile(&iterator_);
while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
found_tile = AdvanceToNextTile(&iterator_);
}
return *this;
}
bool TilingSetEvictionQueue::PendingVisibleTilingIterator::
TileMatchesRequiredFlags(const PrioritizedTile& tile) const {
bool activation_flag_matches = tile.tile()->required_for_activation() ==
return_required_for_activation_tiles_;
return activation_flag_matches;
}
// VisibleTilingIterator
TilingSetEvictionQueue::VisibleTilingIterator::VisibleTilingIterator(
std::vector<PictureLayerTiling*>* tilings,
WhichTree tree,
bool return_occluded_tiles,
bool return_required_for_activation_tiles)
: EvictionRectIterator(tilings, tree, PictureLayerTiling::VISIBLE_RECT),
return_occluded_tiles_(return_occluded_tiles),
return_required_for_activation_tiles_(
return_required_for_activation_tiles) {
// Find the first tiling with a tile.
while (tiling_index_ < tilings_->size()) {
if (!(*tilings_)[tiling_index_]->has_visible_rect_tiles()) {
++tiling_index_;
continue;
}
iterator_ = TilingData::Iterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_visible_rect(), false);
if (!iterator_) {
++tiling_index_;
continue;
}
break;
}
if (tiling_index_ >= tilings_->size())
return;
if (!GetFirstTileAndCheckIfValid(&iterator_)) {
++(*this);
return;
}
if (!TileMatchesRequiredFlags(prioritized_tile_)) {
++(*this);
return;
}
}
TilingSetEvictionQueue::VisibleTilingIterator&
TilingSetEvictionQueue::VisibleTilingIterator::
operator++() {
bool found_tile = AdvanceToNextTile(&iterator_);
while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
found_tile = AdvanceToNextTile(&iterator_);
while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
++tiling_index_;
if (!(*tilings_)[tiling_index_]->has_visible_rect_tiles())
continue;
iterator_ = TilingData::Iterator(
(*tilings_)[tiling_index_]->tiling_data(),
(*tilings_)[tiling_index_]->current_visible_rect(), false);
if (!iterator_)
continue;
found_tile = GetFirstTileAndCheckIfValid(&iterator_);
if (!found_tile)
found_tile = AdvanceToNextTile(&iterator_);
while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
found_tile = AdvanceToNextTile(&iterator_);
}
return *this;
}
bool TilingSetEvictionQueue::VisibleTilingIterator::TileMatchesRequiredFlags(
const PrioritizedTile& tile) const {
bool activation_flag_matches = tile.tile()->required_for_activation() ==
return_required_for_activation_tiles_;
bool occluded_flag_matches = tile.is_occluded() == return_occluded_tiles_;
return activation_flag_matches && occluded_flag_matches;
}
} // namespace cc