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