chromium/third_party/blink/renderer/core/layout/layout_shift_region.cc

// Copyright 2018 The Chromium Authors
// 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/layout_shift_region.h"
#include "third_party/blink/renderer/platform/wtf/hash_map.h"

namespace blink {

namespace {

// A segment is a contiguous range of one or more basic intervals.
struct Segment { … };

// An "event" occurs when a rectangle starts intersecting the sweep line
// (kStart), or when it ceases to intersect the sweep line (kEnd).
enum class EventType { … };
struct SweepEvent { … };

// The sequence of adjacent intervals on the y-axis whose endpoints are the
// extents (gfx::Rect::y and gfx::Rect::bottom) of all the rectangles in the
// input.
class BasicIntervals { … };

#if DCHECK_IS_ON()
#define DCHECK_HAS_INDEX …
#else
#define DCHECK_HAS_INDEX …
#endif

inline void BasicIntervals::AddEndpoint(int endpoint) { … }

void BasicIntervals::CreateIndex() { … }

inline unsigned BasicIntervals::NumIntervals() const { … }

inline Segment BasicIntervals::SegmentFromEndpoints(int start, int end) const { … }

inline unsigned BasicIntervals::SegmentLength(Segment segment) const { … }

#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 { … };

SegmentTree::SegmentTree(const BasicIntervals& intervals)
    : … { … }

inline void SegmentTree::RefSegment(Segment segment) { … }

inline void SegmentTree::DerefSegment(Segment segment) { … }

inline unsigned SegmentTree::ActiveLength() const { … }

unsigned SegmentTree::ComputeCapacity(unsigned leaf_count) { … }

inline unsigned SegmentTree::LeftChild(unsigned node_index) { … }

inline unsigned SegmentTree::RightChild(unsigned node_index) { … }

inline Segment SegmentTree::RootSegment() const { … }

inline unsigned SegmentTree::ComputeActiveLength(unsigned node_index,
                                                 Segment node_segment) const { … }

void SegmentTree::Visit(unsigned node_index,
                        Segment node_segment,
                        Segment query_segment,
                        int refcount_delta) { … }

// Runs the sweep line algorithm to compute the area of a set of rects.
class Sweeper { … };

Sweeper::Sweeper(const Vector<gfx::Rect>& rects) : … { … }

uint64_t Sweeper::Sweep() const { … }

void Sweeper::InitIntervals(BasicIntervals& y_vals) const { … }

void Sweeper::InitEventQueue(Vector<SweepEvent>& events,
                             const BasicIntervals& y_vals) const { … }

uint64_t Sweeper::SweepImpl(SegmentTree& tree,
                            const Vector<SweepEvent>& events) const { … }

}  // namespace

uint64_t LayoutShiftRegion::Area() const { … }

}  // namespace blink