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