[WIP] cc: Use reverse spiral iterator in tiling eviction.

cc/resources/picture_layer_tiling.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/resources/picture_layer_tiling.h"
 
 #include <algorithm>
 #include <cmath>
 #include <limits>
 #include <set>
 
 #include "base/debug/trace_event.h"
 #include "base/debug/trace_event_argument.h"
 #include "base/logging.h"
 #include "cc/base/math_util.h"
 #include "cc/resources/tile.h"
 #include "cc/resources/tile_priority.h"
 #include "ui/gfx/geometry/point_conversions.h"
 #include "ui/gfx/geometry/rect_conversions.h"
 #include "ui/gfx/geometry/safe_integer_conversions.h"
 #include "ui/gfx/geometry/size_conversions.h"
 
 namespace cc {
 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(
     float contents_scale,
     const gfx::Size& layer_bounds,
     PictureLayerTilingClient* client) {
   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
                                                 layer_bounds,
                                                 client));
 }
 
 PictureLayerTiling::PictureLayerTiling(float contents_scale,
                                        const gfx::Size& layer_bounds,
                                        PictureLayerTilingClient* client)
     : contents_scale_(contents_scale),
       layer_bounds_(layer_bounds),
       resolution_(NON_IDEAL_RESOLUTION),
       client_(client),
       tiling_data_(gfx::Size(), gfx::Size(), kBorderTexels),
       last_impl_frame_time_in_seconds_(0.0),
       content_to_screen_scale_(0.f),
       can_require_tiles_for_activation_(false),
       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);
   if (tile_size.IsEmpty()) {
     layer_bounds_ = gfx::Size();
     content_bounds = gfx::Size();
   }
 
   DCHECK(!gfx::ToFlooredSize(
       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
@@ skipping 43 matching lines @@
     }
   }
 
   // Create a new tile because our twin didn't have a valid one.
   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
   if (tile.get()) {
     DCHECK(!tile->is_shared());
     tile->set_tiling_index(i, j);
     tiles_[key] = tile;
   }
-  eviction_tiles_cache_valid_ = false;
   return tile.get();
 }
 
 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
   const PictureLayerTiling* twin_tiling =
       client_->GetPendingOrActiveTwinTiling(this);
   bool include_borders = false;
   for (TilingData::Iterator iter(
            &tiling_data_, live_tiles_rect_, include_borders);
        iter;
@@ skipping 302 matching lines @@
 }
 
 bool PictureLayerTiling::RemoveTileAt(int i,
                                       int j,
                                       PictureLayerTiling* recycled_twin) {
   TileMap::iterator found = tiles_.find(TileMapKey(i, j));
   if (found == tiles_.end())
     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);
   }
   return true;
 }
 
 void PictureLayerTiling::Reset() {
   live_tiles_rect_ = gfx::Rect();
   PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
     it->second->set_shared(false);
     if (recycled_twin)
       recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL);
   }
   tiles_.clear();
-  eviction_tiles_cache_valid_ = false;
 }
 
 gfx::Rect PictureLayerTiling::ComputeSkewport(
     double current_frame_time_in_seconds,
     const gfx::Rect& visible_rect_in_content_space) const {
   gfx::Rect skewport = visible_rect_in_content_space;
   if (last_impl_frame_time_in_seconds_ == 0.0)
     return skewport;
 
   double time_delta =
@@ skipping 89 matching lines @@
   float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale_;
   soon_border_rect.Inset(-border, -border, -border, -border);
 
   // Update the tiling state.
   SetLiveTilesRect(eventually_rect);
 
   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
   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;
   current_eventually_rect_ = eventually_rect;
   current_occlusion_in_layer_space_ = occlusion_in_layer_space;
 
   // Update has_*_tiles state.
   gfx::Rect tiling_rect(tiling_size());
 
   has_visible_rect_tiles_ = tiling_rect.Intersects(current_visible_rect_);
@@ skipping 382 matching lines @@
     if (delta < event.distance)
       break;
   }
 
   gfx::Rect result(origin_x, origin_y, width, height);
   if (cache)
     cache->previous_result = result;
   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) {}
 
 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
     PictureLayerTiling* tiling)
     : tiling_(tiling), phase_(VISIBLE_RECT), current_tile_(NULL) {
   if (!tiling_->has_visible_rect_tiles_) {
     AdvancePhase();
     return;
   }
@@ skipping 113 matching lines @@
     }
     current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
   }
 
   if (current_tile_)
     tiling_->UpdateTileAndTwinPriority(current_tile_);
   return *this;
 }
 
 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
-    : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
+    : tiling_(nullptr),
+      tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES),
+      eviction_category_(EVENTUALLY),
+      processing_soon_border_rect_(false),
+      skip_shared_high_priority_tiles_(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);
+    EvictionCategory category,
+    bool skip_shared_high_priority_tiles)
+    : tiling_(tiling),
+      tree_priority_(tree_priority),
+      eviction_category_(category),
+      processing_soon_border_rect_(true),
+      skip_shared_high_priority_tiles_(skip_shared_high_priority_tiles),
+      unoccluded_now_tiles_index_(0),
+      current_tile_(nullptr) {
+  WhichTree tree = tiling_->client_->GetTree();
+  if (tree == PENDING_TREE) {
+    switch (eviction_category_) {
+      case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      case SOON_AND_REQUIRED_FOR_ACTIVATION:
+        // Pending EVENTUALLY and SOON tiles are never required for activation.
+        return;
+      default:
+        break;
+    }
+  } else {
+    switch (eviction_category_) {
+      case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      case SOON_AND_REQUIRED_FOR_ACTIVATION:
+      case NOW_AND_REQUIRED_FOR_ACTIVATION: {
+        // Early out if there is no pending twin tiling.
+        if (!skip_shared_high_priority_tiles_)
+          return;
+        const PictureLayerTiling* twin_tiling =
+            tiling_->client_->GetPendingOrActiveTwinTiling(tiling_);
+        if (!twin_tiling)
+          return;
+        // Early out if the pending twin tiling does not have NOW tiles.
+        TilePriority::PriorityBin max_twin_tile_priority_bin =
+            twin_tiling->client_->GetMaxTilePriorityBin();
+        if (max_twin_tile_priority_bin > TilePriority::NOW)
+          return;
+        break;
+      }
+      default:
+        break;
+    }
+  }
+  TilePriority::PriorityBin max_tile_priority_bin =
+      tiling_->client_->GetMaxTilePriorityBin();
+  switch (eviction_category_) {
+    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+    case EVENTUALLY:
+      if (tiling_->has_eventually_rect_tiles_) {
+        if (max_tile_priority_bin < TilePriority::EVENTUALLY)
+          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+              &tiling_->tiling_data_, tiling_->current_eventually_rect_,
+              tiling_->current_skewport_rect_,
+              tiling_->current_soon_border_rect_);
+        else
+          spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+              &tiling_->tiling_data_, tiling_->current_eventually_rect_,
+              gfx::Rect(), gfx::Rect());
+        bool skipped_tiles = false;
+        AdvanceEventually(&skipped_tiles);
+        if (!current_tile_ && !skipped_tiles &&
+            max_tile_priority_bin == TilePriority::EVENTUALLY)
+          tiling_->has_eventually_rect_tiles_ = false;
+      }
+      break;
+    case SOON_AND_REQUIRED_FOR_ACTIVATION:
+    case SOON:
+      if (max_tile_priority_bin <= TilePriority::SOON &&
+          (tiling_->has_skewport_rect_tiles_ ||
+           tiling_->has_soon_border_rect_tiles_)) {
+        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();
+      }
+      break;
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+    case NOW:
+      if (max_tile_priority_bin <= TilePriority::NOW &&
+          tiling_->has_visible_rect_tiles_) {
+        visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
+                                                 tiling_->current_visible_rect_,
+                                                 false /* include_borders */);
+        AdvanceNow();
+      }
+      break;
+  }
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceEventually(
+    bool* skipped_tiles) {
+  bool required_for_activation =
+      eviction_category_ == EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION;
+  while (spiral_iterator_) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+    ++spiral_iterator_;
+    if (!tile || !tile->HasResources())
+      continue;
+    if (PrepareTileUnlessReturnedByTwin(tile) &&
+        tile->required_for_activation() == required_for_activation) {
+      current_tile_ = tile;
+      return;
+    }
+    if (skipped_tiles)
+      *skipped_tiles = true;
+  }
+
+  current_tile_ = nullptr;
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceSoon() {
+  bool required_for_activation =
+      eviction_category_ == SOON_AND_REQUIRED_FOR_ACTIVATION;
+  while (spiral_iterator_) {
+    std::pair<int, int> next_index = spiral_iterator_.index();
+    Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+    ++spiral_iterator_;
+    if (tile && tile->HasResources() && PrepareTileUnlessReturnedByTwin(tile) &&
+        tile->required_for_activation() == required_for_activation) {
+      current_tile_ = tile;
+      return;
+    }
+    if (!spiral_iterator_ && processing_soon_border_rect_) {
+      if (tiling_->has_skewport_rect_tiles_) {
+        // Max tile priority bin should never be SOON so there is no need to
+        // create a special case for the inclusion of the visible rect.
+        DCHECK_EQ(tiling_->client_->GetMaxTilePriorityBin(), TilePriority::NOW);
+        DCHECK_LT(tiling_->client_->GetMaxTilePriorityBin(),
+                  TilePriority::SOON);
+        spiral_iterator_ = TilingData::ReverseSpiralDifferenceIterator(
+            &tiling_->tiling_data_, tiling_->current_skewport_rect_,
+            tiling_->current_visible_rect_, tiling_->current_visible_rect_);
+      }
+      processing_soon_border_rect_ = false;
+    }
+  }
+
+  current_tile_ = nullptr;
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::AdvanceNow() {
+  bool required_for_activation =
+      eviction_category_ == NOW_AND_REQUIRED_FOR_ACTIVATION;
+  if (visible_iterator_) {
+    WhichTree tree = tiling_->client_->GetTree();
+    bool skip_all_shared_tiles =
+        skip_shared_high_priority_tiles_ &&
+        tree_priority_ == (tree == ACTIVE_TREE ? NEW_CONTENT_TAKES_PRIORITY
+                                               : SMOOTHNESS_TAKES_PRIORITY);
+    while (visible_iterator_) {
+      std::pair<int, int> next_index = visible_iterator_.index();
+      Tile* tile = tiling_->TileAt(next_index.first, next_index.second);
+      ++visible_iterator_;
+      if (!tile || !tile->HasResources())
+        continue;
+      if (skip_all_shared_tiles && tile->is_shared())
+        continue;
+      if (tree == PENDING_TREE &&
+          tiling_->IsTileRequiredForActivationIfVisible(tile) !=
+              required_for_activation)
+        continue;
+      if (!tiling_->IsTileOccluded(tile)) {
+        unoccluded_now_tiles_.push_back(tile);
+        continue;
+      }
+      if (PrepareTileUnlessReturnedByTwin(tile) &&
+          tile->required_for_activation() == required_for_activation) {
+        current_tile_ = tile;
+        return;
+      }
+    }
+  }
+
+  while (unoccluded_now_tiles_index_ < unoccluded_now_tiles_.size()) {
+    Tile* tile = unoccluded_now_tiles_[unoccluded_now_tiles_index_];
+    ++unoccluded_now_tiles_index_;
+    DCHECK(tile);
+    if (!tile->HasResources())
+      continue;
+    if (PrepareTileUnlessReturnedByTwin(tile) &&
+        tile->required_for_activation() == required_for_activation) {
+      current_tile_ = tile;
+      return;
+    }
+  }
+
+  current_tile_ = nullptr;
+}
+
+bool PictureLayerTiling::TilingEvictionTileIterator::
+    PrepareTileUnlessReturnedByTwin(Tile* tile) const {
+  if (skip_shared_high_priority_tiles_ && tile->is_shared()) {
+    WhichTree tree = tiling_->client_->GetTree();
+    switch (tree_priority_) {
+      case SMOOTHNESS_TAKES_PRIORITY:
+        // The priority for tile priority of a shared tile will be the active
+        // priority thus return shared tiles from the active tree.
+        if (tree != ACTIVE_TREE)
+          return false;
+        break;
+      case NEW_CONTENT_TAKES_PRIORITY:
+        // The priority for tile priority of a shared tile will be the pending
+        // priority thus return shared tiles from the pending tree.
+        if (tree != PENDING_TREE)
+          return false;
+        break;
+      case SAME_PRIORITY_FOR_BOTH_TREES: {
+        // The priority for tile priority of a shared tile will be a combined
+        // priority thus return shared tiles from a higher priority tree.
+        tiling_->UpdateTileAndTwinPriority(tile);
+        WhichTree other_tree = tree == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
+        const TilePriority& priority = tile->priority(tree);
+        const TilePriority& other_priority = tile->priority(other_tree);
+        if (priority.priority_bin != other_priority.priority_bin)
+          return priority.priority_bin < other_priority.priority_bin;
+        const bool occluded = tile->is_occluded(tree);
+        const bool other_occluded = tile->is_occluded(other_tree);
+        if (occluded != other_occluded)
+          return !occluded;
+        if (priority.distance_to_visible != other_priority.distance_to_visible)
+          return priority.distance_to_visible <
+                 other_priority.distance_to_visible;
+        return tree == ACTIVE_TREE;
+      }
+      default:
+        NOTREACHED();
+    }
+  }
+  tiling_->UpdateTileAndTwinPriority(tile);
+  return true;
 }
 
 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:
+    case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceEventually(nullptr);
+      break;
+    case SOON:
+    case SOON_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceSoon();
+      break;
+    case NOW:
+    case NOW_AND_REQUIRED_FOR_ACTIVATION:
+      AdvanceNow();
+      break;
+  }
   return *this;
 }
 
 }  // namespace cc