cc: Use reverse spiral iterator in tiling eviction.

cc/resources/picture_layer_tiling.cc

Index: cc/resources/picture_layer_tiling.cc
diff --git a/cc/resources/picture_layer_tiling.cc b/cc/resources/picture_layer_tiling.cc
index 61b0362ee44c2b9cd073fe86db6e7c238378c69f..96cd25c27c64c2d6b59c692fb5195a6e5a945113 100644
--- a/cc/resources/picture_layer_tiling.cc
+++ b/cc/resources/picture_layer_tiling.cc
@@ -25,35 +25,6 @@ namespace {
 
 const float kSoonBorderDistanceInScreenPixels = 312.f;
 
-class TileEvictionOrder {
- public:
-  explicit TileEvictionOrder(TreePriority tree_priority)
-      : tree_priority_(tree_priority) {}
-  ~TileEvictionOrder() {}
-
-  bool operator()(const Tile* a, const Tile* b) {
-    const TilePriority& a_priority =
-        a->priority_for_tree_priority(tree_priority_);
-    const TilePriority& b_priority =
-        b->priority_for_tree_priority(tree_priority_);
-
-    DCHECK(a_priority.priority_bin == b_priority.priority_bin);
-    DCHECK(a->required_for_activation() == b->required_for_activation());
-
-    // Or if a is occluded and b is unoccluded.
-    bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
-    bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
-    if (a_is_occluded != b_is_occluded)
-      return a_is_occluded;
-
-    // Or if a is farther away from visible.
-    return a_priority.distance_to_visible > b_priority.distance_to_visible;
-  }
-
- private:
-  TreePriority tree_priority_;
-};
-
 }  // namespace
 
 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
@@ -79,9 +50,7 @@ PictureLayerTiling::PictureLayerTiling(float contents_scale,
       has_visible_rect_tiles_(false),
       has_skewport_rect_tiles_(false),
       has_soon_border_rect_tiles_(false),
-      has_eventually_rect_tiles_(false),
-      eviction_tiles_cache_valid_(false),
-      eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
+      has_eventually_rect_tiles_(false) {
   gfx::Size content_bounds =
       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
@@ -469,7 +438,6 @@ bool PictureLayerTiling::RemoveTileAt(int i,
     return false;
   found->second->set_shared(false);
   tiles_.erase(found);
-  eviction_tiles_cache_valid_ = false;
   if (recycled_twin) {
     // Recycled twin does not also have a recycled twin, so pass NULL.
     recycled_twin->RemoveTileAt(i, j, NULL);
@@ -595,8 +563,6 @@ void PictureLayerTiling::ComputeTilePriorityRects(
   last_viewport_in_layer_space_ = viewport_in_layer_space;
   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 
-  eviction_tiles_cache_valid_ = false;
-
   current_visible_rect_ = visible_rect_in_content_space;
   current_skewport_rect_ = skewport;
   current_soon_border_rect_ = soon_border_rect;
@@ -974,92 +940,6 @@ gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
   return result;
 }
 
-void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
-    TreePriority tree_priority) {
-  if (eviction_tiles_cache_valid_ &&
-      eviction_cache_tree_priority_ == tree_priority)
-    return;
-
-  eviction_tiles_now_.clear();
-  eviction_tiles_now_and_required_for_activation_.clear();
-  eviction_tiles_soon_.clear();
-  eviction_tiles_soon_and_required_for_activation_.clear();
-  eviction_tiles_eventually_.clear();
-  eviction_tiles_eventually_and_required_for_activation_.clear();
-
-  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    Tile* tile = it->second.get();
-    UpdateTileAndTwinPriority(tile);
-    const TilePriority& priority =
-        tile->priority_for_tree_priority(tree_priority);
-    switch (priority.priority_bin) {
-      case TilePriority::EVENTUALLY:
-        if (tile->required_for_activation())
-          eviction_tiles_eventually_and_required_for_activation_.push_back(
-              tile);
-        else
-          eviction_tiles_eventually_.push_back(tile);
-        break;
-      case TilePriority::SOON:
-        if (tile->required_for_activation())
-          eviction_tiles_soon_and_required_for_activation_.push_back(tile);
-        else
-          eviction_tiles_soon_.push_back(tile);
-        break;
-      case TilePriority::NOW:
-        if (tile->required_for_activation())
-          eviction_tiles_now_and_required_for_activation_.push_back(tile);
-        else
-          eviction_tiles_now_.push_back(tile);
-        break;
-    }
-  }
-
-  // TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that
-  // can be updated for each of the queues.
-  TileEvictionOrder sort_order(tree_priority);
-  std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order);
-  std::sort(eviction_tiles_now_and_required_for_activation_.begin(),
-            eviction_tiles_now_and_required_for_activation_.end(),
-            sort_order);
-  std::sort(
-      eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order);
-  std::sort(eviction_tiles_soon_and_required_for_activation_.begin(),
-            eviction_tiles_soon_and_required_for_activation_.end(),
-            sort_order);
-  std::sort(eviction_tiles_eventually_.begin(),
-            eviction_tiles_eventually_.end(),
-            sort_order);
-  std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(),
-            eviction_tiles_eventually_and_required_for_activation_.end(),
-            sort_order);
-
-  eviction_tiles_cache_valid_ = true;
-  eviction_cache_tree_priority_ = tree_priority;
-}
-
-const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles(
-    TreePriority tree_priority,
-    EvictionCategory category) {
-  UpdateEvictionCacheIfNeeded(tree_priority);
-  switch (category) {
-    case EVENTUALLY:
-      return &eviction_tiles_eventually_;
-    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
-      return &eviction_tiles_eventually_and_required_for_activation_;
-    case SOON:
-      return &eviction_tiles_soon_;
-    case SOON_AND_REQUIRED_FOR_ACTIVATION:
-      return &eviction_tiles_soon_and_required_for_activation_;
-    case NOW:
-      return &eviction_tiles_now_;
-    case NOW_AND_REQUIRED_FOR_ACTIVATION:
-      return &eviction_tiles_now_and_required_for_activation_;
-  }
-  NOTREACHED();
-  return &eviction_tiles_eventually_;
-}
-
 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
     : tiling_(NULL), current_tile_(NULL) {}
 
@@ -1193,48 +1073,219 @@ operator++() {
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
-    : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
+    : tiling_(nullptr),
+      eviction_category_(EVENTUALLY),
+      processing_occluded_now_tiles_(false),
+      processing_soon_border_rect_(false),
+      unoccluded_now_tiles_index_(0u),
+      current_tile_(nullptr) {
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
     PictureLayerTiling* tiling,
-    TreePriority tree_priority,
     EvictionCategory category)
-    : eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)),
-      // Note: initializing to "0 - 1" works as overflow is well defined for
-      // unsigned integers.
-      current_eviction_tiles_index_(static_cast<size_t>(0) - 1) {
-  DCHECK(eviction_tiles_);
-  ++(*this);
+    : tiling_(tiling),
+      eviction_category_(category),
+      processing_occluded_now_tiles_(true),
+      processing_soon_border_rect_(true),
+      unoccluded_now_tiles_index_(0),
+      current_tile_(nullptr) {
+  switch (category) {
+    case EVENTUALLY:
+      if (tiling_->has_eventually_rect_tiles_) {
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &tiling_->tiling_data_,
+            tiling_->current_eventually_rect_,
+            tiling_->current_skewport_rect_,
+            tiling_->current_soon_border_rect_);
+      }
+      AdvanceEventually(true);
+      break;
+    case SOON:
+      if (tiling_->has_soon_border_rect_tiles_) {
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &tiling_->tiling_data_,
+            tiling_->current_soon_border_rect_,
+            tiling_->current_skewport_rect_,
+            tiling_->current_visible_rect_);
+      }
+      AdvanceSoon(true);
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      if (tiling_->has_visible_rect_tiles_) {
+        visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
+                                                 tiling_->current_visible_rect_,
+                                                 false /* include_borders */);
+      }
+      AdvanceNow(true);
+      break;
+  }
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceEventually(
+    bool first_run) {
+  if (!first_run)
+    ++spiral_iterator_;
+
+  current_tile_ = nullptr;
+  while (spiral_iterator_) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+
+    // If a tile has resources, then it is a valid tile to return.
+    if (tile && tile->HasResources()) {
+      current_tile_ = tile;
+      break;
+    }
+    ++spiral_iterator_;
+  }
+
+  if (current_tile_)
+    tiling_->UpdateTileAndTwinPriority(current_tile_);
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceSoon(
+    bool first_run) {
+  if (!first_run)
+    ++spiral_iterator_;
+
+  // For the soon rect, we process both the soon border rect and
+  // the skewport rect.
+  current_tile_ = nullptr;
+  while (spiral_iterator_) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+
+    // If the tile has resources, we can return it.
+    if (tile && tile->HasResources()) {
+      current_tile_ = tile;
+      break;
+    }
+    ++spiral_iterator_;
+
+    // If we ran out of tiles, but we were processing the soon border rect, then
+    // rebuild the iterator to iterate over skewport.
+    if (!spiral_iterator_ && processing_soon_border_rect_) {
+      if (tiling_->has_skewport_rect_tiles_) {
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &tiling_->tiling_data_,
+            tiling_->current_skewport_rect_,
+            tiling_->current_visible_rect_,
+            tiling_->current_visible_rect_);
+      }
+      processing_soon_border_rect_ = false;
+    }
+  }
+
+  if (current_tile_)
+    tiling_->UpdateTileAndTwinPriority(current_tile_);
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceNow(
+    bool first_run) {
+  if (!first_run) {
+    if (processing_occluded_now_tiles_)
+      ++visible_iterator_;
+    else
+      ++unoccluded_now_tiles_index_;
+  }
+
+  // For NOW bin, we process the visible rect, returning occluded tiles first,
+  // followed by unoccluded tiles.
+  current_tile_ = nullptr;
+  while (visible_iterator_ ||
+         (unoccluded_now_tiles_index_ < unoccluded_now_tiles_.size())) {
+    if (!visible_iterator_)
+      processing_occluded_now_tiles_ = false;
+
+    if (processing_occluded_now_tiles_) {
+      std::pair<int, int> next_index = visible_iterator_.index();
+      Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+
+      // If the tile doesn't have resources, then we won't return it now or
+      // during the occluded tile iteration.
+      if (!tile || !tile->HasResources()) {
+        ++visible_iterator_;
+        continue;
+      }
+
+      bool tile_required_for_activation = false;
+      if (tiling_->client_->GetTree() == PENDING_TREE)
+        tile_required_for_activation =
+            tiling_->IsTileRequiredForActivation(tile);
+
+      // Skip the tile if it doesn't match the requested activation criteria.
+      if ((eviction_category_ == NOW_AND_REQUIRED_FOR_ACTIVATION &&
+           !tile_required_for_activation) ||
+          (eviction_category_ == NOW && tile_required_for_activation)) {
+        ++visible_iterator_;
+        continue;
+      }
+
+      // If the tile is not occluded, then save it temporarily for iteration
+      // later (in this pass, we're returning only occluded tiles).
+      if (!tiling_->IsTileOccluded(tile)) {
+        unoccluded_now_tiles_.push_back(tile);
+        ++visible_iterator_;
+        continue;
+      }
+
+      // All of the above checks passed, so the tile is good to return now.
+      current_tile_ = tile;
+      break;
+    }
+
+    // If we fall through here, that means we're iterating unoccluded tiles,
+    // which we already saved in |unoccluded_now_tiles_|. So, we can just
+    // iterate the vector.
+    Tile* tile = unoccluded_now_tiles_[unoccluded_now_tiles_index_];
+    DCHECK(tile);
+    if (!tile->HasResources()) {
+      ++unoccluded_now_tiles_index_;
+      continue;
+    }
+
+    current_tile_ = tile;
+    break;
+  }
+
+  if (current_tile_)
+    tiling_->UpdateTileAndTwinPriority(current_tile_);
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
-  return eviction_tiles_ &&
-         current_eviction_tiles_index_ != eviction_tiles_->size();
+  return !!current_tile_;
 }
 
 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
   DCHECK(*this);
-  return (*eviction_tiles_)[current_eviction_tiles_index_];
+  return current_tile_;
 }
 
 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
   DCHECK(*this);
-  return (*eviction_tiles_)[current_eviction_tiles_index_];
+  return current_tile_;
 }
 
 PictureLayerTiling::TilingEvictionTileIterator&
 PictureLayerTiling::TilingEvictionTileIterator::
 operator++() {
-  DCHECK(*this);
-  do {
-    ++current_eviction_tiles_index_;
-  } while (current_eviction_tiles_index_ != eviction_tiles_->size() &&
-           !(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources());
-
+  switch (eviction_category_) {
+    case EVENTUALLY:
+      AdvanceEventually(false);
+      break;
+    case SOON:
+      AdvanceSoon(false);
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceNow(false);
+      break;
+  }
   return *this;
 }