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 7namespace cc { 8 9namespace { 10 11class 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 66WhichTree HigherPriorityTree( 67 TreePriority tree_priority, 68 const PictureLayerImpl::LayerRasterTileIterator* active_iterator, 69 const PictureLayerImpl::LayerRasterTileIterator* pending_iterator, 70 const Tile* shared_tile) { 71 switch (tree_priority) { 72 case SMOOTHNESS_TAKES_PRIORITY: 73 return ACTIVE_TREE; 74 case NEW_CONTENT_TAKES_PRIORITY: 75 return PENDING_TREE; 76 case SAME_PRIORITY_FOR_BOTH_TREES: { 77 const Tile* active_tile = shared_tile ? shared_tile : **active_iterator; 78 const Tile* pending_tile = shared_tile ? shared_tile : **pending_iterator; 79 80 const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE); 81 const TilePriority& pending_priority = 82 pending_tile->priority(PENDING_TREE); 83 84 if (active_priority.IsHigherPriorityThan(pending_priority)) 85 return ACTIVE_TREE; 86 return PENDING_TREE; 87 } 88 default: 89 NOTREACHED(); 90 return ACTIVE_TREE; 91 } 92} 93 94} // namespace 95 96RasterTilePriorityQueue::RasterTilePriorityQueue() { 97} 98 99RasterTilePriorityQueue::~RasterTilePriorityQueue() { 100} 101 102void RasterTilePriorityQueue::Build( 103 const std::vector<PictureLayerImpl::Pair>& paired_layers, 104 TreePriority tree_priority) { 105 tree_priority_ = tree_priority; 106 for (std::vector<PictureLayerImpl::Pair>::const_iterator it = 107 paired_layers.begin(); 108 it != paired_layers.end(); 109 ++it) { 110 paired_queues_.push_back( 111 make_scoped_ptr(new PairedPictureLayerQueue(*it, tree_priority_))); 112 } 113 paired_queues_.make_heap(RasterOrderComparator(tree_priority_)); 114} 115 116void RasterTilePriorityQueue::Reset() { 117 paired_queues_.clear(); 118} 119 120bool RasterTilePriorityQueue::IsEmpty() const { 121 return paired_queues_.empty() || paired_queues_.front()->IsEmpty(); 122} 123 124Tile* RasterTilePriorityQueue::Top() { 125 DCHECK(!IsEmpty()); 126 return paired_queues_.front()->Top(tree_priority_); 127} 128 129void RasterTilePriorityQueue::Pop() { 130 DCHECK(!IsEmpty()); 131 132 paired_queues_.pop_heap(RasterOrderComparator(tree_priority_)); 133 PairedPictureLayerQueue* paired_queue = paired_queues_.back(); 134 paired_queue->Pop(tree_priority_); 135 paired_queues_.push_heap(RasterOrderComparator(tree_priority_)); 136} 137 138RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() { 139} 140 141RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue( 142 const PictureLayerImpl::Pair& layer_pair, 143 TreePriority tree_priority) 144 : active_iterator(layer_pair.active 145 ? PictureLayerImpl::LayerRasterTileIterator( 146 layer_pair.active, 147 tree_priority == SMOOTHNESS_TAKES_PRIORITY) 148 : PictureLayerImpl::LayerRasterTileIterator()), 149 pending_iterator(layer_pair.pending 150 ? PictureLayerImpl::LayerRasterTileIterator( 151 layer_pair.pending, 152 tree_priority == SMOOTHNESS_TAKES_PRIORITY) 153 : PictureLayerImpl::LayerRasterTileIterator()), 154 has_both_layers(layer_pair.active && layer_pair.pending) { 155} 156 157RasterTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() { 158} 159 160bool RasterTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const { 161 return !active_iterator && !pending_iterator; 162} 163 164Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::Top( 165 TreePriority tree_priority) { 166 DCHECK(!IsEmpty()); 167 168 WhichTree next_tree = NextTileIteratorTree(tree_priority); 169 PictureLayerImpl::LayerRasterTileIterator* next_iterator = 170 next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator; 171 DCHECK(*next_iterator); 172 Tile* tile = **next_iterator; 173 DCHECK(returned_tiles_for_debug.find(tile) == returned_tiles_for_debug.end()); 174 return tile; 175} 176 177void RasterTilePriorityQueue::PairedPictureLayerQueue::Pop( 178 TreePriority tree_priority) { 179 DCHECK(!IsEmpty()); 180 181 WhichTree next_tree = NextTileIteratorTree(tree_priority); 182 PictureLayerImpl::LayerRasterTileIterator* next_iterator = 183 next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator; 184 DCHECK(*next_iterator); 185 DCHECK(returned_tiles_for_debug.insert(**next_iterator).second); 186 ++(*next_iterator); 187 188 if (has_both_layers) { 189 // We have both layers (active and pending) thus we can encounter shared 190 // tiles twice (from the active iterator and from the pending iterator). 191 for (; !IsEmpty(); ++(*next_iterator)) { 192 next_tree = NextTileIteratorTree(tree_priority); 193 next_iterator = 194 next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator; 195 196 // Accept all non-shared tiles. 197 const Tile* tile = **next_iterator; 198 if (!tile->is_shared()) 199 break; 200 201 // Accept a shared tile if the next tree is the higher priority one 202 // corresponding the iterator (active or pending) which usually (but due 203 // to spiral iterators not always) returns the shared tile first. 204 if (next_tree == HigherPriorityTree(tree_priority, NULL, NULL, tile)) 205 break; 206 } 207 } 208 209 // If no empty, use Top to do DCHECK the next iterator. 210 DCHECK(IsEmpty() || Top(tree_priority)); 211} 212 213WhichTree 214RasterTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree( 215 TreePriority tree_priority) const { 216 DCHECK(!IsEmpty()); 217 218 // If we only have one iterator with tiles, return it. 219 if (!active_iterator) 220 return PENDING_TREE; 221 if (!pending_iterator) 222 return ACTIVE_TREE; 223 224 // Now both iterators have tiles, so we have to decide based on tree priority. 225 return HigherPriorityTree( 226 tree_priority, &active_iterator, &pending_iterator, NULL); 227} 228 229} // namespace cc 230