cc: Change TileManager iterators to be queues.

cc/resources/eviction_tile_priority_queue.cc

Index: cc/resources/eviction_tile_priority_queue.cc
diff --git a/cc/resources/eviction_tile_priority_queue.cc b/cc/resources/eviction_tile_priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..1d9896682dc4fbd7b73270c07bc903f5e563fe2e
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.cc
@@ -0,0 +1,207 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "cc/resources/eviction_tile_priority_queue.h"
+
+namespace cc {
+
+EvictionTilePriorityQueue::EvictionTilePriorityQueue()
+    : comparator_(SAME_PRIORITY_FOR_BOTH_TREES) {
+}
+
+EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
+}
+
+void EvictionTilePriorityQueue::Build(
+    const std::vector<PairedPictureLayer>& paired_layers,
+    TreePriority tree_priority) {
+  tree_priority_ = tree_priority;
+  comparator_ = EvictionOrderComparator(tree_priority_);
+
+  paired_queues_.reserve(paired_layers.size());
+  queue_heap_.reserve(paired_layers.size());

[reveman, 2014/07/18 21:08:04]

both these reserve calls can be removed after my suggestion to the .h file.

[vmpstr, 2014/07/18 23:18:12]

Done.

+  for (std::vector<PairedPictureLayer>::const_iterator it =
+           paired_layers.begin();
+       it != paired_layers.end();
+       ++it) {
+    PairedPictureLayerQueue paired_queue;
+    if (it->active_layer) {
+      paired_queue.active_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->active_layer,
+                                                      tree_priority_);
+    }
+
+    if (it->pending_layer) {
+      paired_queue.pending_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->pending_layer,
+                                                      tree_priority_);
+    }
+
+    if (paired_queue.PeekTile(tree_priority_) != NULL) {
+      paired_queues_.push_back(paired_queue);
+      queue_heap_.push_back(&paired_queues_.back());
+    }

[reveman, 2014/07/18 21:08:04]

Can we remove this and if worthwhile add it in a follow up instead? Looks like
the rest of the code in this file will handle the case when PeekTile returns
NULL just fine.

[vmpstr, 2014/07/18 23:18:12]

Done.

+  }
+
+  std::make_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+}
+
+void EvictionTilePriorityQueue::Reset() {
+  paired_queues_.clear();
+  queue_heap_.clear();
+}
+
+void EvictionTilePriorityQueue::Pop() {
+  DCHECK(!IsEmpty());
+
+  std::pop_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+  PairedPictureLayerQueue* paired_queue = queue_heap_.back();
+  queue_heap_.pop_back();
+
+  paired_queue->PopTile(tree_priority_);
+  if (paired_queue->PeekTile(tree_priority_) != NULL) {

[reveman, 2014/07/18 21:08:04]

remove this conditional and add it in a follow up if it turns out it's
important?

[vmpstr, 2014/07/18 23:18:12]

Done.

+    queue_heap_.push_back(paired_queue);
+    std::push_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+  }
+}
+
+bool EvictionTilePriorityQueue::IsEmpty() const {
+  return queue_heap_.empty();

[reveman, 2014/07/18 21:08:04]

With my other suggestions I think we need "||
!queue_heap_.front()->PeekTile(tree_priority_)" here.

[vmpstr, 2014/07/18 23:18:12]

Done.

+}
+
+Tile* EvictionTilePriorityQueue::Top() {
+  DCHECK(!IsEmpty());
+  return queue_heap_.front()->PeekTile(tree_priority_);
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
+}
+
+Tile* EvictionTilePriorityQueue::PairedPictureLayerQueue::PeekTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      NextTileIterator(tree_priority);
+  if (!next_iterator)
+    return NULL;
+
+  DCHECK(*next_iterator);
+  DCHECK(std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) == returned_shared_tiles.end());
+  return **next_iterator;
+}
+
+void EvictionTilePriorityQueue::PairedPictureLayerQueue::PopTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      NextTileIterator(tree_priority);
+  DCHECK(next_iterator);
+  DCHECK(*next_iterator);
+  returned_shared_tiles.push_back(**next_iterator);
+  ++(*next_iterator);
+
+  next_iterator = NextTileIterator(tree_priority);
+  while (next_iterator &&
+         std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) != returned_shared_tiles.end()) {
+    ++(*next_iterator);
+    next_iterator = NextTileIterator(tree_priority);
+  }
+}
+
+PictureLayerImpl::LayerEvictionTileIterator*
+EvictionTilePriorityQueue::PairedPictureLayerQueue::NextTileIterator(
+    TreePriority tree_priority) {
+  // If both iterators are out of tiles, return NULL.
+  if (!active_iterator && !pending_iterator)
+    return NULL;
+
+  // If we only have one iterator with tiles, return it.
+  if (!active_iterator)
+    return &pending_iterator;
+  if (!pending_iterator)
+    return &active_iterator;
+
+  Tile* active_tile = *active_iterator;
+  Tile* pending_tile = *pending_iterator;
+  if (active_tile == pending_tile)
+    return &active_iterator;
+
+  const TilePriority& active_priority =
+      active_tile->priority_for_tree_priority(tree_priority);
+  const TilePriority& pending_priority =
+      pending_tile->priority_for_tree_priority(tree_priority);
+
+  if (pending_priority.IsHigherPriorityThan(active_priority))
+    return &active_iterator;
+  return &pending_iterator;
+}
+
+EvictionTilePriorityQueue::EvictionOrderComparator::EvictionOrderComparator(
+    TreePriority tree_priority)
+    : tree_priority_(tree_priority) {
+}
+
+bool EvictionTilePriorityQueue::EvictionOrderComparator::operator()(
+    PairedPictureLayerQueue* a,
+    PairedPictureLayerQueue* b) const {
+  PictureLayerImpl::LayerEvictionTileIterator* a_iterator =
+      a->NextTileIterator(tree_priority_);
+  DCHECK(a_iterator);
+  DCHECK(*a_iterator);
+
+  PictureLayerImpl::LayerEvictionTileIterator* b_iterator =
+      b->NextTileIterator(tree_priority_);
+  DCHECK(b_iterator);
+  DCHECK(*b_iterator);
+
+  Tile* a_tile = **a_iterator;
+  Tile* b_tile = **b_iterator;
+
+  const TilePriority& a_priority =
+      a_tile->priority_for_tree_priority(tree_priority_);
+  const TilePriority& b_priority =
+      b_tile->priority_for_tree_priority(tree_priority_);
+  bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
+
+  // Now we have to return true iff b is lower priority than a.
+
+  // If the priority bin differs, b is lower priority if it has the higher
+  // priority bin.
+  if (a_priority.priority_bin != b_priority.priority_bin)
+    return b_priority.priority_bin > a_priority.priority_bin;
+
+  // Otherwise if the resolution differs, then the order will be determined by
+  // whether we prioritize low res or not.
+  // TODO(vmpstr): Remove this when TilePriority is no longer a member of Tile
+  // class but instead produced by the iterators.
+  if (b_priority.resolution != a_priority.resolution) {
+    // Non ideal resolution should be sorted higher than other resolutions.
+    if (a_priority.resolution == NON_IDEAL_RESOLUTION)
+      return false;
+
+    if (b_priority.resolution == NON_IDEAL_RESOLUTION)
+      return true;
+
+    if (prioritize_low_res)
+      return a_priority.resolution == LOW_RESOLUTION;
+
+    return a_priority.resolution == HIGH_RESOLUTION;
+  }
+
+  // Otherwise if the occlusion differs, b is lower priority if it is occluded.
+  bool a_is_occluded = a_tile->is_occluded_for_tree_priority(tree_priority_);
+  bool b_is_occluded = b_tile->is_occluded_for_tree_priority(tree_priority_);
+  if (a_is_occluded != b_is_occluded)
+    return b_is_occluded;
+
+  // b is lower priorty if it is farther from visible.
+  return b_priority.distance_to_visible > a_priority.distance_to_visible;
+}
+
+}  // namespace cc