blob: 8a0b58081b4b69cbb4ce32bf68c9ff704441f401 [file] [log] [blame]
// Copyright 2018 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "third_party/blink/renderer/core/layout/jank_region.h"
namespace blink {
namespace {
// A segment is a contiguous range of one or more basic intervals.
struct Segment {
// These are the 0-based indexes into the basic intervals, of the first and
// last basic interval in the segment.
unsigned first_interval;
unsigned last_interval;
};
// An "event" occurs when a rectangle starts intersecting the sweep line
// (START), or when it ceases to intersect the sweep line (END).
enum class EventType { START, END };
struct SweepEvent {
// X-coordinate at which the event occurs.
int x;
// Whether the sweep line is entering or exiting the generating rect.
EventType type;
// The generating rect's intersection with the sweep line.
Segment y_segment;
};
// The sequence of adjacent intervals on the y-axis whose endpoints are the
// extents (IntRect::Y and IntRect::MaxY) of all the rectangles in the input.
class BasicIntervals {
public:
// Add all the endpoints before creating the index.
void AddEndpoint(int endpoint);
void CreateIndex();
// Create the index before querying these.
unsigned NumIntervals() const;
Segment SegmentFromEndpoints(int start, int end) const;
unsigned SegmentLength(Segment) const;
private:
Vector<int> endpoints_;
std::map<int, unsigned> endpoint_to_index_;
#if DCHECK_IS_ON()
bool has_index_ = false;
#endif
};
#if DCHECK_IS_ON()
#define DCHECK_HAS_INDEX(expected) DCHECK(has_index_ == expected)
#else
#define DCHECK_HAS_INDEX(expected)
#endif
inline void BasicIntervals::AddEndpoint(int endpoint) {
DCHECK_HAS_INDEX(false);
// We can't index yet, but use the map to de-dupe.
auto ret = endpoint_to_index_.insert(std::make_pair(endpoint, 0u));
if (ret.second)
endpoints_.push_back(endpoint);
}
void BasicIntervals::CreateIndex() {
DCHECK_HAS_INDEX(false);
std::sort(endpoints_.begin(), endpoints_.end());
unsigned i = 0;
for (const int& e : endpoints_)
endpoint_to_index_[e] = i++;
#if DCHECK_IS_ON()
has_index_ = true;
#endif
}
inline unsigned BasicIntervals::NumIntervals() const {
DCHECK_HAS_INDEX(true);
return endpoints_.size() - 1;
}
inline Segment BasicIntervals::SegmentFromEndpoints(int start, int end) const {
DCHECK_HAS_INDEX(true);
return Segment{endpoint_to_index_.at(start), endpoint_to_index_.at(end) - 1};
}
inline unsigned BasicIntervals::SegmentLength(Segment segment) const {
DCHECK_HAS_INDEX(true);
return endpoints_[segment.last_interval + 1] -
endpoints_[segment.first_interval];
}
#undef DCHECK_HAS_INDEX
// An array-backed, weight-balanced binary tree whose leaves represent the basic
// intervals. Non-leaf nodes represent the union of their children's intervals.
class SegmentTree {
public:
SegmentTree(const BasicIntervals&);
// The RefSegment and DerefSegment methods mark nodes corresponding to a
// segment by touching the minimal set of nodes that comprise the segment,
// i.e. every node that is fully within the segment, but whose parent isn't.
// There are only O(log N) nodes in this set.
void RefSegment(Segment);
void DerefSegment(Segment);
// Combined length of all active segments.
unsigned ActiveLength() const;
private:
static unsigned ComputeCapacity(unsigned leaf_count);
static unsigned LeftChild(unsigned node_index);
static unsigned RightChild(unsigned node_index);
Segment RootSegment() const;
unsigned ComputeActiveLength(unsigned node_index, Segment node_segment) const;
// Visit implements the recursive descent through the tree to update nodes for
// a RefSegment or DerefSegment operation.
void Visit(unsigned node_index,
Segment node_segment,
Segment query_segment,
int refcount_delta);
struct Node {
// The ref count for a node tells the number of active segments (rectangles
// intersecting the sweep line) that fully contain this node but not its
// parent. It's updated by RefSegment and DerefSegment.
unsigned ref_count = 0;
// Length-contribution of the intervals in this node's subtree that have
// non-zero ref counts.
unsigned active_length = 0;
};
const BasicIntervals& intervals_;
Vector<Node> nodes_;
};
SegmentTree::SegmentTree(const BasicIntervals& intervals)
: intervals_(intervals) {
nodes_.resize(ComputeCapacity(intervals.NumIntervals()));
}
inline void SegmentTree::RefSegment(Segment segment) {
Visit(0, RootSegment(), segment, 1);
}
inline void SegmentTree::DerefSegment(Segment segment) {
Visit(0, RootSegment(), segment, -1);
}
inline unsigned SegmentTree::ActiveLength() const {
return nodes_.front().active_length;
}
unsigned SegmentTree::ComputeCapacity(unsigned leaf_count) {
unsigned cap = 1;
while (cap < leaf_count)
cap = cap << 1;
return (cap << 1) - 1;
}
inline unsigned SegmentTree::LeftChild(unsigned node_index) {
return (node_index << 1) + 1;
}
inline unsigned SegmentTree::RightChild(unsigned node_index) {
return (node_index << 1) + 2;
}
inline Segment SegmentTree::RootSegment() const {
return {0, intervals_.NumIntervals() - 1};
}
inline unsigned SegmentTree::ComputeActiveLength(unsigned node_index,
Segment node_segment) const {
// If any segment fully covers the interval represented by this node,
// then its active length contribution is the entire interval.
if (nodes_[node_index].ref_count > 0)
return intervals_.SegmentLength(node_segment);
// Otherwise, it contributes only the active lengths of its children.
if (node_segment.last_interval > node_segment.first_interval) {
return nodes_[LeftChild(node_index)].active_length +
nodes_[RightChild(node_index)].active_length;
}
return 0;
}
void SegmentTree::Visit(unsigned node_index,
Segment node_segment,
Segment query_segment,
int refcount_delta) {
Node& node = nodes_[node_index];
// node_segment is the interval represented by this node. (We save some space
// by computing it as we descend instead of storing it in the Node.)
unsigned node_low = node_segment.first_interval;
unsigned node_high = node_segment.last_interval;
// query_segment is the interval we want to update within the node.
unsigned query_low = query_segment.first_interval;
unsigned query_high = query_segment.last_interval;
DCHECK(query_low >= node_low && query_high <= node_high);
if (node_low == query_low && node_high == query_high) {
// The entire node is covered.
node.ref_count += refcount_delta;
} else {
// Last interval in left subtree.
unsigned lower_mid = (node_low + node_high) >> 1;
// First interval in right subtree.
unsigned upper_mid = lower_mid + 1;
if (query_low <= lower_mid) {
Visit(LeftChild(node_index), {node_low, lower_mid},
{query_low, std::min(query_high, lower_mid)}, refcount_delta);
}
if (query_high >= upper_mid) {
Visit(RightChild(node_index), {upper_mid, node_high},
{std::max(query_low, upper_mid), query_high}, refcount_delta);
}
}
node.active_length = ComputeActiveLength(node_index, node_segment);
}
// Runs the sweep line algorithm to compute the area of a set of rects.
class Sweeper {
public:
Sweeper(const Vector<IntRect>&);
// Returns the area.
uint64_t Sweep() const;
private:
void InitIntervals(BasicIntervals&) const;
void InitEventQueue(Vector<SweepEvent>&, const BasicIntervals&) const;
uint64_t SweepImpl(SegmentTree&, const Vector<SweepEvent>&) const;
// The input.
const Vector<IntRect>& rects_;
};
Sweeper::Sweeper(const Vector<IntRect>& rects) : rects_(rects) {}
uint64_t Sweeper::Sweep() const {
BasicIntervals y_vals;
InitIntervals(y_vals);
SegmentTree tree(y_vals);
Vector<SweepEvent> events;
InitEventQueue(events, y_vals);
return SweepImpl(tree, events);
}
void Sweeper::InitIntervals(BasicIntervals& y_vals) const {
for (const IntRect& rect : rects_) {
y_vals.AddEndpoint(rect.Y());
y_vals.AddEndpoint(rect.MaxY());
}
y_vals.CreateIndex();
}
void Sweeper::InitEventQueue(Vector<SweepEvent>& events,
const BasicIntervals& y_vals) const {
events.ReserveInitialCapacity(rects_.size() << 1);
for (const IntRect& rect : rects_) {
Segment segment = y_vals.SegmentFromEndpoints(rect.Y(), rect.MaxY());
events.push_back(SweepEvent{rect.X(), EventType::START, segment});
events.push_back(SweepEvent{rect.MaxX(), EventType::END, segment});
}
std::sort(events.begin(), events.end(),
[](const SweepEvent& e1, const SweepEvent& e2) -> bool {
return e1.x < e2.x;
});
}
uint64_t Sweeper::SweepImpl(SegmentTree& tree,
const Vector<SweepEvent>& events) const {
uint64_t area = 0;
int sweep_x = events.front().x;
for (const SweepEvent& e : events) {
if (e.x > sweep_x) {
area += (uint64_t)(e.x - sweep_x) * (uint64_t)tree.ActiveLength();
sweep_x = e.x;
}
if (e.type == EventType::START)
tree.RefSegment(e.y_segment);
else
tree.DerefSegment(e.y_segment);
}
return area;
}
} // namespace
uint64_t JankRegion::Area() const {
if (rects_.IsEmpty())
return 0;
// Optimization: for a single rect, we don't need Sweeper.
if (rects_.size() == 1) {
const IntRect& rect = rects_.front();
return rect.Width() * rect.Height();
}
return Sweeper(rects_).Sweep();
}
} // namespace blink