cc/resources/raster_tile_priority_queue_all.cc

   1 // Copyright 2015 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 "cc/resources/raster_tile_priority_queue_all.h"
   6
   7 #include "cc/resources/tiling_set_raster_queue_all.h"
   8
   9 namespace cc {
  10
  11 namespace {
  12
  13 class RasterOrderComparator {
  14  public:
  15   explicit RasterOrderComparator(TreePriority tree_priority)
  16       : tree_priority_(tree_priority) {}
  17
  18   bool operator()(
  19       const RasterTilePriorityQueueAll::PairedTilingSetQueue* a,
  20       const RasterTilePriorityQueueAll::PairedTilingSetQueue* b) const {
  21     // Note that in this function, we have to return true if and only if
  22     // a is strictly lower priority than b. Note that for the sake of
  23     // completeness, empty queue is considered to have lowest priority.
  24     if (a->IsEmpty() || b->IsEmpty())
  25       return b->IsEmpty() < a->IsEmpty();
  26
  27     WhichTree a_tree = a->NextTileIteratorTree(tree_priority_);
  28     const TilingSetRasterQueueAll* a_queue =
  29         a_tree == ACTIVE_TREE ? a->active_queue() : a->pending_queue();
  30
  31     WhichTree b_tree = b->NextTileIteratorTree(tree_priority_);
  32     const TilingSetRasterQueueAll* b_queue =
  33         b_tree == ACTIVE_TREE ? b->active_queue() : b->pending_queue();
  34
  35     const Tile* a_tile = a_queue->Top();
  36     const Tile* b_tile = b_queue->Top();
  37
  38     const TilePriority& a_priority =
  39         a_tile->priority_for_tree_priority(tree_priority_);
  40     const TilePriority& b_priority =
  41         b_tile->priority_for_tree_priority(tree_priority_);
  42     bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
  43
  44     // In smoothness mode, we should return pending NOW tiles before active
  45     // EVENTUALLY tiles. So if both priorities here are eventually, we need to
  46     // check the pending priority.
  47     if (prioritize_low_res &&
  48         a_priority.priority_bin == TilePriority::EVENTUALLY &&
  49         b_priority.priority_bin == TilePriority::EVENTUALLY) {
  50       bool a_is_pending_now =
  51           a_tile->priority(PENDING_TREE).priority_bin == TilePriority::NOW;
  52       bool b_is_pending_now =
  53           b_tile->priority(PENDING_TREE).priority_bin == TilePriority::NOW;
  54       if (a_is_pending_now || b_is_pending_now)
  55         return a_is_pending_now < b_is_pending_now;
  56
  57       // In case neither one is pending now, fall through.
  58     }
  59
  60     // If the bin is the same but the resolution is not, then the order will be
  61     // determined by whether we prioritize low res or not.
  62     // TODO(vmpstr): Remove this when TilePriority is no longer a member of Tile
  63     // class but instead produced by the iterators.
  64     if (b_priority.priority_bin == a_priority.priority_bin &&
  65         b_priority.resolution != a_priority.resolution) {
  66       // Non ideal resolution should be sorted lower than other resolutions.
  67       if (a_priority.resolution == NON_IDEAL_RESOLUTION)
  68         return true;
  69
  70       if (b_priority.resolution == NON_IDEAL_RESOLUTION)
  71         return false;
  72
  73       if (prioritize_low_res)
  74         return b_priority.resolution == LOW_RESOLUTION;
  75       return b_priority.resolution == HIGH_RESOLUTION;
  76     }
  77
  78     return b_priority.IsHigherPriorityThan(a_priority);
  79   }
  80
  81  private:
  82   TreePriority tree_priority_;
  83 };
  84
  85 WhichTree HigherPriorityTree(TreePriority tree_priority,
  86                              const TilingSetRasterQueueAll* active_queue,
  87                              const TilingSetRasterQueueAll* pending_queue,
  88                              const Tile* shared_tile) {
  89   // In cases when we're given an active tile with a non ideal active resolution
  90   // (or pending tile with non ideal pending resolution), we should return the
  91   // other tree. The reason for this is that tiling set iterators will not
  92   // return non ideal tiles and the only way we get here is if we're skipping
  93   // twin tiles, but since it's non-ideal on the twin, we shouldn't skip it.
  94   // TODO(vmpstr): Remove when tiles aren't shared.
  95   const Tile* active_tile = shared_tile ? shared_tile : active_queue->Top();
  96   const Tile* pending_tile = shared_tile ? shared_tile : pending_queue->Top();
  97   if (active_tile->priority(ACTIVE_TREE).resolution == NON_IDEAL_RESOLUTION)
  98     return PENDING_TREE;
  99   if (pending_tile->priority(PENDING_TREE).resolution == NON_IDEAL_RESOLUTION)
 100     return ACTIVE_TREE;
 101
 102   switch (tree_priority) {
 103     case SMOOTHNESS_TAKES_PRIORITY: {
 104       const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE);
 105       const TilePriority& pending_priority =
 106           pending_tile->priority(PENDING_TREE);
 107
 108       // If we're down to eventually bin tiles on the active tree, process the
 109       // pending tree to allow tiles required for activation to be initialized
 110       // when memory policy only allows prepaint.
 111       if (active_priority.priority_bin == TilePriority::EVENTUALLY &&
 112           pending_priority.priority_bin == TilePriority::NOW) {
 113         return PENDING_TREE;
 114       }
 115       return ACTIVE_TREE;
 116     }
 117     case NEW_CONTENT_TAKES_PRIORITY:
 118       return PENDING_TREE;
 119     case SAME_PRIORITY_FOR_BOTH_TREES: {
 120       const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE);
 121       const TilePriority& pending_priority =
 122           pending_tile->priority(PENDING_TREE);
 123
 124       if (active_priority.IsHigherPriorityThan(pending_priority))
 125         return ACTIVE_TREE;
 126       return PENDING_TREE;
 127     }
 128     default:
 129       NOTREACHED();
 130       return ACTIVE_TREE;
 131   }
 132 }
 133
 134 scoped_ptr<TilingSetRasterQueueAll> CreateTilingSetRasterQueue(
 135     PictureLayerImpl* layer,
 136     TreePriority tree_priority) {
 137   if (!layer)
 138     return nullptr;
 139   PictureLayerTilingSet* tiling_set = layer->picture_layer_tiling_set();
 140   bool prioritize_low_res = tree_priority == SMOOTHNESS_TAKES_PRIORITY;
 141   return make_scoped_ptr(
 142       new TilingSetRasterQueueAll(tiling_set, prioritize_low_res));
 143 }
 144
 145 }  // namespace
 146
 147 RasterTilePriorityQueueAll::RasterTilePriorityQueueAll() {
 148 }
 149
 150 RasterTilePriorityQueueAll::~RasterTilePriorityQueueAll() {
 151 }
 152
 153 void RasterTilePriorityQueueAll::Build(
 154     const std::vector<PictureLayerImpl::Pair>& paired_layers,
 155     TreePriority tree_priority) {
 156   tree_priority_ = tree_priority;
 157   for (std::vector<PictureLayerImpl::Pair>::const_iterator it =
 158            paired_layers.begin();
 159        it != paired_layers.end(); ++it) {
 160     paired_queues_.push_back(
 161         make_scoped_ptr(new PairedTilingSetQueue(*it, tree_priority_)));
 162   }
 163   paired_queues_.make_heap(RasterOrderComparator(tree_priority_));
 164 }
 165
 166 bool RasterTilePriorityQueueAll::IsEmpty() const {
 167   return paired_queues_.empty() || paired_queues_.front()->IsEmpty();
 168 }
 169
 170 Tile* RasterTilePriorityQueueAll::Top() {
 171   DCHECK(!IsEmpty());
 172   return paired_queues_.front()->Top(tree_priority_);
 173 }
 174
 175 void RasterTilePriorityQueueAll::Pop() {
 176   DCHECK(!IsEmpty());
 177
 178   paired_queues_.pop_heap(RasterOrderComparator(tree_priority_));
 179   PairedTilingSetQueue* paired_queue = paired_queues_.back();
 180   paired_queue->Pop(tree_priority_);
 181   paired_queues_.push_heap(RasterOrderComparator(tree_priority_));
 182 }
 183
 184 RasterTilePriorityQueueAll::PairedTilingSetQueue::PairedTilingSetQueue() {
 185 }
 186
 187 RasterTilePriorityQueueAll::PairedTilingSetQueue::PairedTilingSetQueue(
 188     const PictureLayerImpl::Pair& layer_pair,
 189     TreePriority tree_priority)
 190     : active_queue_(
 191           CreateTilingSetRasterQueue(layer_pair.active, tree_priority)),
 192       pending_queue_(
 193           CreateTilingSetRasterQueue(layer_pair.pending, tree_priority)),
 194       has_both_layers_(layer_pair.active && layer_pair.pending) {
 195   SkipTilesReturnedByTwin(tree_priority);
 196
 197   TRACE_EVENT_INSTANT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
 198                        "PairedTilingSetQueue::PairedTilingSetQueue",
 199                        TRACE_EVENT_SCOPE_THREAD, "state", StateAsValue());
 200 }
 201
 202 RasterTilePriorityQueueAll::PairedTilingSetQueue::~PairedTilingSetQueue() {
 203   TRACE_EVENT_INSTANT1(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
 204                        "PairedTilingSetQueue::~PairedTilingSetQueue",
 205                        TRACE_EVENT_SCOPE_THREAD, "state", StateAsValue());
 206 }
 207
 208 bool RasterTilePriorityQueueAll::PairedTilingSetQueue::IsEmpty() const {
 209   return (!active_queue_ || active_queue_->IsEmpty()) &&
 210          (!pending_queue_ || pending_queue_->IsEmpty());
 211 }
 212
 213 Tile* RasterTilePriorityQueueAll::PairedTilingSetQueue::Top(
 214     TreePriority tree_priority) {
 215   DCHECK(!IsEmpty());
 216
 217   WhichTree next_tree = NextTileIteratorTree(tree_priority);
 218   TilingSetRasterQueueAll* next_queue =
 219       next_tree == ACTIVE_TREE ? active_queue_.get() : pending_queue_.get();
 220   DCHECK(next_queue && !next_queue->IsEmpty());
 221   Tile* tile = next_queue->Top();
 222   DCHECK(returned_tiles_for_debug_.find(tile) ==
 223          returned_tiles_for_debug_.end());
 224   return tile;
 225 }
 226
 227 void RasterTilePriorityQueueAll::PairedTilingSetQueue::Pop(
 228     TreePriority tree_priority) {
 229   DCHECK(!IsEmpty());
 230
 231   WhichTree next_tree = NextTileIteratorTree(tree_priority);
 232   TilingSetRasterQueueAll* next_queue =
 233       next_tree == ACTIVE_TREE ? active_queue_.get() : pending_queue_.get();
 234   DCHECK(next_queue && !next_queue->IsEmpty());
 235   DCHECK(returned_tiles_for_debug_.insert(next_queue->Top()).second);
 236   next_queue->Pop();
 237
 238   SkipTilesReturnedByTwin(tree_priority);
 239
 240   // If no empty, use Top to do DCHECK the next iterator.
 241   DCHECK(IsEmpty() || Top(tree_priority));
 242 }
 243
 244 void RasterTilePriorityQueueAll::PairedTilingSetQueue::SkipTilesReturnedByTwin(
 245     TreePriority tree_priority) {
 246   if (!has_both_layers_)
 247     return;
 248
 249   // We have both layers (active and pending) thus we can encounter shared
 250   // tiles twice (from the active iterator and from the pending iterator).
 251   while (!IsEmpty()) {
 252     WhichTree next_tree = NextTileIteratorTree(tree_priority);
 253     TilingSetRasterQueueAll* next_queue =
 254         next_tree == ACTIVE_TREE ? active_queue_.get() : pending_queue_.get();
 255     DCHECK(next_queue && !next_queue->IsEmpty());
 256
 257     // Accept all non-shared tiles.
 258     const Tile* tile = next_queue->Top();
 259     if (!tile->is_shared())
 260       break;
 261
 262     // Accept a shared tile if the next tree is the higher priority one
 263     // corresponding the iterator (active or pending) which usually (but due
 264     // to spiral iterators not always) returns the shared tile first.
 265     if (next_tree == HigherPriorityTree(tree_priority, nullptr, nullptr, tile))
 266       break;
 267
 268     next_queue->Pop();
 269   }
 270 }
 271
 272 WhichTree
 273 RasterTilePriorityQueueAll::PairedTilingSetQueue::NextTileIteratorTree(
 274     TreePriority tree_priority) const {
 275   DCHECK(!IsEmpty());
 276
 277   // If we only have one queue with tiles, return it.
 278   if (!active_queue_ || active_queue_->IsEmpty())
 279     return PENDING_TREE;
 280   if (!pending_queue_ || pending_queue_->IsEmpty())
 281     return ACTIVE_TREE;
 282
 283   // Now both iterators have tiles, so we have to decide based on tree priority.
 284   return HigherPriorityTree(tree_priority, active_queue_.get(),
 285                             pending_queue_.get(), nullptr);
 286 }
 287
 288 scoped_refptr<base::trace_event::ConvertableToTraceFormat>
 289 RasterTilePriorityQueueAll::PairedTilingSetQueue::StateAsValue() const {
 290   scoped_refptr<base::trace_event::TracedValue> state =
 291       new base::trace_event::TracedValue();
 292
 293   bool active_queue_has_tile = active_queue_ && !active_queue_->IsEmpty();
 294   TilePriority::PriorityBin active_priority_bin = TilePriority::EVENTUALLY;
 295   TilePriority::PriorityBin pending_priority_bin = TilePriority::EVENTUALLY;
 296   if (active_queue_has_tile) {
 297     active_priority_bin =
 298         active_queue_->Top()->priority(ACTIVE_TREE).priority_bin;
 299     pending_priority_bin =
 300         active_queue_->Top()->priority(PENDING_TREE).priority_bin;
 301   }
 302
 303   state->BeginDictionary("active_queue");
 304   state->SetBoolean("has_tile", active_queue_has_tile);
 305   state->SetInteger("active_priority_bin", active_priority_bin);
 306   state->SetInteger("pending_priority_bin", pending_priority_bin);
 307   state->EndDictionary();
 308
 309   bool pending_queue_has_tile = pending_queue_ && !pending_queue_->IsEmpty();
 310   active_priority_bin = TilePriority::EVENTUALLY;
 311   pending_priority_bin = TilePriority::EVENTUALLY;
 312   if (pending_queue_has_tile) {
 313     active_priority_bin =
 314         pending_queue_->Top()->priority(ACTIVE_TREE).priority_bin;
 315     pending_priority_bin =
 316         pending_queue_->Top()->priority(PENDING_TREE).priority_bin;
 317   }
 318
 319   state->BeginDictionary("pending_queue");
 320   state->SetBoolean("has_tile", active_queue_has_tile);
 321   state->SetInteger("active_priority_bin", active_priority_bin);
 322   state->SetInteger("pending_priority_bin", pending_priority_bin);
 323   state->EndDictionary();
 324   return state;
 325 }
 326
 327 }  // namespace cc