Bug 1265342 Part 2a: Move interval binary search method into ShapeInfo.
MozReview-Commit-ID: BxJxIU0RVAo
--- a/layout/generic/nsFloatManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -612,16 +612,26 @@ protected:
WritingMode aWM,
const nsSize& aContainerSize);
// Convert the half corner radii (nscoord[8]) to the special logical
// coordinate space used in float manager.
static UniquePtr<nscoord[]> ConvertToFloatLogical(
const nscoord aRadii[8],
WritingMode aWM);
+
+ // Some ShapeInfo subclasses may define their float areas in intervals.
+ // Each interval is a rectangle that is one device pixel deep in the block
+ // axis. The values are stored as block edges in the y coordinates,
+ // and inline edges as the x coordinates. Interval arrays should be sorted
+ // on increasing y values. This function uses a binary search to find the
+ // first interval that contains aTargetY. If no such interval exists, this
+ // function returns aIntervals.Length().
+ static size_t MinIntervalIndexContainingY(const nsTArray<nsRect>& aIntervals,
+ const nscoord aTargetY);
};
/////////////////////////////////////////////////////////////////////////////
// RoundedBoxShapeInfo
//
// Implements shape-outside: <shape-box> and shape-outside: inset().
//
class nsFloatManager::RoundedBoxShapeInfo final : public nsFloatManager::ShapeInfo
@@ -984,17 +994,16 @@ public:
const nscoord aBEnd) const override;
nscoord BStart() const override { return mBStart; }
nscoord BEnd() const override { return mBEnd; }
bool IsEmpty() const override { return mIntervals.IsEmpty(); }
void Translate(nscoord aLineLeft, nscoord aBlockStart) override;
private:
- size_t MinIntervalIndexContainingY(const nscoord aTargetY) const;
nscoord LineEdge(const nscoord aBStart,
const nscoord aBEnd,
bool aLeft) const;
// An interval is slice of the float area defined by this ImageShapeInfo.
// Each interval is a rectangle that is one pixel deep in the block
// axis. The values are stored as block edges in the y coordinates,
// and inline edges as the x coordinates.
@@ -1105,41 +1114,16 @@ nsFloatManager::ImageShapeInfo::ImageSha
}
if (!mIntervals.IsEmpty()) {
mBStart = mIntervals[0].Y();
mBEnd = mIntervals.LastElement().YMost();
}
}
-size_t
-nsFloatManager::ImageShapeInfo::MinIntervalIndexContainingY(
- const nscoord aTargetY) const
-{
- // Perform a binary search to find the minimum index of an interval
- // that contains aTargetY. If no such interval exists, return a value
- // equal to the number of intervals.
- size_t startIdx = 0;
- size_t endIdx = mIntervals.Length();
- while (startIdx < endIdx) {
- size_t midIdx = startIdx + (endIdx - startIdx) / 2;
- if (mIntervals[midIdx].ContainsY(aTargetY)) {
- return midIdx;
- }
- nscoord midY = mIntervals[midIdx].Y();
- if (midY < aTargetY) {
- startIdx = midIdx + 1;
- } else {
- endIdx = midIdx;
- }
- }
-
- return endIdx;
-}
-
nscoord
nsFloatManager::ImageShapeInfo::LineEdge(const nscoord aBStart,
const nscoord aBEnd,
bool aLeft) const
{
MOZ_ASSERT(aBStart <= aBEnd,
"The band's block start is greater than its block end?");
@@ -1149,17 +1133,17 @@ nsFloatManager::ImageShapeInfo::LineEdge
// Since the intervals are stored in block-axis order, we need
// to find the first interval that overlaps aBStart and check
// succeeding intervals until we get past aBEnd.
nscoord lineEdge = aLeft ? nscoord_MAX : nscoord_MIN;
size_t intervalCount = mIntervals.Length();
- for (size_t i = MinIntervalIndexContainingY(aBStart);
+ for (size_t i = MinIntervalIndexContainingY(mIntervals, aBStart);
i < intervalCount; ++i) {
// We can always get the bCoord from the intervals' mLineLeft,
// since the y() coordinate is duplicated in both points in the
// interval.
auto& interval = mIntervals[i];
nscoord bCoord = interval.Y();
if (bCoord > aBEnd) {
break;
@@ -1710,16 +1694,42 @@ nsFloatManager::ShapeInfo::ConvertToFloa
WritingMode aWM,
const nsSize& aContainerSize)
{
LogicalPoint logicalPoint(aWM, aPoint, aContainerSize);
return nsPoint(logicalPoint.LineRelative(aWM, aContainerSize),
logicalPoint.B(aWM));
}
+/* static */ size_t
+nsFloatManager::ShapeInfo::MinIntervalIndexContainingY(
+ const nsTArray<nsRect>& aIntervals,
+ const nscoord aTargetY)
+{
+ // Perform a binary search to find the minimum index of an interval
+ // that contains aTargetY. If no such interval exists, return a value
+ // equal to the number of intervals.
+ size_t startIdx = 0;
+ size_t endIdx = aIntervals.Length();
+ while (startIdx < endIdx) {
+ size_t midIdx = startIdx + (endIdx - startIdx) / 2;
+ if (aIntervals[midIdx].ContainsY(aTargetY)) {
+ return midIdx;
+ }
+ nscoord midY = aIntervals[midIdx].Y();
+ if (midY < aTargetY) {
+ startIdx = midIdx + 1;
+ } else {
+ endIdx = midIdx;
+ }
+ }
+
+ return endIdx;
+}
+
/* static */ UniquePtr<nscoord[]>
nsFloatManager::ShapeInfo::ConvertToFloatLogical(const nscoord aRadii[8],
WritingMode aWM)
{
UniquePtr<nscoord[]> logicalRadii(new nscoord[8]);
// Get the physical side for line-left and line-right since border radii
// are on the physical axis.