cc: Start using raster/eviction iterators.

cc/resources/raster_tile_priority_queue.cc

Index: cc/resources/raster_tile_priority_queue.cc
diff --git a/cc/resources/raster_tile_priority_queue.cc b/cc/resources/raster_tile_priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..7f58551fa9e7e70a1bf8d2f05b901135727b117f
--- /dev/null
+++ b/cc/resources/raster_tile_priority_queue.cc
@@ -0,0 +1,216 @@
+// 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/raster_tile_priority_queue.h"
+
+#include "cc/resources/tile.h"
+
+namespace cc {
+
+RasterTilePriorityQueue::RasterTilePriorityQueue()
+    : tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      comparator_(tree_priority_) {
+}
+
+void RasterTilePriorityQueue::Prepare(
+    const std::vector<PairedPictureLayer>& paired_picture_layers,
+    TreePriority tree_priority) {
+  paired_iterators_.clear();
+  iterator_heap_.clear();
+
+  tree_priority_ = tree_priority;
+  comparator_ = RasterOrderComparator(tree_priority);
+
+  bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
+
+  paired_iterators_.reserve(paired_picture_layers.size());
+  iterator_heap_.reserve(paired_picture_layers.size());
+  for (std::vector<PairedPictureLayer>::const_iterator it =
+           paired_picture_layers.begin();
+       it != paired_picture_layers.end();
+       ++it) {
+    PairedPictureLayerIterator paired_iterator;
+    if (it->active_layer) {
+      paired_iterator.active_iterator =
+          PictureLayerImpl::LayerRasterTileIterator(it->active_layer,
+                                                    prioritize_low_res);
+    }
+
+    if (it->pending_layer) {
+      paired_iterator.pending_iterator =
+          PictureLayerImpl::LayerRasterTileIterator(it->pending_layer,
+                                                    prioritize_low_res);
+    }
+
+    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_);
+}
+
+RasterTilePriorityQueue::~RasterTilePriorityQueue() {
+}
+
+void RasterTilePriorityQueue::Pop() {
+  DCHECK(!IsEmpty());
+
+  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 RasterTilePriorityQueue::IsEmpty() {
+  return iterator_heap_.empty();
+}
+
+Tile* RasterTilePriorityQueue::Top() {
+  DCHECK(!IsEmpty());
+  return iterator_heap_.front()->PeekTile(tree_priority_);
+}
+
+RasterTilePriorityQueue::PairedPictureLayerIterator::
+    PairedPictureLayerIterator() {
+}
+
+RasterTilePriorityQueue::PairedPictureLayerIterator::
+    ~PairedPictureLayerIterator() {
+}
+
+Tile* RasterTilePriorityQueue::PairedPictureLayerIterator::PeekTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerRasterTileIterator* next_iterator =
+      NextTileIterator(tree_priority).first;
+  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 RasterTilePriorityQueue::PairedPictureLayerIterator::PopTile(
+    TreePriority tree_priority) {
+  PictureLayerImpl::LayerRasterTileIterator* next_iterator =
+      NextTileIterator(tree_priority).first;
+  DCHECK(next_iterator);
+  DCHECK(*next_iterator);
+  returned_shared_tiles.push_back(**next_iterator);
+  ++(*next_iterator);
+
+  next_iterator = NextTileIterator(tree_priority).first;
+  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).first;
+  }
+}
+
+std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree>
+RasterTilePriorityQueue::PairedPictureLayerIterator::NextTileIterator(
+    TreePriority tree_priority) {
+  // If both iterators are out of tiles, return NULL.
+  if (!active_iterator && !pending_iterator) {
+    return std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree>(
+        NULL, ACTIVE_TREE);
+  }
+
+  // If we only have one iterator with tiles, return it.
+  if (!active_iterator)
+    return std::make_pair(&pending_iterator, PENDING_TREE);
+  if (!pending_iterator)
+    return std::make_pair(&active_iterator, ACTIVE_TREE);
+
+  // Now both iterators have tiles, so we have to decide based on tree priority.
+  switch (tree_priority) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      return std::make_pair(&active_iterator, ACTIVE_TREE);
+    case NEW_CONTENT_TAKES_PRIORITY:
+      return std::make_pair(&pending_iterator, ACTIVE_TREE);
+    case SAME_PRIORITY_FOR_BOTH_TREES: {
+      Tile* active_tile = *active_iterator;
+      Tile* pending_tile = *pending_iterator;
+      if (active_tile == pending_tile)
+        return std::make_pair(&active_iterator, ACTIVE_TREE);
+
+      const TilePriority& active_priority = active_tile->priority(ACTIVE_TREE);
+      const TilePriority& pending_priority =
+          pending_tile->priority(PENDING_TREE);
+
+      if (active_priority.IsHigherPriorityThan(pending_priority))
+        return std::make_pair(&active_iterator, ACTIVE_TREE);
+      return std::make_pair(&pending_iterator, PENDING_TREE);
+    }
+  }
+
+  NOTREACHED();
+  // Keep the compiler happy.
+  return std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree>(
+      NULL, ACTIVE_TREE);
+}
+
+RasterTilePriorityQueue::RasterOrderComparator::RasterOrderComparator(
+    TreePriority tree_priority)
+    : tree_priority_(tree_priority) {
+}
+
+bool RasterTilePriorityQueue::RasterOrderComparator::operator()(
+    PairedPictureLayerIterator* a,
+    PairedPictureLayerIterator* b) const {
+  std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree> a_pair =
+      a->NextTileIterator(tree_priority_);
+  DCHECK(a_pair.first);
+  DCHECK(*a_pair.first);
+
+  std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree> b_pair =
+      b->NextTileIterator(tree_priority_);
+  DCHECK(b_pair.first);
+  DCHECK(*b_pair.first);
+
+  Tile* a_tile = **a_pair.first;
+  Tile* b_tile = **b_pair.first;
+
+  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 higher 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 lower than other resolutions.
+    if (a_priority.resolution == NON_IDEAL_RESOLUTION)
+      return true;
+
+    if (b_priority.resolution == NON_IDEAL_RESOLUTION)
+      return false;
+
+    if (prioritize_low_res)
+      return b_priority.resolution == LOW_RESOLUTION;
+
+    return b_priority.resolution == HIGH_RESOLUTION;
+  }
+
+  return b_priority.IsHigherPriorityThan(a_priority);
+}
+
+}  // namespace cc

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

A lot of code duplication in eviction/raster_tile_priority_queue.cc. How do we
fix that?

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

Initial thought is to move common code up to TilePriorityQueue, but I don't
exactly like that. I don't want us to fall into the same trap as we did with
rasterizer worker things. There, we had a lot of common code, but that greatly
reduced the readability and simplicity of the code. As you know, we eventually
went with no duplication since the implementations grew in separate directions.

At this point in time, these queues are very similar. However, eviction for
instance might change via https://codereview.chromium.org/377793003/. At this
time, I'd like to keep these separate. Once we're happy with the performance and
implementation of each of the queues, we can refactor. Wdyt?

[reveman, 2014/07/14 19:09:46]

I'm not sure. I'll re-evaluate this when we're happy with other parts of the
patch.