cc/tiles/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/tiles/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()(const TilingSetEvictionQueue* a_queue,
  17                   const TilingSetEvictionQueue* b_queue) const {
  18     // Note that in this function, we have to return true if and only if
  19     // b is strictly lower priority than a.
  20     const PrioritizedTile& a_tile = a_queue->Top();
  21     const PrioritizedTile& b_tile = b_queue->Top();
  22
  23     const TilePriority& a_priority = a_tile.priority();
  24     const TilePriority& b_priority = b_tile.priority();
  25     bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
  26
  27     // If the priority bin differs, b is lower priority if it has the higher
  28     // priority bin.
  29     if (a_priority.priority_bin != b_priority.priority_bin)
  30       return b_priority.priority_bin > a_priority.priority_bin;
  31
  32     // Otherwise if the resolution differs, then the order will be determined by
  33     // whether we prioritize low res or not.
  34     // TODO(vmpstr): Remove this when TilePriority is no longer a member of Tile
  35     // class but instead produced by the iterators.
  36     if (b_priority.resolution != a_priority.resolution) {
  37       // Non ideal resolution should be sorted higher than other resolutions.
  38       if (a_priority.resolution == NON_IDEAL_RESOLUTION)
  39         return false;
  40
  41       if (b_priority.resolution == NON_IDEAL_RESOLUTION)
  42         return true;
  43
  44       if (prioritize_low_res)
  45         return a_priority.resolution == LOW_RESOLUTION;
  46       return a_priority.resolution == HIGH_RESOLUTION;
  47     }
  48
  49     // Otherwise if the occlusion differs, b is lower priority if it is
  50     // occluded.
  51     bool a_is_occluded = a_tile.is_occluded();
  52     bool b_is_occluded = b_tile.is_occluded();
  53     if (a_is_occluded != b_is_occluded)
  54       return b_is_occluded;
  55
  56     // b is lower priorty if it is farther from visible.
  57     return b_priority.distance_to_visible > a_priority.distance_to_visible;
  58   }
  59
  60  private:
  61   TreePriority tree_priority_;
  62 };
  63
  64 void CreateTilingSetEvictionQueues(
  65     const std::vector<PictureLayerImpl*>& layers,
  66     TreePriority tree_priority,
  67     ScopedPtrVector<TilingSetEvictionQueue>* queues) {
  68   DCHECK(queues->empty());
  69
  70   for (auto* layer : layers) {
  71     scoped_ptr<TilingSetEvictionQueue> tiling_set_queue = make_scoped_ptr(
  72         new TilingSetEvictionQueue(layer->picture_layer_tiling_set()));
  73     // Queues will only contain non empty tiling sets.
  74     if (!tiling_set_queue->IsEmpty())
  75       queues->push_back(tiling_set_queue.Pass());
  76   }
  77   queues->make_heap(EvictionOrderComparator(tree_priority));
  78 }
  79
  80 }  // namespace
  81
  82 EvictionTilePriorityQueue::EvictionTilePriorityQueue() {
  83 }
  84
  85 EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
  86 }
  87
  88 void EvictionTilePriorityQueue::Build(
  89     const std::vector<PictureLayerImpl*>& active_layers,
  90     const std::vector<PictureLayerImpl*>& pending_layers,
  91     TreePriority tree_priority) {
  92   tree_priority_ = tree_priority;
  93
  94   CreateTilingSetEvictionQueues(active_layers, tree_priority, &active_queues_);
  95   CreateTilingSetEvictionQueues(pending_layers, tree_priority,
  96                                 &pending_queues_);
  97 }
  98
  99 bool EvictionTilePriorityQueue::IsEmpty() const {
 100   return active_queues_.empty() && pending_queues_.empty();
 101 }
 102
 103 const PrioritizedTile& EvictionTilePriorityQueue::Top() const {
 104   DCHECK(!IsEmpty());
 105   const ScopedPtrVector<TilingSetEvictionQueue>& next_queues = GetNextQueues();
 106   return next_queues.front()->Top();
 107 }
 108
 109 void EvictionTilePriorityQueue::Pop() {
 110   DCHECK(!IsEmpty());
 111
 112   ScopedPtrVector<TilingSetEvictionQueue>& next_queues = GetNextQueues();
 113   next_queues.pop_heap(EvictionOrderComparator(tree_priority_));
 114   TilingSetEvictionQueue* queue = next_queues.back();
 115   queue->Pop();
 116
 117   // Remove empty queues.
 118   if (queue->IsEmpty())
 119     next_queues.pop_back();
 120   else
 121     next_queues.push_heap(EvictionOrderComparator(tree_priority_));
 122 }
 123
 124 ScopedPtrVector<TilingSetEvictionQueue>&
 125 EvictionTilePriorityQueue::GetNextQueues() {
 126   return const_cast<ScopedPtrVector<TilingSetEvictionQueue>&>(
 127       static_cast<const EvictionTilePriorityQueue*>(this)->GetNextQueues());
 128 }
 129
 130 const ScopedPtrVector<TilingSetEvictionQueue>&
 131 EvictionTilePriorityQueue::GetNextQueues() const {
 132   DCHECK(!IsEmpty());
 133
 134   // If we only have one queue with tiles, return it.
 135   if (active_queues_.empty())
 136     return pending_queues_;
 137   if (pending_queues_.empty())
 138     return active_queues_;
 139
 140   const PrioritizedTile& active_tile = active_queues_.front()->Top();
 141   const PrioritizedTile& pending_tile = pending_queues_.front()->Top();
 142
 143   const TilePriority& active_priority = active_tile.priority();
 144   const TilePriority& pending_priority = pending_tile.priority();
 145
 146   // If the bins are the same and activation differs, then return the tree of
 147   // the tile not required for activation.
 148   if (active_priority.priority_bin == pending_priority.priority_bin &&
 149       active_tile.tile()->required_for_activation() !=
 150           pending_tile.tile()->required_for_activation()) {
 151     return active_tile.tile()->required_for_activation() ? pending_queues_
 152                                                          : active_queues_;
 153   }
 154
 155   // Return tile with a lower priority.
 156   if (pending_priority.IsHigherPriorityThan(active_priority))
 157     return active_queues_;
 158   return pending_queues_;
 159 }
 160
 161 }  // namespace cc