cc: Rework tiling set eviction iterator.

cc/resources/tiling_set_eviction_queue.cc

 // 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 <utility>
 
 #include "cc/resources/tiling_set_eviction_queue.h"
 
 namespace cc {
+namespace {
+
+bool IsSharedOutOfOrderTile(WhichTree tree,
+                            TreePriority tree_priority,
+                            const Tile* tile) {
+  if (!tile->is_shared())
+    return false;
+
+  switch (tree_priority) {
+    case SMOOTHNESS_TAKES_PRIORITY:
+      DCHECK_EQ(ACTIVE_TREE, tree);
+      return false;
+    case NEW_CONTENT_TAKES_PRIORITY:
+      DCHECK_EQ(PENDING_TREE, tree);
+      return false;
+    case SAME_PRIORITY_FOR_BOTH_TREES:
+      break;
+  }
+
+  // The priority for tile priority of a shared tile will be a combined
+  // priority thus return shared tiles from a higher priority tree as
+  // it is out of order for a lower priority tree.
+  WhichTree twin_tree = tree == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
+  const TilePriority& priority = tile->priority(tree);
+  const TilePriority& twin_priority = tile->priority(twin_tree);
+  if (priority.priority_bin != twin_priority.priority_bin)
+    return priority.priority_bin > twin_priority.priority_bin;
+  const bool occluded = tile->is_occluded(tree);
+  const bool twin_occluded = tile->is_occluded(twin_tree);
+  if (occluded != twin_occluded)
+    return occluded;
+  if (priority.distance_to_visible != twin_priority.distance_to_visible)
+    return priority.distance_to_visible > twin_priority.distance_to_visible;
+
+  // If priorities are the same, it does not matter which tree returns
+  // the tile. Let's pick the pending tree.
+  return tree != PENDING_TREE;
+}
+
+}  // namespace
 
 TilingSetEvictionQueue::TilingSetEvictionQueue(
     PictureLayerTilingSet* tiling_set,
     TreePriority tree_priority,
     bool skip_shared_out_of_order_tiles)
-    : tiling_set_(tiling_set),
-      tree_(tiling_set->client()->GetTree()),
+    : tree_(tiling_set->client()->GetTree()),
       tree_priority_(tree_priority),
       skip_all_shared_tiles_(
           skip_shared_out_of_order_tiles &&
           tree_priority == (tree_ == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
                                                  : SMOOTHNESS_TAKES_PRIORITY)),
       skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
-      processing_soon_border_rect_(false),
-      processing_tiling_with_required_for_activation_tiles_(false),
-      tiling_index_with_required_for_activation_tiles_(0u),
-      current_priority_bin_(TilePriority::EVENTUALLY),
-      current_tiling_index_(0u),
-      current_tiling_range_type_(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES),
-      current_eviction_tile_(nullptr) {
+      phase_(EVENTUALLY_RECT),
+      current_tile_(nullptr) {
   // Early out if the layer has no tilings.
-  if (!tiling_set_->num_tilings())
-    return;
-
-  tiling_index_with_required_for_activation_tiles_ =
-      TilingIndexWithRequiredForActivationTiles();
-
-  current_tiling_index_ = CurrentTilingRange().start - 1u;
-  AdvanceToNextValidTiling();
+  if (!tiling_set->num_tilings())
+    return;
+  GenerateTilingOrder(tiling_set);
+  eventually_iterator_ = EventuallyTilingIterator(
+      &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+      skip_all_shared_tiles_);
+  if (eventually_iterator_.done()) {
+    AdvancePhase();
+    return;
+  }
+  current_tile_ = *eventually_iterator_;
 }
 
 TilingSetEvictionQueue::~TilingSetEvictionQueue() {
 }
 
+void TilingSetEvictionQueue::GenerateTilingOrder(
+    PictureLayerTilingSet* tiling_set) {
+  tilings_.reserve(tiling_set->num_tilings());
+  // Generate all of the tilings in the following order:
+  // 1. Higher than high res from higher to lower resolution.

[enne (OOO), 2015/03/27 19:12:11]

This seems like a duplicate comment from some other file.  Can you make it one
place and then just refer to the other?

[vmpstr, 2015/03/27 20:19:27]

Done.

+  // 2. Lower than low res from lower to higher resolution.
+  // 3. Between high and low res from lower to higher resolution.
+  // 4. Low res tiling if one exists.
+  // 5. High res tiling if one exists.
+  auto range =
+      tiling_set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES);
+  for (int i = range.start; i < range.end; ++i)
+    tilings_.push_back(tiling_set->tiling_at(i));
+
+  range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES);
+  for (int i = range.end - 1; i >= range.start; --i)
+    tilings_.push_back(tiling_set->tiling_at(i));
+
+  range = tiling_set->GetTilingRange(
+      PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES);
+  for (int i = range.end - 1; i >= range.start; --i)
+    tilings_.push_back(tiling_set->tiling_at(i));
+
+  range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOW_RES);
+  for (int i = range.start; i < range.end; ++i)
+    tilings_.push_back(tiling_set->tiling_at(i));
+
+  range = tiling_set->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
+  for (int i = range.start; i < range.end; ++i)
+    tilings_.push_back(tiling_set->tiling_at(i));
+  DCHECK_EQ(tiling_set->num_tilings(), tilings_.size());
+}
+
+void TilingSetEvictionQueue::AdvancePhase() {
+  current_tile_ = nullptr;
+  while (!current_tile_ &&
+         phase_ != VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED) {
+    phase_ = static_cast<Phase>(phase_ + 1);
+    switch (phase_) {
+      case EVENTUALLY_RECT:
+        NOTREACHED();
+        break;
+      case SOON_BORDER_RECT:
+        soon_iterator_ = SoonBorderTilingIterator(
+            &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+            skip_all_shared_tiles_);
+        if (!soon_iterator_.done())
+          current_tile_ = *soon_iterator_;
+        break;
+      case SKEWPORT_RECT:
+        skewport_iterator_ = SkewportTilingIterator(
+            &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+            skip_all_shared_tiles_);
+        if (!skewport_iterator_.done())
+          current_tile_ = *skewport_iterator_;
+        break;
+      case VISIBLE_RECT_OCCLUDED:
+        visible_iterator_ = VisibleTilingIterator(
+            &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+            skip_all_shared_tiles_, true /* return occluded tiles */,
+            false /* return required for activation tiles */);
+        if (!visible_iterator_.done())
+          current_tile_ = *visible_iterator_;
+        break;
+      case VISIBLE_RECT_UNOCCLUDED:
+        visible_iterator_ = VisibleTilingIterator(
+            &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+            skip_all_shared_tiles_, false /* return occluded tiles */,
+            false /* return required for activation tiles */);
+        if (!visible_iterator_.done())
+          current_tile_ = *visible_iterator_;
+        break;
+      case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
+        visible_iterator_ = VisibleTilingIterator(
+            &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+            skip_all_shared_tiles_, true /* return occluded tiles */,
+            true /* return required for activation tiles */);
+        if (!visible_iterator_.done())
+          current_tile_ = *visible_iterator_;
+        break;
+      case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
+        visible_iterator_ = VisibleTilingIterator(
+            &tilings_, tree_, tree_priority_, skip_shared_out_of_order_tiles_,
+            skip_all_shared_tiles_, false /* return occluded tiles */,
+            true /* return required for activation tiles */);
+        if (!visible_iterator_.done())
+          current_tile_ = *visible_iterator_;
+        break;
+    }
+  }
+}
+
 bool TilingSetEvictionQueue::IsEmpty() const {
-  return !current_eviction_tile_;
+  return !current_tile_;
+}
+
+Tile* TilingSetEvictionQueue::Top() {
+  DCHECK(!IsEmpty());
+  return current_tile_;
+}
+
+const Tile* TilingSetEvictionQueue::Top() const {
+  DCHECK(!IsEmpty());
+  return current_tile_;
 }
 
 void TilingSetEvictionQueue::Pop() {
   DCHECK(!IsEmpty());
-
-  if (!AdvanceToNextEvictionTile())
-    AdvanceToNextValidTiling();
-}
-
-Tile* TilingSetEvictionQueue::Top() {
-  DCHECK(!IsEmpty());
-  return current_eviction_tile_;
-}
-
-const Tile* TilingSetEvictionQueue::Top() const {
-  DCHECK(!IsEmpty());
-  return current_eviction_tile_;
-}
-
-bool TilingSetEvictionQueue::AdvanceToNextEvictionTile() {
-  // Advance to the next eviction tile within the current priority bin and
-  // tiling. This is done while advancing to a new tiling and while popping
-  // the current tile.
-
-  bool required_for_activation =
-      processing_tiling_with_required_for_activation_tiles_;
-
+  current_tile_ = nullptr;
+  switch (phase_) {
+    case EVENTUALLY_RECT:
+      ++eventually_iterator_;
+      if (!eventually_iterator_.done())
+        current_tile_ = *eventually_iterator_;
+      break;
+    case SOON_BORDER_RECT:
+      ++soon_iterator_;
+      if (!soon_iterator_.done())
+        current_tile_ = *soon_iterator_;
+      break;
+    case SKEWPORT_RECT:
+      ++skewport_iterator_;
+      if (!skewport_iterator_.done())
+        current_tile_ = *skewport_iterator_;
+      break;
+    case VISIBLE_RECT_OCCLUDED:
+    case VISIBLE_RECT_UNOCCLUDED:
+    case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
+    case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
+      ++visible_iterator_;
+      if (!visible_iterator_.done())
+        current_tile_ = *visible_iterator_;
+      break;
+  }
+  if (!current_tile_)
+    AdvancePhase();
+}
+
+// OnePriorityRectIterator
+TilingSetEvictionQueue::OnePriorityRectIterator::OnePriorityRectIterator()
+    : tile_(nullptr),
+      tilings_(nullptr),
+      tree_(ACTIVE_TREE),
+      tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      skip_shared_out_of_order_tiles_(false),
+      skip_all_shared_tiles_(false),
+      tiling_index_(0) {
+}
+
+TilingSetEvictionQueue::OnePriorityRectIterator::OnePriorityRectIterator(
+    std::vector<PictureLayerTiling*>* tilings,
+    WhichTree tree,
+    TreePriority tree_priority,
+    bool skip_shared_out_of_order_tiles,
+    bool skip_all_shared_tiles)
+    : tile_(nullptr),
+      tilings_(tilings),
+      tree_(tree),
+      tree_priority_(tree_priority),
+      skip_shared_out_of_order_tiles_(skip_shared_out_of_order_tiles),
+      skip_all_shared_tiles_(skip_all_shared_tiles),
+      tiling_index_(0) {
+}
+
+template <typename TilingIteratorType>
+bool TilingSetEvictionQueue::OnePriorityRectIterator::AdvanceToNextTile(
+    TilingIteratorType* iterator) {
   for (;;) {
-    while (spiral_iterator_) {
-      std::pair<int, int> next_index = spiral_iterator_.index();
-      Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
-      ++spiral_iterator_;
-      if (!tile || !tile->HasResource())
-        continue;
-      if (skip_all_shared_tiles_ && tile->is_shared())
-        continue;
-      current_tiling_->UpdateTileAndTwinPriority(tile);
-      if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
-        continue;
-      if (tile->required_for_activation() != required_for_activation)
-        continue;
-      current_eviction_tile_ = tile;
+    ++(*iterator);
+    if (!(*iterator)) {
+      tile_ = nullptr;
+      return false;
+    }
+    bool have_valid_tile = GetFirstTileAndCheckIfValid(iterator);
+    if (have_valid_tile)
       return true;
-    }
-    if (processing_soon_border_rect_) {
-      // Advance from soon border rect to skewport rect.
-      processing_soon_border_rect_ = false;
-      if (current_tiling_->has_skewport_rect_tiles_) {
-        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
-            &current_tiling_->tiling_data_,
-            current_tiling_->current_skewport_rect_,
-            current_tiling_->current_visible_rect_,
-            current_tiling_->current_visible_rect_);
-        continue;
-      }
-    }
-    break;
-  }
-
-  TilePriority::PriorityBin max_tile_priority_bin =
-      current_tiling_->client_->GetMaxTilePriorityBin();
-  while (visible_iterator_) {
-    std::pair<int, int> next_index = visible_iterator_.index();
-    Tile* tile = current_tiling_->TileAt(next_index.first, next_index.second);
-    ++visible_iterator_;
-    if (!tile || !tile->HasResource())
-      continue;
-    if (skip_all_shared_tiles_ && tile->is_shared())
-      continue;
-    // If the max tile priority is not NOW, updated priorities for tiles
-    // returned by the visible iterator will not have NOW (but EVENTUALLY)
-    // priority bin and cannot therefore be required for activation tiles nor
-    // occluded NOW tiles in the current tiling.
-    if (max_tile_priority_bin <= TilePriority::NOW) {
-      // If the current tiling is a pending tree tiling, required for
-      // activation tiles can be detected without updating tile priorities.
-      if (tree_ == PENDING_TREE &&
-          current_tiling_->IsTileRequiredForActivationIfVisible(tile) !=
-              required_for_activation) {
-        continue;
-      }
-      // Unoccluded NOW tiles should be evicted (and thus returned) only after
-      // all occluded NOW tiles.
-      if (!current_tiling_->IsTileOccluded(tile)) {
-        unoccluded_now_tiles_.push_back(tile);
-        continue;
-      }
-    }
-    current_tiling_->UpdateTileAndTwinPriority(tile);
-    if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
-      continue;
-    if (tile->required_for_activation() != required_for_activation)
-      continue;
-    current_eviction_tile_ = tile;
-    return true;
-  }
-
-  while (!unoccluded_now_tiles_.empty()) {
-    // All (unoccluded) NOW tiles have the same priority bin (NOW) and the same
-    // distance to visible (0.0), so it does not matter that tiles are popped
-    // in reversed (FILO) order.
-    Tile* tile = unoccluded_now_tiles_.back();
-    unoccluded_now_tiles_.pop_back();
-    DCHECK(tile);
-    if (!tile->HasResource())
-      continue;
-    current_tiling_->UpdateTileAndTwinPriority(tile);
-    if (skip_shared_out_of_order_tiles_ && IsSharedOutOfOrderTile(tile))
-      continue;
-    if (tile->required_for_activation() != required_for_activation)
-      continue;
-    current_eviction_tile_ = tile;
-    return true;
-  }
-
-  current_eviction_tile_ = nullptr;
-  return false;
-}
-
-bool TilingSetEvictionQueue::AdvanceToNextPriorityBin() {
-  // Advance to the next priority bin. This is done only after all tiling range
-  // types (including the required for activation tiling) within the previous
-  // priority bin have been gone through.
-  DCHECK_EQ(current_tiling_range_type_, PictureLayerTilingSet::HIGH_RES);
-
-  switch (current_priority_bin_) {
-    case TilePriority::EVENTUALLY:
-      current_priority_bin_ = TilePriority::SOON;
-      return true;
-    case TilePriority::SOON:
-      current_priority_bin_ = TilePriority::NOW;
-      return true;
-    case TilePriority::NOW:
-      return false;
   }
   NOTREACHED();
   return false;
 }
 
-bool TilingSetEvictionQueue::AdvanceToNextTilingRangeType() {
-  // Advance to the next tiling range type within the current priority bin, to
-  // the required for activation tiling range type within the current priority
-  // bin or to the first tiling range type within the next priority bin. This
-  // is done only after all tilings within the previous tiling range type have
-  // been gone through.
-  DCHECK_EQ(current_tiling_index_, CurrentTilingRange().end);
-
-  switch (current_tiling_range_type_) {
-    case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
-      current_tiling_range_type_ = PictureLayerTilingSet::LOWER_THAN_LOW_RES;
-      return true;
-    case PictureLayerTilingSet::LOWER_THAN_LOW_RES:
-      current_tiling_range_type_ =
-          PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES;
-      return true;
-    case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
-      current_tiling_range_type_ = PictureLayerTilingSet::LOW_RES;
-      return true;
-    case PictureLayerTilingSet::LOW_RES:
-      current_tiling_range_type_ = PictureLayerTilingSet::HIGH_RES;
-      return true;
-    case PictureLayerTilingSet::HIGH_RES:
-      // Process required for activation tiles (unless that has already been
-      // done for the current priority bin) if there is a tiling with required
-      // for activation tiles and that tiling may have required for activation
-      // tiles having the current priority bin (in the pending tree only NOW
-      // tiles may be required for activation).
-      if (!processing_tiling_with_required_for_activation_tiles_ &&
-          tiling_index_with_required_for_activation_tiles_ <
-              tiling_set_->num_tilings() &&
-          (current_priority_bin_ == TilePriority::NOW ||
-           tree_ == ACTIVE_TREE)) {
-        processing_tiling_with_required_for_activation_tiles_ = true;
-        return true;
-      }
-      processing_tiling_with_required_for_activation_tiles_ = false;
-
-      if (!AdvanceToNextPriorityBin())
-        return false;
-
-      current_tiling_range_type_ = PictureLayerTilingSet::HIGHER_THAN_HIGH_RES;
-      return true;
-  }
-  NOTREACHED();
-  return false;
-}
-
-bool TilingSetEvictionQueue::AdvanceToNextValidTiling() {
-  // Advance to the next tiling within current tiling range type or to
-  // the first tiling within the next tiling range type or priority bin until
-  // the next eviction tile is found. This is done only after all eviction
-  // tiles within the previous tiling within the current priority bin and
-  // tiling range type have been gone through.
-  DCHECK(!current_eviction_tile_);
-  DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
-
-  for (;;) {
-    ++current_tiling_index_;
-    while (current_tiling_index_ == CurrentTilingRange().end) {
-      if (!AdvanceToNextTilingRangeType())
-        return false;
-      current_tiling_index_ = CurrentTilingRange().start;
-    }
-    current_tiling_ = tiling_set_->tiling_at(CurrentTilingIndex());
-
-    switch (current_priority_bin_) {
-      case TilePriority::EVENTUALLY:
-        if (current_tiling_->has_eventually_rect_tiles_) {
-          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
-              &current_tiling_->tiling_data_,
-              current_tiling_->current_eventually_rect_,
-              current_tiling_->current_skewport_rect_,
-              current_tiling_->current_soon_border_rect_);
-          if (AdvanceToNextEvictionTile())
-            return true;
-        }
-        break;
-      case TilePriority::SOON:
-        if (current_tiling_->has_skewport_rect_tiles_ ||
-            current_tiling_->has_soon_border_rect_tiles_) {
-          processing_soon_border_rect_ = true;
-          if (current_tiling_->has_soon_border_rect_tiles_)
-            spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
-                &current_tiling_->tiling_data_,
-                current_tiling_->current_soon_border_rect_,
-                current_tiling_->current_skewport_rect_,
-                current_tiling_->current_visible_rect_);
-          if (AdvanceToNextEvictionTile())
-            return true;
-        }
-        break;
-      case TilePriority::NOW:
-        if (current_tiling_->has_visible_rect_tiles_) {
-          visible_iterator_ =
-              TilingData::Iterator(&current_tiling_->tiling_data_,
-                                   current_tiling_->current_visible_rect_,
-                                   false /* include_borders */);
-          if (AdvanceToNextEvictionTile())
-            return true;
-        }
-        break;
-    }
-  }
-}
-
-PictureLayerTilingSet::TilingRange
-TilingSetEvictionQueue::CurrentTilingRange() const {
-  if (processing_tiling_with_required_for_activation_tiles_)
-    return PictureLayerTilingSet::TilingRange(
-        tiling_index_with_required_for_activation_tiles_,
-        tiling_index_with_required_for_activation_tiles_ + 1);
-  return tiling_set_->GetTilingRange(current_tiling_range_type_);
-}
-
-size_t TilingSetEvictionQueue::CurrentTilingIndex() const {
-  DCHECK_NE(current_tiling_index_, CurrentTilingRange().end);
-  switch (current_tiling_range_type_) {
-    case PictureLayerTilingSet::HIGHER_THAN_HIGH_RES:
-    case PictureLayerTilingSet::LOW_RES:
-    case PictureLayerTilingSet::HIGH_RES:
-      return current_tiling_index_;
-    // Tilings in the following ranges are accessed in reverse order.
-    case PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES:
-    case PictureLayerTilingSet::LOWER_THAN_LOW_RES: {
-      PictureLayerTilingSet::TilingRange tiling_range = CurrentTilingRange();
-      size_t current_tiling_range_offset =
-          current_tiling_index_ - tiling_range.start;
-      return tiling_range.end - 1 - current_tiling_range_offset;
-    }
-  }
-  NOTREACHED();
-  return 0;
-}
-
-bool TilingSetEvictionQueue::IsSharedOutOfOrderTile(const Tile* tile) const {
-  if (!tile->is_shared())
+template <typename TilingIteratorType>
+bool TilingSetEvictionQueue::OnePriorityRectIterator::
+    GetFirstTileAndCheckIfValid(TilingIteratorType* iterator) {
+  tile_ = (*tilings_)[tiling_index_]->TileAt(iterator->index_x(),
+                                             iterator->index_y());
+  // If there's nothing to evict, return false.
+  if (!tile_ || !tile_->HasResource())
     return false;
-
-  switch (tree_priority_) {
-    case SMOOTHNESS_TAKES_PRIORITY:
-      DCHECK_EQ(ACTIVE_TREE, tree_);
-      return false;
-    case NEW_CONTENT_TAKES_PRIORITY:
-      DCHECK_EQ(PENDING_TREE, tree_);
-      return false;
-    case SAME_PRIORITY_FOR_BOTH_TREES:
-      break;
-  }
-
-  // The priority for tile priority of a shared tile will be a combined
-  // priority thus return shared tiles from a higher priority tree as
-  // it is out of order for a lower priority tree.
-  WhichTree twin_tree = tree_ == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
-  const TilePriority& priority = tile->priority(tree_);
-  const TilePriority& twin_priority = tile->priority(twin_tree);
-  if (priority.priority_bin != twin_priority.priority_bin)
-    return priority.priority_bin > twin_priority.priority_bin;
-  const bool occluded = tile->is_occluded(tree_);
-  const bool twin_occluded = tile->is_occluded(twin_tree);
-  if (occluded != twin_occluded)
-    return occluded;
-  if (priority.distance_to_visible != twin_priority.distance_to_visible)
-    return priority.distance_to_visible > twin_priority.distance_to_visible;
-
-  // If priorities are the same, it does not matter which tree returns
-  // the tile. Let's pick the pending tree.
-  return tree_ != PENDING_TREE;
-}
-
-size_t TilingSetEvictionQueue::TilingIndexWithRequiredForActivationTiles()
-    const {
-  // Returns the tiling index of the tiling with requuired for activation tiles.
-  // If no such tiling exists, returns the past-the-last index (num_tilings).
-  size_t num_tilings = tiling_set_->num_tilings();
-
-  if (tree_ == PENDING_TREE) {
-    // For the pending tree, the tiling with required for activation tiles is
-    // the high res one.
-    PictureLayerTilingSet::TilingRange high_res_tiling_range =
-        tiling_set_->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
-    if (high_res_tiling_range.start != high_res_tiling_range.end)
-      return high_res_tiling_range.start;
-  } else {
-    DCHECK_EQ(ACTIVE_TREE, tree_);
-    // Only pending tree tiles can be required for activation. They can appear
-    // also in the active tree only if they are shared. If we skip all shared
-    // tiles, there is no need to find them as they will not be returned.
-    if (skip_all_shared_tiles_)
-      return num_tilings;
-
-    // For the active tree, the tiling with required for activation tiles is
-    // the one whose twin tiling is the high res pending tiling.
-    for (size_t i = 0; i < num_tilings; ++i) {
-      const PictureLayerTiling* tiling = tiling_set_->tiling_at(i);
-      const PictureLayerTiling* pending_tiling =
-          tiling_set_->client()->GetPendingOrActiveTwinTiling(tiling);
-      if (pending_tiling && pending_tiling->resolution() == HIGH_RESOLUTION)
-        return i;
-    }
-  }
-
-  return num_tilings;
+  // If the tile is shared while we're skipping shared tiles, return false.
+  if (skip_all_shared_tiles_ && tile_->is_shared())
+    return false;
+  (*tilings_)[tiling_index_]->UpdateTileAndTwinPriority(tile_);
+  // If the tile is out of order, return false.
+  if (skip_shared_out_of_order_tiles_ &&
+      IsSharedOutOfOrderTile(tree_, tree_priority_, tile_)) {
+    return false;
+  }
+  // In other cases, the tile we got is a viable candidate, return true.
+  return true;
+}
+
+// EventuallyTilingIterator
+TilingSetEvictionQueue::EventuallyTilingIterator::EventuallyTilingIterator(
+    std::vector<PictureLayerTiling*>* tilings,
+    WhichTree tree,
+    TreePriority tree_priority,
+    bool skip_shared_out_of_order_tiles,
+    bool skip_all_shared_tiles)
+    : OnePriorityRectIterator(tilings,
+                              tree,
+                              tree_priority,
+                              skip_shared_out_of_order_tiles,
+                              skip_all_shared_tiles) {
+  // Find the first tiling with a tile.
+  while (tiling_index_ < tilings_->size()) {
+    if (!((*tilings_))[tiling_index_]->has_eventually_rect_tiles()) {
+      ++tiling_index_;
+      continue;
+    }
+    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_eventually_rect(),
+        ((*tilings_))[tiling_index_]->current_skewport_rect(),
+        ((*tilings_))[tiling_index_]->current_soon_border_rect());
+    if (!iterator_) {
+      ++tiling_index_;
+      continue;
+    }
+    break;
+  }
+  if (tiling_index_ >= tilings_->size())
+    return;
+  if (!GetFirstTileAndCheckIfValid(&iterator_))
+    ++(*this);
+}
+
+TilingSetEvictionQueue::EventuallyTilingIterator&
+    TilingSetEvictionQueue::EventuallyTilingIterator::
+    operator++() {
+  bool found_tile = AdvanceToNextTile(&iterator_);
+  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
+    ++tiling_index_;
+    if (!((*tilings_))[tiling_index_]->has_eventually_rect_tiles())
+      continue;
+    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_eventually_rect(),
+        ((*tilings_))[tiling_index_]->current_skewport_rect(),
+        ((*tilings_))[tiling_index_]->current_soon_border_rect());
+    if (!iterator_)
+      continue;
+    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
+    if (!found_tile)
+      found_tile = AdvanceToNextTile(&iterator_);
+  }
+  return *this;
+}
+
+// SoonBorderTilingIterator
+TilingSetEvictionQueue::SoonBorderTilingIterator::SoonBorderTilingIterator(
+    std::vector<PictureLayerTiling*>* tilings,
+    WhichTree tree,
+    TreePriority tree_priority,
+    bool skip_shared_out_of_order_tiles,
+    bool skip_all_shared_tiles)
+    : OnePriorityRectIterator(tilings,
+                              tree,
+                              tree_priority,
+                              skip_shared_out_of_order_tiles,
+                              skip_all_shared_tiles) {
+  // Find the first tiling with a tile.
+  while (tiling_index_ < tilings_->size()) {
+    if (!((*tilings_))[tiling_index_]->has_soon_border_rect_tiles()) {
+      ++tiling_index_;
+      continue;
+    }
+    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_soon_border_rect(),
+        ((*tilings_))[tiling_index_]->current_skewport_rect(),
+        ((*tilings_))[tiling_index_]->current_visible_rect());
+    if (!iterator_) {
+      ++tiling_index_;
+      continue;
+    }
+    break;
+  }
+  if (tiling_index_ >= tilings_->size())
+    return;
+  if (!GetFirstTileAndCheckIfValid(&iterator_))
+    ++(*this);
+}
+
+TilingSetEvictionQueue::SoonBorderTilingIterator&
+    TilingSetEvictionQueue::SoonBorderTilingIterator::
+    operator++() {
+  bool found_tile = AdvanceToNextTile(&iterator_);
+  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
+    ++tiling_index_;
+    if (!((*tilings_))[tiling_index_]->has_soon_border_rect_tiles())
+      continue;
+    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_soon_border_rect(),
+        ((*tilings_))[tiling_index_]->current_skewport_rect(),
+        ((*tilings_))[tiling_index_]->current_visible_rect());
+    if (!iterator_)
+      continue;
+    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
+    if (!found_tile)
+      found_tile = AdvanceToNextTile(&iterator_);
+  }
+  return *this;
+}
+
+// SkewportTilingIterator
+TilingSetEvictionQueue::SkewportTilingIterator::SkewportTilingIterator(
+    std::vector<PictureLayerTiling*>* tilings,
+    WhichTree tree,
+    TreePriority tree_priority,
+    bool skip_shared_out_of_order_tiles,
+    bool skip_all_shared_tiles)
+    : OnePriorityRectIterator(tilings,
+                              tree,
+                              tree_priority,
+                              skip_shared_out_of_order_tiles,
+                              skip_all_shared_tiles) {
+  // Find the first tiling with a tile.
+  while (tiling_index_ < tilings_->size()) {
+    if (!((*tilings_))[tiling_index_]->has_skewport_rect_tiles()) {
+      ++tiling_index_;
+      continue;

[enne (OOO), 2015/03/27 19:12:11]

This is maybe just a style nit, but these loops are a bit confusing to me. 
tilings_ is ordered, right? So, the first time we don't have a skewport tile,
you should just break instead of continue?

Can this just be like:

  for (size_t idx = tiling_index_; idx < tilings_->size() &&
has_skewport_tiles(idx); ++idx)

...instead of a while loop and this continue?

[vmpstr, 2015/03/27 20:19:27]

The has skewport rect tiles check is on the tiling though. That is, if the first
tiling doesn't have tiles in that region, a second one could. 

This is like:

If this tiling doesn't have tiles, try the next tiling
Create the iterator
If the iterator is empty, try the next tiling
Else done.

The while loop with continues seems like a most natural way to capture that to
me. I'm open to suggestions (a for loop would also work, but it would still have
continues, would you prefer that instead?)

[enne (OOO), 2015/03/27 21:48:05]

Oh, right.  I think I was thinking about the wrong dimension of the problem
here.  Ignore this comment!

+    }
+    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_skewport_rect(),
+        ((*tilings_))[tiling_index_]->current_visible_rect(),
+        ((*tilings_))[tiling_index_]->current_visible_rect());
+    if (!iterator_) {
+      ++tiling_index_;
+      continue;
+    }
+    break;
+  }
+  if (tiling_index_ >= tilings_->size())
+    return;
+  if (!GetFirstTileAndCheckIfValid(&iterator_))
+    ++(*this);
+}
+
+TilingSetEvictionQueue::SkewportTilingIterator&
+    TilingSetEvictionQueue::SkewportTilingIterator::
+    operator++() {
+  bool found_tile = AdvanceToNextTile(&iterator_);
+  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
+    ++tiling_index_;
+    if (!((*tilings_))[tiling_index_]->has_skewport_rect_tiles())
+      continue;
+    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_skewport_rect(),
+        ((*tilings_))[tiling_index_]->current_visible_rect(),
+        ((*tilings_))[tiling_index_]->current_visible_rect());
+    if (!iterator_)
+      continue;
+    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
+    if (!found_tile)
+      found_tile = AdvanceToNextTile(&iterator_);
+  }
+  return *this;
+}
+
+// VisibleTilingIterator
+TilingSetEvictionQueue::VisibleTilingIterator::VisibleTilingIterator(
+    std::vector<PictureLayerTiling*>* tilings,
+    WhichTree tree,
+    TreePriority tree_priority,
+    bool skip_shared_out_of_order_tiles,
+    bool skip_all_shared_tiles,
+    bool return_occluded_tiles,
+    bool return_required_for_activation_tiles)
+    : OnePriorityRectIterator(tilings,
+                              tree,
+                              tree_priority,
+                              skip_shared_out_of_order_tiles,
+                              skip_all_shared_tiles),
+      return_occluded_tiles_(return_occluded_tiles),
+      return_required_for_activation_tiles_(
+          return_required_for_activation_tiles) {
+  // Find the first tiling with a tile.
+  while (tiling_index_ < tilings_->size()) {
+    if (!((*tilings_))[tiling_index_]->has_visible_rect_tiles()) {
+      ++tiling_index_;
+      continue;
+    }
+    iterator_ = TilingData::Iterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_visible_rect(), false);
+    if (!iterator_) {
+      ++tiling_index_;
+      continue;
+    }
+    break;
+  }
+  if (tiling_index_ >= tilings_->size())
+    return;
+  if (!GetFirstTileAndCheckIfValid(&iterator_)) {
+    ++(*this);
+    return;
+  }
+  if (!TileMatchesRequiredFlags(tile_)) {
+    ++(*this);
+    return;
+  }
+}
+
+TilingSetEvictionQueue::VisibleTilingIterator&
+    TilingSetEvictionQueue::VisibleTilingIterator::
+    operator++() {
+  bool found_tile = AdvanceToNextTile(&iterator_);
+  while (found_tile && !TileMatchesRequiredFlags(tile_))
+    found_tile = AdvanceToNextTile(&iterator_);
+
+  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
+    ++tiling_index_;
+    if (!((*tilings_))[tiling_index_]->has_visible_rect_tiles())
+      continue;
+    iterator_ = TilingData::Iterator(
+        ((*tilings_))[tiling_index_]->tiling_data(),
+        ((*tilings_))[tiling_index_]->current_visible_rect(), false);
+    if (!iterator_)
+      continue;
+    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
+    if (!found_tile)
+      found_tile = AdvanceToNextTile(&iterator_);
+    while (found_tile && !TileMatchesRequiredFlags(tile_))
+      found_tile = AdvanceToNextTile(&iterator_);
+  }
+  return *this;
+}
+
+bool TilingSetEvictionQueue::VisibleTilingIterator::TileMatchesRequiredFlags(
+    const Tile* tile) const {
+  return (tile->required_for_activation() ==

[enne (OOO), 2015/03/27 19:12:11]

style nit: no need for parens.  You could also break this up into two temporary
booleans, and it'd still be three lines long.

[vmpstr, 2015/03/27 20:19:27]

Eh, I'm not so worried about length, but I did change it for clarity.

+              return_required_for_activation_tiles_ &&
+          tile->is_occluded(tree_) == return_occluded_tiles_);
 }
 
 }  // namespace cc