From 2baa84b7baa39dd52ae6c19d22b88db50487fa1f Mon Sep 17 00:00:00 2001
From: caryclark <caryclark@google.com>
Date: Mon, 1 Feb 2016 04:34:57 -0800
Subject: [PATCH] batch merge new edges

Find where newly introduced edges go in the edge list once,
then stitch all of them into the edge list.

R=reed@google.com
BUG=573166
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1647223002

Committed: https://skia.googlesource.com/skia/+/ae658e15477df86d1a864feb48d0274af2784f40

Review URL: https://codereview.chromium.org/1647223002
---
 src/core/SkScan_Path.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

diff --git a/src/core/SkScan_Path.cpp b/src/core/SkScan_Path.cpp
index 804148d..077d9a0 100644
--- a/src/core/SkScan_Path.cpp
+++ b/src/core/SkScan_Path.cpp
@@ -61,7 +61,21 @@ static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, cur
     }
 }
 
+#ifndef SK_SUPPORT_LEGACY_INSERT_NEW_EDGES
+// Start from the right side, searching backwards for the point to begin the new edge list
+// insertion, marching forwards from here. The implementation could have started from the left
+// of the prior insertion, and search to the right, or with some additional caching, binary
+// search the starting point. More work could be done to determine optimal new edge insertion.
+static SkEdge* backward_insert_start(SkEdge* prev, SkFixed x) {
+    while (prev->fX > x) {
+        prev = prev->fPrev;
+    }
+    return prev;
+}
+#endif
+
 static void insert_new_edges(SkEdge* newEdge, int curr_y) {
+#ifdef SK_SUPPORT_LEGACY_INSERT_NEW_EDGES
     SkASSERT(newEdge->fFirstY >= curr_y);
 
     while (newEdge->fFirstY == curr_y) {
@@ -69,6 +83,36 @@ static void insert_new_edges(SkEdge* newEdge, int curr_y) {
         backward_insert_edge_based_on_x(newEdge  SkPARAM(curr_y));
         newEdge = next;
     }
+#else
+    if (newEdge->fFirstY != curr_y) {
+        return;
+    }
+    SkEdge* prev = newEdge->fPrev;
+    if (prev->fX <= newEdge->fX) {
+        return;
+    }
+    // find first x pos to insert
+    SkEdge* start = backward_insert_start(prev, newEdge->fX);
+    // insert the lot, fixing up the links as we go
+    do {
+        SkEdge* next = newEdge->fNext;
+        do {
+            if (start->fNext == newEdge) {
+                goto nextEdge;
+            }
+            SkEdge* after = start->fNext;
+            if (after->fX >= newEdge->fX) {
+                break;
+            }
+            start = after;
+        } while (true);
+        remove_edge(newEdge);
+        insert_edge_after(newEdge, start);
+nextEdge:
+        start = newEdge;
+        newEdge = next;
+    } while (newEdge->fFirstY == curr_y);
+#endif
 }
 
 #ifdef SK_DEBUG
-- 
2.7.4