src/cc/resources/picture_layer_tiling.cc

   1 // Copyright 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "cc/resources/picture_layer_tiling.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9 #include <limits>
  10 #include <set>
  11
  12 #include "base/debug/trace_event.h"
  13 #include "base/debug/trace_event_argument.h"
  14 #include "base/logging.h"
  15 #include "cc/base/math_util.h"
  16 #include "cc/resources/tile.h"
  17 #include "cc/resources/tile_priority.h"
  18 #include "ui/gfx/point_conversions.h"
  19 #include "ui/gfx/rect_conversions.h"
  20 #include "ui/gfx/safe_integer_conversions.h"
  21 #include "ui/gfx/size_conversions.h"
  22
  23 namespace cc {
  24 namespace {
  25
  26 const float kSoonBorderDistanceInScreenPixels = 312.f;
  27
  28 class TileEvictionOrder {
  29  public:
  30   explicit TileEvictionOrder(TreePriority tree_priority)
  31       : tree_priority_(tree_priority) {}
  32   ~TileEvictionOrder() {}
  33
  34   bool operator()(const Tile* a, const Tile* b) {
  35     const TilePriority& a_priority =
  36         a->priority_for_tree_priority(tree_priority_);
  37     const TilePriority& b_priority =
  38         b->priority_for_tree_priority(tree_priority_);
  39
  40     DCHECK(a_priority.priority_bin == b_priority.priority_bin);
  41     DCHECK(a->required_for_activation() == b->required_for_activation());
  42
  43     // Or if a is occluded and b is unoccluded.
  44     bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
  45     bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
  46     if (a_is_occluded != b_is_occluded)
  47       return a_is_occluded;
  48
  49     // Or if a is farther away from visible.
  50     return a_priority.distance_to_visible > b_priority.distance_to_visible;
  51   }
  52
  53  private:
  54   TreePriority tree_priority_;
  55 };
  56
  57 void ReleaseTile(Tile* tile, WhichTree tree) {
  58   // Reset priority as tile is ref-counted and might still be used
  59   // even though we no longer hold a reference to it here anymore.
  60   tile->SetPriority(tree, TilePriority());
  61   tile->set_shared(false);
  62 }
  63
  64 }  // namespace
  65
  66 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
  67     float contents_scale,
  68     const gfx::Size& layer_bounds,
  69     PictureLayerTilingClient* client) {
  70   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
  71                                                 layer_bounds,
  72                                                 client));
  73 }
  74
  75 PictureLayerTiling::PictureLayerTiling(float contents_scale,
  76                                        const gfx::Size& layer_bounds,
  77                                        PictureLayerTilingClient* client)
  78     : contents_scale_(contents_scale),
  79       layer_bounds_(layer_bounds),
  80       resolution_(NON_IDEAL_RESOLUTION),
  81       client_(client),
  82       tiling_data_(gfx::Size(), gfx::Size(), true),
  83       last_impl_frame_time_in_seconds_(0.0),
  84       has_visible_rect_tiles_(false),
  85       has_skewport_rect_tiles_(false),
  86       has_soon_border_rect_tiles_(false),
  87       has_eventually_rect_tiles_(false),
  88       eviction_tiles_cache_valid_(false),
  89       eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
  90   gfx::Size content_bounds =
  91       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
  92   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
  93   if (tile_size.IsEmpty()) {
  94     layer_bounds_ = gfx::Size();
  95     content_bounds = gfx::Size();
  96   }
  97
  98   DCHECK(!gfx::ToFlooredSize(
  99       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
 100       "Tiling created with scale too small as contents become empty." <<
 101       " Layer bounds: " << layer_bounds.ToString() <<
 102       " Contents scale: " << contents_scale;
 103
 104   tiling_data_.SetTilingSize(content_bounds);
 105   tiling_data_.SetMaxTextureSize(tile_size);
 106 }
 107
 108 PictureLayerTiling::~PictureLayerTiling() {
 109   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 110     ReleaseTile(it->second.get(), client_->GetTree());
 111 }
 112
 113 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
 114   client_ = client;
 115 }
 116
 117 Tile* PictureLayerTiling::CreateTile(int i,
 118                                      int j,
 119                                      const PictureLayerTiling* twin_tiling) {
 120   TileMapKey key(i, j);
 121   DCHECK(tiles_.find(key) == tiles_.end());
 122
 123   gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
 124   gfx::Rect tile_rect = paint_rect;
 125   tile_rect.set_size(tiling_data_.max_texture_size());
 126
 127   // Check our twin for a valid tile.
 128   if (twin_tiling &&
 129       tiling_data_.max_texture_size() ==
 130       twin_tiling->tiling_data_.max_texture_size()) {
 131     if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
 132       gfx::Rect rect =
 133           gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
 134       if (!client_->GetInvalidation()->Intersects(rect)) {
 135         DCHECK(!candidate_tile->is_shared());
 136         candidate_tile->set_shared(true);
 137         tiles_[key] = candidate_tile;
 138         return candidate_tile;
 139       }
 140     }
 141   }
 142
 143   // Create a new tile because our twin didn't have a valid one.
 144   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
 145   if (tile.get()) {
 146     DCHECK(!tile->is_shared());
 147     tiles_[key] = tile;
 148   }
 149   return tile.get();
 150 }
 151
 152 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
 153   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 154   bool include_borders = false;
 155   for (TilingData::Iterator iter(
 156            &tiling_data_, live_tiles_rect_, include_borders);
 157        iter;
 158        ++iter) {
 159     TileMapKey key = iter.index();
 160     TileMap::iterator find = tiles_.find(key);
 161     if (find != tiles_.end())
 162       continue;
 163     CreateTile(key.first, key.second, twin_tiling);
 164   }
 165
 166   VerifyLiveTilesRect();
 167 }
 168
 169 void PictureLayerTiling::UpdateTilesToCurrentPile(
 170     const Region& layer_invalidation,
 171     const gfx::Size& new_layer_bounds) {
 172   DCHECK(!new_layer_bounds.IsEmpty());
 173
 174   gfx::Size tile_size = tiling_data_.max_texture_size();
 175
 176   if (new_layer_bounds != layer_bounds_) {
 177     gfx::Size content_bounds =
 178         gfx::ToCeiledSize(gfx::ScaleSize(new_layer_bounds, contents_scale_));
 179
 180     tile_size = client_->CalculateTileSize(content_bounds);
 181     if (tile_size.IsEmpty()) {
 182       layer_bounds_ = gfx::Size();
 183       content_bounds = gfx::Size();
 184     } else {
 185       layer_bounds_ = new_layer_bounds;
 186     }
 187
 188     // The SetLiveTilesRect() method would drop tiles outside the new bounds,
 189     // but may do so incorrectly if resizing the tiling causes the number of
 190     // tiles in the tiling_data_ to change.
 191     gfx::Rect content_rect(content_bounds);
 192     int before_left = tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.x());
 193     int before_top = tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.y());
 194     int before_right =
 195         tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 196     int before_bottom =
 197         tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 198
 199     // The live_tiles_rect_ is clamped to stay within the tiling size as we
 200     // change it.
 201     live_tiles_rect_.Intersect(content_rect);
 202     tiling_data_.SetTilingSize(content_bounds);
 203
 204     int after_right = -1;
 205     int after_bottom = -1;
 206     if (!live_tiles_rect_.IsEmpty()) {
 207       after_right =
 208           tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 209       after_bottom =
 210           tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 211     }
 212
 213     // There is no recycled twin since this is run on the pending tiling.
 214     PictureLayerTiling* recycled_twin = NULL;
 215     DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this));
 216     DCHECK_EQ(PENDING_TREE, client_->GetTree());
 217
 218     // Drop tiles outside the new layer bounds if the layer shrank.
 219     for (int i = after_right + 1; i <= before_right; ++i) {
 220       for (int j = before_top; j <= before_bottom; ++j)
 221         RemoveTileAt(i, j, recycled_twin);
 222     }
 223     for (int i = before_left; i <= after_right; ++i) {
 224       for (int j = after_bottom + 1; j <= before_bottom; ++j)
 225         RemoveTileAt(i, j, recycled_twin);
 226     }
 227
 228     // If the layer grew, the live_tiles_rect_ is not changed, but a new row
 229     // and/or column of tiles may now exist inside the same live_tiles_rect_.
 230     const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 231     if (after_right > before_right) {
 232       DCHECK_EQ(after_right, before_right + 1);
 233       for (int j = before_top; j <= after_bottom; ++j)
 234         CreateTile(after_right, j, twin_tiling);
 235     }
 236     if (after_bottom > before_bottom) {
 237       DCHECK_EQ(after_bottom, before_bottom + 1);
 238       for (int i = before_left; i <= before_right; ++i)
 239         CreateTile(i, after_bottom, twin_tiling);
 240     }
 241   }
 242
 243   if (tile_size != tiling_data_.max_texture_size()) {
 244     tiling_data_.SetMaxTextureSize(tile_size);
 245     // When the tile size changes, the TilingData positions no longer work
 246     // as valid keys to the TileMap, so just drop all tiles.
 247     Reset();
 248   } else {
 249     Invalidate(layer_invalidation);
 250   }
 251
 252   PicturePileImpl* pile = client_->GetPile();
 253   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 254     it->second->set_picture_pile(pile);
 255   VerifyLiveTilesRect();
 256 }
 257
 258 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) {
 259   bool recreate_invalidated_tiles = false;
 260   DoInvalidate(layer_region, recreate_invalidated_tiles);
 261 }
 262
 263 void PictureLayerTiling::Invalidate(const Region& layer_region) {
 264   bool recreate_invalidated_tiles = true;
 265   DoInvalidate(layer_region, recreate_invalidated_tiles);
 266 }
 267
 268 void PictureLayerTiling::DoInvalidate(const Region& layer_region,
 269                                       bool recreate_invalidated_tiles) {
 270   std::vector<TileMapKey> new_tile_keys;
 271   gfx::Rect expanded_live_tiles_rect =
 272       tiling_data_.ExpandRectIgnoringBordersToTileBounds(live_tiles_rect_);
 273   for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
 274     gfx::Rect layer_rect = iter.rect();
 275     gfx::Rect content_rect =
 276         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
 277     // Consider tiles inside the live tiles rect even if only their border
 278     // pixels intersect the invalidation. But don't consider tiles outside
 279     // the live tiles rect with the same conditions, as they won't exist.
 280     int border_pixels = tiling_data_.border_texels();
 281     content_rect.Inset(-border_pixels, -border_pixels);
 282     // Avoid needless work by not bothering to invalidate where there aren't
 283     // tiles.
 284     content_rect.Intersect(expanded_live_tiles_rect);
 285     if (content_rect.IsEmpty())
 286       continue;
 287     // Since the content_rect includes border pixels already, don't include
 288     // borders when iterating to avoid double counting them.
 289     bool include_borders = false;
 290     for (TilingData::Iterator iter(
 291              &tiling_data_, content_rect, include_borders);
 292          iter;
 293          ++iter) {
 294       // There is no recycled twin since this is run on the pending tiling.
 295       PictureLayerTiling* recycled_twin = NULL;
 296       DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this));
 297       DCHECK_EQ(PENDING_TREE, client_->GetTree());
 298       if (RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin))
 299         new_tile_keys.push_back(iter.index());
 300     }
 301   }
 302
 303   if (recreate_invalidated_tiles && !new_tile_keys.empty()) {
 304     for (size_t i = 0; i < new_tile_keys.size(); ++i) {
 305       // Don't try to share a tile with the twin layer, it's been invalidated so
 306       // we have to make our own tile here.
 307       const PictureLayerTiling* twin_tiling = NULL;
 308       CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
 309     }
 310   }
 311 }
 312
 313 PictureLayerTiling::CoverageIterator::CoverageIterator()
 314     : tiling_(NULL),
 315       current_tile_(NULL),
 316       tile_i_(0),
 317       tile_j_(0),
 318       left_(0),
 319       top_(0),
 320       right_(-1),
 321       bottom_(-1) {
 322 }
 323
 324 PictureLayerTiling::CoverageIterator::CoverageIterator(
 325     const PictureLayerTiling* tiling,
 326     float dest_scale,
 327     const gfx::Rect& dest_rect)
 328     : tiling_(tiling),
 329       dest_rect_(dest_rect),
 330       dest_to_content_scale_(0),
 331       current_tile_(NULL),
 332       tile_i_(0),
 333       tile_j_(0),
 334       left_(0),
 335       top_(0),
 336       right_(-1),
 337       bottom_(-1) {
 338   DCHECK(tiling_);
 339   if (dest_rect_.IsEmpty())
 340     return;
 341
 342   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 343
 344   gfx::Rect content_rect =
 345       gfx::ScaleToEnclosingRect(dest_rect_,
 346                                 dest_to_content_scale_,
 347                                 dest_to_content_scale_);
 348   // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
 349   // check for non-intersection first.
 350   content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 351   if (content_rect.IsEmpty())
 352     return;
 353
 354   left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
 355   top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
 356   right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
 357       content_rect.right() - 1);
 358   bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
 359       content_rect.bottom() - 1);
 360
 361   tile_i_ = left_ - 1;
 362   tile_j_ = top_;
 363   ++(*this);
 364 }
 365
 366 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 367 }
 368
 369 PictureLayerTiling::CoverageIterator&
 370 PictureLayerTiling::CoverageIterator::operator++() {
 371   if (tile_j_ > bottom_)
 372     return *this;
 373
 374   bool first_time = tile_i_ < left_;
 375   bool new_row = false;
 376   tile_i_++;
 377   if (tile_i_ > right_) {
 378     tile_i_ = left_;
 379     tile_j_++;
 380     new_row = true;
 381     if (tile_j_ > bottom_) {
 382       current_tile_ = NULL;
 383       return *this;
 384     }
 385   }
 386
 387   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 388
 389   // Calculate the current geometry rect.  Due to floating point rounding
 390   // and ToEnclosingRect, tiles might overlap in destination space on the
 391   // edges.
 392   gfx::Rect last_geometry_rect = current_geometry_rect_;
 393
 394   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 395
 396   current_geometry_rect_ =
 397       gfx::ScaleToEnclosingRect(content_rect,
 398                                 1 / dest_to_content_scale_,
 399                                 1 / dest_to_content_scale_);
 400
 401   current_geometry_rect_.Intersect(dest_rect_);
 402
 403   if (first_time)
 404     return *this;
 405
 406   // Iteration happens left->right, top->bottom.  Running off the bottom-right
 407   // edge is handled by the intersection above with dest_rect_.  Here we make
 408   // sure that the new current geometry rect doesn't overlap with the last.
 409   int min_left;
 410   int min_top;
 411   if (new_row) {
 412     min_left = dest_rect_.x();
 413     min_top = last_geometry_rect.bottom();
 414   } else {
 415     min_left = last_geometry_rect.right();
 416     min_top = last_geometry_rect.y();
 417   }
 418
 419   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 420   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 421   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 422
 423   if (!new_row) {
 424     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 425     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 426     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 427   }
 428
 429   return *this;
 430 }
 431
 432 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 433   return current_geometry_rect_;
 434 }
 435
 436 gfx::Rect
 437 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
 438   gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
 439   rect.set_size(tiling_->tiling_data_.max_texture_size());
 440   return rect;
 441 }
 442
 443 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 444   gfx::PointF tex_origin =
 445       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 446
 447   // Convert from dest space => content space => texture space.
 448   gfx::RectF texture_rect(current_geometry_rect_);
 449   texture_rect.Scale(dest_to_content_scale_,
 450                      dest_to_content_scale_);
 451   texture_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 452   if (texture_rect.IsEmpty())
 453     return texture_rect;
 454   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 455
 456   return texture_rect;
 457 }
 458
 459 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
 460   return tiling_->tiling_data_.max_texture_size();
 461 }
 462
 463 bool PictureLayerTiling::RemoveTileAt(int i,
 464                                       int j,
 465                                       PictureLayerTiling* recycled_twin) {
 466   TileMap::iterator found = tiles_.find(TileMapKey(i, j));
 467   if (found == tiles_.end())
 468     return false;
 469   ReleaseTile(found->second.get(), client_->GetTree());
 470   tiles_.erase(found);
 471   if (recycled_twin) {
 472     // Recycled twin does not also have a recycled twin, so pass NULL.
 473     recycled_twin->RemoveTileAt(i, j, NULL);
 474   }
 475   return true;
 476 }
 477
 478 void PictureLayerTiling::Reset() {
 479   live_tiles_rect_ = gfx::Rect();
 480   PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
 481   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 482     ReleaseTile(it->second.get(), client_->GetTree());
 483     if (recycled_twin)
 484       recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL);
 485   }
 486   tiles_.clear();
 487 }
 488
 489 gfx::Rect PictureLayerTiling::ComputeSkewport(
 490     double current_frame_time_in_seconds,
 491     const gfx::Rect& visible_rect_in_content_space) const {
 492   gfx::Rect skewport = visible_rect_in_content_space;
 493   if (last_impl_frame_time_in_seconds_ == 0.0)
 494     return skewport;
 495
 496   double time_delta =
 497       current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
 498   if (time_delta == 0.0)
 499     return skewport;
 500
 501   float skewport_target_time_in_seconds =
 502       client_->GetSkewportTargetTimeInSeconds();
 503   double extrapolation_multiplier =
 504       skewport_target_time_in_seconds / time_delta;
 505
 506   int old_x = last_visible_rect_in_content_space_.x();
 507   int old_y = last_visible_rect_in_content_space_.y();
 508   int old_right = last_visible_rect_in_content_space_.right();
 509   int old_bottom = last_visible_rect_in_content_space_.bottom();
 510
 511   int new_x = visible_rect_in_content_space.x();
 512   int new_y = visible_rect_in_content_space.y();
 513   int new_right = visible_rect_in_content_space.right();
 514   int new_bottom = visible_rect_in_content_space.bottom();
 515
 516   int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels();
 517
 518   // Compute the maximum skewport based on |skewport_limit|.
 519   gfx::Rect max_skewport = skewport;
 520   max_skewport.Inset(
 521       -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit);
 522
 523   // Inset the skewport by the needed adjustment.
 524   skewport.Inset(extrapolation_multiplier * (new_x - old_x),
 525                  extrapolation_multiplier * (new_y - old_y),
 526                  extrapolation_multiplier * (old_right - new_right),
 527                  extrapolation_multiplier * (old_bottom - new_bottom));
 528
 529   // Clip the skewport to |max_skewport|.
 530   skewport.Intersect(max_skewport);
 531
 532   // Finally, ensure that visible rect is contained in the skewport.
 533   skewport.Union(visible_rect_in_content_space);
 534   return skewport;
 535 }
 536
 537 void PictureLayerTiling::UpdateTilePriorities(
 538     WhichTree tree,
 539     const gfx::Rect& viewport_in_layer_space,
 540     float ideal_contents_scale,
 541     double current_frame_time_in_seconds,
 542     const Occlusion& occlusion_in_layer_space) {
 543   if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
 544     // This should never be zero for the purposes of has_ever_been_updated().
 545     DCHECK_NE(current_frame_time_in_seconds, 0.0);
 546     return;
 547   }
 548
 549   gfx::Rect visible_rect_in_content_space =
 550       gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
 551
 552   if (tiling_size().IsEmpty()) {
 553     last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 554     last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 555     return;
 556   }
 557
 558   size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea();
 559
 560   gfx::Size tile_size = tiling_data_.max_texture_size();
 561   int64 eventually_rect_area =
 562       max_tiles_for_interest_area * tile_size.width() * tile_size.height();
 563
 564   gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
 565                                        visible_rect_in_content_space);
 566   DCHECK(skewport.Contains(visible_rect_in_content_space));
 567
 568   gfx::Rect eventually_rect =
 569       ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space,
 570                                        eventually_rect_area,
 571                                        gfx::Rect(tiling_size()),
 572                                        &expansion_cache_);
 573
 574   DCHECK(eventually_rect.IsEmpty() ||
 575          gfx::Rect(tiling_size()).Contains(eventually_rect))
 576       << "tiling_size: " << tiling_size().ToString()
 577       << " eventually_rect: " << eventually_rect.ToString();
 578
 579   SetLiveTilesRect(eventually_rect);
 580
 581   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 582   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 583
 584   eviction_tiles_cache_valid_ = false;
 585
 586   TilePriority now_priority(resolution_, TilePriority::NOW, 0);
 587   float content_to_screen_scale = ideal_contents_scale / contents_scale_;
 588
 589   // Assign now priority to all visible tiles.
 590   bool include_borders = false;
 591   has_visible_rect_tiles_ = false;
 592   for (TilingData::Iterator iter(
 593            &tiling_data_, visible_rect_in_content_space, include_borders);
 594        iter;
 595        ++iter) {
 596     TileMap::iterator find = tiles_.find(iter.index());
 597     if (find == tiles_.end())
 598       continue;
 599     has_visible_rect_tiles_ = true;
 600     Tile* tile = find->second.get();
 601
 602     tile->SetPriority(tree, now_priority);
 603
 604     // Set whether tile is occluded or not.
 605     gfx::Rect tile_query_rect = ScaleToEnclosingRect(
 606         IntersectRects(tile->content_rect(), visible_rect_in_content_space),
 607         1.0f / contents_scale_);
 608     bool is_occluded = occlusion_in_layer_space.IsOccluded(tile_query_rect);
 609     tile->set_is_occluded(tree, is_occluded);
 610   }
 611
 612   // Assign soon priority to skewport tiles.
 613   has_skewport_rect_tiles_ = false;
 614   for (TilingData::DifferenceIterator iter(
 615            &tiling_data_, skewport, visible_rect_in_content_space);
 616        iter;
 617        ++iter) {
 618     TileMap::iterator find = tiles_.find(iter.index());
 619     if (find == tiles_.end())
 620       continue;
 621     has_skewport_rect_tiles_ = true;
 622     Tile* tile = find->second.get();
 623
 624     gfx::Rect tile_bounds =
 625         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 626
 627     float distance_to_visible =
 628         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
 629         content_to_screen_scale;
 630
 631     TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible);
 632     tile->SetPriority(tree, priority);
 633   }
 634
 635   // Assign eventually priority to interest rect tiles.
 636   has_eventually_rect_tiles_ = false;
 637   for (TilingData::DifferenceIterator iter(
 638            &tiling_data_, eventually_rect, skewport);
 639        iter;
 640        ++iter) {
 641     TileMap::iterator find = tiles_.find(iter.index());
 642     if (find == tiles_.end())
 643       continue;
 644     has_eventually_rect_tiles_ = true;
 645     Tile* tile = find->second.get();
 646
 647     gfx::Rect tile_bounds =
 648         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 649
 650     float distance_to_visible =
 651         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
 652         content_to_screen_scale;
 653     TilePriority priority(
 654         resolution_, TilePriority::EVENTUALLY, distance_to_visible);
 655     tile->SetPriority(tree, priority);
 656   }
 657
 658   // Upgrade the priority on border tiles to be SOON.
 659   gfx::Rect soon_border_rect = visible_rect_in_content_space;
 660   float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale;
 661   soon_border_rect.Inset(-border, -border, -border, -border);
 662   has_soon_border_rect_tiles_ = false;
 663   for (TilingData::DifferenceIterator iter(
 664            &tiling_data_, soon_border_rect, skewport);
 665        iter;
 666        ++iter) {
 667     TileMap::iterator find = tiles_.find(iter.index());
 668     if (find == tiles_.end())
 669       continue;
 670     has_soon_border_rect_tiles_ = true;
 671     Tile* tile = find->second.get();
 672
 673     TilePriority priority(resolution_,
 674                           TilePriority::SOON,
 675                           tile->priority(tree).distance_to_visible);
 676     tile->SetPriority(tree, priority);
 677   }
 678
 679   // Update iteration rects.
 680   current_visible_rect_ = visible_rect_in_content_space;
 681   current_skewport_rect_ = skewport;
 682   current_soon_border_rect_ = soon_border_rect;
 683   current_eventually_rect_ = eventually_rect;
 684 }
 685
 686 void PictureLayerTiling::SetLiveTilesRect(
 687     const gfx::Rect& new_live_tiles_rect) {
 688   DCHECK(new_live_tiles_rect.IsEmpty() ||
 689          gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
 690       << "tiling_size: " << tiling_size().ToString()
 691       << " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
 692   if (live_tiles_rect_ == new_live_tiles_rect)
 693     return;
 694
 695   // Iterate to delete all tiles outside of our new live_tiles rect.
 696   PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
 697   for (TilingData::DifferenceIterator iter(&tiling_data_,
 698                                            live_tiles_rect_,
 699                                            new_live_tiles_rect);
 700        iter;
 701        ++iter) {
 702     RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin);
 703   }
 704
 705   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 706
 707   // Iterate to allocate new tiles for all regions with newly exposed area.
 708   for (TilingData::DifferenceIterator iter(&tiling_data_,
 709                                            new_live_tiles_rect,
 710                                            live_tiles_rect_);
 711        iter;
 712        ++iter) {
 713     TileMapKey key(iter.index());
 714     CreateTile(key.first, key.second, twin_tiling);
 715   }
 716
 717   live_tiles_rect_ = new_live_tiles_rect;
 718   VerifyLiveTilesRect();
 719 }
 720
 721 void PictureLayerTiling::VerifyLiveTilesRect() {
 722 #if DCHECK_IS_ON
 723   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 724     if (!it->second.get())
 725       continue;
 726     DCHECK(it->first.first < tiling_data_.num_tiles_x())
 727         << this << " " << it->first.first << "," << it->first.second
 728         << " num_tiles_x " << tiling_data_.num_tiles_x() << " live_tiles_rect "
 729         << live_tiles_rect_.ToString();
 730     DCHECK(it->first.second < tiling_data_.num_tiles_y())
 731         << this << " " << it->first.first << "," << it->first.second
 732         << " num_tiles_y " << tiling_data_.num_tiles_y() << " live_tiles_rect "
 733         << live_tiles_rect_.ToString();
 734     DCHECK(tiling_data_.TileBounds(it->first.first, it->first.second)
 735                .Intersects(live_tiles_rect_))
 736         << this << " " << it->first.first << "," << it->first.second
 737         << " tile bounds "
 738         << tiling_data_.TileBounds(it->first.first, it->first.second).ToString()
 739         << " live_tiles_rect " << live_tiles_rect_.ToString();
 740   }
 741 #endif
 742 }
 743
 744 void PictureLayerTiling::DidBecomeRecycled() {
 745   // DidBecomeActive below will set the active priority for tiles that are
 746   // still in the tree. Calling this first on an active tiling that is becoming
 747   // recycled takes care of tiles that are no longer in the active tree (eg.
 748   // due to a pending invalidation).
 749   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 750     it->second->SetPriority(ACTIVE_TREE, TilePriority());
 751   }
 752 }
 753
 754 void PictureLayerTiling::DidBecomeActive() {
 755   PicturePileImpl* active_pile = client_->GetPile();
 756   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 757     it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
 758     it->second->SetPriority(PENDING_TREE, TilePriority());
 759
 760     // Tile holds a ref onto a picture pile. If the tile never gets invalidated
 761     // and recreated, then that picture pile ref could exist indefinitely.  To
 762     // prevent this, ask the client to update the pile to its own ref.  This
 763     // will cause PicturePileImpls to get deleted once the corresponding
 764     // PictureLayerImpl and any in flight raster jobs go out of scope.
 765     it->second->set_picture_pile(active_pile);
 766   }
 767 }
 768
 769 void PictureLayerTiling::GetAllTilesForTracing(
 770     std::set<const Tile*>* tiles) const {
 771   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 772     tiles->insert(it->second.get());
 773 }
 774
 775 void PictureLayerTiling::AsValueInto(base::debug::TracedValue* state) const {
 776   state->SetInteger("num_tiles", tiles_.size());
 777   state->SetDouble("content_scale", contents_scale_);
 778   state->BeginDictionary("tiling_size");
 779   MathUtil::AddToTracedValue(tiling_size(), state);
 780   state->EndDictionary();
 781 }
 782
 783 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 784   size_t amount = 0;
 785   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 786     const Tile* tile = it->second.get();
 787     amount += tile->GPUMemoryUsageInBytes();
 788   }
 789   return amount;
 790 }
 791
 792 PictureLayerTiling::RectExpansionCache::RectExpansionCache()
 793   : previous_target(0) {
 794 }
 795
 796 namespace {
 797
 798 // This struct represents an event at which the expending rect intersects
 799 // one of its boundaries.  4 intersection events will occur during expansion.
 800 struct EdgeEvent {
 801   enum { BOTTOM, TOP, LEFT, RIGHT } edge;
 802   int* num_edges;
 803   int distance;
 804 };
 805
 806 // Compute the delta to expand from edges to cover target_area.
 807 int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
 808                           int width, int height,
 809                           int64 target_area) {
 810   // Compute coefficients for the quadratic equation:
 811   //   a*x^2 + b*x + c = 0
 812   int a = num_y_edges * num_x_edges;
 813   int b = num_y_edges * width + num_x_edges * height;
 814   int64 c = static_cast<int64>(width) * height - target_area;
 815
 816   // Compute the delta for our edges using the quadratic equation.
 817   int delta =
 818       (a == 0) ? -c / b : (-b + static_cast<int>(std::sqrt(
 819                                     static_cast<int64>(b) * b - 4.0 * a * c))) /
 820                               (2 * a);
 821   return std::max(0, delta);
 822 }
 823
 824 }  // namespace
 825
 826 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
 827     const gfx::Rect& starting_rect,
 828     int64 target_area,
 829     const gfx::Rect& bounding_rect,
 830     RectExpansionCache* cache) {
 831   if (starting_rect.IsEmpty())
 832     return starting_rect;
 833
 834   if (cache &&
 835       cache->previous_start == starting_rect &&
 836       cache->previous_bounds == bounding_rect &&
 837       cache->previous_target == target_area)
 838     return cache->previous_result;
 839
 840   if (cache) {
 841     cache->previous_start = starting_rect;
 842     cache->previous_bounds = bounding_rect;
 843     cache->previous_target = target_area;
 844   }
 845
 846   DCHECK(!bounding_rect.IsEmpty());
 847   DCHECK_GT(target_area, 0);
 848
 849   // Expand the starting rect to cover target_area, if it is smaller than it.
 850   int delta = ComputeExpansionDelta(
 851       2, 2, starting_rect.width(), starting_rect.height(), target_area);
 852   gfx::Rect expanded_starting_rect = starting_rect;
 853   if (delta > 0)
 854     expanded_starting_rect.Inset(-delta, -delta);
 855
 856   gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
 857   if (rect.IsEmpty()) {
 858     // The starting_rect and bounding_rect are far away.
 859     if (cache)
 860       cache->previous_result = rect;
 861     return rect;
 862   }
 863   if (delta >= 0 && rect == expanded_starting_rect) {
 864     // The starting rect already covers the entire bounding_rect and isn't too
 865     // large for the target_area.
 866     if (cache)
 867       cache->previous_result = rect;
 868     return rect;
 869   }
 870
 871   // Continue to expand/shrink rect to let it cover target_area.
 872
 873   // These values will be updated by the loop and uses as the output.
 874   int origin_x = rect.x();
 875   int origin_y = rect.y();
 876   int width = rect.width();
 877   int height = rect.height();
 878
 879   // In the beginning we will consider 2 edges in each dimension.
 880   int num_y_edges = 2;
 881   int num_x_edges = 2;
 882
 883   // Create an event list.
 884   EdgeEvent events[] = {
 885     { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
 886     { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
 887     { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
 888     { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
 889   };
 890
 891   // Sort the events by distance (closest first).
 892   if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
 893   if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
 894   if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
 895   if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
 896   if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
 897
 898   for (int event_index = 0; event_index < 4; event_index++) {
 899     const EdgeEvent& event = events[event_index];
 900
 901     int delta = ComputeExpansionDelta(
 902         num_x_edges, num_y_edges, width, height, target_area);
 903
 904     // Clamp delta to our event distance.
 905     if (delta > event.distance)
 906       delta = event.distance;
 907
 908     // Adjust the edge count for this kind of edge.
 909     --*event.num_edges;
 910
 911     // Apply the delta to the edges and edge events.
 912     for (int i = event_index; i < 4; i++) {
 913       switch (events[i].edge) {
 914         case EdgeEvent::BOTTOM:
 915             origin_y -= delta;
 916             height += delta;
 917             break;
 918         case EdgeEvent::TOP:
 919             height += delta;
 920             break;
 921         case EdgeEvent::LEFT:
 922             origin_x -= delta;
 923             width += delta;
 924             break;
 925         case EdgeEvent::RIGHT:
 926             width += delta;
 927             break;
 928       }
 929       events[i].distance -= delta;
 930     }
 931
 932     // If our delta is less then our event distance, we're done.
 933     if (delta < event.distance)
 934       break;
 935   }
 936
 937   gfx::Rect result(origin_x, origin_y, width, height);
 938   if (cache)
 939     cache->previous_result = result;
 940   return result;
 941 }
 942
 943 void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
 944     TreePriority tree_priority) {
 945   if (eviction_tiles_cache_valid_ &&
 946       eviction_cache_tree_priority_ == tree_priority)
 947     return;
 948
 949   eviction_tiles_now_.clear();
 950   eviction_tiles_now_and_required_for_activation_.clear();
 951   eviction_tiles_soon_.clear();
 952   eviction_tiles_soon_and_required_for_activation_.clear();
 953   eviction_tiles_eventually_.clear();
 954   eviction_tiles_eventually_and_required_for_activation_.clear();
 955
 956   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 957     // TODO(vmpstr): This should update the priority if UpdateTilePriorities
 958     // changes not to do this.
 959     Tile* tile = it->second.get();
 960     const TilePriority& priority =
 961         tile->priority_for_tree_priority(tree_priority);
 962     switch (priority.priority_bin) {
 963       case TilePriority::EVENTUALLY:
 964         if (tile->required_for_activation())
 965           eviction_tiles_eventually_and_required_for_activation_.push_back(
 966               tile);
 967         else
 968           eviction_tiles_eventually_.push_back(tile);
 969         break;
 970       case TilePriority::SOON:
 971         if (tile->required_for_activation())
 972           eviction_tiles_soon_and_required_for_activation_.push_back(tile);
 973         else
 974           eviction_tiles_soon_.push_back(tile);
 975         break;
 976       case TilePriority::NOW:
 977         if (tile->required_for_activation())
 978           eviction_tiles_now_and_required_for_activation_.push_back(tile);
 979         else
 980           eviction_tiles_now_.push_back(tile);
 981         break;
 982     }
 983   }
 984
 985   // TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that
 986   // can be updated for each of the queues.
 987   TileEvictionOrder sort_order(tree_priority);
 988   std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order);
 989   std::sort(eviction_tiles_now_and_required_for_activation_.begin(),
 990             eviction_tiles_now_and_required_for_activation_.end(),
 991             sort_order);
 992   std::sort(
 993       eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order);
 994   std::sort(eviction_tiles_soon_and_required_for_activation_.begin(),
 995             eviction_tiles_soon_and_required_for_activation_.end(),
 996             sort_order);
 997   std::sort(eviction_tiles_eventually_.begin(),
 998             eviction_tiles_eventually_.end(),
 999             sort_order);
1000   std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(),
1001             eviction_tiles_eventually_and_required_for_activation_.end(),
1002             sort_order);
1003
1004   eviction_tiles_cache_valid_ = true;
1005   eviction_cache_tree_priority_ = tree_priority;
1006 }
1007
1008 const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles(
1009     TreePriority tree_priority,
1010     EvictionCategory category) {
1011   UpdateEvictionCacheIfNeeded(tree_priority);
1012   switch (category) {
1013     case EVENTUALLY:
1014       return &eviction_tiles_eventually_;
1015     case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
1016       return &eviction_tiles_eventually_and_required_for_activation_;
1017     case SOON:
1018       return &eviction_tiles_soon_;
1019     case SOON_AND_REQUIRED_FOR_ACTIVATION:
1020       return &eviction_tiles_soon_and_required_for_activation_;
1021     case NOW:
1022       return &eviction_tiles_now_;
1023     case NOW_AND_REQUIRED_FOR_ACTIVATION:
1024       return &eviction_tiles_now_and_required_for_activation_;
1025   }
1026   NOTREACHED();
1027   return &eviction_tiles_eventually_;
1028 }
1029
1030 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
1031     : tiling_(NULL), current_tile_(NULL) {}
1032
1033 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
1034     PictureLayerTiling* tiling,
1035     WhichTree tree)
1036     : tiling_(tiling), phase_(VISIBLE_RECT), tree_(tree), current_tile_(NULL) {
1037   if (!tiling_->has_visible_rect_tiles_) {
1038     AdvancePhase();
1039     return;
1040   }
1041
1042   visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
1043                                            tiling_->current_visible_rect_,
1044                                            false /* include_borders */);
1045   if (!visible_iterator_) {
1046     AdvancePhase();
1047     return;
1048   }
1049
1050   current_tile_ =
1051       tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y());
1052   if (!current_tile_ || !TileNeedsRaster(current_tile_))
1053     ++(*this);
1054 }
1055
1056 PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
1057
1058 void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() {
1059   DCHECK_LT(phase_, EVENTUALLY_RECT);
1060
1061   do {
1062     phase_ = static_cast<Phase>(phase_ + 1);
1063     switch (phase_) {
1064       case VISIBLE_RECT:
1065         NOTREACHED();
1066         return;
1067       case SKEWPORT_RECT:
1068         if (!tiling_->has_skewport_rect_tiles_)
1069           continue;
1070
1071         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
1072             &tiling_->tiling_data_,
1073             tiling_->current_skewport_rect_,
1074             tiling_->current_visible_rect_,
1075             tiling_->current_visible_rect_);
1076         break;
1077       case SOON_BORDER_RECT:
1078         if (!tiling_->has_soon_border_rect_tiles_)
1079           continue;
1080
1081         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
1082             &tiling_->tiling_data_,
1083             tiling_->current_soon_border_rect_,
1084             tiling_->current_skewport_rect_,
1085             tiling_->current_visible_rect_);
1086         break;
1087       case EVENTUALLY_RECT:
1088         if (!tiling_->has_eventually_rect_tiles_) {
1089           current_tile_ = NULL;
1090           return;
1091         }
1092
1093         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
1094             &tiling_->tiling_data_,
1095             tiling_->current_eventually_rect_,
1096             tiling_->current_skewport_rect_,
1097             tiling_->current_soon_border_rect_);
1098         break;
1099     }
1100
1101     while (spiral_iterator_) {
1102       current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(),
1103                                       spiral_iterator_.index_y());
1104       if (current_tile_ && TileNeedsRaster(current_tile_))
1105         break;
1106       ++spiral_iterator_;
1107     }
1108
1109     if (!spiral_iterator_ && phase_ == EVENTUALLY_RECT) {
1110       current_tile_ = NULL;
1111       break;
1112     }
1113   } while (!spiral_iterator_);
1114 }
1115
1116 PictureLayerTiling::TilingRasterTileIterator&
1117 PictureLayerTiling::TilingRasterTileIterator::
1118 operator++() {
1119   current_tile_ = NULL;
1120   while (!current_tile_ || !TileNeedsRaster(current_tile_)) {
1121     std::pair<int, int> next_index;
1122     switch (phase_) {
1123       case VISIBLE_RECT:
1124         ++visible_iterator_;
1125         if (!visible_iterator_) {
1126           AdvancePhase();
1127           return *this;
1128         }
1129         next_index = visible_iterator_.index();
1130         break;
1131       case SKEWPORT_RECT:
1132       case SOON_BORDER_RECT:
1133         ++spiral_iterator_;
1134         if (!spiral_iterator_) {
1135           AdvancePhase();
1136           return *this;
1137         }
1138         next_index = spiral_iterator_.index();
1139         break;
1140       case EVENTUALLY_RECT:
1141         ++spiral_iterator_;
1142         if (!spiral_iterator_) {
1143           current_tile_ = NULL;
1144           return *this;
1145         }
1146         next_index = spiral_iterator_.index();
1147         break;
1148     }
1149     current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
1150   }
1151   return *this;
1152 }
1153
1154 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
1155     : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
1156 }
1157
1158 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
1159     PictureLayerTiling* tiling,
1160     TreePriority tree_priority,
1161     EvictionCategory category)
1162     : eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)),
1163       // Note: initializing to "0 - 1" works as overflow is well defined for
1164       // unsigned integers.
1165       current_eviction_tiles_index_(static_cast<size_t>(0) - 1) {
1166   DCHECK(eviction_tiles_);
1167   ++(*this);
1168 }
1169
1170 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
1171 }
1172
1173 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
1174   return eviction_tiles_ &&
1175          current_eviction_tiles_index_ != eviction_tiles_->size();
1176 }
1177
1178 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
1179   DCHECK(*this);
1180   return (*eviction_tiles_)[current_eviction_tiles_index_];
1181 }
1182
1183 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
1184   DCHECK(*this);
1185   return (*eviction_tiles_)[current_eviction_tiles_index_];
1186 }
1187
1188 PictureLayerTiling::TilingEvictionTileIterator&
1189 PictureLayerTiling::TilingEvictionTileIterator::
1190 operator++() {
1191   DCHECK(*this);
1192   do {
1193     ++current_eviction_tiles_index_;
1194   } while (current_eviction_tiles_index_ != eviction_tiles_->size() &&
1195            !(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources());
1196
1197   return *this;
1198 }
1199
1200 }  // namespace cc