cc: Remove vectors from tiling eviction tile iterator.

cc/layers/picture_layer_impl.cc

 // Copyright 2012 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/layers/picture_layer_impl.h"
 
 #include <algorithm>
 #include <limits>
 
 #include "base/time/time.h"
@@ skipping 1538 matching lines @@
   DCHECK(*this);
 
   IteratorType index = stages_[current_stage_].iterator_type;
   DCHECK(iterators_[index]);
   DCHECK(iterators_[index].get_type() == stages_[current_stage_].tile_type);
 
   return *iterators_[index];
 }
 
 PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator()
-    : iterator_index_(0),
+    : tiling_index_(0),
       iteration_stage_(TilePriority::EVENTUALLY),
+      range_index_(0),
       required_for_activation_(false),
-      layer_(NULL) {}
+      tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      layer_(NULL) {
+}
 
 PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
     PictureLayerImpl* layer,
     TreePriority tree_priority)
-    : iterator_index_(0),
+    : tiling_index_(0),
       iteration_stage_(TilePriority::EVENTUALLY),
+      range_index_(0),
       required_for_activation_(false),
+      tree_priority_(tree_priority),
       layer_(layer) {
   // Early out if the layer has no tilings.
   // TODO(vmpstr): Once tile priorities are determined by the iterators, ensure
   // that layers that don't have valid tile priorities have lowest priorities so
   // they evict their tiles first (crbug.com/381704)
   if (!layer_->tilings_ || !layer_->tilings_->num_tilings())
     return;
 
+  ConstructRanges();
+  if (!CurrentTilingIndexInRange())
+    AdvanceRange();
+
+  // There must be at least one valid range.
+  DCHECK(CurrentTilingIndexInRange());
+
+  iterator_ = PictureLayerTiling::TilingEvictionTileIterator(
+      layer_->tilings_->tiling_at(tiling_index_),
+      tree_priority,
+      iteration_stage_,
+      required_for_activation_);
+
+  if (!iterator_)
+    AdvanceToNextIterator();
+}
+
+PictureLayerImpl::LayerEvictionTileIterator::~LayerEvictionTileIterator() {
+}
+
+Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() {
+  DCHECK(*this);
+  return *iterator_;
+}
+
+const Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() const {
+  DCHECK(*this);
+  return *iterator_;
+}
+
+PictureLayerImpl::LayerEvictionTileIterator&
+PictureLayerImpl::LayerEvictionTileIterator::
+operator++() {
+  DCHECK(*this);
+  ++iterator_;
+
+  if (!iterator_)
+    AdvanceToNextIterator();
+  return *this;
+}
+
+void PictureLayerImpl::LayerEvictionTileIterator::ConstructRanges() {
+  // TODO(vmpstr): See if these can be looked up from the tiling set.
   size_t high_res_tiling_index = layer_->tilings_->num_tilings();
   size_t low_res_tiling_index = layer_->tilings_->num_tilings();
   for (size_t i = 0; i < layer_->tilings_->num_tilings(); ++i) {
     PictureLayerTiling* tiling = layer_->tilings_->tiling_at(i);
     if (tiling->resolution() == HIGH_RESOLUTION)
       high_res_tiling_index = i;
     else if (tiling->resolution() == LOW_RESOLUTION)
       low_res_tiling_index = i;
   }
 
-  iterators_.reserve(layer_->tilings_->num_tilings());
+  DCHECK_LT(high_res_tiling_index, layer_->tilings_->num_tilings());
 
-  // Higher resolution non-ideal goes first.
-  for (size_t i = 0; i < high_res_tiling_index; ++i) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(i), tree_priority));
+  // First iterate from highest resolution to the HIGH_RES tiling.
+  ranges_[0].start_index = 0;
+  ranges_[0].one_past_end_index = high_res_tiling_index;
+
+  // Next, iterate from the lowest resolution to the LOW_RES tiling. Note that
+  // if we don't have a low res tiling, then the start index will be the same as
+  // one past the end, which means it is an empty range.
+  ranges_[1].start_index = layer_->tilings_->num_tilings() - 1;
+  ranges_[1].one_past_end_index = low_res_tiling_index;
+
+  // Next, iterate from just after the LOW_RES tiling to the HIGH_RES tiling.
+  // Note that if there is no low res tiling, then start index will be the last
+  // tiling.
+  ranges_[2].start_index = low_res_tiling_index - 1;
+  ranges_[2].one_past_end_index = high_res_tiling_index;
+
+  if (low_res_tiling_index < layer_->tilings_->num_tilings()) {
+    // Next, iterate a range of one element: LOW_RES tiling.
+    ranges_[3].start_index = low_res_tiling_index;
+    ranges_[3].one_past_end_index = low_res_tiling_index + 1;
+  } else {
+    // If there is no LOW_RES tiling, then set an empty range.
+    ranges_[3].start_index = 0;
+    ranges_[3].one_past_end_index = 0;
   }
 
-  // Lower resolution non-ideal goes next.
-  for (size_t i = layer_->tilings_->num_tilings() - 1;
-       i > high_res_tiling_index;
-       --i) {
-    PictureLayerTiling* tiling = layer_->tilings_->tiling_at(i);
-    if (tiling->resolution() == LOW_RESOLUTION)
-      continue;
+  // Finally, iterate a range of one element: HIGH_RES tiling.
+  ranges_[4].start_index = high_res_tiling_index;
+  ranges_[4].one_past_end_index = high_res_tiling_index + 1;
 
-    iterators_.push_back(
-        PictureLayerTiling::TilingEvictionTileIterator(tiling, tree_priority));
+  range_index_ = 0;
+  tiling_index_ = ranges_[range_index_].start_index;
+}
+
+bool PictureLayerImpl::LayerEvictionTileIterator::CurrentTilingIndexInRange() {
+  TilingIterationRange& range = ranges_[range_index_];
+  if (range.start_index < range.one_past_end_index) {
+    return tiling_index_ >= range.start_index &&
+           tiling_index_ < range.one_past_end_index;
+  } else if (range.start_index > range.one_past_end_index) {
+    return tiling_index_ <= range.start_index &&
+           tiling_index_ > range.one_past_end_index;
   }
+  // Empty range means we're not in range.
+  return false;
+}
 
-  // Now, put the low res tiling if we have one.
-  if (low_res_tiling_index < layer_->tilings_->num_tilings()) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(low_res_tiling_index), tree_priority));
-  }
+void PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextIterator() {
+  DCHECK(!iterator_);
+  while (!iterator_) {
+    bool success = AdvanceTiling();
+    if (!success)
+      success = AdvanceRange();
+    if (!success)
+      success = AdvanceStage();
+    if (!success)
+      break;
 
-  // Finally, put the high res tiling if we have one.
-  if (high_res_tiling_index < layer_->tilings_->num_tilings()) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(high_res_tiling_index), tree_priority));
-  }
-
-  DCHECK_GT(iterators_.size(), 0u);
-
-  if (!iterators_[iterator_index_] ||
-      !IsCorrectType(&iterators_[iterator_index_])) {
-    AdvanceToNextIterator();
+    iterator_ = PictureLayerTiling::TilingEvictionTileIterator(
+        layer_->tilings_->tiling_at(tiling_index_),
+        tree_priority_,
+        iteration_stage_,
+        required_for_activation_);
   }
 }
 
-PictureLayerImpl::LayerEvictionTileIterator::~LayerEvictionTileIterator() {}
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceTiling() {
+  // We can't advance the tiling if we're already not in range.
+  if (!CurrentTilingIndexInRange())
+    return false;
 
-Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() {
-  DCHECK(*this);
-  return *iterators_[iterator_index_];
+  int direction = ranges_[range_index_].start_index <
+                          ranges_[range_index_].one_past_end_index
+                      ? 1
+                      : -1;
+  tiling_index_ += direction;
+
+  return CurrentTilingIndexInRange();
 }
 
-const Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() const {
-  DCHECK(*this);
-  return *iterators_[iterator_index_];
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceRange() {
+  DCHECK(!CurrentTilingIndexInRange());
+  while (!CurrentTilingIndexInRange()) {
+    range_index_ = (range_index_ + 1) % arraysize(ranges_);
+    tiling_index_ = ranges_[range_index_].start_index;
+    // If we failed to find a range and cycled back to the start, then we need
+    // to indicate that we should advance the stage instead.
+    if (range_index_ == 0)
+      return false;
+  }
+  return true;
 }
 
-PictureLayerImpl::LayerEvictionTileIterator&
-PictureLayerImpl::LayerEvictionTileIterator::
-operator++() {
-  DCHECK(*this);
-  ++iterators_[iterator_index_];
-  if (!iterators_[iterator_index_] ||
-      !IsCorrectType(&iterators_[iterator_index_])) {
-    AdvanceToNextIterator();
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceStage() {
+  // If we're NOW and required_for_activation, then this was the last pass
+  // through the iterators.
+  if (iteration_stage_ == TilePriority::NOW && required_for_activation_)
+    return false;
+
+  if (!required_for_activation_) {
+    required_for_activation_ = true;
+  } else {
+    required_for_activation_ = false;
+    iteration_stage_ =
+        static_cast<TilePriority::PriorityBin>(iteration_stage_ - 1);
   }
-  return *this;
-}
-
-void PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextIterator() {
-  ++iterator_index_;
-
-  while (true) {
-    while (iterator_index_ < iterators_.size()) {
-      if (iterators_[iterator_index_] &&
-          IsCorrectType(&iterators_[iterator_index_])) {
-        return;
-      }
-      ++iterator_index_;
-    }
-
-    // If we're NOW and required_for_activation, then this was the last pass
-    // through the iterators.
-    if (iteration_stage_ == TilePriority::NOW && required_for_activation_)
-      break;
-
-    if (!required_for_activation_) {
-      required_for_activation_ = true;
-    } else {
-      required_for_activation_ = false;
-      iteration_stage_ =
-          static_cast<TilePriority::PriorityBin>(iteration_stage_ - 1);
-    }
-    iterator_index_ = 0;
-  }
+  return true;
 }
 
 PictureLayerImpl::LayerEvictionTileIterator::operator bool() const {
-  return iterator_index_ < iterators_.size();
-}
-
-bool PictureLayerImpl::LayerEvictionTileIterator::IsCorrectType(
-    PictureLayerTiling::TilingEvictionTileIterator* it) const {
-  return it->get_type() == iteration_stage_ &&
-         (**it)->required_for_activation() == required_for_activation_;
+  return iterator_;
 }
 
 }  // namespace cc