Bug 1265342 Part 2a: Move interval binary search method into ShapeInfo. r=dholbert
☠☠ backed out by 723a9f786923 ☠ ☠
authorBrad Werth <bwerth@mozilla.com>
Wed, 11 Apr 2018 14:05:06 -0700
changeset 471514 5ee470e75a5340cbdefeb0dc545bfc5cd17379e3
parent 471513 802aa95a52d946c6d124fac91a9b318a2af601cb
child 471515 ce473fa5f1f43e5914251aea21ca59286e643264
push id1728
push userjlund@mozilla.com
push dateMon, 18 Jun 2018 21:12:27 +0000
treeherdermozilla-release@c296fde26f5f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdholbert
bugs1265342
milestone61.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1265342 Part 2a: Move interval binary search method into ShapeInfo. r=dholbert MozReview-Commit-ID: BxJxIU0RVAo
layout/generic/nsFloatManager.cpp
--- 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.