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