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     // b is strictly lower priority than a. 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     // If the bin is the same but the resolution is not, then the order will be
  43     // determined by whether we prioritize low res or not.
  44     // TODO(vmpstr): Remove this when TilePriority is no longer a member of Tile
  45     // class but instead produced by the iterators.
  46     if (b_priority.priority_bin == a_priority.priority_bin &&
  47         b_priority.resolution != a_priority.resolution) {
  48       // Non ideal resolution should be sorted lower than other resolutions.
  49       if (a_priority.resolution == NON_IDEAL_RESOLUTION)
  50         return true;
  51
  52       if (b_priority.resolution == NON_IDEAL_RESOLUTION)
  53         return false;
  54
  55       if (prioritize_low_res)
  56         return b_priority.resolution == LOW_RESOLUTION;
  57       return b_priority.resolution == HIGH_RESOLUTION;
  58     }
  59     return b_priority.IsHigherPriorityThan(a_priority);
  60   }
  61
  62  private:
  63   TreePriority tree_priority_;
  64 };
  65
  66 }  // namespace
  67
  68 RasterTilePriorityQueue::RasterTilePriorityQueue() {
  69 }
  70
  71 RasterTilePriorityQueue::~RasterTilePriorityQueue() {
  72 }
  73
  74 void RasterTilePriorityQueue::Build(
  75     const std::vector<PictureLayerImpl::Pair>& paired_layers,
  76     TreePriority tree_priority) {
  77   tree_priority_ = tree_priority;
  78   for (std::vector<PictureLayerImpl::Pair>::const_iterator it =
  79            paired_layers.begin();
  80        it != paired_layers.end();
  81        ++it) {
  82     paired_queues_.push_back(
  83         make_scoped_ptr(new PairedPictureLayerQueue(*it, tree_priority_)));
  84   }
  85   paired_queues_.make_heap(RasterOrderComparator(tree_priority_));
  86 }
  87
  88 void RasterTilePriorityQueue::Reset() {
  89   paired_queues_.clear();
  90 }
  91
  92 bool RasterTilePriorityQueue::IsEmpty() const {
  93   return paired_queues_.empty() || paired_queues_.front()->IsEmpty();
  94 }
  95
  96 Tile* RasterTilePriorityQueue::Top() {
  97   DCHECK(!IsEmpty());
  98   return paired_queues_.front()->Top(tree_priority_);
  99 }
 100
 101 void RasterTilePriorityQueue::Pop() {
 102   DCHECK(!IsEmpty());
 103
 104   paired_queues_.pop_heap(RasterOrderComparator(tree_priority_));
 105   PairedPictureLayerQueue* paired_queue = paired_queues_.back();
 106   paired_queue->Pop(tree_priority_);
 107   paired_queues_.push_heap(RasterOrderComparator(tree_priority_));
 108 }
 109
 110 RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
 111 }
 112
 113 RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue(
 114     const PictureLayerImpl::Pair& layer_pair,
 115     TreePriority tree_priority)
 116     : active_iterator(layer_pair.active
 117                           ? PictureLayerImpl::LayerRasterTileIterator(
 118                                 layer_pair.active,
 119                                 tree_priority == SMOOTHNESS_TAKES_PRIORITY)
 120                           : PictureLayerImpl::LayerRasterTileIterator()),
 121       pending_iterator(layer_pair.pending
 122                            ? PictureLayerImpl::LayerRasterTileIterator(
 123                                  layer_pair.pending,
 124                                  tree_priority == SMOOTHNESS_TAKES_PRIORITY)
 125                            : PictureLayerImpl::LayerRasterTileIterator()) {
 126 }
 127
 128 RasterTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
 129 }
 130
 131 bool RasterTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const {
 132   return !active_iterator && !pending_iterator;
 133 }
 134
 135 Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::Top(
 136     TreePriority tree_priority) {
 137   DCHECK(!IsEmpty());
 138
 139   WhichTree next_tree = NextTileIteratorTree(tree_priority);
 140   PictureLayerImpl::LayerRasterTileIterator* next_iterator =
 141       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
 142   DCHECK(*next_iterator);
 143   Tile* tile = **next_iterator;
 144   DCHECK(std::find(returned_shared_tiles.begin(),
 145                    returned_shared_tiles.end(),
 146                    tile) == returned_shared_tiles.end());
 147   return tile;
 148 }
 149
 150 void RasterTilePriorityQueue::PairedPictureLayerQueue::Pop(
 151     TreePriority tree_priority) {
 152   DCHECK(!IsEmpty());
 153
 154   WhichTree next_tree = NextTileIteratorTree(tree_priority);
 155   PictureLayerImpl::LayerRasterTileIterator* next_iterator =
 156       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
 157   DCHECK(*next_iterator);
 158   returned_shared_tiles.push_back(**next_iterator);
 159   ++(*next_iterator);
 160
 161   if (IsEmpty())
 162     return;
 163
 164   next_tree = NextTileIteratorTree(tree_priority);
 165   next_iterator =
 166       next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
 167   while (std::find(returned_shared_tiles.begin(),
 168                    returned_shared_tiles.end(),
 169                    **next_iterator) != returned_shared_tiles.end()) {
 170     ++(*next_iterator);
 171     if (IsEmpty())
 172       break;
 173     next_tree = NextTileIteratorTree(tree_priority);
 174     next_iterator =
 175         next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
 176   }
 177 }
 178
 179 WhichTree
 180 RasterTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
 181     TreePriority tree_priority) const {
 182   DCHECK(!IsEmpty());
 183
 184   // If we only have one iterator with tiles, return it.
 185   if (!active_iterator)
 186     return PENDING_TREE;
 187   if (!pending_iterator)
 188     return ACTIVE_TREE;
 189
 190   // Now both iterators have tiles, so we have to decide based on tree priority.
 191   switch (tree_priority) {
 192     case SMOOTHNESS_TAKES_PRIORITY:
 193       return ACTIVE_TREE;
 194     case NEW_CONTENT_TAKES_PRIORITY:
 195       return PENDING_TREE;
 196     case SAME_PRIORITY_FOR_BOTH_TREES: {
 197       const Tile* active_tile = *active_iterator;
 198       const Tile* pending_tile = *pending_iterator;
 199       if (active_tile == pending_tile)
 200         return ACTIVE_TREE;
 201
 202       const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE);
 203       const TilePriority& pending_priority =
 204           pending_tile->priority(PENDING_TREE);
 205
 206       if (active_priority.IsHigherPriorityThan(pending_priority))
 207         return ACTIVE_TREE;
 208       return PENDING_TREE;
 209     }
 210     default:
 211       NOTREACHED();
 212   }
 213
 214   NOTREACHED();
 215   // Keep the compiler happy.
 216   return ACTIVE_TREE;
 217 }
 218
 219 }  // namespace cc