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 1523 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),
-      iteration_stage_(TilePriority::EVENTUALLY),
-      required_for_activation_(false),
-      layer_(NULL) {}
+    : current_range_offset_(0),
+      current_range_type_(HIGHER_THAN_HIGH_RES),
+      current_stage_(TilePriority::EVENTUALLY, false),
+      tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      layer_(NULL) {
+}
 
 PictureLayerImpl::LayerEvictionTileIterator::LayerEvictionTileIterator(
     PictureLayerImpl* layer,
     TreePriority tree_priority)
-    : iterator_index_(0),
-      iteration_stage_(TilePriority::EVENTUALLY),
-      required_for_activation_(false),
+    : current_range_offset_(0),
+      current_range_type_(HIGHER_THAN_HIGH_RES),
+      current_stage_(TilePriority::EVENTUALLY, 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 (current_range_offset_ >= ranges_[current_range_type_].count)
+    AdvanceRange();
+
+  // There must be at least one valid range.
+  DCHECK(current_range_offset_ < ranges_[current_range_type_].count);
+
+  iterator_ = PictureLayerTiling::TilingEvictionTileIterator(
+      layer_->tilings_->tiling_at(GetCurrentTilingIndex()),
+      tree_priority,
+      current_stage_.tile_type,
+      current_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::SetEmptyRange(
+    RangeType type) {
+  ranges_[type].tiling_offset = 0;
+  ranges_[type].count = 0;
+}
+
+void PictureLayerImpl::LayerEvictionTileIterator::SetRange(RangeType type,
+                                                           int start_index,
+                                                           int end_index) {
+  if (start_index > end_index) {
+    SetEmptyRange(type);
+    return;
+  }
+  ranges_[type].tiling_offset = start_index;
+  ranges_[type].count = end_index - start_index + 1;
+}
+
+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());
-
-  // 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));
-  }
-
-  // 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;
-
-    iterators_.push_back(
-        PictureLayerTiling::TilingEvictionTileIterator(tiling, tree_priority));
-  }
-
-  // Now, put the low res tiling if we have one.
+  DCHECK_LT(high_res_tiling_index, layer_->tilings_->num_tilings());
+
+  // First iterate from highest resolution to the HIGH_RES tiling.
+  int start_index = 0;
+  int end_index = high_res_tiling_index - 1;
+  SetRange(HIGHER_THAN_HIGH_RES, start_index, end_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.
+  start_index = low_res_tiling_index + 1;
+  end_index = layer_->tilings_->num_tilings() - 1;
+  SetRange(LOWER_THAN_LOW_RES, start_index, end_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.
+  start_index = high_res_tiling_index + 1;
+  end_index = low_res_tiling_index - 1;
+  SetRange(BETWEEN_HIGH_AND_LOW_RES, start_index, end_index);
+
   if (low_res_tiling_index < layer_->tilings_->num_tilings()) {
-    iterators_.push_back(PictureLayerTiling::TilingEvictionTileIterator(
-        layer_->tilings_->tiling_at(low_res_tiling_index), tree_priority));
-  }
-
-  // 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();
-  }
-}
-
-PictureLayerImpl::LayerEvictionTileIterator::~LayerEvictionTileIterator() {}
-
-Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() {
-  DCHECK(*this);
-  return *iterators_[iterator_index_];
-}
-
-const Tile* PictureLayerImpl::LayerEvictionTileIterator::operator*() const {
-  DCHECK(*this);
-  return *iterators_[iterator_index_];
-}
-
-PictureLayerImpl::LayerEvictionTileIterator&
-PictureLayerImpl::LayerEvictionTileIterator::
-operator++() {
-  DCHECK(*this);
-  ++iterators_[iterator_index_];
-  if (!iterators_[iterator_index_] ||
-      !IsCorrectType(&iterators_[iterator_index_])) {
-    AdvanceToNextIterator();
-  }
-  return *this;
+    // Next, iterate a range of one element: LOW_RES tiling.
+    SetRange(LOW_RES, low_res_tiling_index, low_res_tiling_index);
+  } else {
+    SetEmptyRange(LOW_RES);
+  }
+
+  // Finally, iterate a range of one element: HIGH_RES tiling.
+  SetRange(HIGH_RES, high_res_tiling_index, high_res_tiling_index);
+
+  current_range_type_ = HIGHER_THAN_HIGH_RES;
+  current_range_offset_ = 0;
 }
 
 void PictureLayerImpl::LayerEvictionTileIterator::AdvanceToNextIterator() {
-  ++iterator_index_;
-
-  while (true) {
-    while (iterator_index_ < iterators_.size()) {
-      if (iterators_[iterator_index_] &&
-          IsCorrectType(&iterators_[iterator_index_])) {
-        return;
-      }
-      ++iterator_index_;
+  DCHECK(!iterator_);
+  while (!iterator_) {
+    bool success = AdvanceTiling();
+    if (!success)
+      success = AdvanceRange();
+    if (!success)
+      success = AdvanceStage();
+    if (!success)
+      break;
+
+    iterator_ = PictureLayerTiling::TilingEvictionTileIterator(
+        layer_->tilings_->tiling_at(GetCurrentTilingIndex()),
+        tree_priority_,
+        current_stage_.tile_type,
+        current_stage_.required_for_activation);
+  }
+}
+
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceTiling() {
+  DCHECK(current_range_offset_ < ranges_[current_range_type_].count);
+  ++current_range_offset_;
+  return current_range_offset_ < ranges_[current_range_type_].count;
+}
+
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceRange() {
+  DCHECK(current_range_offset_ >= ranges_[current_range_type_].count);
+  bool wrapped_around = false;
+  while (current_range_offset_ >= ranges_[current_range_type_].count) {
+    switch (current_range_type_) {
+      case HIGHER_THAN_HIGH_RES:
+        current_range_type_ = LOWER_THAN_LOW_RES;
+        break;
+      case LOWER_THAN_LOW_RES:
+        current_range_type_ = BETWEEN_HIGH_AND_LOW_RES;
+        break;
+      case BETWEEN_HIGH_AND_LOW_RES:
+        current_range_type_ = LOW_RES;
+        break;
+      case LOW_RES:
+        current_range_type_ = HIGH_RES;
+        break;
+      case HIGH_RES:
+        current_range_type_ = HIGHER_THAN_HIGH_RES;
+        wrapped_around = true;
+        break;
+      case NUM_RANGE_TYPES:
+        NOTREACHED();
+        break;
     }
-
-    // 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_)
+    current_range_offset_ = 0;
+  }
+  // If we wrapped around the ranges, we need to indicate that we should advance
+  // the stage.
+  return !wrapped_around;
+}
+
+int PictureLayerImpl::LayerEvictionTileIterator::GetCurrentTilingIndex() {

[reveman, 2014/07/31 15:32:48]

can you move this function to anonymous namespace?

[vmpstr, 2014/08/01 06:04:48]

It's using member variables. I like the fact that I don't have to think about
what index/offset to pass to it, to be honest. If we want to change this, I'd
recommend we move the whole iterator to a different file, since I don't really
want to have anonymous functions in layer that are only used in one of the
iterators.

[reveman, 2014/08/01 17:54:46]

Acknowledged.

+  DCHECK(current_range_offset_ < ranges_[current_range_type_].count);
+  const TilingIterationRange& range = ranges_[current_range_type_];
+  switch (current_range_type_) {
+    case HIGHER_THAN_HIGH_RES:
+    case LOW_RES:
+    case HIGH_RES:
+      return range.tiling_offset + current_range_offset_;
+    case BETWEEN_HIGH_AND_LOW_RES:
+    case LOWER_THAN_LOW_RES:
+      return range.tiling_offset + (range.count - current_range_offset_ - 1);
+    case NUM_RANGE_TYPES:
       break;
-
-    if (!required_for_activation_) {
-      required_for_activation_ = true;
-    } else {
-      required_for_activation_ = false;
-      iteration_stage_ =
-          static_cast<TilePriority::PriorityBin>(iteration_stage_ - 1);
+  }
+  NOTREACHED();
+  return 0;
+}
+
+bool PictureLayerImpl::LayerEvictionTileIterator::AdvanceStage() {
+  // This function advances the stage to the next stage. The order of stages
+  // is as follows:
+  //
+  // EVENTUALLY bin and not required for activation,
+  // EVENTUALLY bin and required for activation
+  // SOON bin and not required for activation,
+  // SOON bin and required for activation,
+  // NOW bin and not required for activation,
+  // NOW bin and required for activation.
+
+  // If we're NOW and required_for_activation, then this was the last pass
+  // through the iterators.
+  if (current_stage_.tile_type == TilePriority::NOW &&
+      current_stage_.required_for_activation)
+    return false;
+
+  if (!current_stage_.required_for_activation) {
+    current_stage_.required_for_activation = true;
+  } else {
+    current_stage_.required_for_activation = false;
+    switch (current_stage_.tile_type) {
+      case TilePriority::EVENTUALLY:
+        current_stage_.tile_type = TilePriority::SOON;
+        break;
+      case TilePriority::SOON:
+        current_stage_.tile_type = TilePriority::NOW;
+        break;
+      case TilePriority::NOW:
+        NOTREACHED();
+        break;
     }
-    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