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 7namespace cc { 8 9namespace { 10 11class 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 81EvictionTilePriorityQueue::EvictionTilePriorityQueue() { 82} 83 84EvictionTilePriorityQueue::~EvictionTilePriorityQueue() { 85} 86 87void 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 103void EvictionTilePriorityQueue::Reset() { 104 paired_queues_.clear(); 105} 106 107bool EvictionTilePriorityQueue::IsEmpty() const { 108 return paired_queues_.empty() || paired_queues_.front()->IsEmpty(); 109} 110 111Tile* EvictionTilePriorityQueue::Top() { 112 DCHECK(!IsEmpty()); 113 return paired_queues_.front()->Top(tree_priority_); 114} 115 116void 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 125EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() { 126} 127 128EvictionTilePriorityQueue::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 143EvictionTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() { 144} 145 146bool EvictionTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const { 147 return !active_iterator && !pending_iterator; 148} 149 150Tile* 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 166void 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 195WhichTree 196EvictionTilePriorityQueue::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 222