Small GrTessellator refactor and cleanup.

src/gpu/GrTessellator.cpp

 /*
  * Copyright 2015 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "GrTessellator.h"
 
 #include "GrBatchFlushState.h"
@@ skipping 76 matching lines @@
 
 #define ALLOC_NEW(Type, args, alloc) new (alloc.allocThrow(sizeof(Type))) Type args
 
 namespace {
 
 struct Vertex;
 struct Edge;
 struct Poly;
 
 template <class T, T* T::*Prev, T* T::*Next>
-void insert(T* t, T* prev, T* next, T** head, T** tail) {
+void list_insert(T* t, T* prev, T* next, T** head, T** tail) {
     t->*Prev = prev;
     t->*Next = next;
     if (prev) {
         prev->*Next = t;
     } else if (head) {
         *head = t;
     }
     if (next) {
         next->*Prev = t;
     } else if (tail) {
         *tail = t;
     }
 }
 
 template <class T, T* T::*Prev, T* T::*Next>
-void remove(T* t, T** head, T** tail) {
+void list_remove(T* t, T** head, T** tail) {
     if (t->*Prev) {
         t->*Prev->*Next = t->*Next;
     } else if (head) {
         *head = t->*Next;
     }
     if (t->*Next) {
         t->*Next->*Prev = t->*Prev;
     } else if (tail) {
         *tail = t->*Prev;
     }
@@ skipping 79 matching lines @@
 #endif
     return data;
 }
 
 struct EdgeList {
     EdgeList() : fHead(nullptr), fTail(nullptr) {}
     Edge* fHead;
     Edge* fTail;
 };
 
+struct VertexList {
+    VertexList() : fHead(nullptr), fTail(nullptr) {}
+    Vertex* fHead;
+    Vertex* fTail;
+    void insert(Vertex* v, Vertex* prev, Vertex* next) {
+        list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail);
+    }
+    void append(Vertex* v) {
+        insert(v, fTail, nullptr);
+    }
+    void prepend(Vertex* v) {
+        insert(v, nullptr, fHead);
+    }
+};
+
 /**
  * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
  * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
  * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
  * point). For speed, that case is only tested by the callers which require it (e.g.,
  * cleanup_active_edges()). Edges also handle checking for intersection with other edges.
  * Currently, this converts the edges to the parametric form, in order to avoid doing a division
  * until an intersection has been confirmed. This is slightly slower in the "found" case, but
  * a lot faster in the "not found" case.
  *
@@ skipping 96 matching lines @@
 #if LOGGING_ENABLED
         static int gID = 0;
         fID = gID++;
         LOG("*** created Poly %d\n", fID);
 #endif
     }
     typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side;
     struct MonotonePoly {
         MonotonePoly()
             : fSide(kNeither_Side)
-            , fHead(nullptr)
-            , fTail(nullptr)
             , fPrev(nullptr)
             , fNext(nullptr) {}
         Side          fSide;
-        Vertex*       fHead;
-        Vertex*       fTail;
+        VertexList    fVertices;
         MonotonePoly* fPrev;
         MonotonePoly* fNext;
         bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
             Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc);
             bool done = false;
             if (fSide == kNeither_Side) {
                 fSide = side;
             } else {
                 done = side != fSide;
             }
-            if (fHead == nullptr) {
-                fHead = fTail = newV;
-            } else if (fSide == kRight_Side) {
-                newV->fPrev = fTail;
-                fTail->fNext = newV;
-                fTail = newV;
+            if (fSide == kRight_Side) {
+                fVertices.append(newV);
             } else {
-                newV->fNext = fHead;
-                fHead->fPrev = newV;
-                fHead = newV;
+                fVertices.prepend(newV);
             }
             return done;
         }
 
         SkPoint* emit(SkPoint* data) {
-            Vertex* first = fHead;
+            Vertex* first = fVertices.fHead;
             Vertex* v = first->fNext;
-            while (v != fTail) {
+            while (v != fVertices.fTail) {
                 SkASSERT(v && v->fPrev && v->fNext);
                 Vertex* prev = v->fPrev;
                 Vertex* curr = v;
                 Vertex* next = v->fNext;
                 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
                 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
                 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
                 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
                 if (ax * by - ay * bx >= 0.0) {
                     data = emit_triangle(prev, curr, next, data);
@@ skipping 28 matching lines @@
                 fTail->fNext = fActive;
                 fTail = fActive;
             } else {
                 fHead = fTail = fActive;
             }
             if (partner) {
                 partner->addVertex(v, side, alloc);
                 poly = partner;
             } else {
                 Vertex* prev = fActive->fSide == Poly::kLeft_Side ?
-                               fActive->fHead->fNext : fActive->fTail->fPrev;
+                               fActive->fVertices.fHead->fNext : fActive->fVertices.fTail->fPrev;
                 fActive = ALLOC_NEW(MonotonePoly, , alloc);
                 fActive->addVertex(prev, Poly::kNeither_Side, alloc);
                 fActive->addVertex(v, side, alloc);
             }
         }
         fCount++;
         return poly;
     }
     void end(Vertex* v, SkChunkAlloc& alloc) {
         LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY);
@@ skipping 215 matching lines @@
 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
     int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
     Vertex* top = winding < 0 ? next : prev;
     Vertex* bottom = winding < 0 ? prev : next;
     return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
 }
 
 void remove_edge(Edge* edge, EdgeList* edges) {
     LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
     SkASSERT(edge->isActive(edges));
-    remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
+    list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
 }
 
 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
     LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
     SkASSERT(!edge->isActive(edges));
     Edge* next = prev ? prev->fRight : edges->fHead;
-    insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
+    list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
 }
 
 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
     if (v->fFirstEdgeAbove) {
         *left = v->fFirstEdgeAbove->fLeft;
         *right = v->fLastEdgeAbove->fRight;
         return;
     }
     Edge* next = nullptr;
     Edge* prev;
     for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) {
         if (prev->isLeftOf(v)) {
             break;
         }
         next = prev;
     }
     *left = prev;
     *right = next;
-    return;
 }
 
 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {
     Edge* prev = nullptr;
     Edge* next;
     for (next = edges->fHead; next != nullptr; next = next->fRight) {
         if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
             (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
             (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
              next->isRightOf(edge->fBottom)) ||
             (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
              edge->isLeftOf(next->fBottom))) {
             break;
         }
         prev = next;
     }
     *left = prev;
     *right = next;
-    return;
 }
 
 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
     if (edge->isActive(activeEdges)) {
         if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
             remove_edge(edge, activeEdges);
         }
     } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
         Edge* left;
         Edge* right;
         find_enclosing_edges(edge, activeEdges, c, &left, &right);
         insert_edge(edge, left, activeEdges);
     }
 }
 
 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
         c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
         return;
     }
     LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
     Edge* prev = nullptr;
     Edge* next;
     for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
         if (next->isRightOf(edge->fTop)) {
             break;
         }
         prev = next;
     }
-    insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
+    list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
         edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
 }
 
 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
         c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
         return;
     }
     LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
     Edge* prev = nullptr;
     Edge* next;
     for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
         if (next->isRightOf(edge->fBottom)) {
             break;
         }
         prev = next;
     }
-    insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
+    list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
         edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
 }
 
 void remove_edge_above(Edge* edge) {
     LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
         edge->fBottom->fID);
-    remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
+    list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
         edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
 }
 
 void remove_edge_below(Edge* edge) {
     LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
         edge->fTop->fID);
-    remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
+    list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
         edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
 }
 
 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
     if (edge->fWinding != 0) {
         return;
     }
     LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
     remove_edge_above(edge);
     remove_edge_below(edge);
@@ skipping 140 matching lines @@
     for (Edge* edge = src->fFirstEdgeAbove; edge;) {
         Edge* next = edge->fNextEdgeAbove;
         set_bottom(edge, dst, nullptr, c);
         edge = next;
     }
     for (Edge* edge = src->fFirstEdgeBelow; edge;) {
         Edge* next = edge->fNextEdgeBelow;
         set_top(edge, dst, nullptr, c);
         edge = next;
     }
-    remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr);
+    list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr);
 }
 
 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
                                SkChunkAlloc& alloc) {
     SkPoint p;
     if (!edge || !other) {
         return nullptr;
     }
     if (edge->intersect(*other, &p)) {
         Vertex* v;
@@ skipping 150 matching lines @@
     Vertex* a;
     Vertex* b;
     front_back_split(*head, &a, &b);
 
     merge_sort(&a, c);
     merge_sort(&b, c);
 
     *head = sorted_merge(a, b, c);
 }
 
-inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) {
-    insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, nullptr, head, tail);
-}
-
-inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) {
-    insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tail);
-}
-
 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) {
-    Vertex* head = nullptr;
-    Vertex* tail = nullptr;
+    VertexList vertices;
 
     while (a && b) {
         if (c.sweep_lt(a->fPoint, b->fPoint)) {
             Vertex* next = a->fNext;
-            append_vertex(a, &head, &tail);
+            vertices.append(a);
             a = next;
         } else {
             Vertex* next = b->fNext;
-            append_vertex(b, &head, &tail);
+            vertices.append(b);
             b = next;
         }
     }
     if (a) {
-        append_vertex_list(a, &head, &tail);
+        vertices.insert(a, vertices.fTail, a->fNext);
     }
     if (b) {
-        append_vertex_list(b, &head, &tail);
+        vertices.insert(b, vertices.fTail, b->fNext);
     }
-    return head;
+    return vertices.fHead;
 }
 
 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
 
 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) {
     LOG("simplifying complex polygons\n");
     EdgeList activeEdges;
     for (Vertex* v = vertices; v != nullptr; v = v->fNext) {
         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
             continue;
@@ skipping 334 matching lines @@
         }
     }
     int actualCount = static_cast<int>(vertsEnd - *verts);
     SkASSERT(actualCount <= count);
     SkASSERT(pointsEnd - points == actualCount);
     delete[] points;
     return actualCount;
 }
 
 } // namespace