cc: Add tiling eviction tile iterator.

This patch adds a naive version of the eviction iterator for a tiling.
This sets the interface for the class, so that work can continue on
handing eviction from the layer and tile manager, as well as being able
to independently change the implementation for something more optimal.

R=enne

Review URL: https://codereview.chromium.org/217033004

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@260999 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 181 insertions, 2 deletions

diff --git a/cc/resources/picture_layer_tiling.cc b/cc/resources/picture_layer_tiling.cc
index 356ac1b..99b6283 100644
--- a/cc/resources/picture_layer_tiling.cc
+++ b/cc/resources/picture_layer_tiling.cc
@@ -18,6 +18,24 @@
 #include "ui/gfx/size_conversions.h"
 
 namespace cc {
+namespace {
+
+class TileEvictionOrder {
+ public:
+  explicit TileEvictionOrder(WhichTree tree) : tree_(tree) {}
+  ~TileEvictionOrder() {}
+
+  bool operator()(const Tile* a, const Tile* b) {
+    const TilePriority& a_priority = a->priority(tree_);
+    const TilePriority& b_priority = b->priority(tree_);
+
+    return a_priority.IsHigherPriorityThan(b_priority);
+  }
+
+ private:
+  WhichTree tree_;
+};
+}  // namespace
 
 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
     float contents_scale,
@@ -36,7 +54,8 @@ PictureLayerTiling::PictureLayerTiling(float contents_scale,
       resolution_(NON_IDEAL_RESOLUTION),
       client_(client),
       tiling_data_(gfx::Size(), gfx::Size(), true),
-      last_impl_frame_time_in_seconds_(0.0) {
+      last_impl_frame_time_in_seconds_(0.0),
+      eviction_tiles_cache_valid_(false) {
   gfx::Size content_bounds =
       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
@@ -436,6 +455,7 @@ void PictureLayerTiling::UpdateTilePriorities(
   current_visible_rect_in_content_space_ = visible_rect_in_content_space;
   current_skewport_ = skewport;
   current_eventually_rect_ = eventually_rect;
+  eviction_tiles_cache_valid_ = false;
 
   TilePriority now_priority(resolution_, TilePriority::NOW, 0);
   float content_to_screen_scale =
@@ -732,6 +752,24 @@ gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
   return result;
 }
 
+void PictureLayerTiling::UpdateEvictionCacheIfNeeded(WhichTree tree) {
+  if (eviction_tiles_cache_valid_)
+    return;
+
+  eviction_tiles_cache_.clear();
+  eviction_tiles_cache_.reserve(tiles_.size());
+  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
+    // TODO(vmpstr): This should update the priority if UpdateTilePriorities
+    // changes not to do this.
+    eviction_tiles_cache_.push_back(it->second);
+  }
+
+  std::sort(eviction_tiles_cache_.begin(),
+            eviction_tiles_cache_.end(),
+            TileEvictionOrder(tree));
+  eviction_tiles_cache_valid_ = true;
+}
+
 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
     : tiling_(NULL), current_tile_(NULL) {}
 
@@ -827,4 +865,54 @@ operator++() {
   return *this;
 }
 
+PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
+    : is_valid_(false), tiling_(NULL) {}
+
+PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
+    PictureLayerTiling* tiling,
+    WhichTree tree)
+    : is_valid_(false), tiling_(tiling), tree_(tree) {}
+
+PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {}
+
+PictureLayerTiling::TilingEvictionTileIterator::operator bool() {
+  if (!IsValid())
+    Initialize();
+
+  return IsValid() && tile_iterator_ != tiling_->eviction_tiles_cache_.end();
+}
+
+Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
+  if (!IsValid())
+    Initialize();
+
+  DCHECK(*this);
+  return *tile_iterator_;
+}
+
+PictureLayerTiling::TilingEvictionTileIterator&
+PictureLayerTiling::TilingEvictionTileIterator::
+operator++() {
+  DCHECK(*this);
+  do {
+    ++tile_iterator_;
+  } while (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
+           (!(*tile_iterator_)->HasResources()));
+
+  return *this;
+}
+
+void PictureLayerTiling::TilingEvictionTileIterator::Initialize() {
+  if (!tiling_)
+    return;
+
+  tiling_->UpdateEvictionCacheIfNeeded(tree_);
+  tile_iterator_ = tiling_->eviction_tiles_cache_.begin();
+  is_valid_ = true;
+  if (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
+      !(*tile_iterator_)->HasResources()) {
+    ++(*this);
+  }
+}
+
 }  // namespace cc
diff --git a/cc/resources/picture_layer_tiling.h b/cc/resources/picture_layer_tiling.h
index d27d39a..19bc717 100644
--- a/cc/resources/picture_layer_tiling.h
+++ b/cc/resources/picture_layer_tiling.h
@@ -91,6 +91,30 @@ class CC_EXPORT PictureLayerTiling {
     TilingData::SpiralDifferenceIterator spiral_iterator_;
   };
 
+  class CC_EXPORT TilingEvictionTileIterator {
+   public:
+    TilingEvictionTileIterator();
+    TilingEvictionTileIterator(PictureLayerTiling* tiling, WhichTree tree);
+    ~TilingEvictionTileIterator();
+
+    operator bool();
+    Tile* operator*();
+    TilingEvictionTileIterator& operator++();
+    TilePriority::PriorityBin get_type() {
+      DCHECK(*this);
+      return (*tile_iterator_)->priority(tree_).priority_bin;
+    }
+
+   private:
+    void Initialize();
+    bool IsValid() const { return is_valid_; }
+
+    bool is_valid_;
+    PictureLayerTiling* tiling_;
+    WhichTree tree_;
+    std::vector<Tile*>::iterator tile_iterator_;
+  };
+
   ~PictureLayerTiling();
 
   // Create a tiling with no tiles.  CreateTiles must be called to add some.
@@ -232,7 +256,9 @@ class CC_EXPORT PictureLayerTiling {
   }
 
  protected:
+  friend class CoverageIterator;
   friend class TilingRasterTileIterator;
+  friend class TilingEvictionTileIterator;
 
   typedef std::pair<int, int> TileMapKey;
   typedef base::hash_map<TileMapKey, scoped_refptr<Tile> > TileMap;
@@ -251,6 +277,8 @@ class CC_EXPORT PictureLayerTiling {
                             const gfx::Rect& visible_rect_in_content_space)
       const;
 
+  void UpdateEvictionCacheIfNeeded(WhichTree tree);
+
   // Given properties.
   float contents_scale_;
   gfx::Size layer_bounds_;
@@ -270,7 +298,8 @@ class CC_EXPORT PictureLayerTiling {
   gfx::Rect current_skewport_;
   gfx::Rect current_eventually_rect_;
 
-  friend class CoverageIterator;
+  std::vector<Tile*> eviction_tiles_cache_;
+  bool eviction_tiles_cache_valid_;
 
  private:
   DISALLOW_ASSIGN(PictureLayerTiling);
diff --git a/cc/resources/picture_layer_tiling_unittest.cc b/cc/resources/picture_layer_tiling_unittest.cc
index 837f647..009cd98 100644
--- a/cc/resources/picture_layer_tiling_unittest.cc
+++ b/cc/resources/picture_layer_tiling_unittest.cc
@@ -13,6 +13,7 @@
 #include "cc/test/fake_output_surface_client.h"
 #include "cc/test/fake_picture_layer_tiling_client.h"
 #include "cc/test/test_context_provider.h"
+#include "cc/test/test_shared_bitmap_manager.h"
 #include "testing/gtest/include/gtest/gtest.h"
 #include "ui/gfx/rect_conversions.h"
 #include "ui/gfx/size_conversions.h"
@@ -924,6 +925,67 @@ static void TileExists(bool exists, Tile* tile,
   EXPECT_EQ(exists, tile != NULL) << geometry_rect.ToString();
 }
 
+TEST(PictureLayerTilingTest, TilingEvictionTileIteratorStaticViewport) {
+  FakeOutputSurfaceClient output_surface_client;
+  scoped_ptr<FakeOutputSurface> output_surface = FakeOutputSurface::Create3d();
+  CHECK(output_surface->BindToClient(&output_surface_client));
+  TestSharedBitmapManager shared_bitmap_manager;
+  scoped_ptr<ResourceProvider> resource_provider = ResourceProvider::Create(
+      output_surface.get(), &shared_bitmap_manager, 0, false, 1);
+
+  FakePictureLayerTilingClient client(resource_provider.get());
+  scoped_ptr<TestablePictureLayerTiling> tiling;
+
+  gfx::Rect viewport(50, 50, 100, 100);
+  gfx::Size layer_bounds(200, 200);
+
+  client.SetTileSize(gfx::Size(30, 30));
+
+  tiling = TestablePictureLayerTiling::Create(1.0f, layer_bounds, &client);
+  tiling->UpdateTilePriorities(ACTIVE_TREE, viewport, 1.0f, 1.0);
+
+  PictureLayerTiling::TilingRasterTileIterator empty_iterator;
+  EXPECT_FALSE(empty_iterator);
+
+  std::vector<Tile*> all_tiles = tiling->AllTilesForTesting();
+
+  PictureLayerTiling::TilingEvictionTileIterator it(tiling.get(), ACTIVE_TREE);
+
+  // Tiles don't have resources to evict.
+  EXPECT_FALSE(it);
+
+  // Sanity check.
+  EXPECT_EQ(64u, all_tiles.size());
+
+  client.tile_manager()->InitializeTilesWithResourcesForTesting(
+      all_tiles, resource_provider.get());
+
+  std::set<Tile*> all_tiles_set(all_tiles.begin(), all_tiles.end());
+
+  it =
+      PictureLayerTiling::TilingEvictionTileIterator(tiling.get(), ACTIVE_TREE);
+  EXPECT_TRUE(it);
+
+  std::set<Tile*> eviction_tiles;
+  Tile* last_tile = *it;
+  for (; it; ++it) {
+    Tile* tile = *it;
+    EXPECT_TRUE(tile);
+    EXPECT_LE(tile->priority(ACTIVE_TREE).priority_bin,
+              last_tile->priority(ACTIVE_TREE).priority_bin);
+    if (tile->priority(ACTIVE_TREE).priority_bin ==
+        last_tile->priority(ACTIVE_TREE).priority_bin) {
+      EXPECT_LE(tile->priority(ACTIVE_TREE).distance_to_visible,
+                last_tile->priority(ACTIVE_TREE).distance_to_visible);
+    }
+    last_tile = tile;
+    eviction_tiles.insert(tile);
+  }
+
+  EXPECT_GT(all_tiles_set.size(), 0u);
+  EXPECT_EQ(all_tiles_set, eviction_tiles);
+}
+
 TEST_F(PictureLayerTilingIteratorTest, TilesExist) {
   gfx::Size layer_bounds(1099, 801);
   Initialize(gfx::Size(100, 100), 1.f, layer_bounds);