update pathops to circle sort

src/pathops/SkPathOpsOp.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkAddIntersections.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
 #include "SkPathWriter.h"
 
-// FIXME: this and find chase should be merge together, along with
-// other code that walks winding in angles
-// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
-// so it isn't duplicated by walkers like this one
-static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) {
+static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
     while (chase.count()) {
         SkOpSpan* span;
         chase.pop(&span);
         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
         SkOpSegment* segment = backPtr.fOther;
-        nextStart = backPtr.fOtherIndex;
-        SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
-        int done = 0;
-        if (segment->activeAngle(nextStart, &done, &angles)) {
-            SkOpAngle* last = angles.end() - 1;
-            nextStart = last->start();
-            nextEnd = last->end();
+        *tIndex = backPtr.fOtherIndex;
+        bool sortable = true;
+        bool done = true;
+        *endIndex = -1;
+        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+                &sortable)) {
+            *tIndex = last->start();
+            *endIndex = last->end();
    #if TRY_ROTATE
             *chase.insert(0) = span;
    #else
             *chase.append() = span;
    #endif
             return last->segment();
         }
-        if (done == angles.count()) {
+        if (done) {
             continue;
         }
-        SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
-        bool sortable = SkOpSegment::SortAngles(angles, &sorted,
-                SkOpSegment::kMayBeUnordered_SortAngleKind);
-        int angleCount = sorted.count();
-#if DEBUG_SORT
-        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable);
-#endif
         if (!sortable) {
             continue;
         }
         // find first angle, initialize winding to computed fWindSum
-        int firstIndex = -1;
-        const SkOpAngle* angle;
-        bool foundAngle = true;
+        const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+        const SkOpAngle* firstAngle = angle;
+        SkDEBUGCODE(bool loop = false);
+        int winding;
         do {
-            ++firstIndex;
-            if (firstIndex >= angleCount) {
-                foundAngle = false;
-                break;
-            }
-            angle = sorted[firstIndex];
+            angle = angle->next();
+            SkASSERT(angle != firstAngle || !loop);
+            SkDEBUGCODE(loop |= angle == firstAngle);
             segment = angle->segment();
-        } while (segment->windSum(angle) == SK_MinS32);
-        if (!foundAngle) {
-            continue;
-        }
-    #if DEBUG_SORT
-        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
-    #endif
+            winding = segment->windSum(angle);
+        } while (winding == SK_MinS32);
         int sumMiWinding = segment->updateWindingReverse(angle);
         int sumSuWinding = segment->updateOppWindingReverse(angle);
         if (segment->operand()) {
             SkTSwap<int>(sumMiWinding, sumSuWinding);
         }
-        int nextIndex = firstIndex + 1;
-        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
         SkOpSegment* first = NULL;
-        do {
-            SkASSERT(nextIndex != firstIndex);
-            if (nextIndex == angleCount) {
-                nextIndex = 0;
-            }
-            angle = sorted[nextIndex];
+        while ((angle = angle->next()) != firstAngle) {
             segment = angle->segment();
             int start = angle->start();
             int end = angle->end();
             int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
             segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
                     &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
             if (!segment->done(angle)) {
                 if (!first) {
                     first = segment;
-                    nextStart = start;
-                    nextEnd = end;
+                    *tIndex = start;
+                    *endIndex = end;
                 }
                 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
                     oppSumWinding, angle);
             }
-        } while (++nextIndex != lastIndex);
+        }
         if (first) {
        #if TRY_ROTATE
             *chase.insert(0) = span;
        #else
             *chase.append() = span;
        #endif
             return first;
         }
     }
     return NULL;
@@ skipping 45 matching lines @@
                 topLeft.fX = topLeft.fY = SK_ScalarMin;
                 continue;
             }
             break;
         }
         SkTDArray<SkOpSpan*> chaseArray;
         do {
             if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
                 do {
                     if (!unsortable && current->done()) {
-            #if DEBUG_ACTIVE_SPANS
-                        DebugShowActiveSpans(contourList);
-            #endif
                         if (simple->isEmpty()) {
                             simple->init();
                         }
                         break;
                     }
                     SkASSERT(unsortable || !current->done());
                     int nextStart = index;
                     int nextEnd = endIndex;
                     SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd,
                             &unsortable, op, xorMask, xorOpMask);
@@ skipping 16 matching lines @@
                     index = nextStart;
                     endIndex = nextEnd;
                 } while (!simple->isClosed() && (!unsortable
                         || !current->done(SkMin32(index, endIndex))));
                 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
                     // FIXME : add to simplify, xor cpaths
                     int min = SkMin32(index, endIndex);
                     if (!unsortable && !simple->isEmpty()) {
                         unsortable = current->checkSmall(min);
                     }
-                    SkASSERT(unsortable || simple->isEmpty());
                     if (!current->done(min)) {
                         current->addCurveTo(index, endIndex, simple, true);
                         current->markDoneBinary(min);
                     }
                 }
                 simple->close();
             } else {
                 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
-                if (last && !last->fLoop) {
+                if (last && !last->fChased && !last->fLoop) {
+                    last->fChased = true;
+                    SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last));
                     *chaseArray.append() = last;
                 }
             }
-            current = findChaseOp(chaseArray, index, endIndex);
+            current = findChaseOp(chaseArray, &index, &endIndex);
         #if DEBUG_ACTIVE_SPANS
             DebugShowActiveSpans(contourList);
         #endif
             if (!current) {
                 break;
             }
         } while (true);
     } while (true);
     return simple->someAssemblyRequired();
 }
@@ skipping 71 matching lines @@
             next = *nextPtr++;
         } while (AddIntersectTs(current, next) && nextPtr != listEnd);
     } while (currentPtr != listEnd);
     // eat through coincident edges
 
     int total = 0;
     int index;
     for (index = 0; index < contourList.count(); ++index) {
         total += contourList[index]->segments().count();
     }
-    HandleCoincidence(&contourList, total);
+    if (!HandleCoincidence(&contourList, total)) {
+        return false;
+    }
     // construct closed contours
     SkPathWriter wrapper(*result);
     bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
     {  // if some edges could not be resolved, assemble remaining fragments
         SkPath temp;
         temp.setFillType(fillType);
         SkPathWriter assembled(temp);
         Assemble(wrapper, &assembled);
         *result = *assembled.nativePath();
         result->setFillType(fillType);
     }
     return true;
 }