| // 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; |
| } |
| (*tilings_)[tiling_index_]->UpdateRequiredStatesOnTile(tile); |
| 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 |