Bug 1265342 Part 2a: Move interval binary search method into ShapeInfo. draft
authorBrad Werth <bwerth@mozilla.com>
Wed, 11 Apr 2018 14:05:06 -0700
changeset 787945 7a5d88647099dd268174d7f3327c7ff10f4b3424
parent 787944 f7fa75645645fd8e308f134b3f166e07a15189e6
child 787946 c74ab8bdb317ce51e011c10cb6d1f1cd50697e2b
push id107854
push userbwerth@mozilla.com
push dateWed, 25 Apr 2018 18:14:35 +0000
bugs1265342
milestone61.0a1
Bug 1265342 Part 2a: Move interval binary search method into ShapeInfo. 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.