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..fc7b2bbcf4e04c4ab9fe6f15bd132f3213d766bc
--- /dev/null
+++ b/cc/resources/raster_tile_priority_queue.cc
@@ -0,0 +1,221 @@
+// 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::Reset() {
+  paired_queues_.clear();
+  queue_heap_.clear();
+}
+
+void RasterTilePriorityQueue::BuildQueue(
+    const std::vector<PictureLayerImpl*>& layers,
+    TreePriority tree_priority) {
+  DCHECK(paired_queues_.empty());
+  DCHECK(queue_heap_.empty());
+
+  tree_priority_ = tree_priority;
+  comparator_ = RasterOrderComparator(tree_priority);
+
+  bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
+
+  std::vector<PairedPictureLayer> paired_picture_layers;
+  GetPairedPictureLayers(layers, &paired_picture_layers);
+
+  // Since iterator heap uses pointers into paired_queues, we have to reserve
+  // the paired_queues to avoid reallocations of the vector.
+  paired_queues_.reserve(paired_picture_layers.size());
+  for (std::vector<PairedPictureLayer>::const_iterator it =
+           paired_picture_layers.begin();
+       it != paired_picture_layers.end();
+       ++it) {
+    PairedPictureLayerQueue paired_queue;
+    if (it->active_layer) {
+      paired_queue.active_iterator = PictureLayerImpl::LayerRasterTileIterator(
+          it->active_layer, prioritize_low_res);
+    }
+
+    if (it->pending_layer) {
+      paired_queue.pending_iterator = PictureLayerImpl::LayerRasterTileIterator(
+          it->pending_layer, prioritize_low_res);
+    }
+
+    if (paired_queue.PeekTile(tree_priority_) != NULL) {
+      paired_queues_.push_back(paired_queue);
+      queue_heap_.push_back(&paired_queues_.back());
+    }
+  }
+
+  std::make_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+}
+
+RasterTilePriorityQueue::~RasterTilePriorityQueue() {
+}
+
+void RasterTilePriorityQueue::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) {
+    queue_heap_.push_back(paired_queue);
+    std::push_heap(queue_heap_.begin(), queue_heap_.end(), comparator_);
+  }
+}
+
+bool RasterTilePriorityQueue::IsEmpty() {
+  return queue_heap_.empty();
+}
+
+Tile* RasterTilePriorityQueue::Top() {
+  DCHECK(!IsEmpty());
+  return queue_heap_.front()->PeekTile(tree_priority_);
+}
+
+RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
+}
+
+RasterTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
+}
+
+Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::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::PairedPictureLayerQueue::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::PairedPictureLayerQueue::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()(
+    PairedPictureLayerQueue* a,
+    PairedPictureLayerQueue* 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