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