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 a6c46a1689a29282ce4921a2021bd86aacfdda2d..891b3713229114f894b818b1f021df35e0bec445 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);
@@ -588,8 +557,6 @@ void PictureLayerTiling::ComputeTilePriorityRects(
   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
   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;
@@ -964,92 +931,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) {}
 
@@ -1183,48 +1064,206 @@ 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,

[ajuma, 2014/10/23 23:12:54]

Unused now, remove?

[vmpstr, 2014/10/29 18:19:41]

Done.

     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 EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      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 SOON_AND_REQUIRED_FOR_ACTIVATION:

[ajuma, 2014/10/23 23:12:54]

Why is there nothing to do for this case? Is it because SOON tiles are never
required for activation? (And if that's the case, why do we have this category
at all?)

[vmpstr, 2014/10/29 18:19:41]

Yes and removed.

+      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 (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_;
+
+  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 (tile && tile->HasResources()) {
+      current_tile_ = tile;
+      break;
+    }
+    ++spiral_iterator_;
+    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_;
+  }
+
+  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 (!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);
+      if ((eviction_category_ == NOW_AND_REQUIRED_FOR_ACTIVATION &&
+           !tile_required_for_activation) ||
+          (eviction_category_ == NOW && tile_required_for_activation)) {
+        ++visible_iterator_;
+        continue;
+      }
+
+      if (!tiling_->IsTileOccluded(tile)) {
+        unoccluded_now_tiles_.push_back(tile);
+        ++visible_iterator_;
+        continue;
+      }
+
+      current_tile_ = tile;
+      break;
+    }
+
+    Tile* tile = unoccluded_now_tiles_[unoccluded_now_tiles_index_];
+    DCHECK(tile);
+    if (!tile->HasResources()) {
+      ++unoccluded_now_tiles_index_;
+      continue;
+    }

[ajuma, 2014/10/23 23:12:54]

Why don't we need to consider whether the tile is required for activation when
dealing with unoccluded tiles?

[vmpstr, 2014/10/29 18:19:41]

Tile that is occluded is not required for activation... I've added some comments
throughout the code that hopefully makes it easier to read.

+
+    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 EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      break;
+    case SOON:
+      AdvanceSoon(false);
+      break;
+    case SOON_AND_REQUIRED_FOR_ACTIVATION:
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceNow(false);
+      break;
+  }
   return *this;
 }