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