12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Copyright 2012 The Chromium Authors. All rights reserved.
22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be
32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// found in the LICENSE file.
42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "cc/resources/picture_layer_tiling.h"
62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include <algorithm>
82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <cmath>
9ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include <limits>
10b86c3127098f5d0040c6c12ced76a2591343dc47vmpstr#include <set>
112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "base/debug/trace_event.h"
132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "cc/base/math_util.h"
14a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "cc/resources/tile.h"
15a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "cc/resources/tile_priority.h"
162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/point_conversions.h"
172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/rect_conversions.h"
182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/safe_integer_conversions.h"
192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "ui/gfx/size_conversions.h"
202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace cc {
22e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochnamespace {
23e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
24010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)const float kSoonBorderDistanceInScreenPixels = 312.f;
25010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)
26e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochclass TileEvictionOrder {
27e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch public:
28a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch  explicit TileEvictionOrder(TreePriority tree_priority)
29a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch      : tree_priority_(tree_priority) {}
30e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  ~TileEvictionOrder() {}
31e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
32e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  bool operator()(const Tile* a, const Tile* b) {
33a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch    const TilePriority& a_priority =
34a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch        a->priority_for_tree_priority(tree_priority_);
35a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch    const TilePriority& b_priority =
36a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch        b->priority_for_tree_priority(tree_priority_);
37e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
38c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch    if (a_priority.priority_bin == b_priority.priority_bin &&
39c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch        a->required_for_activation() != b->required_for_activation()) {
40c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch      return b->required_for_activation();
41c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch    }
42c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch    return b_priority.IsHigherPriorityThan(a_priority);
43e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  }
44e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
45e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch private:
46a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch  TreePriority tree_priority_;
47e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch};
48e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch}  // namespace
492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    float contents_scale,
525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Size& layer_bounds,
53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    PictureLayerTilingClient* client) {
54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  return make_scoped_ptr(new PictureLayerTiling(contents_scale,
55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                                layer_bounds,
56c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                                client));
572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::PictureLayerTiling(float contents_scale,
605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                                       const gfx::Size& layer_bounds,
61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                       PictureLayerTilingClient* client)
62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    : contents_scale_(contents_scale),
63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)      layer_bounds_(layer_bounds),
642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      resolution_(NON_IDEAL_RESOLUTION),
65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)      client_(client),
660529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch      tiling_data_(gfx::Size(), gfx::Rect(), true),
67e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch      last_impl_frame_time_in_seconds_(0.0),
68a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch      eviction_tiles_cache_valid_(false),
69a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch      eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  gfx::Size content_bounds =
71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)      gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
72c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
74b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)  DCHECK(!gfx::ToFlooredSize(
75b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)      gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
7690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)      "Tiling created with scale too small as contents become empty." <<
7790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)      " Layer bounds: " << layer_bounds.ToString() <<
7890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)      " Contents scale: " << contents_scale;
79b2df76ea8fec9e32f6f3718986dba0d95315b29cTorne (Richard Coles)
800529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  tiling_data_.SetTilingRect(gfx::Rect(content_bounds));
81c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  tiling_data_.SetMaxTextureSize(tile_size);
822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)PictureLayerTiling::~PictureLayerTiling() {
852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  client_ = client;
892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
910529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochgfx::Rect PictureLayerTiling::TilingRect() const {
920529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  return tiling_data_.tiling_rect();
932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
95a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)Tile* PictureLayerTiling::CreateTile(int i,
96a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)                                     int j,
97a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)                                     const PictureLayerTiling* twin_tiling) {
985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  TileMapKey key(i, j);
995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  DCHECK(tiles_.find(key) == tiles_.end());
100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
101c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
102c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  gfx::Rect tile_rect = paint_rect;
103c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  tile_rect.set_size(tiling_data_.max_texture_size());
104c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
105c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Check our twin for a valid tile.
1065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  if (twin_tiling &&
1075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      tiling_data_.max_texture_size() ==
1085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      twin_tiling->tiling_data_.max_texture_size()) {
1095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
1105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      gfx::Rect rect =
1115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)          gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
1125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      if (!client_->GetInvalidation()->Intersects(rect)) {
1135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        tiles_[key] = candidate_tile;
114a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        return candidate_tile;
1155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      }
116c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    }
117c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
118c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
119c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Create a new tile because our twin didn't have a valid one.
1202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
121868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  if (tile.get())
1225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    tiles_[key] = tile;
123a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  return tile.get();
1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
126eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochvoid PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
12790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
12823730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)  bool include_borders = true;
12923730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)  for (TilingData::Iterator iter(
13023730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)           &tiling_data_, live_tiles_rect_, include_borders);
13123730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)       iter;
132eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch       ++iter) {
1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMapKey key = iter.index();
1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMap::iterator find = tiles_.find(key);
1355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (find != tiles_.end())
136eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch      continue;
1375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    CreateTile(key.first, key.second, twin_tiling);
1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
1415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void PictureLayerTiling::SetLayerBounds(const gfx::Size& layer_bounds) {
142eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  if (layer_bounds_ == layer_bounds)
143eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    return;
144eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
145eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  DCHECK(!layer_bounds.IsEmpty());
146eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
147eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  gfx::Size old_layer_bounds = layer_bounds_;
148eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  layer_bounds_ = layer_bounds;
149eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  gfx::Size content_bounds =
150eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch      gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
151eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
152eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
153eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  if (tile_size != tiling_data_.max_texture_size()) {
1540529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch    tiling_data_.SetTilingRect(gfx::Rect(content_bounds));
155eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    tiling_data_.SetMaxTextureSize(tile_size);
156eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    Reset();
157eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    return;
158eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  }
159eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
160eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  // Any tiles outside our new bounds are invalid and should be dropped.
161eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  gfx::Rect bounded_live_tiles_rect(live_tiles_rect_);
162eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  bounded_live_tiles_rect.Intersect(gfx::Rect(content_bounds));
163eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  SetLiveTilesRect(bounded_live_tiles_rect);
1640529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  tiling_data_.SetTilingRect(gfx::Rect(content_bounds));
165eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
166eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  // Create tiles for newly exposed areas.
167eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  Region layer_region((gfx::Rect(layer_bounds_)));
168eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  layer_region.Subtract(gfx::Rect(old_layer_bounds));
169eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  Invalidate(layer_region);
170eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch}
171eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
172c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdochvoid PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) {
173c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch  DoInvalidate(layer_region, false /* recreate_tiles */);
174c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch}
175c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch
176eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochvoid PictureLayerTiling::Invalidate(const Region& layer_region) {
177c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch  DoInvalidate(layer_region, true /* recreate_tiles */);
178c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch}
179c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch
180c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdochvoid PictureLayerTiling::DoInvalidate(const Region& layer_region,
181c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch                                      bool recreate_tiles) {
1825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  std::vector<TileMapKey> new_tile_keys;
1830529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  gfx::Rect expanded_live_tiles_rect(
1840529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch      tiling_data_.ExpandRectToTileBoundsWithBorders(live_tiles_rect_));
185eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
186eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    gfx::Rect layer_rect = iter.rect();
187eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    gfx::Rect content_rect =
188eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch        gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
1890529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch    // Avoid needless work by not bothering to invalidate where there aren't
1900529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch    // tiles.
1910529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch    content_rect.Intersect(expanded_live_tiles_rect);
192eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    if (content_rect.IsEmpty())
193eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch      continue;
19423730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)    bool include_borders = true;
19523730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)    for (TilingData::Iterator iter(
19623730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)             &tiling_data_, content_rect, include_borders);
19723730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)         iter;
19823730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)         ++iter) {
1995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      TileMapKey key(iter.index());
2005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      TileMap::iterator find = tiles_.find(key);
2015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      if (find == tiles_.end())
2025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        continue;
2035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      tiles_.erase(find);
204c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch      if (recreate_tiles)
205c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch        new_tile_keys.push_back(key);
206eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch    }
207eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  }
208eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
209c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch  if (recreate_tiles) {
210c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch    const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
211c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch    for (size_t i = 0; i < new_tile_keys.size(); ++i)
212c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch      CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
213c5cede9ae108bb15f6b7a8aea21c7e1fefa2834cBen Murdoch  }
214eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch}
215eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
216c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::CoverageIterator::CoverageIterator()
2172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    : tiling_(NULL),
2182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      current_tile_(NULL),
2192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      tile_i_(0),
2202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      tile_j_(0),
2212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      left_(0),
2222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      top_(0),
2232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      right_(-1),
2242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      bottom_(-1) {
2252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
2262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
227c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::CoverageIterator::CoverageIterator(
228c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    const PictureLayerTiling* tiling,
229c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    float dest_scale,
2305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Rect& dest_rect)
2312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    : tiling_(tiling),
2322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      dest_rect_(dest_rect),
2332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      dest_to_content_scale_(0),
2342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      current_tile_(NULL),
2352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      tile_i_(0),
2362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      tile_j_(0),
2372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      left_(0),
2382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      top_(0),
2392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      right_(-1),
2405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      bottom_(-1) {
2412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  DCHECK(tiling_);
2422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (dest_rect_.IsEmpty())
2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return;
2442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
2462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::Rect content_rect =
24890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)      gfx::ScaleToEnclosingRect(dest_rect_,
24990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)                                dest_to_content_scale_,
25090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)                                dest_to_content_scale_);
2512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
2522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // check for non-intersection first.
2530529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  content_rect.Intersect(tiling_->TilingRect());
2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (content_rect.IsEmpty())
2552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return;
2562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
2582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
2592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
2602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      content_rect.right() - 1);
2612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
2622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      content_rect.bottom() - 1);
2632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  tile_i_ = left_ - 1;
2652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  tile_j_ = top_;
2662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  ++(*this);
2672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
2682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
269c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::CoverageIterator::~CoverageIterator() {
2702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
2712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
272c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::CoverageIterator&
273c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::CoverageIterator::operator++() {
2742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (tile_j_ > bottom_)
2752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return *this;
2762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  bool first_time = tile_i_ < left_;
2782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  bool new_row = false;
2792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  tile_i_++;
2802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (tile_i_ > right_) {
2812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    tile_i_ = left_;
2822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    tile_j_++;
2832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    new_row = true;
2842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    if (tile_j_ > bottom_) {
2852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      current_tile_ = NULL;
2862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      return *this;
2872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    }
2882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
2892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
2912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // Calculate the current geometry rect.  Due to floating point rounding
2932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // and ToEnclosingRect, tiles might overlap in destination space on the
2942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // edges.
2952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::Rect last_geometry_rect = current_geometry_rect_;
2962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
2972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
2982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
29990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)  current_geometry_rect_ =
30090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)      gfx::ScaleToEnclosingRect(content_rect,
30190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)                                1 / dest_to_content_scale_,
30290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)                                1 / dest_to_content_scale_);
3032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  current_geometry_rect_.Intersect(dest_rect_);
3052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (first_time)
3072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return *this;
3082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // Iteration happens left->right, top->bottom.  Running off the bottom-right
3102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // edge is handled by the intersection above with dest_rect_.  Here we make
3112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // sure that the new current geometry rect doesn't overlap with the last.
3122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int min_left;
3132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int min_top;
3142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (new_row) {
3152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    min_left = dest_rect_.x();
3162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    min_top = last_geometry_rect.bottom();
3172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  } else {
3182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    min_left = last_geometry_rect.right();
3192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    min_top = last_geometry_rect.y();
3202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
3212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int inset_left = std::max(0, min_left - current_geometry_rect_.x());
3232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int inset_top = std::max(0, min_top - current_geometry_rect_.y());
3242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
3252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (!new_row) {
3272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
3282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
3292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
3302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
3312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  return *this;
3332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
3342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
335c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
3362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  return current_geometry_rect_;
3372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
3382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
339c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)gfx::Rect
340c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
3412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
3422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  rect.set_size(tiling_->tiling_data_.max_texture_size());
3432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  return rect;
3442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
3452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
346c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
3472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::PointF tex_origin =
3482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
3492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // Convert from dest space => content space => texture space.
3512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::RectF texture_rect(current_geometry_rect_);
3522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  texture_rect.Scale(dest_to_content_scale_,
3532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)                     dest_to_content_scale_);
3540529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  texture_rect.Intersect(tiling_->TilingRect());
3550529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  if (texture_rect.IsEmpty())
3560529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch    return texture_rect;
3572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  texture_rect.Offset(-tex_origin.OffsetFromOrigin());
3582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
3592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  return texture_rect;
3602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
3612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
362c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
3632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  return tiling_->tiling_data_.max_texture_size();
3642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
3652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
366c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void PictureLayerTiling::Reset() {
367c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  live_tiles_rect_ = gfx::Rect();
3685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  tiles_.clear();
369c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)}
370c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
3715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)gfx::Rect PictureLayerTiling::ComputeSkewport(
372c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    double current_frame_time_in_seconds,
3735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Rect& visible_rect_in_content_space) const {
3745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  gfx::Rect skewport = visible_rect_in_content_space;
3755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  if (last_impl_frame_time_in_seconds_ == 0.0)
3765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    return skewport;
3775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
3785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  double time_delta =
3795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
3805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  if (time_delta == 0.0)
3815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    return skewport;
3825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
3835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  float skewport_target_time_in_seconds =
3845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      client_->GetSkewportTargetTimeInSeconds();
3855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  double extrapolation_multiplier =
3865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      skewport_target_time_in_seconds / time_delta;
3875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
3885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int old_x = last_visible_rect_in_content_space_.x();
3895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int old_y = last_visible_rect_in_content_space_.y();
3905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int old_right = last_visible_rect_in_content_space_.right();
3915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int old_bottom = last_visible_rect_in_content_space_.bottom();
3925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
3935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int new_x = visible_rect_in_content_space.x();
3945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int new_y = visible_rect_in_content_space.y();
3955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int new_right = visible_rect_in_content_space.right();
3965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int new_bottom = visible_rect_in_content_space.bottom();
3975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
3985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels();
399a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)
4005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // Compute the maximum skewport based on |skewport_limit|.
4015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  gfx::Rect max_skewport = skewport;
4025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  max_skewport.Inset(
4035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit);
4045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // Inset the skewport by the needed adjustment.
4065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  skewport.Inset(extrapolation_multiplier * (new_x - old_x),
4075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                 extrapolation_multiplier * (new_y - old_y),
4085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                 extrapolation_multiplier * (old_right - new_right),
4095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                 extrapolation_multiplier * (old_bottom - new_bottom));
4105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // Clip the skewport to |max_skewport|.
4125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  skewport.Intersect(max_skewport);
4135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // Finally, ensure that visible rect is contained in the skewport.
4155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  skewport.Union(visible_rect_in_content_space);
4165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  return skewport;
4175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}
4185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void PictureLayerTiling::UpdateTilePriorities(
4205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    WhichTree tree,
4215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Rect& visible_layer_rect,
4225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    float layer_contents_scale,
4235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    double current_frame_time_in_seconds) {
424c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
425c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    // This should never be zero for the purposes of has_ever_been_updated().
426c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    DCHECK_NE(current_frame_time_in_seconds, 0.0);
4272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return;
428c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
4295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  gfx::Rect visible_rect_in_content_space =
4315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
4325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4330529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  if (TilingRect().IsEmpty()) {
434c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
4355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    last_visible_rect_in_content_space_ = visible_rect_in_content_space;
4362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return;
437c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
4382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
4395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea();
4402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
4412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  gfx::Size tile_size = tiling_data_.max_texture_size();
4425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  int64 eventually_rect_area =
443c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)      max_tiles_for_interest_area * tile_size.width() * tile_size.height();
444c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
4455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
4465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                                       visible_rect_in_content_space);
4475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  DCHECK(skewport.Contains(visible_rect_in_content_space));
4485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  gfx::Rect eventually_rect =
4505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space,
4515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                                       eventually_rect_area,
4520529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch                                       TilingRect(),
4535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)                                       &expansion_cache_);
4545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4550529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  DCHECK(eventually_rect.IsEmpty() || TilingRect().Contains(eventually_rect));
4565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  SetLiveTilesRect(eventually_rect);
4585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
4605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  last_visible_rect_in_content_space_ = visible_rect_in_content_space;
4615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
462a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  current_visible_rect_in_content_space_ = visible_rect_in_content_space;
463a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  current_skewport_ = skewport;
464a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  current_eventually_rect_ = eventually_rect;
465e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  eviction_tiles_cache_valid_ = false;
466a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
4675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  TilePriority now_priority(resolution_, TilePriority::NOW, 0);
468ef8900b995d4dd406c0a62ebaf7d535b2b0809cbernstm@chromium.org  float content_to_screen_scale = layer_contents_scale / contents_scale_;
469a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
470a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  // Assign now priority to all visible tiles.
47123730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)  bool include_borders = true;
47223730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)  for (TilingData::Iterator iter(
47323730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)           &tiling_data_, visible_rect_in_content_space, include_borders);
4745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)       iter;
4755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)       ++iter) {
4765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMap::iterator find = tiles_.find(iter.index());
4775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (find == tiles_.end())
4785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      continue;
4795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    Tile* tile = find->second.get();
4805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
4815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    tile->SetPriority(tree, now_priority);
4822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
4832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
484a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  // Assign soon priority to skewport tiles.
4855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (TilingData::DifferenceIterator iter(
4865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)           &tiling_data_, skewport, visible_rect_in_content_space);
4875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)       iter;
4885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)       ++iter) {
4895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMap::iterator find = tiles_.find(iter.index());
4905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (find == tiles_.end())
4915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      continue;
4925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    Tile* tile = find->second.get();
4932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
4945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    gfx::Rect tile_bounds =
4955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        tiling_data_.TileBounds(iter.index_x(), iter.index_y());
496ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch
4975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    float distance_to_visible =
4985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
4995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        content_to_screen_scale;
5002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
5015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible);
5025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    tile->SetPriority(tree, priority);
5032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
5042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
505a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  // Assign eventually priority to interest rect tiles.
5065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (TilingData::DifferenceIterator iter(
5075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)           &tiling_data_, eventually_rect, skewport);
5085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)       iter;
5095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)       ++iter) {
5105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMap::iterator find = tiles_.find(iter.index());
5115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    if (find == tiles_.end())
5125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      continue;
5135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    Tile* tile = find->second.get();
5145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
5155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    gfx::Rect tile_bounds =
5165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        tiling_data_.TileBounds(iter.index_x(), iter.index_y());
5175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
5185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    float distance_to_visible =
5195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
5205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        content_to_screen_scale;
5215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TilePriority priority(
5225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)        resolution_, TilePriority::EVENTUALLY, distance_to_visible);
5235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    tile->SetPriority(tree, priority);
5245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  }
525010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)
526010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)  // Upgrade the priority on border tiles to be SOON.
527010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)  current_soon_border_rect_ = visible_rect_in_content_space;
528010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)  float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale;
529010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)  current_soon_border_rect_.Inset(-border, -border, -border, -border);
530010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)  for (TilingData::DifferenceIterator iter(
531010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)           &tiling_data_, current_soon_border_rect_, skewport);
532010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)       iter;
533010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)       ++iter) {
534010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)    TileMap::iterator find = tiles_.find(iter.index());
535010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)    if (find == tiles_.end())
536010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)      continue;
537010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)    Tile* tile = find->second.get();
538010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)
539010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)    TilePriority priority(resolution_,
540010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)                          TilePriority::SOON,
541010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)                          tile->priority(tree).distance_to_visible);
542010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)    tile->SetPriority(tree, priority);
543010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)  }
544c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)}
545c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
546c2bc7c74934f64e7d2125415f27a3803a4879085vmpstrvoid PictureLayerTiling::RemoveTileAt(int i, int j) {
547c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr  TileMapKey key(i, j);
548c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr  TileMap::iterator found = tiles_.find(key);
549c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr  if (found == tiles_.end())
550c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr    return;
551c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr  tiles_.erase(found);
552c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr}
553c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr
5545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void PictureLayerTiling::SetLiveTilesRect(
5555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Rect& new_live_tiles_rect) {
556c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  DCHECK(new_live_tiles_rect.IsEmpty() ||
5570529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch         TilingRect().Contains(new_live_tiles_rect));
558c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  if (live_tiles_rect_ == new_live_tiles_rect)
559c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    return;
560c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
561c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Iterate to delete all tiles outside of our new live_tiles rect.
562c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr  PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
563c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  for (TilingData::DifferenceIterator iter(&tiling_data_,
564c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                           live_tiles_rect_,
565c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                           new_live_tiles_rect);
566c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)       iter;
567c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)       ++iter) {
5685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMapKey key(iter.index());
5695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMap::iterator found = tiles_.find(key);
570c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    // If the tile was outside of the recorded region, it won't exist even
571c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    // though it was in the live rect.
572c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr    if (found != tiles_.end()) {
5735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)      tiles_.erase(found);
574c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr      if (recycled_twin)
575c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr        recycled_twin->RemoveTileAt(iter.index_x(), iter.index_y());
576c2bc7c74934f64e7d2125415f27a3803a4879085vmpstr    }
577c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
578c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
57990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
58090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)
581c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Iterate to allocate new tiles for all regions with newly exposed area.
582c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  for (TilingData::DifferenceIterator iter(&tiling_data_,
583c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                           new_live_tiles_rect,
584c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                                           live_tiles_rect_);
585c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)       iter;
586c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)       ++iter) {
5875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    TileMapKey key(iter.index());
5885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    CreateTile(key.first, key.second, twin_tiling);
589c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
590c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
591c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  live_tiles_rect_ = new_live_tiles_rect;
5922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
5932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
5944e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)void PictureLayerTiling::DidBecomeRecycled() {
5954e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)  // DidBecomeActive below will set the active priority for tiles that are
5964e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)  // still in the tree. Calling this first on an active tiling that is becoming
5974e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)  // recycled takes care of tiles that are no longer in the active tree (eg.
5984e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)  // due to a pending invalidation).
5995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
6005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    it->second->SetPriority(ACTIVE_TREE, TilePriority());
6014e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)  }
6024e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)}
6034e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)
6042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void PictureLayerTiling::DidBecomeActive() {
6055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
6065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
6075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    it->second->SetPriority(PENDING_TREE, TilePriority());
6085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
6095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    // Tile holds a ref onto a picture pile. If the tile never gets invalidated
6105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    // and recreated, then that picture pile ref could exist indefinitely.  To
6115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    // prevent this, ask the client to update the pile to its own ref.  This
6125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    // will cause PicturePileImpls and their clones to get deleted once the
6135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    // corresponding PictureLayerImpl and any in flight raster jobs go out of
6145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    // scope.
6155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    client_->UpdatePile(it->second.get());
6162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
6172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
6182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
619eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochvoid PictureLayerTiling::UpdateTilesToCurrentPile() {
6205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
6215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    client_->UpdatePile(it->second.get());
622eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch  }
623eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch}
624eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch
625b86c3127098f5d0040c6c12ced76a2591343dc47vmpstrvoid PictureLayerTiling::GetAllTilesForTracing(
626b86c3127098f5d0040c6c12ced76a2591343dc47vmpstr    std::set<const Tile*>* tiles) const {
627b86c3127098f5d0040c6c12ced76a2591343dc47vmpstr  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
628b86c3127098f5d0040c6c12ced76a2591343dc47vmpstr    tiles->insert(it->second.get());
629b86c3127098f5d0040c6c12ced76a2591343dc47vmpstr}
630b86c3127098f5d0040c6c12ced76a2591343dc47vmpstr
6312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
6322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
6335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  state->SetInteger("num_tiles", tiles_.size());
6342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  state->SetDouble("content_scale", contents_scale_);
6350529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch  state->Set("tiling_rect", MathUtil::AsValue(TilingRect()).release());
6362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  return state.PassAs<base::Value>();
6372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
6382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
63990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
64090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)  size_t amount = 0;
6415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
6425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const Tile* tile = it->second.get();
6435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    amount += tile->GPUMemoryUsageInBytes();
64490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)  }
64590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)  return amount;
64690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)}
64790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)
6488bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)PictureLayerTiling::RectExpansionCache::RectExpansionCache()
6498bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  : previous_target(0) {
6508bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)}
6518bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)
652c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace {
653c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
6542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This struct represents an event at which the expending rect intersects
6552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// one of its boundaries.  4 intersection events will occur during expansion.
6562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct EdgeEvent {
6572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  enum { BOTTOM, TOP, LEFT, RIGHT } edge;
6582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int* num_edges;
6592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int distance;
6602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)};
6612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
662c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Compute the delta to expand from edges to cover target_area.
663c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
664c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                          int width, int height,
665c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)                          int64 target_area) {
666c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Compute coefficients for the quadratic equation:
667c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  //   a*x^2 + b*x + c = 0
668c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  int a = num_y_edges * num_x_edges;
669c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  int b = num_y_edges * width + num_x_edges * height;
670c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  int64 c = static_cast<int64>(width) * height - target_area;
671c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
672c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Compute the delta for our edges using the quadratic equation.
673c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  return a == 0 ? -c / b :
674c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)     (-b + static_cast<int>(
675c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)         std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
676c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)}
677c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
678c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)}  // namespace
679c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
6802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
6815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Rect& starting_rect,
6822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    int64 target_area,
6835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    const gfx::Rect& bounding_rect,
6848bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    RectExpansionCache* cache) {
685c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  if (starting_rect.IsEmpty())
686c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    return starting_rect;
6872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
6888bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  if (cache &&
6898bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)      cache->previous_start == starting_rect &&
6908bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)      cache->previous_bounds == bounding_rect &&
6918bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)      cache->previous_target == target_area)
6928bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    return cache->previous_result;
6938bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)
6948bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  if (cache) {
6958bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    cache->previous_start = starting_rect;
6968bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    cache->previous_bounds = bounding_rect;
6978bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    cache->previous_target = target_area;
6988bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  }
6998bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)
700c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  DCHECK(!bounding_rect.IsEmpty());
701c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  DCHECK_GT(target_area, 0);
702c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
703c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Expand the starting rect to cover target_area, if it is smaller than it.
704c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  int delta = ComputeExpansionDelta(
705c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)      2, 2, starting_rect.width(), starting_rect.height(), target_area);
706c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  gfx::Rect expanded_starting_rect = starting_rect;
707c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  if (delta > 0)
708c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    expanded_starting_rect.Inset(-delta, -delta);
709c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
710c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
711c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  if (rect.IsEmpty()) {
712c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    // The starting_rect and bounding_rect are far away.
7138bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    if (cache)
7148bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)      cache->previous_result = rect;
7152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    return rect;
716c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
717c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  if (delta >= 0 && rect == expanded_starting_rect) {
718c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    // The starting rect already covers the entire bounding_rect and isn't too
719c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    // large for the target_area.
7208bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    if (cache)
7218bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)      cache->previous_result = rect;
722c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    return rect;
723c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  }
724c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)
725c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)  // Continue to expand/shrink rect to let it cover target_area.
7262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // These values will be updated by the loop and uses as the output.
7282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int origin_x = rect.x();
7292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int origin_y = rect.y();
7302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int width = rect.width();
7312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int height = rect.height();
7322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // In the beginning we will consider 2 edges in each dimension.
7342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int num_y_edges = 2;
7352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  int num_x_edges = 2;
7362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // Create an event list.
7382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  EdgeEvent events[] = {
7392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
7402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
7412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
7422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
7432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  };
7442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  // Sort the events by distance (closest first).
7462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
7472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
7482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
7492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
7502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
7512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  for (int event_index = 0; event_index < 4; event_index++) {
7532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    const EdgeEvent& event = events[event_index];
7542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
755c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)    int delta = ComputeExpansionDelta(
756c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)        num_x_edges, num_y_edges, width, height, target_area);
7572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    // Clamp delta to our event distance.
7592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    if (delta > event.distance)
7602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      delta = event.distance;
7612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    // Adjust the edge count for this kind of edge.
7632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    --*event.num_edges;
7642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    // Apply the delta to the edges and edge events.
7662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    for (int i = event_index; i < 4; i++) {
7672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      switch (events[i].edge) {
7682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)        case EdgeEvent::BOTTOM:
7692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            origin_y -= delta;
7702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            height += delta;
7712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            break;
7722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)        case EdgeEvent::TOP:
7732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            height += delta;
7742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            break;
7752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)        case EdgeEvent::LEFT:
7762a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            origin_x -= delta;
7772a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            width += delta;
7782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            break;
7792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)        case EdgeEvent::RIGHT:
7802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            width += delta;
7812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)            break;
7822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      }
7832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      events[i].distance -= delta;
7842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    }
7852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    // If our delta is less then our event distance, we're done.
7872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)    if (delta < event.distance)
7882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)      break;
7892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)  }
7902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
7918bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  gfx::Rect result(origin_x, origin_y, width, height);
7928bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  if (cache)
7938bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    cache->previous_result = result;
7948bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  return result;
7952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}
7962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)
797a02191e04bc25c4935f804f2c080ae28663d096dBen Murdochvoid PictureLayerTiling::UpdateEvictionCacheIfNeeded(
798a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch    TreePriority tree_priority) {
799a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch  if (eviction_tiles_cache_valid_ &&
800a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch      eviction_cache_tree_priority_ == tree_priority)
801e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    return;
802e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
803e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  eviction_tiles_cache_.clear();
804e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  eviction_tiles_cache_.reserve(tiles_.size());
805e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
806e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    // TODO(vmpstr): This should update the priority if UpdateTilePriorities
807e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    // changes not to do this.
808e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    eviction_tiles_cache_.push_back(it->second);
809e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  }
810e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
811e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  std::sort(eviction_tiles_cache_.begin(),
812e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch            eviction_tiles_cache_.end(),
813a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch            TileEvictionOrder(tree_priority));
814e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  eviction_tiles_cache_valid_ = true;
815a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch  eviction_cache_tree_priority_ = tree_priority;
816e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch}
817e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
818a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
819a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    : tiling_(NULL), current_tile_(NULL) {}
820a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
821a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
822a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    PictureLayerTiling* tiling,
823a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    WhichTree tree)
824a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    : tiling_(tiling),
825e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch      type_(TilePriority::NOW),
826a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      visible_rect_in_content_space_(
827a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          tiling_->current_visible_rect_in_content_space_),
828a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      skewport_in_content_space_(tiling_->current_skewport_),
829a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      eventually_rect_in_content_space_(tiling_->current_eventually_rect_),
830010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)      soon_border_rect_in_content_space_(tiling_->current_soon_border_rect_),
831a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      tree_(tree),
832a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      current_tile_(NULL),
83323730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)      visible_iterator_(&tiling->tiling_data_,
83423730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)                        visible_rect_in_content_space_,
83523730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles)                        true /* include_borders */),
836a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      spiral_iterator_(&tiling->tiling_data_,
837a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)                       skewport_in_content_space_,
838a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)                       visible_rect_in_content_space_,
839010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)                       visible_rect_in_content_space_),
840010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)      skewport_processed_(false) {
841a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  if (!visible_iterator_) {
842a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    AdvancePhase();
843a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    return;
844a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  }
845a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
846a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  current_tile_ =
847a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y());
848a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  if (!current_tile_ || !TileNeedsRaster(current_tile_))
849a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    ++(*this);
850a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}
851a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
852a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
853a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
854a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() {
855e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  DCHECK_LT(type_, TilePriority::EVENTUALLY);
856a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
857a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  do {
858e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    type_ = static_cast<TilePriority::PriorityBin>(type_ + 1);
859e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    if (type_ == TilePriority::EVENTUALLY) {
860a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      spiral_iterator_ = TilingData::SpiralDifferenceIterator(
861a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          &tiling_->tiling_data_,
862a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          eventually_rect_in_content_space_,
863a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          skewport_in_content_space_,
864a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          visible_rect_in_content_space_);
865a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    }
866a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
867a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    while (spiral_iterator_) {
868a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(),
869a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)                                      spiral_iterator_.index_y());
870a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      if (current_tile_ && TileNeedsRaster(current_tile_))
871a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        break;
872a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      ++spiral_iterator_;
873a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    }
874a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
875cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)    if (!spiral_iterator_ && type_ == TilePriority::EVENTUALLY) {
876cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)      current_tile_ = NULL;
877a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)      break;
878cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)    }
879a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  } while (!spiral_iterator_);
880a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}
881a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
882a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)PictureLayerTiling::TilingRasterTileIterator&
883a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)PictureLayerTiling::TilingRasterTileIterator::
884a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)operator++() {
885a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  current_tile_ = NULL;
886a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  while (!current_tile_ || !TileNeedsRaster(current_tile_)) {
887a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    std::pair<int, int> next_index;
888a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    switch (type_) {
889e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch      case TilePriority::NOW:
890a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        ++visible_iterator_;
891a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        if (!visible_iterator_) {
892a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          AdvancePhase();
893a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          return *this;
894a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        }
895a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        next_index = visible_iterator_.index();
896a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        break;
897e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch      case TilePriority::SOON:
898a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        ++spiral_iterator_;
899a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        if (!spiral_iterator_) {
900010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)          if (skewport_processed_) {
901010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)            AdvancePhase();
902010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)            return *this;
903010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)          }
904010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)          skewport_processed_ = true;
905010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)          spiral_iterator_ = TilingData::SpiralDifferenceIterator(
906010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)              &tiling_->tiling_data_,
907010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)              soon_border_rect_in_content_space_,
908010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)              skewport_in_content_space_,
909010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)              visible_rect_in_content_space_);
910010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)          if (!spiral_iterator_) {
911010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)            AdvancePhase();
912010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)            return *this;
913010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles)          }
914a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        }
915a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        next_index = spiral_iterator_.index();
916a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        break;
917e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch      case TilePriority::EVENTUALLY:
918a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        ++spiral_iterator_;
919cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)        if (!spiral_iterator_) {
920cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)          current_tile_ = NULL;
921a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)          return *this;
922cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)        }
923a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        next_index = spiral_iterator_.index();
924a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)        break;
925a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    }
926a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)    current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
927a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  }
928a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)  return *this;
929a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)}
930a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)
931e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochPictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
932e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    : is_valid_(false), tiling_(NULL) {}
933e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
934e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochPictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
935e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    PictureLayerTiling* tiling,
936a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch    TreePriority tree_priority)
937a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch    : is_valid_(false), tiling_(tiling), tree_priority_(tree_priority) {}
938e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
939e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochPictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {}
940e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
941e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochPictureLayerTiling::TilingEvictionTileIterator::operator bool() {
942e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  if (!IsValid())
943e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    Initialize();
944e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
945e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  return IsValid() && tile_iterator_ != tiling_->eviction_tiles_cache_.end();
946e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch}
947e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
948e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochTile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
949e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  if (!IsValid())
950e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    Initialize();
951e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
952e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  DCHECK(*this);
953e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  return *tile_iterator_;
954e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch}
955e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
956e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochPictureLayerTiling::TilingEvictionTileIterator&
957e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen MurdochPictureLayerTiling::TilingEvictionTileIterator::
958e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochoperator++() {
959e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  DCHECK(*this);
960e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  do {
961e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    ++tile_iterator_;
962e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  } while (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
963e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch           (!(*tile_iterator_)->HasResources()));
964e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
965e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  return *this;
966e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch}
967e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
968e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochvoid PictureLayerTiling::TilingEvictionTileIterator::Initialize() {
969e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  if (!tiling_)
970e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    return;
971e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
972a02191e04bc25c4935f804f2c080ae28663d096dBen Murdoch  tiling_->UpdateEvictionCacheIfNeeded(tree_priority_);
973e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  tile_iterator_ = tiling_->eviction_tiles_cache_.begin();
974e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  is_valid_ = true;
975e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  if (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
976e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch      !(*tile_iterator_)->HasResources()) {
977e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch    ++(*this);
978e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch  }
979e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch}
980e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch
9812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}  // namespace cc
982