cc/tiles/tiling_set_eviction_queue.h - chromium/src - Git at Google

 // Copyright 2014 The Chromium Authors
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #ifndef CC_TILES_TILING_SET_EVICTION_QUEUE_H_
 #define CC_TILES_TILING_SET_EVICTION_QUEUE_H_

 #include <stddef.h>

 #include <vector>

 #include "base/memory/raw_ptr_exclusion.h"
 #include "cc/cc_export.h"
 #include "cc/tiles/picture_layer_tiling_set.h"
 #include "cc/tiles/prioritized_tile.h"

 namespace cc {

 // This eviction queue returned tiles from all tilings in a tiling set in
 // the order in which the tiles should be evicted. It can be thought of as the
 // following:
 //  for all phases:
 //    for all ordered tilings:
 //      yield the next tile for the given phase from the given tiling
 //
 // Phases are the following (in order in which they are processed):
 // EVENTUALLY_RECT - Tiles in the eventually region of the tiling.
 // SOON_BORDER_RECT - Tiles in the prepainting skirt of the tiling.
 // SKEWPORT_RECT - Tiles in the skewport of the tiling.
 // PENDING_VISIBLE_RECT - Tiles that will be visible upon activation, not
 //     required for activation.
 // PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION - Tiles that will be visible
 //     upon activation, required for activation.
 // VISIBLE_RECT_OCCLUDED - Occluded, not required for activation, visible tiles.
 // VISIBLE_RECT_UNOCCLUDED - Unoccluded, not required for activation, visible
 //     tiles.
 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED - Occluded, but required for
 //     activation, visible tiles. This can happen when an active tree tile is
 //     occluded, but is not occluded on the pending tree (and is required for
 //     activation).
 // VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED - Unoccluded, required for
 //     activation, tiles.
 //
 // The tilings are ordered as follows. Suppose we have tilings with the scales
 // below:
 // 2.0   1.5   1.0(HR)   0.8   0.5   0.25(LR)   0.2   0.1
 // With HR referring to high res tiling and LR referring to low res tiling,
 // then tilings are processed in this order:
 // 2.0   1.5   0.1   0.2   0.5   0.8   0.25(LR)   1.0(HR).
 //
 // To put it differently:
 //  1. Process the highest scale tiling down to, but not including, high res
 //     tiling.
 //  2. Process the lowest scale tiling up to, but not including, the low res
 //     tiling. In cases without a low res tiling, this is an empty set.
 //  3. Process low res tiling up to high res tiling, including neither high
 //     nor low res tilings. In cases without a low res tiling, this set
 //     includes all tilings with a lower scale than the high res tiling.
 //  4. Process the low res tiling.
 //  5. Process the high res tiling.
 //
 // Additional notes:
 // Since eventually the tiles are considered to have the priority which is the
 // higher of the two trees, we might visit a tile that should actually be
 // returned by its twin. In those situations, the tiles are not returned. That
 // is, since the twin has higher priority, it should return it when it gets to
 // it. This ensures that we don't block raster because we've returned a tile
 // with low priority on one tree, but high combined priority.
 class CC_EXPORT TilingSetEvictionQueue {
  public:
   explicit TilingSetEvictionQueue(PictureLayerTilingSet* tiling_set,
                                   bool is_drawing_layer);
   ~TilingSetEvictionQueue();

   const PrioritizedTile& Top() const;
   void Pop();
   bool IsEmpty() const;
   bool is_drawing_layer() const { return is_drawing_layer_; }

  private:
   enum Phase {
     EVENTUALLY_RECT,
     SOON_BORDER_RECT,
     SKEWPORT_RECT,
     PENDING_VISIBLE_RECT,
     PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION,
     VISIBLE_RECT_OCCLUDED,
     VISIBLE_RECT_UNOCCLUDED,
     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED,
     VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED
   };

   void GenerateTilingOrder(PictureLayerTilingSet* tiling_set);

   // Helper base class for individual region iterators.
   class EvictionRectIterator {
    public:
     EvictionRectIterator();
     EvictionRectIterator(
         std::vector<PictureLayerTiling*>* tilings,
         WhichTree tree,
         PictureLayerTiling::PriorityRectType priority_rect_type);

     bool done() const { return !prioritized_tile_.tile(); }
     const PrioritizedTile& operator*() const { return prioritized_tile_; }

    protected:
     ~EvictionRectIterator() = default;

     template <typename TilingIteratorType>
     bool AdvanceToNextTile(TilingIteratorType* iterator);
     template <typename TilingIteratorType>
     bool GetFirstTileAndCheckIfValid(TilingIteratorType* iterator);

     PrioritizedTile prioritized_tile_;

     // `tilings_` is not a raw_ptr<...> for performance reasons (based on
     // analysis of sampling profiler data and tab_search:top100:2020).
     RAW_PTR_EXCLUSION std::vector<PictureLayerTiling*>* tilings_;

     WhichTree tree_;
     PictureLayerTiling::PriorityRectType priority_rect_type_;
     size_t tiling_index_;
   };

   class PendingVisibleTilingIterator : public EvictionRectIterator {
    public:
     PendingVisibleTilingIterator() = default;
     PendingVisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
                                  WhichTree tree,
                                  bool return_required_for_activation_tiles);

     PendingVisibleTilingIterator& operator++();

    private:
     bool TileMatchesRequiredFlags(const PrioritizedTile& tile) const;

     TilingData::DifferenceIterator iterator_;
     bool return_required_for_activation_tiles_;
   };

   class VisibleTilingIterator : public EvictionRectIterator {
    public:
     VisibleTilingIterator() = default;
     VisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
                           WhichTree tree,
                           bool return_occluded_tiles,
                           bool return_required_for_activation_tiles);

     VisibleTilingIterator& operator++();

    private:
     bool TileMatchesRequiredFlags(const PrioritizedTile& tile) const;

     TilingData::Iterator iterator_;
     bool return_occluded_tiles_;
     bool return_required_for_activation_tiles_;
   };

   class SkewportTilingIterator : public EvictionRectIterator {
    public:
     SkewportTilingIterator() = default;
     SkewportTilingIterator(std::vector<PictureLayerTiling*>* tilings,
                            WhichTree tree);

     SkewportTilingIterator& operator++();

    private:
     TilingData::ReverseSpiralDifferenceIterator iterator_;
   };

   class SoonBorderTilingIterator : public EvictionRectIterator {
    public:
     SoonBorderTilingIterator() = default;
     SoonBorderTilingIterator(std::vector<PictureLayerTiling*>* tilings,
                              WhichTree tree);

     SoonBorderTilingIterator& operator++();

    private:
     TilingData::ReverseSpiralDifferenceIterator iterator_;
   };

   class EventuallyTilingIterator : public EvictionRectIterator {
    public:
     EventuallyTilingIterator() = default;
     EventuallyTilingIterator(std::vector<PictureLayerTiling*>* tilings,
                              WhichTree tree);

     EventuallyTilingIterator& operator++();

    private:
     TilingData::ReverseSpiralDifferenceIterator iterator_;
   };

   void AdvancePhase();

   WhichTree tree_;
   Phase phase_;
   PrioritizedTile current_tile_;
   std::vector<PictureLayerTiling*> tilings_;

   EventuallyTilingIterator eventually_iterator_;
   SoonBorderTilingIterator soon_iterator_;
   SkewportTilingIterator skewport_iterator_;
   PendingVisibleTilingIterator pending_visible_iterator_;
   VisibleTilingIterator visible_iterator_;
   bool is_drawing_layer_;
 };

 }  // namespace cc

 #endif  // CC_TILES_TILING_SET_EVICTION_QUEUE_H_
	// Copyright 2014 The Chromium Authors
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#ifndef CC_TILES_TILING_SET_EVICTION_QUEUE_H_
	#define CC_TILES_TILING_SET_EVICTION_QUEUE_H_

	#include <stddef.h>

	#include <vector>

	#include "base/memory/raw_ptr_exclusion.h"
	#include "cc/cc_export.h"
	#include "cc/tiles/picture_layer_tiling_set.h"
	#include "cc/tiles/prioritized_tile.h"

	namespace cc {

	// This eviction queue returned tiles from all tilings in a tiling set in
	// the order in which the tiles should be evicted. It can be thought of as the
	// following:
	// for all phases:
	// for all ordered tilings:
	// yield the next tile for the given phase from the given tiling
	//
	// Phases are the following (in order in which they are processed):
	// EVENTUALLY_RECT - Tiles in the eventually region of the tiling.
	// SOON_BORDER_RECT - Tiles in the prepainting skirt of the tiling.
	// SKEWPORT_RECT - Tiles in the skewport of the tiling.
	// PENDING_VISIBLE_RECT - Tiles that will be visible upon activation, not
	// required for activation.
	// PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION - Tiles that will be visible
	// upon activation, required for activation.
	// VISIBLE_RECT_OCCLUDED - Occluded, not required for activation, visible tiles.
	// VISIBLE_RECT_UNOCCLUDED - Unoccluded, not required for activation, visible
	// tiles.
	// VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED - Occluded, but required for
	// activation, visible tiles. This can happen when an active tree tile is
	// occluded, but is not occluded on the pending tree (and is required for
	// activation).
	// VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED - Unoccluded, required for
	// activation, tiles.
	//
	// The tilings are ordered as follows. Suppose we have tilings with the scales
	// below:
	// 2.0 1.5 1.0(HR) 0.8 0.5 0.25(LR) 0.2 0.1
	// With HR referring to high res tiling and LR referring to low res tiling,
	// then tilings are processed in this order:
	// 2.0 1.5 0.1 0.2 0.5 0.8 0.25(LR) 1.0(HR).
	//
	// To put it differently:
	// 1. Process the highest scale tiling down to, but not including, high res
	// tiling.
	// 2. Process the lowest scale tiling up to, but not including, the low res
	// tiling. In cases without a low res tiling, this is an empty set.
	// 3. Process low res tiling up to high res tiling, including neither high
	// nor low res tilings. In cases without a low res tiling, this set
	// includes all tilings with a lower scale than the high res tiling.
	// 4. Process the low res tiling.
	// 5. Process the high res tiling.
	//
	// Additional notes:
	// Since eventually the tiles are considered to have the priority which is the
	// higher of the two trees, we might visit a tile that should actually be
	// returned by its twin. In those situations, the tiles are not returned. That
	// is, since the twin has higher priority, it should return it when it gets to
	// it. This ensures that we don't block raster because we've returned a tile
	// with low priority on one tree, but high combined priority.
	class CC_EXPORT TilingSetEvictionQueue {
	public:
	explicit TilingSetEvictionQueue(PictureLayerTilingSet* tiling_set,
	bool is_drawing_layer);
	~TilingSetEvictionQueue();

	const PrioritizedTile& Top() const;
	void Pop();
	bool IsEmpty() const;
	bool is_drawing_layer() const { return is_drawing_layer_; }

	private:
	enum Phase {
	EVENTUALLY_RECT,
	SOON_BORDER_RECT,
	SKEWPORT_RECT,
	PENDING_VISIBLE_RECT,
	PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION,
	VISIBLE_RECT_OCCLUDED,
	VISIBLE_RECT_UNOCCLUDED,
	VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED,
	VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED
	};

	void GenerateTilingOrder(PictureLayerTilingSet* tiling_set);

	// Helper base class for individual region iterators.
	class EvictionRectIterator {
	public:
	EvictionRectIterator();
	EvictionRectIterator(
	std::vector<PictureLayerTiling> tilings,
	WhichTree tree,
	PictureLayerTiling::PriorityRectType priority_rect_type);

	bool done() const { return !prioritized_tile_.tile(); }
	const PrioritizedTile& operator*() const { return prioritized_tile_; }

	protected:
	~EvictionRectIterator() = default;

	template <typename TilingIteratorType>
	bool AdvanceToNextTile(TilingIteratorType* iterator);
	template <typename TilingIteratorType>
	bool GetFirstTileAndCheckIfValid(TilingIteratorType* iterator);

	PrioritizedTile prioritized_tile_;

	// `tilings_` is not a raw_ptr<...> for performance reasons (based on
	// analysis of sampling profiler data and tab_search:top100:2020).
	RAW_PTR_EXCLUSION std::vector<PictureLayerTiling> tilings_;

	WhichTree tree_;
	PictureLayerTiling::PriorityRectType priority_rect_type_;
	size_t tiling_index_;
	};

	class PendingVisibleTilingIterator : public EvictionRectIterator {
	public:
	PendingVisibleTilingIterator() = default;
	PendingVisibleTilingIterator(std::vector<PictureLayerTiling> tilings,
	WhichTree tree,
	bool return_required_for_activation_tiles);

	PendingVisibleTilingIterator& operator++();

	private:
	bool TileMatchesRequiredFlags(const PrioritizedTile& tile) const;

	TilingData::DifferenceIterator iterator_;
	bool return_required_for_activation_tiles_;
	};

	class VisibleTilingIterator : public EvictionRectIterator {
	public:
	VisibleTilingIterator() = default;
	VisibleTilingIterator(std::vector<PictureLayerTiling> tilings,
	WhichTree tree,
	bool return_occluded_tiles,
	bool return_required_for_activation_tiles);

	VisibleTilingIterator& operator++();

	private:
	bool TileMatchesRequiredFlags(const PrioritizedTile& tile) const;

	TilingData::Iterator iterator_;
	bool return_occluded_tiles_;
	bool return_required_for_activation_tiles_;
	};

	class SkewportTilingIterator : public EvictionRectIterator {
	public:
	SkewportTilingIterator() = default;
	SkewportTilingIterator(std::vector<PictureLayerTiling> tilings,
	WhichTree tree);

	SkewportTilingIterator& operator++();

	private:
	TilingData::ReverseSpiralDifferenceIterator iterator_;
	};

	class SoonBorderTilingIterator : public EvictionRectIterator {
	public:
	SoonBorderTilingIterator() = default;
	SoonBorderTilingIterator(std::vector<PictureLayerTiling> tilings,
	WhichTree tree);

	SoonBorderTilingIterator& operator++();

	private:
	TilingData::ReverseSpiralDifferenceIterator iterator_;
	};

	class EventuallyTilingIterator : public EvictionRectIterator {
	public:
	EventuallyTilingIterator() = default;
	EventuallyTilingIterator(std::vector<PictureLayerTiling> tilings,
	WhichTree tree);

	EventuallyTilingIterator& operator++();

	private:
	TilingData::ReverseSpiralDifferenceIterator iterator_;
	};

	void AdvancePhase();

	WhichTree tree_;
	Phase phase_;
	PrioritizedTile current_tile_;
	std::vector<PictureLayerTiling*> tilings_;

	EventuallyTilingIterator eventually_iterator_;
	SoonBorderTilingIterator soon_iterator_;
	SkewportTilingIterator skewport_iterator_;
	PendingVisibleTilingIterator pending_visible_iterator_;
	VisibleTilingIterator visible_iterator_;
	bool is_drawing_layer_;
	};

	} // namespace cc

	#endif // CC_TILES_TILING_SET_EVICTION_QUEUE_H_