(Reland) cc: Change TileManager iterators to be queues.

This is a reland of https://codereview.chromium.org/406543003/ that
changes tile manager iterators to be queues.

R=reveman

Review URL: https://codereview.chromium.org/409943005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@285187 0039d316-1c4b-4281-b951-d872f2087c98

17 files changed, 842 insertions, 703 deletions

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 211de0d..79b22a9 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -309,14 +309,16 @@ component("cc") {
     "resources/bitmap_skpicture_content_layer_updater.h",
     "resources/content_layer_updater.cc",
     "resources/content_layer_updater.h",
+    "resources/eviction_tile_priority_queue.cc",
+    "resources/eviction_tile_priority_queue.h",
     "resources/gpu_raster_worker_pool.cc",
     "resources/gpu_raster_worker_pool.h",
+    "resources/image_copy_raster_worker_pool.cc",
+    "resources/image_copy_raster_worker_pool.h",
     "resources/image_layer_updater.cc",
     "resources/image_layer_updater.h",
     "resources/image_raster_worker_pool.cc",
     "resources/image_raster_worker_pool.h",
-    "resources/image_copy_raster_worker_pool.cc",
-    "resources/image_copy_raster_worker_pool.h",
     "resources/layer_painter.h",
     "resources/layer_quad.cc",
     "resources/layer_quad.h",
@@ -334,10 +336,10 @@ component("cc") {
     "resources/picture_layer_tiling.h",
     "resources/picture_layer_tiling_set.cc",
     "resources/picture_layer_tiling_set.h",
-    "resources/picture_pile.cc",
-    "resources/picture_pile.h",
     "resources/picture_pile_base.cc",
     "resources/picture_pile_base.h",
+    "resources/picture_pile.cc",
+    "resources/picture_pile.h",
     "resources/picture_pile_impl.cc",
     "resources/picture_pile_impl.h",
     "resources/pixel_buffer_raster_worker_pool.cc",
@@ -351,25 +353,27 @@ component("cc") {
     "resources/prioritized_tile_set.h",
     "resources/priority_calculator.cc",
     "resources/priority_calculator.h",
+    "resources/rasterizer.cc",
+    "resources/rasterizer.h",
     "resources/raster_mode.cc",
     "resources/raster_mode.h",
+    "resources/raster_tile_priority_queue.cc",
+    "resources/raster_tile_priority_queue.h",
     "resources/raster_worker_pool.cc",
     "resources/raster_worker_pool.h",
-    "resources/rasterizer.cc",
-    "resources/rasterizer.h",
     "resources/release_callback.h",
     "resources/resource.cc",
-    "resources/resource.h",
-    "resources/resource_format.h",
     "resources/resource_format.cc",
+    "resources/resource_format.h",
+    "resources/resource.h",
     "resources/resource_pool.cc",
     "resources/resource_pool.h",
     "resources/resource_provider.cc",
     "resources/resource_provider.h",
     "resources/resource_update.cc",
-    "resources/resource_update.h",
     "resources/resource_update_controller.cc",
     "resources/resource_update_controller.h",
+    "resources/resource_update.h",
     "resources/resource_update_queue.cc",
     "resources/resource_update_queue.h",
     "resources/returned_resource.h",
@@ -389,9 +393,9 @@ component("cc") {
     "resources/task_graph_runner.cc",
     "resources/task_graph_runner.h",
     "resources/texture_mailbox.cc",
-    "resources/texture_mailbox.h",
     "resources/texture_mailbox_deleter.cc",
     "resources/texture_mailbox_deleter.h",
+    "resources/texture_mailbox.h",
     "resources/texture_uploader.cc",
     "resources/texture_uploader.h",
     "resources/tile.cc",
diff --git a/cc/cc.gyp b/cc/cc.gyp
index ba74085..eeb4cb6 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp
@@ -338,14 +338,16 @@
         'resources/bitmap_skpicture_content_layer_updater.h',
         'resources/content_layer_updater.cc',
         'resources/content_layer_updater.h',
+        'resources/eviction_tile_priority_queue.cc',
+        'resources/eviction_tile_priority_queue.h',
         'resources/gpu_raster_worker_pool.cc',
         'resources/gpu_raster_worker_pool.h',
+        'resources/image_copy_raster_worker_pool.cc',
+        'resources/image_copy_raster_worker_pool.h',
         'resources/image_layer_updater.cc',
         'resources/image_layer_updater.h',
         'resources/image_raster_worker_pool.cc',
         'resources/image_raster_worker_pool.h',
-        'resources/image_copy_raster_worker_pool.cc',
-        'resources/image_copy_raster_worker_pool.h',
         'resources/layer_painter.h',
         'resources/layer_quad.cc',
         'resources/layer_quad.h',
@@ -363,10 +365,10 @@
         'resources/picture_layer_tiling.h',
         'resources/picture_layer_tiling_set.cc',
         'resources/picture_layer_tiling_set.h',
-        'resources/picture_pile.cc',
-        'resources/picture_pile.h',
         'resources/picture_pile_base.cc',
         'resources/picture_pile_base.h',
+        'resources/picture_pile.cc',
+        'resources/picture_pile.h',
         'resources/picture_pile_impl.cc',
         'resources/picture_pile_impl.h',
         'resources/pixel_buffer_raster_worker_pool.cc',
@@ -380,25 +382,27 @@
         'resources/prioritized_tile_set.h',
         'resources/priority_calculator.cc',
         'resources/priority_calculator.h',
+        'resources/rasterizer.cc',
+        'resources/rasterizer.h',
         'resources/raster_mode.cc',
         'resources/raster_mode.h',
+        'resources/raster_tile_priority_queue.cc',
+        'resources/raster_tile_priority_queue.h',
         'resources/raster_worker_pool.cc',
         'resources/raster_worker_pool.h',
-        'resources/rasterizer.cc',
-        'resources/rasterizer.h',
         'resources/release_callback.h',
         'resources/resource.cc',
-        'resources/resource.h',
-        'resources/resource_format.h',
         'resources/resource_format.cc',
+        'resources/resource_format.h',
+        'resources/resource.h',
         'resources/resource_pool.cc',
         'resources/resource_pool.h',
         'resources/resource_provider.cc',
         'resources/resource_provider.h',
         'resources/resource_update.cc',
-        'resources/resource_update.h',
         'resources/resource_update_controller.cc',
         'resources/resource_update_controller.h',
+        'resources/resource_update.h',
         'resources/resource_update_queue.cc',
         'resources/resource_update_queue.h',
         'resources/returned_resource.h',
@@ -418,9 +422,9 @@
         'resources/task_graph_runner.cc',
         'resources/task_graph_runner.h',
         'resources/texture_mailbox.cc',
-        'resources/texture_mailbox.h',
         'resources/texture_mailbox_deleter.cc',
         'resources/texture_mailbox_deleter.h',
+        'resources/texture_mailbox.h',
         'resources/texture_uploader.cc',
         'resources/texture_uploader.h',
         'resources/tile.cc',
diff --git a/cc/layers/picture_layer_impl.cc b/cc/layers/picture_layer_impl.cc
index c38ba76..3f13076 100644
--- a/cc/layers/picture_layer_impl.cc
+++ b/cc/layers/picture_layer_impl.cc
@@ -46,6 +46,17 @@ const int kMinDimensionsForAnalysis = 256;
 
 namespace cc {
 
+PictureLayerImpl::Pair::Pair() : active(NULL), pending(NULL) {
+}
+
+PictureLayerImpl::Pair::Pair(PictureLayerImpl* active_layer,
+                             PictureLayerImpl* pending_layer)
+    : active(active_layer), pending(pending_layer) {
+}
+
+PictureLayerImpl::Pair::~Pair() {
+}
+
 PictureLayerImpl::PictureLayerImpl(LayerTreeImpl* tree_impl, int id)
     : LayerImpl(tree_impl, id),
       twin_layer_(NULL),
diff --git a/cc/layers/picture_layer_impl.h b/cc/layers/picture_layer_impl.h
index d40285a..d492051 100644
--- a/cc/layers/picture_layer_impl.h
+++ b/cc/layers/picture_layer_impl.h
@@ -27,6 +27,15 @@ class CC_EXPORT PictureLayerImpl
     : public LayerImpl,
       NON_EXPORTED_BASE(public PictureLayerTilingClient) {
  public:
+  struct CC_EXPORT Pair {
+    Pair();
+    Pair(PictureLayerImpl* active_layer, PictureLayerImpl* pending_layer);
+    ~Pair();
+
+    PictureLayerImpl* active;
+    PictureLayerImpl* pending;
+  };
+
   class CC_EXPORT LayerRasterTileIterator {
    public:
     LayerRasterTileIterator();
diff --git a/cc/resources/eviction_tile_priority_queue.cc b/cc/resources/eviction_tile_priority_queue.cc
new file mode 100644
index 0000000..1542c3e
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.cc
@@ -0,0 +1,229 @@
+// 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 {
+
+namespace {
+
+class EvictionOrderComparator {
+ public:
+  explicit EvictionOrderComparator(TreePriority tree_priority)
+      : tree_priority_(tree_priority) {}
+
+  bool operator()(
+      const EvictionTilePriorityQueue::PairedPictureLayerQueue& a,
+      const EvictionTilePriorityQueue::PairedPictureLayerQueue& b) const {
+    if (a.IsEmpty())
+      return true;
+
+    if (b.IsEmpty())
+      return false;
+
+    WhichTree a_tree = a.NextTileIteratorTree(tree_priority_);
+    const PictureLayerImpl::LayerEvictionTileIterator* a_iterator =
+        a_tree == ACTIVE_TREE ? &a.active_iterator : &a.pending_iterator;
+
+    WhichTree b_tree = b.NextTileIteratorTree(tree_priority_);
+    const PictureLayerImpl::LayerEvictionTileIterator* b_iterator =
+        b_tree == ACTIVE_TREE ? &b.active_iterator : &b.pending_iterator;
+
+    const Tile* a_tile = **a_iterator;
+    const 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;
+  }
+
+ private:
+  TreePriority tree_priority_;
+};
+
+}  // namespace
+
+EvictionTilePriorityQueue::EvictionTilePriorityQueue() {
+}
+
+EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
+}
+
+void EvictionTilePriorityQueue::Build(
+    const std::vector<PictureLayerImpl::Pair>& paired_layers,
+    TreePriority tree_priority) {
+  tree_priority_ = tree_priority;
+
+  for (std::vector<PictureLayerImpl::Pair>::const_iterator it =
+           paired_layers.begin();
+       it != paired_layers.end();
+       ++it) {
+    paired_queues_.push_back(PairedPictureLayerQueue(*it, tree_priority_));
+  }
+
+  std::make_heap(paired_queues_.begin(),
+                 paired_queues_.end(),
+                 EvictionOrderComparator(tree_priority_));
+}
+
+void EvictionTilePriorityQueue::Reset() {
+  paired_queues_.clear();
+}
+
+bool EvictionTilePriorityQueue::IsEmpty() const {
+  return paired_queues_.empty() || paired_queues_.front().IsEmpty();
+}
+
+Tile* EvictionTilePriorityQueue::Top() {
+  DCHECK(!IsEmpty());
+  return paired_queues_.front().Top(tree_priority_);
+}
+
+void EvictionTilePriorityQueue::Pop() {
+  DCHECK(!IsEmpty());
+
+  std::pop_heap(paired_queues_.begin(),
+                paired_queues_.end(),
+                EvictionOrderComparator(tree_priority_));
+  PairedPictureLayerQueue& paired_queue = paired_queues_.back();
+  paired_queue.Pop(tree_priority_);
+  std::push_heap(paired_queues_.begin(),
+                 paired_queues_.end(),
+                 EvictionOrderComparator(tree_priority_));
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue(
+    const PictureLayerImpl::Pair& layer_pair,
+    TreePriority tree_priority)
+    : active_iterator(
+          layer_pair.active
+              ? PictureLayerImpl::LayerEvictionTileIterator(layer_pair.active,
+                                                            tree_priority)
+              : PictureLayerImpl::LayerEvictionTileIterator()),
+      pending_iterator(
+          layer_pair.pending
+              ? PictureLayerImpl::LayerEvictionTileIterator(layer_pair.pending,
+                                                            tree_priority)
+              : PictureLayerImpl::LayerEvictionTileIterator()) {
+}
+
+EvictionTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
+}
+
+bool EvictionTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const {
+  return !active_iterator && !pending_iterator;
+}
+
+Tile* EvictionTilePriorityQueue::PairedPictureLayerQueue::Top(
+    TreePriority tree_priority) {
+  DCHECK(!IsEmpty());
+
+  WhichTree next_tree = NextTileIteratorTree(tree_priority);
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  DCHECK(*next_iterator);
+
+  Tile* tile = **next_iterator;
+  DCHECK(std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   tile) == returned_shared_tiles.end());
+  return tile;
+}
+
+void EvictionTilePriorityQueue::PairedPictureLayerQueue::Pop(
+    TreePriority tree_priority) {
+  DCHECK(!IsEmpty());
+
+  WhichTree next_tree = NextTileIteratorTree(tree_priority);
+  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
+      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  DCHECK(*next_iterator);
+  returned_shared_tiles.push_back(**next_iterator);
+  ++(*next_iterator);
+
+  if (IsEmpty())
+    return;
+
+  next_tree = NextTileIteratorTree(tree_priority);
+  next_iterator =
+      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  while (std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) != returned_shared_tiles.end()) {
+    ++(*next_iterator);
+    if (IsEmpty())
+      break;
+    next_tree = NextTileIteratorTree(tree_priority);
+    next_iterator =
+        next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  }
+}
+
+WhichTree
+EvictionTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
+    TreePriority tree_priority) const {
+  DCHECK(!IsEmpty());
+
+  // If we only have one iterator with tiles, return it.
+  if (!active_iterator)
+    return PENDING_TREE;
+  if (!pending_iterator)
+    return ACTIVE_TREE;
+
+  const Tile* active_tile = *active_iterator;
+  const Tile* pending_tile = *pending_iterator;
+  if (active_tile == pending_tile)
+    return ACTIVE_TREE;
+
+  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_TREE;
+  return PENDING_TREE;
+}
+
+}  // namespace cc
diff --git a/cc/resources/eviction_tile_priority_queue.h b/cc/resources/eviction_tile_priority_queue.h
new file mode 100644
index 0000000..3b02c96
--- /dev/null
+++ b/cc/resources/eviction_tile_priority_queue.h
@@ -0,0 +1,58 @@
+// 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.
+
+#ifndef CC_RESOURCES_EVICTION_TILE_PRIORITY_QUEUE_H_
+#define CC_RESOURCES_EVICTION_TILE_PRIORITY_QUEUE_H_
+
+#include <utility>
+#include <vector>
+
+#include "cc/base/cc_export.h"
+#include "cc/layers/picture_layer_impl.h"
+#include "cc/resources/tile_priority.h"
+
+namespace cc {
+
+class CC_EXPORT EvictionTilePriorityQueue {
+ public:
+  struct PairedPictureLayerQueue {
+    PairedPictureLayerQueue();
+    PairedPictureLayerQueue(const PictureLayerImpl::Pair& layer_pair,
+                            TreePriority tree_priority);
+    ~PairedPictureLayerQueue();
+
+    bool IsEmpty() const;
+    Tile* Top(TreePriority tree_priority);
+    void Pop(TreePriority tree_priority);
+
+    WhichTree NextTileIteratorTree(TreePriority tree_priority) const;
+
+    PictureLayerImpl::LayerEvictionTileIterator active_iterator;
+    PictureLayerImpl::LayerEvictionTileIterator pending_iterator;
+
+    // TODO(vmpstr): Investigate removing this.
+    std::vector<Tile*> returned_shared_tiles;
+  };
+
+  EvictionTilePriorityQueue();
+  ~EvictionTilePriorityQueue();
+
+  void Build(const std::vector<PictureLayerImpl::Pair>& paired_layers,
+             TreePriority tree_priority);
+  void Reset();
+
+  bool IsEmpty() const;
+  Tile* Top();
+  void Pop();
+
+ private:
+  std::vector<PairedPictureLayerQueue> paired_queues_;
+  TreePriority tree_priority_;
+
+  DISALLOW_COPY_AND_ASSIGN(EvictionTilePriorityQueue);
+};
+
+}  // namespace cc
+
+#endif  // CC_RESOURCES_EVICTION_TILE_PRIORITY_QUEUE_H_
diff --git a/cc/resources/raster_tile_priority_queue.cc b/cc/resources/raster_tile_priority_queue.cc
new file mode 100644
index 0000000..3dae625
--- /dev/null
+++ b/cc/resources/raster_tile_priority_queue.cc
@@ -0,0 +1,229 @@
+// 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"
+
+namespace cc {
+
+namespace {
+
+class RasterOrderComparator {
+ public:
+  explicit RasterOrderComparator(TreePriority tree_priority)
+      : tree_priority_(tree_priority) {}
+
+  bool operator()(
+      const RasterTilePriorityQueue::PairedPictureLayerQueue& a,
+      const RasterTilePriorityQueue::PairedPictureLayerQueue& b) const {
+    if (a.IsEmpty())
+      return true;
+
+    if (b.IsEmpty())
+      return false;
+
+    WhichTree a_tree = a.NextTileIteratorTree(tree_priority_);
+    const PictureLayerImpl::LayerRasterTileIterator* a_iterator =
+        a_tree == ACTIVE_TREE ? &a.active_iterator : &a.pending_iterator;
+
+    WhichTree b_tree = b.NextTileIteratorTree(tree_priority_);
+    const PictureLayerImpl::LayerRasterTileIterator* b_iterator =
+        b_tree == ACTIVE_TREE ? &b.active_iterator : &b.pending_iterator;
+
+    const Tile* a_tile = **a_iterator;
+    const 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 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);
+  }
+
+ private:
+  TreePriority tree_priority_;
+};
+
+}  // namespace
+
+RasterTilePriorityQueue::RasterTilePriorityQueue() {
+}
+
+RasterTilePriorityQueue::~RasterTilePriorityQueue() {
+}
+
+void RasterTilePriorityQueue::Build(
+    const std::vector<PictureLayerImpl::Pair>& paired_layers,
+    TreePriority tree_priority) {
+  tree_priority_ = tree_priority;
+  for (std::vector<PictureLayerImpl::Pair>::const_iterator it =
+           paired_layers.begin();
+       it != paired_layers.end();
+       ++it) {
+    paired_queues_.push_back(PairedPictureLayerQueue(*it, tree_priority_));
+  }
+
+  std::make_heap(paired_queues_.begin(),
+                 paired_queues_.end(),
+                 RasterOrderComparator(tree_priority_));
+}
+
+void RasterTilePriorityQueue::Reset() {
+  paired_queues_.clear();
+}
+
+bool RasterTilePriorityQueue::IsEmpty() const {
+  return paired_queues_.empty() || paired_queues_.front().IsEmpty();
+}
+
+Tile* RasterTilePriorityQueue::Top() {
+  DCHECK(!IsEmpty());
+  return paired_queues_.front().Top(tree_priority_);
+}
+
+void RasterTilePriorityQueue::Pop() {
+  DCHECK(!IsEmpty());
+
+  std::pop_heap(paired_queues_.begin(),
+                paired_queues_.end(),
+                RasterOrderComparator(tree_priority_));
+  PairedPictureLayerQueue& paired_queue = paired_queues_.back();
+  paired_queue.Pop(tree_priority_);
+  std::push_heap(paired_queues_.begin(),
+                 paired_queues_.end(),
+                 RasterOrderComparator(tree_priority_));
+}
+
+RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
+}
+
+RasterTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue(
+    const PictureLayerImpl::Pair& layer_pair,
+    TreePriority tree_priority)
+    : active_iterator(layer_pair.active
+                          ? PictureLayerImpl::LayerRasterTileIterator(
+                                layer_pair.active,
+                                tree_priority == SMOOTHNESS_TAKES_PRIORITY)
+                          : PictureLayerImpl::LayerRasterTileIterator()),
+      pending_iterator(layer_pair.pending
+                           ? PictureLayerImpl::LayerRasterTileIterator(
+                                 layer_pair.pending,
+                                 tree_priority == SMOOTHNESS_TAKES_PRIORITY)
+                           : PictureLayerImpl::LayerRasterTileIterator()) {
+}
+
+RasterTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
+}
+
+bool RasterTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const {
+  return !active_iterator && !pending_iterator;
+}
+
+Tile* RasterTilePriorityQueue::PairedPictureLayerQueue::Top(
+    TreePriority tree_priority) {
+  DCHECK(!IsEmpty());
+
+  WhichTree next_tree = NextTileIteratorTree(tree_priority);
+  PictureLayerImpl::LayerRasterTileIterator* next_iterator =
+      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  DCHECK(*next_iterator);
+  Tile* tile = **next_iterator;
+  DCHECK(std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   tile) == returned_shared_tiles.end());
+  return tile;
+}
+
+void RasterTilePriorityQueue::PairedPictureLayerQueue::Pop(
+    TreePriority tree_priority) {
+  DCHECK(!IsEmpty());
+
+  WhichTree next_tree = NextTileIteratorTree(tree_priority);
+  PictureLayerImpl::LayerRasterTileIterator* next_iterator =
+      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  DCHECK(*next_iterator);
+  returned_shared_tiles.push_back(**next_iterator);
+  ++(*next_iterator);
+
+  if (IsEmpty())
+    return;
+
+  next_tree = NextTileIteratorTree(tree_priority);
+  next_iterator =
+      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  while (std::find(returned_shared_tiles.begin(),
+                   returned_shared_tiles.end(),
+                   **next_iterator) != returned_shared_tiles.end()) {
+    ++(*next_iterator);
+    if (IsEmpty())
+      break;
+    next_tree = NextTileIteratorTree(tree_priority);
+    next_iterator =
+        next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
+  }
+}
+
+WhichTree
+RasterTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
+    TreePriority tree_priority) const {
+  DCHECK(!IsEmpty());
+
+  // If we only have one iterator with tiles, return it.
+  if (!active_iterator)
+    return PENDING_TREE;
+  if (!pending_iterator)
+    return ACTIVE_TREE;
+
+  // Now both iterators have tiles, so we have to decide based on tree priority.
+  switch (tree_priority) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      return ACTIVE_TREE;
+    case NEW_CONTENT_TAKES_PRIORITY:
+      return PENDING_TREE;
+    case SAME_PRIORITY_FOR_BOTH_TREES: {
+      const Tile* active_tile = *active_iterator;
+      const Tile* pending_tile = *pending_iterator;
+      if (active_tile == pending_tile)
+        return 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 ACTIVE_TREE;
+      return PENDING_TREE;
+    }
+    default:
+      NOTREACHED();
+  }
+
+  NOTREACHED();
+  // Keep the compiler happy.
+  return ACTIVE_TREE;
+}
+
+}  // namespace cc
diff --git a/cc/resources/raster_tile_priority_queue.h b/cc/resources/raster_tile_priority_queue.h
new file mode 100644
index 0000000..7c028d1
--- /dev/null
+++ b/cc/resources/raster_tile_priority_queue.h
@@ -0,0 +1,58 @@
+// 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.
+
+#ifndef CC_RESOURCES_RASTER_TILE_PRIORITY_QUEUE_H_
+#define CC_RESOURCES_RASTER_TILE_PRIORITY_QUEUE_H_
+
+#include <utility>
+#include <vector>
+
+#include "cc/base/cc_export.h"
+#include "cc/layers/picture_layer_impl.h"
+#include "cc/resources/tile_priority.h"
+
+namespace cc {
+
+class CC_EXPORT RasterTilePriorityQueue {
+ public:
+  struct PairedPictureLayerQueue {
+    PairedPictureLayerQueue();
+    PairedPictureLayerQueue(const PictureLayerImpl::Pair& layer_pair,
+                            TreePriority tree_priority);
+    ~PairedPictureLayerQueue();
+
+    bool IsEmpty() const;
+    Tile* Top(TreePriority tree_priority);
+    void Pop(TreePriority tree_priority);
+
+    WhichTree NextTileIteratorTree(TreePriority tree_priority) const;
+
+    PictureLayerImpl::LayerRasterTileIterator active_iterator;
+    PictureLayerImpl::LayerRasterTileIterator pending_iterator;
+
+    // TODO(vmpstr): Investigate removing this.
+    std::vector<Tile*> returned_shared_tiles;
+  };
+
+  RasterTilePriorityQueue();
+  ~RasterTilePriorityQueue();
+
+  void Build(const std::vector<PictureLayerImpl::Pair>& paired_layers,
+             TreePriority tree_priority);
+  void Reset();
+
+  bool IsEmpty() const;
+  Tile* Top();
+  void Pop();
+
+ private:
+  std::vector<PairedPictureLayerQueue> paired_queues_;
+  TreePriority tree_priority_;
+
+  DISALLOW_COPY_AND_ASSIGN(RasterTilePriorityQueue);
+};
+
+}  // namespace cc
+
+#endif  // CC_RESOURCES_RASTER_TILE_PRIORITY_QUEUE_H_
diff --git a/cc/resources/tile_manager.cc b/cc/resources/tile_manager.cc
index dab3f55..bf10d95 100644
--- a/cc/resources/tile_manager.cc
+++ b/cc/resources/tile_manager.cc
@@ -1136,441 +1136,6 @@ scoped_refptr<Tile> TileManager::CreateTile(PicturePileImpl* picture_pile,
   return tile;
 }
 
-void TileManager::GetPairedPictureLayers(
-    std::vector<PairedPictureLayer>* paired_layers) const {
-  const std::vector<PictureLayerImpl*>& layers = client_->GetPictureLayers();
-
-  paired_layers->clear();
-  // Reserve a maximum possible paired layers.
-  paired_layers->reserve(layers.size());
-
-  for (std::vector<PictureLayerImpl*>::const_iterator it = layers.begin();
-       it != layers.end();
-       ++it) {
-    PictureLayerImpl* layer = *it;
-
-    // TODO(vmpstr): Iterators and should handle this instead. crbug.com/381704
-    if (!layer->HasValidTilePriorities())
-      continue;
-
-    PictureLayerImpl* twin_layer = layer->GetTwinLayer();
-
-    // Ignore the twin layer when tile priorities are invalid.
-    // TODO(vmpstr): Iterators should handle this instead. crbug.com/381704
-    if (twin_layer && !twin_layer->HasValidTilePriorities())
-      twin_layer = NULL;
-
-    PairedPictureLayer paired_layer;
-    WhichTree tree = layer->GetTree();
-
-    // If the current tree is ACTIVE_TREE, then always generate a paired_layer.
-    // If current tree is PENDING_TREE, then only generate a paired_layer if
-    // there is no twin layer.
-    if (tree == ACTIVE_TREE) {
-      DCHECK(!twin_layer || twin_layer->GetTree() == PENDING_TREE);
-      paired_layer.active_layer = layer;
-      paired_layer.pending_layer = twin_layer;
-      paired_layers->push_back(paired_layer);
-    } else if (!twin_layer) {
-      paired_layer.active_layer = NULL;
-      paired_layer.pending_layer = layer;
-      paired_layers->push_back(paired_layer);
-    }
-  }
-}
-
-TileManager::PairedPictureLayer::PairedPictureLayer()
-    : active_layer(NULL), pending_layer(NULL) {}
-
-TileManager::PairedPictureLayer::~PairedPictureLayer() {}
-
-TileManager::RasterTileIterator::RasterTileIterator(TileManager* tile_manager,
-                                                    TreePriority tree_priority)
-    : tree_priority_(tree_priority), comparator_(tree_priority) {
-  std::vector<TileManager::PairedPictureLayer> paired_layers;
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-  bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;
-
-  paired_iterators_.reserve(paired_layers.size());
-  iterator_heap_.reserve(paired_layers.size());
-  for (std::vector<TileManager::PairedPictureLayer>::iterator it =
-           paired_layers.begin();
-       it != paired_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_);
-}
-
-TileManager::RasterTileIterator::~RasterTileIterator() {}
-
-TileManager::RasterTileIterator& TileManager::RasterTileIterator::operator++() {
-  DCHECK(*this);
-
-  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_);
-  }
-  return *this;
-}
-
-TileManager::RasterTileIterator::operator bool() const {
-  return !iterator_heap_.empty();
-}
-
-Tile* TileManager::RasterTileIterator::operator*() {
-  DCHECK(*this);
-  return iterator_heap_.front()->PeekTile(tree_priority_);
-}
-
-TileManager::RasterTileIterator::PairedPictureLayerIterator::
-    PairedPictureLayerIterator() {}
-
-TileManager::RasterTileIterator::PairedPictureLayerIterator::
-    ~PairedPictureLayerIterator() {}
-
-Tile* TileManager::RasterTileIterator::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 TileManager::RasterTileIterator::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>
-TileManager::RasterTileIterator::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);
-    }
-    default:
-      NOTREACHED();
-  }
-
-  NOTREACHED();
-  // Keep the compiler happy.
-  return std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree>(
-      NULL, ACTIVE_TREE);
-}
-
-TileManager::RasterTileIterator::RasterOrderComparator::RasterOrderComparator(
-    TreePriority tree_priority)
-    : tree_priority_(tree_priority) {}
-
-bool TileManager::RasterTileIterator::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);
-}
-
-TileManager::EvictionTileIterator::EvictionTileIterator()
-    : comparator_(SAME_PRIORITY_FOR_BOTH_TREES) {}
-
-TileManager::EvictionTileIterator::EvictionTileIterator(
-    TileManager* tile_manager,
-    TreePriority tree_priority)
-    : tree_priority_(tree_priority), comparator_(tree_priority) {
-  std::vector<TileManager::PairedPictureLayer> paired_layers;
-
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-
-  paired_iterators_.reserve(paired_layers.size());
-  iterator_heap_.reserve(paired_layers.size());
-  for (std::vector<TileManager::PairedPictureLayer>::iterator it =
-           paired_layers.begin();
-       it != paired_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_);
-}
-
-TileManager::EvictionTileIterator::~EvictionTileIterator() {}
-
-TileManager::EvictionTileIterator& TileManager::EvictionTileIterator::
-operator++() {
-  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_);
-  }
-  return *this;
-}
-
-TileManager::EvictionTileIterator::operator bool() const {
-  return !iterator_heap_.empty();
-}
-
-Tile* TileManager::EvictionTileIterator::operator*() {
-  DCHECK(*this);
-  return iterator_heap_.front()->PeekTile(tree_priority_);
-}
-
-TileManager::EvictionTileIterator::PairedPictureLayerIterator::
-    PairedPictureLayerIterator() {}
-
-TileManager::EvictionTileIterator::PairedPictureLayerIterator::
-    ~PairedPictureLayerIterator() {}
-
-Tile* TileManager::EvictionTileIterator::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 TileManager::EvictionTileIterator::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*
-TileManager::EvictionTileIterator::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;
-}
-
-TileManager::EvictionTileIterator::EvictionOrderComparator::
-    EvictionOrderComparator(TreePriority tree_priority)
-    : tree_priority_(tree_priority) {}
-
-bool TileManager::EvictionTileIterator::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 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;
-}
-
 void TileManager::SetRasterizerForTesting(Rasterizer* rasterizer) {
   rasterizer_ = rasterizer;
   rasterizer_->SetClient(this);
diff --git a/cc/resources/tile_manager.h b/cc/resources/tile_manager.h
index 5ad8091..686d0d0 100644
--- a/cc/resources/tile_manager.h
+++ b/cc/resources/tile_manager.h
@@ -17,22 +17,26 @@
 #include "cc/base/ref_counted_managed.h"
 #include "cc/base/unique_notifier.h"
 #include "cc/debug/rendering_stats_instrumentation.h"
-#include "cc/layers/picture_layer_impl.h"
+#include "cc/resources/eviction_tile_priority_queue.h"
 #include "cc/resources/managed_tile_state.h"
 #include "cc/resources/memory_history.h"
 #include "cc/resources/picture_pile_impl.h"
 #include "cc/resources/prioritized_tile_set.h"
+#include "cc/resources/raster_tile_priority_queue.h"
 #include "cc/resources/rasterizer.h"
 #include "cc/resources/resource_pool.h"
 #include "cc/resources/tile.h"
 
 namespace cc {
+class PictureLayerImpl;
 class ResourceProvider;
 
 class CC_EXPORT TileManagerClient {
  public:
   // Returns the set of layers that the tile manager should consider for raster.
-  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() = 0;
+  // TODO(vmpstr): Change the way we determine if we are ready to activate, so
+  // that this can be removed.
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() const = 0;
 
   // Called when all tiles marked as required for activation are ready to draw.
   virtual void NotifyReadyToActivate() = 0;
@@ -44,6 +48,18 @@ class CC_EXPORT TileManagerClient {
   // - Tile marked for on-demand raster.
   virtual void NotifyTileStateChanged(const Tile* tile) = 0;
 
+  // Given an empty raster tile priority queue, this will build a priority queue
+  // that will return tiles in order in which they should be rasterized.
+  // Note if the queue was previous built, Reset must be called on it.
+  virtual void BuildRasterQueue(RasterTilePriorityQueue* queue,
+                                TreePriority tree_priority) = 0;
+
+  // Given an empty eviction tile priority queue, this will build a priority
+  // queue that will return tiles in order in which they should be evicted.
+  // Note if the queue was previous built, Reset must be called on it.
+  virtual void BuildEvictionQueue(EvictionTilePriorityQueue* queue,
+                                  TreePriority tree_priority) = 0;
+
  protected:
   virtual ~TileManagerClient() {}
 };
@@ -64,105 +80,6 @@ scoped_ptr<base::Value> RasterTaskCompletionStatsAsValue(
 class CC_EXPORT TileManager : public RasterizerClient,
                               public RefCountedManager<Tile> {
  public:
-  struct CC_EXPORT PairedPictureLayer {
-    PairedPictureLayer();
-    ~PairedPictureLayer();
-
-    PictureLayerImpl* active_layer;
-    PictureLayerImpl* pending_layer;
-  };
-
-  class CC_EXPORT RasterTileIterator {
-   public:
-    RasterTileIterator(TileManager* tile_manager, TreePriority tree_priority);
-    ~RasterTileIterator();
-
-    RasterTileIterator& operator++();
-    operator bool() const;
-    Tile* operator*();
-
-   private:
-    struct PairedPictureLayerIterator {
-      PairedPictureLayerIterator();
-      ~PairedPictureLayerIterator();
-
-      Tile* PeekTile(TreePriority tree_priority);
-      void PopTile(TreePriority tree_priority);
-
-      std::pair<PictureLayerImpl::LayerRasterTileIterator*, WhichTree>
-          NextTileIterator(TreePriority tree_priority);
-
-      PictureLayerImpl::LayerRasterTileIterator active_iterator;
-      PictureLayerImpl::LayerRasterTileIterator pending_iterator;
-
-      std::vector<Tile*> returned_shared_tiles;
-    };
-
-    class RasterOrderComparator {
-     public:
-      explicit RasterOrderComparator(TreePriority tree_priority);
-
-      bool operator()(PairedPictureLayerIterator* a,
-                      PairedPictureLayerIterator* b) const;
-
-     private:
-      TreePriority tree_priority_;
-    };
-
-    std::vector<PairedPictureLayerIterator> paired_iterators_;
-    std::vector<PairedPictureLayerIterator*> iterator_heap_;
-    TreePriority tree_priority_;
-    RasterOrderComparator comparator_;
-
-    DISALLOW_COPY_AND_ASSIGN(RasterTileIterator);
-  };
-
-  struct CC_EXPORT EvictionTileIterator {
-   public:
-    EvictionTileIterator();
-    EvictionTileIterator(TileManager* tile_manager, TreePriority tree_priority);
-    ~EvictionTileIterator();
-
-    EvictionTileIterator& operator++();
-    operator bool() const;
-    Tile* operator*();
-
-   private:
-    struct PairedPictureLayerIterator {
-      PairedPictureLayerIterator();
-      ~PairedPictureLayerIterator();
-
-      Tile* PeekTile(TreePriority tree_priority);
-      void PopTile(TreePriority tree_priority);
-
-      PictureLayerImpl::LayerEvictionTileIterator* NextTileIterator(
-          TreePriority tree_priority);
-
-      PictureLayerImpl::LayerEvictionTileIterator active_iterator;
-      PictureLayerImpl::LayerEvictionTileIterator pending_iterator;
-
-      std::vector<Tile*> returned_shared_tiles;
-    };
-
-    class EvictionOrderComparator {
-     public:
-      explicit EvictionOrderComparator(TreePriority tree_priority);
-
-      bool operator()(PairedPictureLayerIterator* a,
-                      PairedPictureLayerIterator* b) const;
-
-     private:
-      TreePriority tree_priority_;
-    };
-
-    std::vector<PairedPictureLayerIterator> paired_iterators_;
-    std::vector<PairedPictureLayerIterator*> iterator_heap_;
-    TreePriority tree_priority_;
-    EvictionOrderComparator comparator_;
-
-    DISALLOW_COPY_AND_ASSIGN(EvictionTileIterator);
-  };
-
   static scoped_ptr<TileManager> Create(
       TileManagerClient* client,
       base::SequencedTaskRunner* task_runner,
@@ -191,8 +108,6 @@ class CC_EXPORT TileManager : public RasterizerClient,
     return memory_stats_from_last_assign_;
   }
 
-  void GetPairedPictureLayers(std::vector<PairedPictureLayer>* layers) const;
-
   void InitializeTilesWithResourcesForTesting(const std::vector<Tile*>& tiles) {
     for (size_t i = 0; i < tiles.size(); ++i) {
       ManagedTileState& mts = tiles[i]->managed_state();
diff --git a/cc/resources/tile_manager_perftest.cc b/cc/resources/tile_manager_perftest.cc
index 3b2df2a..3f583f4 100644
--- a/cc/resources/tile_manager_perftest.cc
+++ b/cc/resources/tile_manager_perftest.cc
@@ -180,13 +180,13 @@ class TileManagerPerfTest : public testing::Test {
     timer_.Reset();
     do {
       int count = tile_count;
-      for (TileManager::RasterTileIterator it(tile_manager(),
-                                              SAME_PRIORITY_FOR_BOTH_TREES);
-           it && count;
-           ++it) {
-        --count;
+      RasterTilePriorityQueue queue;
+      host_impl_.BuildRasterQueue(&queue, SAME_PRIORITY_FOR_BOTH_TREES);
+      while (count--) {
+        ASSERT_FALSE(queue.IsEmpty());
+        ASSERT_TRUE(queue.Top() != NULL);
+        queue.Pop();
       }
-      ASSERT_EQ(0, count);
       timer_.NextLap();
     } while (!timer_.HasTimeLimitExpired());
 
diff --git a/cc/resources/tile_manager_unittest.cc b/cc/resources/tile_manager_unittest.cc
index c56ffd3..87aa880 100644
--- a/cc/resources/tile_manager_unittest.cc
+++ b/cc/resources/tile_manager_unittest.cc
@@ -2,6 +2,8 @@
 // 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/raster_tile_priority_queue.h"
 #include "cc/resources/tile.h"
 #include "cc/resources/tile_priority.h"
 #include "cc/test/fake_impl_proxy.h"
@@ -83,11 +85,16 @@ class TileManagerTest : public testing::TestWithParam<bool>,
   }
 
   // TileManagerClient implementation.
-  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() OVERRIDE {
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers()
+      const OVERRIDE {
     return picture_layers_;
   }
   virtual void NotifyReadyToActivate() OVERRIDE { ready_to_activate_ = true; }
   virtual void NotifyTileStateChanged(const Tile* tile) OVERRIDE {}
+  virtual void BuildRasterQueue(RasterTilePriorityQueue* queue,
+                                TreePriority priority) OVERRIDE {}
+  virtual void BuildEvictionQueue(EvictionTilePriorityQueue* queue,
+                                  TreePriority priority) OVERRIDE {}
 
   TileVector CreateTilesWithSize(int count,
                                  TilePriority active_priority,
@@ -424,9 +431,9 @@ INSTANTIATE_TEST_CASE_P(TileManagerTests,
                         TileManagerTest,
                         ::testing::Values(true, false));
 
-class TileManagerTileIteratorTest : public testing::Test {
+class TileManagerTilePriorityQueueTest : public testing::Test {
  public:
-  TileManagerTileIteratorTest()
+  TileManagerTilePriorityQueueTest()
       : memory_limit_policy_(ALLOW_ANYTHING),
         max_tiles_(10000),
         ready_to_activate_(false),
@@ -537,75 +544,23 @@ class TileManagerTileIteratorTest : public testing::Test {
   FakePictureLayerImpl* active_layer_;
 };
 
-TEST_F(TileManagerTileIteratorTest, PairedPictureLayers) {
-  host_impl_.CreatePendingTree();
-  host_impl_.ActivateSyncTree();
-  host_impl_.CreatePendingTree();
-
-  LayerTreeImpl* active_tree = host_impl_.active_tree();
-  LayerTreeImpl* pending_tree = host_impl_.pending_tree();
-  EXPECT_NE(active_tree, pending_tree);
-
-  scoped_ptr<FakePictureLayerImpl> active_layer =
-      FakePictureLayerImpl::Create(active_tree, 10);
-  scoped_ptr<FakePictureLayerImpl> pending_layer =
-      FakePictureLayerImpl::Create(pending_tree, 10);
-
-  TileManager* tile_manager = TileManagerTileIteratorTest::tile_manager();
-  EXPECT_TRUE(tile_manager);
-
-  std::vector<TileManager::PairedPictureLayer> paired_layers;
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-
-  EXPECT_EQ(2u, paired_layers.size());
-  if (paired_layers[0].active_layer) {
-    EXPECT_EQ(active_layer.get(), paired_layers[0].active_layer);
-    EXPECT_EQ(NULL, paired_layers[0].pending_layer);
-  } else {
-    EXPECT_EQ(pending_layer.get(), paired_layers[0].pending_layer);
-    EXPECT_EQ(NULL, paired_layers[0].active_layer);
-  }
-
-  if (paired_layers[1].active_layer) {
-    EXPECT_EQ(active_layer.get(), paired_layers[1].active_layer);
-    EXPECT_EQ(NULL, paired_layers[1].pending_layer);
-  } else {
-    EXPECT_EQ(pending_layer.get(), paired_layers[1].pending_layer);
-    EXPECT_EQ(NULL, paired_layers[1].active_layer);
-  }
-
-  active_layer->set_twin_layer(pending_layer.get());
-  pending_layer->set_twin_layer(active_layer.get());
-
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-  EXPECT_EQ(1u, paired_layers.size());
-
-  EXPECT_EQ(active_layer.get(), paired_layers[0].active_layer);
-  EXPECT_EQ(pending_layer.get(), paired_layers[0].pending_layer);
-}
-
-TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
+TEST_F(TileManagerTilePriorityQueueTest, RasterTilePriorityQueue) {
   SetupDefaultTrees(gfx::Size(1000, 1000));
-  TileManager* tile_manager = TileManagerTileIteratorTest::tile_manager();
-  EXPECT_TRUE(tile_manager);
 
   active_layer_->CreateDefaultTilingsAndTiles();
   pending_layer_->CreateDefaultTilingsAndTiles();
 
-  std::vector<TileManager::PairedPictureLayer> paired_layers;
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-  EXPECT_EQ(1u, paired_layers.size());
-
-  TileManager::RasterTileIterator it(tile_manager,
-                                     SAME_PRIORITY_FOR_BOTH_TREES);
-  EXPECT_TRUE(it);
+  RasterTilePriorityQueue queue;
+  host_impl_.BuildRasterQueue(&queue, SAME_PRIORITY_FOR_BOTH_TREES);
+  EXPECT_FALSE(queue.IsEmpty());
 
   size_t tile_count = 0;
   std::set<Tile*> all_tiles;
-  for (; it; ++it) {
-    EXPECT_TRUE(*it);
-    all_tiles.insert(*it);
+  while (!queue.IsEmpty()) {
+    EXPECT_TRUE(queue.Top());
+    all_tiles.insert(queue.Top());
     ++tile_count;
+    queue.Pop();
   }
 
   EXPECT_EQ(tile_count, all_tiles.size());
@@ -613,15 +568,15 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
 
   // Sanity check, all tiles should be visible.
   std::set<Tile*> smoothness_tiles;
-  for (TileManager::RasterTileIterator it(tile_manager,
-                                          SMOOTHNESS_TAKES_PRIORITY);
-       it;
-       ++it) {
-    Tile* tile = *it;
+  queue.Reset();
+  host_impl_.BuildRasterQueue(&queue, SMOOTHNESS_TAKES_PRIORITY);
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     EXPECT_TRUE(tile);
     EXPECT_EQ(TilePriority::NOW, tile->priority(ACTIVE_TREE).priority_bin);
     EXPECT_EQ(TilePriority::NOW, tile->priority(PENDING_TREE).priority_bin);
     smoothness_tiles.insert(tile);
+    queue.Pop();
   }
   EXPECT_EQ(all_tiles, smoothness_tiles);
 
@@ -699,11 +654,10 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
   tile_count = 0;
   size_t increasing_distance_tiles = 0u;
   // Here we expect to get increasing ACTIVE_TREE priority_bin.
-  for (TileManager::RasterTileIterator it(tile_manager,
-                                          SMOOTHNESS_TAKES_PRIORITY);
-       it;
-       ++it) {
-    Tile* tile = *it;
+  queue.Reset();
+  host_impl_.BuildRasterQueue(&queue, SMOOTHNESS_TAKES_PRIORITY);
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     EXPECT_TRUE(tile);
 
     if (!last_tile)
@@ -728,6 +682,7 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
     last_tile = tile;
     ++tile_count;
     smoothness_tiles.insert(tile);
+    queue.Pop();
   }
 
   EXPECT_EQ(tile_count, smoothness_tiles.size());
@@ -740,11 +695,10 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
   last_tile = NULL;
   increasing_distance_tiles = 0u;
   // Here we expect to get increasing PENDING_TREE priority_bin.
-  for (TileManager::RasterTileIterator it(tile_manager,
-                                          NEW_CONTENT_TAKES_PRIORITY);
-       it;
-       ++it) {
-    Tile* tile = *it;
+  queue.Reset();
+  host_impl_.BuildRasterQueue(&queue, NEW_CONTENT_TAKES_PRIORITY);
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     EXPECT_TRUE(tile);
 
     if (!last_tile)
@@ -768,6 +722,7 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
 
     last_tile = tile;
     new_content_tiles.insert(tile);
+    queue.Pop();
   }
 
   EXPECT_EQ(tile_count, new_content_tiles.size());
@@ -777,55 +732,51 @@ TEST_F(TileManagerTileIteratorTest, RasterTileIterator) {
   EXPECT_GT(increasing_distance_tiles, 3 * tile_count / 4);
 }
 
-TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
+TEST_F(TileManagerTilePriorityQueueTest, EvictionTilePriorityQueue) {
   SetupDefaultTrees(gfx::Size(1000, 1000));
-  TileManager* tile_manager = TileManagerTileIteratorTest::tile_manager();
-  EXPECT_TRUE(tile_manager);
 
   active_layer_->CreateDefaultTilingsAndTiles();
   pending_layer_->CreateDefaultTilingsAndTiles();
 
-  std::vector<TileManager::PairedPictureLayer> paired_layers;
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-  EXPECT_EQ(1u, paired_layers.size());
-
-  TileManager::EvictionTileIterator empty_it(tile_manager,
-                                             SAME_PRIORITY_FOR_BOTH_TREES);
-  EXPECT_FALSE(empty_it);
+  EvictionTilePriorityQueue empty_queue;
+  host_impl_.BuildEvictionQueue(&empty_queue, SAME_PRIORITY_FOR_BOTH_TREES);
+  EXPECT_TRUE(empty_queue.IsEmpty());
   std::set<Tile*> all_tiles;
   size_t tile_count = 0;
 
-  for (TileManager::RasterTileIterator raster_it(tile_manager,
-                                                 SAME_PRIORITY_FOR_BOTH_TREES);
-       raster_it;
-       ++raster_it) {
+  RasterTilePriorityQueue raster_queue;
+  host_impl_.BuildRasterQueue(&raster_queue, SAME_PRIORITY_FOR_BOTH_TREES);
+  while (!raster_queue.IsEmpty()) {
     ++tile_count;
-    EXPECT_TRUE(*raster_it);
-    all_tiles.insert(*raster_it);
+    EXPECT_TRUE(raster_queue.Top());
+    all_tiles.insert(raster_queue.Top());
+    raster_queue.Pop();
   }
 
   EXPECT_EQ(tile_count, all_tiles.size());
   EXPECT_EQ(17u, tile_count);
 
-  tile_manager->InitializeTilesWithResourcesForTesting(
+  tile_manager()->InitializeTilesWithResourcesForTesting(
       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 
-  TileManager::EvictionTileIterator it(tile_manager, SMOOTHNESS_TAKES_PRIORITY);
-  EXPECT_TRUE(it);
+  EvictionTilePriorityQueue queue;
+  host_impl_.BuildEvictionQueue(&queue, SMOOTHNESS_TAKES_PRIORITY);
+  EXPECT_FALSE(queue.IsEmpty());
 
   // Sanity check, all tiles should be visible.
   std::set<Tile*> smoothness_tiles;
-  for (; it; ++it) {
-    Tile* tile = *it;
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     EXPECT_TRUE(tile);
     EXPECT_EQ(TilePriority::NOW, tile->priority(ACTIVE_TREE).priority_bin);
     EXPECT_EQ(TilePriority::NOW, tile->priority(PENDING_TREE).priority_bin);
     EXPECT_TRUE(tile->HasResources());
     smoothness_tiles.insert(tile);
+    queue.Pop();
   }
   EXPECT_EQ(all_tiles, smoothness_tiles);
 
-  tile_manager->ReleaseTileResourcesForTesting(
+  tile_manager()->ReleaseTileResourcesForTesting(
       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 
   Region invalidation(gfx::Rect(0, 0, 500, 500));
@@ -897,18 +848,17 @@ TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
   for (size_t i = 0; i < active_low_res_tiles.size(); ++i)
     all_tiles.insert(active_low_res_tiles[i]);
 
-  tile_manager->InitializeTilesWithResourcesForTesting(
+  tile_manager()->InitializeTilesWithResourcesForTesting(
       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 
   Tile* last_tile = NULL;
   smoothness_tiles.clear();
   tile_count = 0;
   // Here we expect to get increasing ACTIVE_TREE priority_bin.
-  for (TileManager::EvictionTileIterator it(tile_manager,
-                                            SMOOTHNESS_TAKES_PRIORITY);
-       it;
-       ++it) {
-    Tile* tile = *it;
+  queue.Reset();
+  host_impl_.BuildEvictionQueue(&queue, SMOOTHNESS_TAKES_PRIORITY);
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     EXPECT_TRUE(tile);
     EXPECT_TRUE(tile->HasResources());
 
@@ -926,6 +876,7 @@ TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
     last_tile = tile;
     ++tile_count;
     smoothness_tiles.insert(tile);
+    queue.Pop();
   }
 
   EXPECT_EQ(tile_count, smoothness_tiles.size());
@@ -934,11 +885,10 @@ TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
   std::set<Tile*> new_content_tiles;
   last_tile = NULL;
   // Here we expect to get increasing PENDING_TREE priority_bin.
-  for (TileManager::EvictionTileIterator it(tile_manager,
-                                            NEW_CONTENT_TAKES_PRIORITY);
-       it;
-       ++it) {
-    Tile* tile = *it;
+  queue.Reset();
+  host_impl_.BuildEvictionQueue(&queue, NEW_CONTENT_TAKES_PRIORITY);
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     EXPECT_TRUE(tile);
 
     if (!last_tile)
@@ -954,6 +904,7 @@ TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
 
     last_tile = tile;
     new_content_tiles.insert(tile);
+    queue.Pop();
   }
 
   EXPECT_EQ(tile_count, new_content_tiles.size());
@@ -961,13 +912,14 @@ TEST_F(TileManagerTileIteratorTest, EvictionTileIterator) {
 }
 
 #if defined(OS_WIN)
-#define MAYBE_EvictionTileIteratorWithOcclusion \
-  DISABLED_EvictionTileIteratorWithOcclusion
+#define MAYBE_EvictionTilePriorityQueueWithOcclusion \
+  DISABLED_EvictionTilePriorityQueueWithOcclusion
 #else
-#define MAYBE_EvictionTileIteratorWithOcclusion \
-  EvictionTileIteratorWithOcclusion
+#define MAYBE_EvictionTilePriorityQueueWithOcclusion \
+  EvictionTilePriorityQueueWithOcclusion
 #endif
-TEST_F(TileManagerTileIteratorTest, MAYBE_EvictionTileIteratorWithOcclusion) {
+TEST_F(TileManagerTilePriorityQueueTest,
+       MAYBE_EvictionTilePriorityQueueWithOcclusion) {
   gfx::Size tile_size(102, 102);
   gfx::Size layer_bounds(1000, 1000);
 
@@ -987,22 +939,15 @@ TEST_F(TileManagerTileIteratorTest, MAYBE_EvictionTileIteratorWithOcclusion) {
   pending_child_layer->DoPostCommitInitializationIfNeeded();
   pending_child_layer->CreateDefaultTilingsAndTiles();
 
-  TileManager* tile_manager = TileManagerTileIteratorTest::tile_manager();
-  EXPECT_TRUE(tile_manager);
-
-  std::vector<TileManager::PairedPictureLayer> paired_layers;
-  tile_manager->GetPairedPictureLayers(&paired_layers);
-  EXPECT_EQ(2u, paired_layers.size());
-
   std::set<Tile*> all_tiles;
   size_t tile_count = 0;
-  for (TileManager::RasterTileIterator raster_it(tile_manager,
-                                                 NEW_CONTENT_TAKES_PRIORITY);
-       raster_it;
-       ++raster_it) {
+  RasterTilePriorityQueue raster_queue;
+  host_impl_.BuildRasterQueue(&raster_queue, SAME_PRIORITY_FOR_BOTH_TREES);
+  while (!raster_queue.IsEmpty()) {
     ++tile_count;
-    EXPECT_TRUE(*raster_it);
-    all_tiles.insert(*raster_it);
+    EXPECT_TRUE(raster_queue.Top());
+    all_tiles.insert(raster_queue.Top());
+    raster_queue.Pop();
   }
   EXPECT_EQ(tile_count, all_tiles.size());
   EXPECT_EQ(34u, tile_count);
@@ -1071,16 +1016,17 @@ TEST_F(TileManagerTileIteratorTest, MAYBE_EvictionTileIteratorWithOcclusion) {
     all_tiles.insert(pending_child_low_res_tiles[i]);
   }
 
-  tile_manager->InitializeTilesWithResourcesForTesting(
+  tile_manager()->InitializeTilesWithResourcesForTesting(
       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 
-  // Verify occlusion is considered by EvictionTileIterator.
+  // Verify occlusion is considered by EvictionTilePriorityQueue.
   TreePriority tree_priority = NEW_CONTENT_TAKES_PRIORITY;
   size_t occluded_count = 0u;
   Tile* last_tile = NULL;
-  for (TileManager::EvictionTileIterator it(tile_manager, tree_priority); it;
-       ++it) {
-    Tile* tile = *it;
+  EvictionTilePriorityQueue queue;
+  host_impl_.BuildEvictionQueue(&queue, tree_priority);
+  while (!queue.IsEmpty()) {
+    Tile* tile = queue.Top();
     if (!last_tile)
       last_tile = tile;
 
@@ -1106,6 +1052,7 @@ TEST_F(TileManagerTileIteratorTest, MAYBE_EvictionTileIteratorWithOcclusion) {
       }
     }
     last_tile = tile;
+    queue.Pop();
   }
   size_t expected_occluded_count =
       pending_child_high_res_tiles.size() + pending_child_low_res_tiles.size();
diff --git a/cc/test/fake_tile_manager_client.cc b/cc/test/fake_tile_manager_client.cc
index adbae1c..f6b3749 100644
--- a/cc/test/fake_tile_manager_client.cc
+++ b/cc/test/fake_tile_manager_client.cc
@@ -14,8 +14,8 @@ FakeTileManagerClient::FakeTileManagerClient() {
 FakeTileManagerClient::~FakeTileManagerClient() {
 }
 
-const std::vector<PictureLayerImpl*>&
-FakeTileManagerClient::GetPictureLayers() {
+const std::vector<PictureLayerImpl*>& FakeTileManagerClient::GetPictureLayers()
+    const {
   return picture_layers_;
 }
 
diff --git a/cc/test/fake_tile_manager_client.h b/cc/test/fake_tile_manager_client.h
index 5c38128..9b5bf5d 100644
--- a/cc/test/fake_tile_manager_client.h
+++ b/cc/test/fake_tile_manager_client.h
@@ -17,9 +17,14 @@ class FakeTileManagerClient : public TileManagerClient {
   virtual ~FakeTileManagerClient();
 
   // TileManagerClient implementation.
-  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() OVERRIDE;
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers()
+      const OVERRIDE;
   virtual void NotifyReadyToActivate() OVERRIDE {}
   virtual void NotifyTileStateChanged(const Tile* tile) OVERRIDE {}
+  virtual void BuildRasterQueue(RasterTilePriorityQueue* queue,
+                                TreePriority tree_priority) OVERRIDE {}
+  virtual void BuildEvictionQueue(EvictionTilePriorityQueue* queue,
+                                  TreePriority tree_priority) OVERRIDE {}
 
  private:
   std::vector<PictureLayerImpl*> picture_layers_;
diff --git a/cc/trees/layer_tree_host_impl.cc b/cc/trees/layer_tree_host_impl.cc
index 68daaf8..4c7f740f 100644
--- a/cc/trees/layer_tree_host_impl.cc
+++ b/cc/trees/layer_tree_host_impl.cc
@@ -45,6 +45,7 @@
 #include "cc/quads/shared_quad_state.h"
 #include "cc/quads/solid_color_draw_quad.h"
 #include "cc/quads/texture_draw_quad.h"
+#include "cc/resources/eviction_tile_priority_queue.h"
 #include "cc/resources/gpu_raster_worker_pool.h"
 #include "cc/resources/image_copy_raster_worker_pool.h"
 #include "cc/resources/image_raster_worker_pool.h"
@@ -52,6 +53,7 @@
 #include "cc/resources/picture_layer_tiling.h"
 #include "cc/resources/pixel_buffer_raster_worker_pool.h"
 #include "cc/resources/prioritized_resource_manager.h"
+#include "cc/resources/raster_tile_priority_queue.h"
 #include "cc/resources/raster_worker_pool.h"
 #include "cc/resources/resource_pool.h"
 #include "cc/resources/texture_mailbox_deleter.h"
@@ -1244,7 +1246,54 @@ void LayerTreeHostImpl::DidInitializeVisibleTile() {
     client_->DidInitializeVisibleTileOnImplThread();
 }
 
-const std::vector<PictureLayerImpl*>& LayerTreeHostImpl::GetPictureLayers() {
+void LayerTreeHostImpl::GetPictureLayerImplPairs(
+    std::vector<PictureLayerImpl::Pair>* layer_pairs) const {
+  DCHECK(layer_pairs->empty());
+  for (std::vector<PictureLayerImpl*>::const_iterator it =
+           picture_layers_.begin();
+       it != picture_layers_.end();
+       ++it) {
+    PictureLayerImpl* layer = *it;
+
+    // TODO(vmpstr): Iterators and should handle this instead. crbug.com/381704
+    if (!layer->HasValidTilePriorities())
+      continue;
+
+    PictureLayerImpl* twin_layer = layer->GetTwinLayer();
+
+    // Ignore the twin layer when tile priorities are invalid.
+    // TODO(vmpstr): Iterators should handle this instead. crbug.com/381704
+    if (twin_layer && !twin_layer->HasValidTilePriorities())
+      twin_layer = NULL;
+
+    // If the current tree is ACTIVE_TREE, then always generate a layer_pair.
+    // If current tree is PENDING_TREE, then only generate a layer_pair if
+    // there is no twin layer.
+    if (layer->GetTree() == ACTIVE_TREE) {
+      DCHECK(!twin_layer || twin_layer->GetTree() == PENDING_TREE);
+      layer_pairs->push_back(PictureLayerImpl::Pair(layer, twin_layer));
+    } else if (!twin_layer) {
+      layer_pairs->push_back(PictureLayerImpl::Pair(NULL, layer));
+    }
+  }
+}
+
+void LayerTreeHostImpl::BuildRasterQueue(RasterTilePriorityQueue* queue,
+                                         TreePriority tree_priority) {
+  picture_layer_pairs_.clear();
+  GetPictureLayerImplPairs(&picture_layer_pairs_);
+  queue->Build(picture_layer_pairs_, tree_priority);
+}
+
+void LayerTreeHostImpl::BuildEvictionQueue(EvictionTilePriorityQueue* queue,
+                                           TreePriority tree_priority) {
+  picture_layer_pairs_.clear();
+  GetPictureLayerImplPairs(&picture_layer_pairs_);
+  queue->Build(picture_layer_pairs_, tree_priority);
+}
+
+const std::vector<PictureLayerImpl*>& LayerTreeHostImpl::GetPictureLayers()
+    const {
   return picture_layers_;
 }
 
diff --git a/cc/trees/layer_tree_host_impl.h b/cc/trees/layer_tree_host_impl.h
index b9dceed..eae2866 100644
--- a/cc/trees/layer_tree_host_impl.h
+++ b/cc/trees/layer_tree_host_impl.h
@@ -41,6 +41,7 @@ namespace cc {
 class CompletionEvent;
 class CompositorFrameMetadata;
 class DebugRectHistory;
+class EvictionTilePriorityQueue;
 class FrameRateCounter;
 class LayerImpl;
 class LayerTreeHostImplTimeSourceAdapter;
@@ -49,6 +50,7 @@ class MemoryHistory;
 class PageScaleAnimation;
 class PaintTimeCounter;
 class PictureLayerImpl;
+class RasterTilePriorityQueue;
 class RasterWorkerPool;
 class RenderPassDrawQuad;
 class RenderingStatsInstrumentation;
@@ -233,9 +235,14 @@ class CC_EXPORT LayerTreeHostImpl
   virtual void RunOnDemandRasterTask(Task* on_demand_raster_task) OVERRIDE;
 
   // TileManagerClient implementation.
-  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers() OVERRIDE;
+  virtual const std::vector<PictureLayerImpl*>& GetPictureLayers()
+      const OVERRIDE;
   virtual void NotifyReadyToActivate() OVERRIDE;
   virtual void NotifyTileStateChanged(const Tile* tile) OVERRIDE;
+  virtual void BuildRasterQueue(RasterTilePriorityQueue* queue,
+                                TreePriority tree_priority) OVERRIDE;
+  virtual void BuildEvictionQueue(EvictionTilePriorityQueue* queue,
+                                  TreePriority tree_priority) OVERRIDE;
 
   // ScrollbarAnimationControllerClient implementation.
   virtual void PostDelayedScrollbarFade(const base::Closure& start_fade,
@@ -464,6 +471,9 @@ class CC_EXPORT LayerTreeHostImpl
   void RegisterPictureLayerImpl(PictureLayerImpl* layer);
   void UnregisterPictureLayerImpl(PictureLayerImpl* layer);
 
+  void GetPictureLayerImplPairs(
+      std::vector<PictureLayerImpl::Pair>* layers) const;
+
  protected:
   LayerTreeHostImpl(
       const LayerTreeSettings& settings,
@@ -691,6 +701,7 @@ class CC_EXPORT LayerTreeHostImpl
   size_t transfer_buffer_memory_limit_;
 
   std::vector<PictureLayerImpl*> picture_layers_;
+  std::vector<PictureLayerImpl::Pair> picture_layer_pairs_;
 
   DISALLOW_COPY_AND_ASSIGN(LayerTreeHostImpl);
 };
diff --git a/cc/trees/layer_tree_host_impl_unittest.cc b/cc/trees/layer_tree_host_impl_unittest.cc
index 4f1c59a..a13c09a 100644
--- a/cc/trees/layer_tree_host_impl_unittest.cc
+++ b/cc/trees/layer_tree_host_impl_unittest.cc
@@ -6711,5 +6711,50 @@ TEST_F(LayerTreeHostImplTest, ScrollAnimated) {
   EXPECT_EQ(NULL, host_impl_->CurrentlyScrollingLayer());
 }
 
+TEST_F(LayerTreeHostImplTest, GetPictureLayerImplPairs) {
+  host_impl_->CreatePendingTree();
+  host_impl_->ActivateSyncTree();
+  host_impl_->CreatePendingTree();
+
+  LayerTreeImpl* active_tree = host_impl_->active_tree();
+  LayerTreeImpl* pending_tree = host_impl_->pending_tree();
+  EXPECT_NE(active_tree, pending_tree);
+
+  scoped_ptr<FakePictureLayerImpl> active_layer =
+      FakePictureLayerImpl::Create(active_tree, 10);
+  scoped_ptr<FakePictureLayerImpl> pending_layer =
+      FakePictureLayerImpl::Create(pending_tree, 10);
+
+  std::vector<PictureLayerImpl::Pair> layer_pairs;
+  host_impl_->GetPictureLayerImplPairs(&layer_pairs);
+
+  EXPECT_EQ(2u, layer_pairs.size());
+  if (layer_pairs[0].active) {
+    EXPECT_EQ(active_layer.get(), layer_pairs[0].active);
+    EXPECT_EQ(NULL, layer_pairs[0].pending);
+  } else {
+    EXPECT_EQ(pending_layer.get(), layer_pairs[0].pending);
+    EXPECT_EQ(NULL, layer_pairs[0].active);
+  }
+
+  if (layer_pairs[1].active) {
+    EXPECT_EQ(active_layer.get(), layer_pairs[1].active);
+    EXPECT_EQ(NULL, layer_pairs[1].pending);
+  } else {
+    EXPECT_EQ(pending_layer.get(), layer_pairs[1].pending);
+    EXPECT_EQ(NULL, layer_pairs[1].active);
+  }
+
+  active_layer->set_twin_layer(pending_layer.get());
+  pending_layer->set_twin_layer(active_layer.get());
+
+  layer_pairs.clear();
+  host_impl_->GetPictureLayerImplPairs(&layer_pairs);
+  EXPECT_EQ(1u, layer_pairs.size());
+
+  EXPECT_EQ(active_layer.get(), layer_pairs[0].active);
+  EXPECT_EQ(pending_layer.get(), layer_pairs[0].pending);
+}
+
 }  // namespace
 }  // namespace cc