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 // VISIBLE_RECT_OCCLUDED - Occluded, not required for activation, visible tiles.
  27 // VISIBLE_RECT_UNOCCLUDED - Unoccluded, not required for activation, visible
  28 //     tiles.
  29 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED - Occluded, but required for
  30 //     activation, visible tiles. This can happen when an active tree tile is
  31 //     occluded, but is not occluded on the pending tree (and is required for
  32 //     activation).
  33 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED - Unoccluded, required for
  34 //     activation, tiles.
  35 //
  36 // The tilings are ordered as follows. Suppose we have tilings with the scales
  37 // below:
  38 // 2.0   1.5   1.0(HR)   0.8   0.5   0.25(LR)   0.2   0.1
  39 // With HR referring to high res tiling and LR referring to low res tiling,
  40 // then tilings are processed in this order:
  41 // 2.0   1.5   0.1   0.2   0.5   0.8   0.25(LR)   1.0(HR).
  42 //
  43 // To put it differently:
  44 //  1. Process the highest scale tiling down to, but not including, high res
  45 //     tiling.
  46 //  2. Process the lowest scale tiling up to, but not including, the low res
  47 //     tiling. In cases without a low res tiling, this is an empty set.
  48 //  3. Process low res tiling up to high res tiling, including neither high
  49 //     nor low res tilings. In cases without a low res tiling, this set
  50 //     includes all tilings with a lower scale than the high res tiling.
  51 //  4. Process the low res tiling.
  52 //  5. Process the high res tiling.
  53 //
  54 // Additional notes:
  55 // Since eventually the tiles are considered to have the priority which is the
  56 // higher of the two trees, we might visit a tile that should actually be
  57 // returned by its twin. In those situations, the tiles are not returned. That
  58 // is, since the twin has higher priority, it should return it when it gets to
  59 // it. This ensures that we don't block raster because we've returned a tile
  60 // with low priority on one tree, but high combined priority.
  61 class CC_EXPORT TilingSetEvictionQueue {
  62  public:
  63   TilingSetEvictionQueue(PictureLayerTilingSet* tiling_set,
  64                          bool skip_shared_out_of_order_tiles);
  65   ~TilingSetEvictionQueue();
  66
  67   Tile* Top();
  68   const Tile* Top() const;
  69   void Pop();
  70   bool IsEmpty() const;
  71
  72  private:
  73   enum Phase {
  74     EVENTUALLY_RECT,
  75     SOON_BORDER_RECT,
  76     SKEWPORT_RECT,
  77     VISIBLE_RECT_OCCLUDED,
  78     VISIBLE_RECT_UNOCCLUDED,
  79     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED,
  80     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED
  81   };
  82
  83   void GenerateTilingOrder(PictureLayerTilingSet* tiling_set);
  84
  85   // Helper base class for individual region iterators.
  86   class EvictionRectIterator {
  87    public:
  88     EvictionRectIterator();
  89     EvictionRectIterator(std::vector<PictureLayerTiling*>* tilings,
  90                          WhichTree tree,
  91                          bool skip_shared_out_of_order_tiles);
  92
  93     bool done() const { return !tile_; }
  94     Tile* operator*() const { return tile_; }
  95
  96    protected:
  97     ~EvictionRectIterator() = default;
  98
  99     template <typename TilingIteratorType>
 100     bool AdvanceToNextTile(TilingIteratorType* iterator);
 101     template <typename TilingIteratorType>
 102     bool GetFirstTileAndCheckIfValid(TilingIteratorType* iterator);
 103
 104     Tile* tile_;
 105     std::vector<PictureLayerTiling*>* tilings_;
 106     WhichTree tree_;
 107     bool skip_shared_out_of_order_tiles_;
 108     size_t tiling_index_;
 109   };
 110
 111   class VisibleTilingIterator : public EvictionRectIterator {
 112    public:
 113     VisibleTilingIterator() = default;
 114     VisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 115                           WhichTree tree,
 116                           bool skip_shared_out_of_order_tiles,
 117                           bool return_occluded_tiles,
 118                           bool return_required_for_activation_tiles);
 119
 120     VisibleTilingIterator& operator++();
 121
 122    private:
 123     bool TileMatchesRequiredFlags(const Tile* tile) const;
 124
 125     TilingData::Iterator iterator_;
 126     bool return_occluded_tiles_;
 127     bool return_required_for_activation_tiles_;
 128   };
 129
 130   class SkewportTilingIterator : public EvictionRectIterator {
 131    public:
 132     SkewportTilingIterator() = default;
 133     SkewportTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 134                            WhichTree tree,
 135                            bool skip_shared_out_of_order_tiles);
 136
 137     SkewportTilingIterator& operator++();
 138
 139    private:
 140     TilingData::ReverseSpiralDifferenceIterator iterator_;
 141   };
 142
 143   class SoonBorderTilingIterator : public EvictionRectIterator {
 144    public:
 145     SoonBorderTilingIterator() = default;
 146     SoonBorderTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 147                              WhichTree tree,
 148                              bool skip_shared_out_of_order_tiles);
 149
 150     SoonBorderTilingIterator& operator++();
 151
 152    private:
 153     TilingData::ReverseSpiralDifferenceIterator iterator_;
 154   };
 155
 156   class EventuallyTilingIterator : public EvictionRectIterator {
 157    public:
 158     EventuallyTilingIterator() = default;
 159     EventuallyTilingIterator(std::vector<PictureLayerTiling*>* tilings,
 160                              WhichTree tree,
 161                              bool skip_shared_out_of_order_tiles);
 162
 163     EventuallyTilingIterator& operator++();
 164
 165    private:
 166     TilingData::ReverseSpiralDifferenceIterator iterator_;
 167   };
 168
 169   void AdvancePhase();
 170
 171   WhichTree tree_;
 172   bool skip_shared_out_of_order_tiles_;
 173   Phase phase_;
 174   Tile* current_tile_;
 175   std::vector<PictureLayerTiling*> tilings_;
 176
 177   EventuallyTilingIterator eventually_iterator_;
 178   SoonBorderTilingIterator soon_iterator_;
 179   SkewportTilingIterator skewport_iterator_;
 180   VisibleTilingIterator visible_iterator_;
 181 };
 182
 183 }  // namespace cc
 184
 185 #endif  // CC_RESOURCES_TILING_SET_EVICTION_QUEUE_H_