cc: Start using raster/eviction iterators.

cc/resources/tile_priority_queue.cc

Index: cc/resources/tile_priority_queue.cc
diff --git a/cc/resources/tile_priority_queue.cc b/cc/resources/tile_priority_queue.cc
new file mode 100644
index 0000000000000000000000000000000000000000..6226d8066b1c97d0cb9ec87a52ac361747bc33a3
--- /dev/null
+++ b/cc/resources/tile_priority_queue.cc
@@ -0,0 +1,419 @@
+// 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/tile_priority_queue.h"
+
+#include "cc/resources/tile.h"
+#include "cc/resources/tile_manager.h"
+
+namespace cc {
+
+PairedPictureLayer::PairedPictureLayer()
+    : active_layer(NULL), pending_layer(NULL) {
+}
+
+PairedPictureLayer::~PairedPictureLayer() {
+}
+
+RasterTileQueue::RasterTileQueue()
+    : tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      comparator_(tree_priority_) {
+}
+
+void RasterTileQueue::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_);
+}
+
+RasterTileQueue::~RasterTileQueue() {
+}
+
+void RasterTileQueue::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 RasterTileQueue::IsEmpty() {
+  return iterator_heap_.empty();
+}
+
+Tile* RasterTileQueue::Top() {
+  DCHECK(!IsEmpty());
+  return iterator_heap_.front()->PeekTile(tree_priority_);
+}
+
+RasterTileQueue::PairedPictureLayerIterator::PairedPictureLayerIterator() {
+}
+
+RasterTileQueue::PairedPictureLayerIterator::~PairedPictureLayerIterator() {
+}
+
+Tile* RasterTileQueue::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 RasterTileQueue::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>
+RasterTileQueue::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);
+}
+
+RasterTileQueue::RasterOrderComparator::RasterOrderComparator(
+    TreePriority tree_priority)
+    : tree_priority_(tree_priority) {
+}
+
+bool RasterTileQueue::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);
+}
+
+EvictionTileQueue::EvictionTileQueue()
+    : tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      comparator_(tree_priority_),
+      initialized_(true) {
+}
+
+void EvictionTileQueue::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 EvictionTileQueue::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;
+}
+
+EvictionTileQueue::~EvictionTileQueue() {
+}
+
+void EvictionTileQueue::Pop() {
+  if (!initialized_)
+    Initialize();
+
+  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 EvictionTileQueue::IsEmpty() {
+  if (!initialized_)
+    Initialize();
+
+  return !iterator_heap_.empty();
+}
+
+Tile* EvictionTileQueue::Top() {
+  if (!initialized_)
+    Initialize();
+
+  DCHECK(!IsEmpty());
+  return iterator_heap_.front()->PeekTile(tree_priority_);
+}
+
+EvictionTileQueue::PairedPictureLayerIterator::PairedPictureLayerIterator() {
+}
+
+EvictionTileQueue::PairedPictureLayerIterator::~PairedPictureLayerIterator() {
+}
+
+Tile* EvictionTileQueue::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 EvictionTileQueue::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*
+EvictionTileQueue::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;
+}
+
+EvictionTileQueue::EvictionOrderComparator::EvictionOrderComparator(
+    TreePriority tree_priority)
+    : tree_priority_(tree_priority) {
+}
+
+bool EvictionTileQueue::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