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::PairedTilingSetQueue* a,
  18       const EvictionTilePriorityQueue::PairedTilingSetQueue* 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 TilingSetEvictionQueue* a_queue =
  27         a_tree == ACTIVE_TREE ? a->active_queue.get() : a->pending_queue.get();
  28
  29     WhichTree b_tree = b->NextTileIteratorTree(tree_priority_);
  30     const TilingSetEvictionQueue* b_queue =
  31         b_tree == ACTIVE_TREE ? b->active_queue.get() : b->pending_queue.get();
  32
  33     const Tile* a_tile = a_queue->Top();
  34     const Tile* b_tile = b_queue->Top();
  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 PairedTilingSetQueue(*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   PairedTilingSetQueue* paired_queue = paired_queues_.back();
 121   paired_queue->Pop(tree_priority_);
 122   paired_queues_.push_heap(EvictionOrderComparator(tree_priority_));
 123 }
 124
 125 EvictionTilePriorityQueue::PairedTilingSetQueue::PairedTilingSetQueue() {
 126 }
 127
 128 EvictionTilePriorityQueue::PairedTilingSetQueue::PairedTilingSetQueue(
 129     const PictureLayerImpl::Pair& layer_pair,
 130     TreePriority tree_priority) {
 131   bool skip_shared_out_of_order_tiles = layer_pair.active && layer_pair.pending;
 132   if (layer_pair.active) {
 133     active_queue = make_scoped_ptr(new TilingSetEvictionQueue(
 134         layer_pair.active->picture_layer_tiling_set(), tree_priority,
 135         skip_shared_out_of_order_tiles));
 136   }
 137   if (layer_pair.pending) {
 138     pending_queue = make_scoped_ptr(new TilingSetEvictionQueue(
 139         layer_pair.pending->picture_layer_tiling_set(), tree_priority,
 140         skip_shared_out_of_order_tiles));
 141   }
 142 }
 143
 144 EvictionTilePriorityQueue::PairedTilingSetQueue::~PairedTilingSetQueue() {
 145 }
 146
 147 bool EvictionTilePriorityQueue::PairedTilingSetQueue::IsEmpty() const {
 148   return (!active_queue || active_queue->IsEmpty()) &&
 149          (!pending_queue || pending_queue->IsEmpty());
 150 }
 151
 152 Tile* EvictionTilePriorityQueue::PairedTilingSetQueue::Top(
 153     TreePriority tree_priority) {
 154   DCHECK(!IsEmpty());
 155
 156   WhichTree next_tree = NextTileIteratorTree(tree_priority);
 157   TilingSetEvictionQueue* next_queue =
 158       next_tree == ACTIVE_TREE ? active_queue.get() : pending_queue.get();
 159   DCHECK(next_queue && !next_queue->IsEmpty());
 160
 161   Tile* tile = next_queue->Top();
 162   DCHECK(returned_tiles_for_debug.find(tile) == returned_tiles_for_debug.end());
 163   return tile;
 164 }
 165
 166 void EvictionTilePriorityQueue::PairedTilingSetQueue::Pop(
 167     TreePriority tree_priority) {
 168   DCHECK(!IsEmpty());
 169
 170   WhichTree next_tree = NextTileIteratorTree(tree_priority);
 171   TilingSetEvictionQueue* next_queue =
 172       next_tree == ACTIVE_TREE ? active_queue.get() : pending_queue.get();
 173   DCHECK(next_queue && !next_queue->IsEmpty());
 174   DCHECK(returned_tiles_for_debug.insert(next_queue->Top()).second);
 175   next_queue->Pop();
 176
 177   // If not empty, use Top to DCHECK the next iterator.
 178   DCHECK_IMPLIES(!IsEmpty(), Top(tree_priority));
 179 }
 180
 181 WhichTree
 182 EvictionTilePriorityQueue::PairedTilingSetQueue::NextTileIteratorTree(
 183     TreePriority tree_priority) const {
 184   DCHECK(!IsEmpty());
 185
 186   // If we only have one iterator with tiles, return it.
 187   if (!active_queue || active_queue->IsEmpty())
 188     return PENDING_TREE;
 189   if (!pending_queue || pending_queue->IsEmpty())
 190     return ACTIVE_TREE;
 191
 192   const Tile* active_tile = active_queue->Top();
 193   const Tile* pending_tile = pending_queue->Top();
 194
 195   // If tiles are the same, it doesn't matter which tree we return.
 196   if (active_tile == pending_tile)
 197     return ACTIVE_TREE;
 198
 199   const TilePriority& active_priority =
 200       active_tile->priority_for_tree_priority(tree_priority);
 201   const TilePriority& pending_priority =
 202       pending_tile->priority_for_tree_priority(tree_priority);
 203
 204   // If the bins are the same and activation differs, then return the tree of
 205   // the tile not required for activation.
 206   if (active_priority.priority_bin == pending_priority.priority_bin &&
 207       active_tile->required_for_activation() !=
 208           pending_tile->required_for_activation()) {
 209     return active_tile->required_for_activation() ? PENDING_TREE : ACTIVE_TREE;
 210   }
 211
 212   // Return tile with a lower priority.
 213   if (pending_priority.IsHigherPriorityThan(active_priority))
 214     return ACTIVE_TREE;
 215   return PENDING_TREE;
 216 }
 217
 218 }  // namespace cc