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