cc: Start using raster/eviction iterators.

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..862084adfc604f53a2bd14a33214f9dbf2f73bf4
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.cc
@@ -0,0 +1,210 @@
+// 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"
+
+#include "cc/resources/tile.h"
+
+namespace cc {
+
+EvictionTilePriorityQueue::EvictionTilePriorityQueue()
+    : tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      comparator_(tree_priority_),
+      initialized_(true) {
+}
+
+void EvictionTilePriorityQueue::Prepare(
+    const std::vector<PairedPictureLayer>& paired_picture_layers,
+    TreePriority tree_priority) {
+  paired_iterators_.clear();
+  iterator_heap_.clear();
+  paired_picture_layers_ = paired_picture_layers;
+  tree_priority_ = tree_priority;
+  comparator_ = EvictionOrderComparator(tree_priority);
+  initialized_ = false;
+}
+
+void EvictionTilePriorityQueue::Initialize() {
+  paired_iterators_.reserve(paired_picture_layers_.size());
+  iterator_heap_.reserve(paired_picture_layers_.size());
+  for (std::vector<PairedPictureLayer>::iterator it =
+           paired_picture_layers_.begin();
+       it != paired_picture_layers_.end();
+       ++it) {
+    PairedPictureLayerIterator paired_iterator;
+    if (it->active_layer) {
+      paired_iterator.active_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->active_layer,
+                                                      tree_priority_);
+    }
+
+    if (it->pending_layer) {
+      paired_iterator.pending_iterator =
+          PictureLayerImpl::LayerEvictionTileIterator(it->pending_layer,
+                                                      tree_priority_);
+    }
+
+    if (paired_iterator.PeekTile(tree_priority_) != NULL) {
+      paired_iterators_.push_back(paired_iterator);
+      iterator_heap_.push_back(&paired_iterators_.back());
+    }
+  }
+
+  std::make_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  initialized_ = true;
+}
+
+EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
+}
+
+void EvictionTilePriorityQueue::Pop() {
+  if (!initialized_)
+    Initialize();

[reveman, 2014/07/14 15:52:38]

I think this lazy init stuff should be consistent between raster/eviction.
However, now that it's explicit that building a queue has a cost we could
instead handle this optimization in AssignGpuMemory and only create/rebuild the
queue if necessary.

[vmpstr, 2014/07/14 18:10:44]

I would strongly prefer to keep this knowledge outside of tile manager. I think
the fact that we lazy initialize is an implementation detail of this particular
queue. If we tie in the construction to be in tile manager, then I think we
restrict how much we can change the underlying implementation later. For
instance, if we maintain a persistent queue in LTHI, and update it as it
evolves, we can have TilePriorityQueue* RebuildPriorityQueue simply return a
pointer (and maybe rebuild it in special situations). If we enforce tile manager
calls some sort of a "construct/rebuild" operation on it, then it's either going
to be no-op or do unnecessary work. 

+
+  std::pop_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  PairedPictureLayerIterator* paired_iterator = iterator_heap_.back();
+  iterator_heap_.pop_back();
+
+  paired_iterator->PopTile(tree_priority_);
+  if (paired_iterator->PeekTile(tree_priority_) != NULL) {
+    iterator_heap_.push_back(paired_iterator);
+    std::push_heap(iterator_heap_.begin(), iterator_heap_.end(), comparator_);
+  }
+}
+
+bool EvictionTilePriorityQueue::IsEmpty() {
+  if (!initialized_)
+    Initialize();
+
+  return iterator_heap_.empty();
+}
+
+Tile* EvictionTilePriorityQueue::Top() {
+  if (!initialized_)
+    Initialize();
+
+  DCHECK(!IsEmpty());
+  return iterator_heap_.front()->PeekTile(tree_priority_);
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerIterator::
+    PairedPictureLayerIterator() {
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerIterator::
+    ~PairedPictureLayerIterator() {
+}
+
+Tile* EvictionTilePriorityQueue::PairedPictureLayerIterator::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::PairedPictureLayerIterator::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::PairedPictureLayerIterator::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()(
+    PairedPictureLayerIterator* a,
+    PairedPictureLayerIterator* 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 bin is the same but the resolution is not, 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.priority_bin == a_priority.priority_bin &&
+      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;
+  }
+  return a_priority.IsHigherPriorityThan(b_priority);
+}
+
+}  // namespace cc