cc/resources/tiling_set_eviction_queue.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef CC_RESOURCES_TILING_SET_EVICTION_QUEUE_H_
   6 #define CC_RESOURCES_TILING_SET_EVICTION_QUEUE_H_
   7
   8 #include <vector>
   9
  10 #include "cc/base/cc_export.h"
  11 #include "cc/resources/picture_layer_tiling_set.h"
  12
  13 namespace cc {
  14
  15 // This eviction queue returned tiles from all tilings in a tiling set in
  16 // the order in which the tiles should be evicted. It can be thought of as the
  17 // following:
  18 //  for all phases:
  19 //    for all ordered tilings:
  20 //      yield the next tile for the given phase from the given tiling
  21 //
  22 // Phases are the following (in order in which they are processed):
  23 // EVENTUALLY_RECT - Tiles in the eventually region of the tiling.
  24 // SOON_BORDER_RECT - Tiles in the prepainting skirt of the tiling.
  25 // SKEWPORT_RECT - Tiles in the skewport of the tiling.
  26 // PENDING_VISIBLE_RECT - Tiles that will be visible upon activation, not
  27 //     required for activation.
  28 // PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION - Tiles that will be visible
  29 //     upon activation, required for activation.
  30 // VISIBLE_RECT_OCCLUDED - Occluded, not required for activation, visible tiles.
  31 // VISIBLE_RECT_UNOCCLUDED - Unoccluded, not required for activation, visible
  32 //     tiles.
  33 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED - Occluded, but required for
  34 //     activation, visible tiles. This can happen when an active tree tile is
  35 //     occluded, but is not occluded on the pending tree (and is required for
  36 //     activation).
  37 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED - Unoccluded, required for
  38 //     activation, tiles.
  39 //
  40 // The tilings are ordered as follows. Suppose we have tilings with the scales
  41 // below:
  42 // 2.0   1.5   1.0(HR)   0.8   0.5   0.25(LR)   0.2   0.1
  43 // With HR referring to high res tiling and LR referring to low res tiling,
  44 // then tilings are processed in this order:
  45 // 2.0   1.5   0.1   0.2   0.5   0.8   0.25(LR)   1.0(HR).
  46 //
  47 // To put it differently:
  48 //  1. Process the highest scale tiling down to, but not including, high res
  49 //     tiling.
  50 //  2. Process the lowest scale tiling up to, but not including, the low res
  51 //     tiling. In cases without a low res tiling, this is an empty set.
  52 //  3. Process low res tiling up to high res tiling, including neither high
  53 //     nor low res tilings. In cases without a low res tiling, this set
  54 //     includes all tilings with a lower scale than the high res tiling.
  55 //  4. Process the low res tiling.
  56 //  5. Process the high res tiling.
  57 //
  58 // Additional notes:
  59 // Since eventually the tiles are considered to have the priority which is the
  60 // higher of the two trees, we might visit a tile that should actually be
  61 // returned by its twin. In those situations, the tiles are not returned. That
  62 // is, since the twin has higher priority, it should return it when it gets to
  63 // it. This ensures that we don't block raster because we've returned a tile
  64 // with low priority on one tree, but high combined priority.
  65 class CC_EXPORT TilingSetEvictionQueue {
  66  public:
  67   explicit TilingSetEvictionQueue(PictureLayerTilingSet* tiling_set);
  68   ~TilingSetEvictionQueue();
  69
  70   Tile* Top();
  71   const Tile* Top() const;
  72   void Pop();
  73   bool IsEmpty() const;
  74
  75  private:
  76   enum Phase {
  77     EVENTUALLY_RECT,
  78     SOON_BORDER_RECT,
  79     SKEWPORT_RECT,
  80     PENDING_VISIBLE_RECT,
  81     PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION,
  82     VISIBLE_RECT_OCCLUDED,
  83     VISIBLE_RECT_UNOCCLUDED,
  84     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED,
  85     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED
  86   };
  87
  88   void GenerateTilingOrder(PictureLayerTilingSet* tiling_set);
  89
  90   // Helper base class for individual region iterators.
  91   class EvictionRectIterator {
  92    public:
  93     EvictionRectIterator();
  94     EvictionRectIterator(std::vector<PictureLayerTiling*>* tilings,
  95                          WhichTree tree,
  96                          bool skip_pending_visible_rect);
  97
  98     bool done() const { return !tile_; }
  99     Tile* operator*() const { return tile_; }
 100
 101    protected:
 102     ~EvictionRectIterator() = default;
 103
 104     template <typename TilingIteratorType>
 105     bool AdvanceToNextTile(TilingIteratorType* iterator);
 106     template <typename TilingIteratorType>
 107     bool GetFirstTileAndCheckIfValid(TilingIteratorType* iterator);
 108
 109     Tile* tile_;
 110     std::vector<PictureLayerTiling*>* tilings_;
 111     WhichTree tree_;
 112     bool skip_pending_visible_rect_;
 113     size_t tiling_index_;
 114   };
 115
 116   class PendingVisibleTilingIterator : public EvictionRectIterator {
 117    public:
 118     PendingVisibleTilingIterator() = default;
 119     PendingVisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 120                                  WhichTree tree,
 121                                  bool return_required_for_activation_tiles);
 122
 123     PendingVisibleTilingIterator& operator++();
 124
 125    private:
 126     bool TileMatchesRequiredFlags(const Tile* tile) const;
 127
 128     TilingData::DifferenceIterator iterator_;
 129     bool return_required_for_activation_tiles_;
 130   };
 131
 132   class VisibleTilingIterator : public EvictionRectIterator {
 133    public:
 134     VisibleTilingIterator() = default;
 135     VisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 136                           WhichTree tree,
 137                           bool return_occluded_tiles,
 138                           bool return_required_for_activation_tiles);
 139
 140     VisibleTilingIterator& operator++();
 141
 142    private:
 143     bool TileMatchesRequiredFlags(const Tile* tile) const;
 144
 145     TilingData::Iterator iterator_;
 146     bool return_occluded_tiles_;
 147     bool return_required_for_activation_tiles_;
 148   };
 149
 150   class SkewportTilingIterator : public EvictionRectIterator {
 151    public:
 152     SkewportTilingIterator() = default;
 153     SkewportTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 154                            WhichTree tree);
 155
 156     SkewportTilingIterator& operator++();
 157
 158    private:
 159     TilingData::ReverseSpiralDifferenceIterator iterator_;
 160   };
 161
 162   class SoonBorderTilingIterator : public EvictionRectIterator {
 163    public:
 164     SoonBorderTilingIterator() = default;
 165     SoonBorderTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 166                              WhichTree tree);
 167
 168     SoonBorderTilingIterator& operator++();
 169
 170    private:
 171     TilingData::ReverseSpiralDifferenceIterator iterator_;
 172   };
 173
 174   class EventuallyTilingIterator : public EvictionRectIterator {
 175    public:
 176     EventuallyTilingIterator() = default;
 177     EventuallyTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 178                              WhichTree tree);
 179
 180     EventuallyTilingIterator& operator++();
 181
 182    private:
 183     TilingData::ReverseSpiralDifferenceIterator iterator_;
 184   };
 185
 186   void AdvancePhase();
 187
 188   WhichTree tree_;
 189   Phase phase_;
 190   Tile* current_tile_;
 191   std::vector<PictureLayerTiling*> tilings_;
 192
 193   EventuallyTilingIterator eventually_iterator_;
 194   SoonBorderTilingIterator soon_iterator_;
 195   SkewportTilingIterator skewport_iterator_;
 196   PendingVisibleTilingIterator pending_visible_iterator_;
 197   VisibleTilingIterator visible_iterator_;
 198 };
 199
 200 }  // namespace cc
 201
 202 #endif  // CC_RESOURCES_TILING_SET_EVICTION_QUEUE_H_