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