mi: Fold mipolyutil.c into mipoly.c

Reviewed-by: Keith Packard <keithp@keithp.com>
Signed-off-by: Adam Jackson <ajax@redhat.com>

4 files changed, 285 insertions, 387 deletions

diff --git a/mi/Makefile.am b/mi/Makefile.am
index 44e4f2053..ce416c41f 100644
--- a/mi/Makefile.am
+++ b/mi/Makefile.am
@@ -40,7 +40,6 @@ libmi_la_SOURCES = 	\
 	mipolyrect.c	\
 	mipolyseg.c	\
 	mipolytext.c	\
-	mipolyutil.c	\
 	mipushpxl.c	\
 	miscanfill.h	\
 	miscrinit.c	\
diff --git a/mi/mipoly.c b/mi/mipoly.c
index 3d49789b0..0ed2edb44 100644
--- a/mi/mipoly.c
+++ b/mi/mipoly.c
@@ -61,6 +61,291 @@ SOFTWARE.
 #include "mipoly.h"
 #include "regionstr.h"
 
+/*
+ * Insert the given edge into the edge table.  First we must find the correct
+ * bucket in the Edge table, then find the right slot in the bucket.  Finally,
+ * we can insert it.
+ */
+static Bool
+miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline,
+                 ScanLineListBlock ** SLLBlock, int *iSLLBlock)
+{
+    EdgeTableEntry *start, *prev;
+    ScanLineList *pSLL, *pPrevSLL;
+    ScanLineListBlock *tmpSLLBlock;
+
+    /*
+     * find the right bucket to put the edge into
+     */
+    pPrevSLL = &ET->scanlines;
+    pSLL = pPrevSLL->next;
+    while (pSLL && (pSLL->scanline < scanline)) {
+        pPrevSLL = pSLL;
+        pSLL = pSLL->next;
+    }
+
+    /*
+     * reassign pSLL (pointer to ScanLineList) if necessary
+     */
+    if ((!pSLL) || (pSLL->scanline > scanline)) {
+        if (*iSLLBlock > SLLSPERBLOCK - 1) {
+            tmpSLLBlock = malloc(sizeof(ScanLineListBlock));
+            if (!tmpSLLBlock)
+                return FALSE;
+            (*SLLBlock)->next = tmpSLLBlock;
+            tmpSLLBlock->next = NULL;
+            *SLLBlock = tmpSLLBlock;
+            *iSLLBlock = 0;
+        }
+        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
+
+        pSLL->next = pPrevSLL->next;
+        pSLL->edgelist = NULL;
+        pPrevSLL->next = pSLL;
+    }
+    pSLL->scanline = scanline;
+
+    /*
+     * now insert the edge in the right bucket
+     */
+    prev = NULL;
+    start = pSLL->edgelist;
+    while (start && (start->bres.minor < ETE->bres.minor)) {
+        prev = start;
+        start = start->next;
+    }
+    ETE->next = start;
+
+    if (prev)
+        prev->next = ETE;
+    else
+        pSLL->edgelist = ETE;
+    return TRUE;
+}
+
+static void
+miFreeStorage(ScanLineListBlock * pSLLBlock)
+{
+    ScanLineListBlock *tmpSLLBlock;
+
+    while (pSLLBlock) {
+        tmpSLLBlock = pSLLBlock->next;
+        free(pSLLBlock);
+        pSLLBlock = tmpSLLBlock;
+    }
+}
+
+/*
+ * CreateEdgeTable
+ *
+ * This routine creates the edge table for scan converting polygons.
+ * The Edge Table (ET) looks like:
+ *
+ * EdgeTable
+ *  --------
+ * |  ymax  |        ScanLineLists
+ * |scanline|-->------------>-------------->...
+ *  --------   |scanline|   |scanline|
+ *             |edgelist|   |edgelist|
+ *             ---------    ---------
+ *                 |             |
+ *                 |             |
+ *                 V             V
+ *           list of ETEs   list of ETEs
+ *
+ * where ETE is an EdgeTableEntry data structure, and there is one ScanLineList
+ * per scanline at which an edge is initially entered.
+ */
+
+static Bool
+miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET,
+                 EdgeTableEntry * AET, EdgeTableEntry * pETEs,
+                 ScanLineListBlock * pSLLBlock)
+{
+    DDXPointPtr top, bottom;
+    DDXPointPtr PrevPt, CurrPt;
+    int iSLLBlock = 0;
+
+    int dy;
+
+    if (count < 2)
+        return TRUE;
+
+    /*
+     *  initialize the Active Edge Table
+     */
+    AET->next = NULL;
+    AET->back = NULL;
+    AET->nextWETE = NULL;
+    AET->bres.minor = MININT;
+
+    /*
+     *  initialize the Edge Table.
+     */
+    ET->scanlines.next = NULL;
+    ET->ymax = MININT;
+    ET->ymin = MAXINT;
+    pSLLBlock->next = NULL;
+
+    PrevPt = &pts[count - 1];
+
+    /*
+     *  for each vertex in the array of points.
+     *  In this loop we are dealing with two vertices at
+     *  a time -- these make up one edge of the polygon.
+     */
+    while (count--) {
+        CurrPt = pts++;
+
+        /*
+         *  find out which point is above and which is below.
+         */
+        if (PrevPt->y > CurrPt->y) {
+            bottom = PrevPt, top = CurrPt;
+            pETEs->ClockWise = 0;
+        }
+        else {
+            bottom = CurrPt, top = PrevPt;
+            pETEs->ClockWise = 1;
+        }
+
+        /*
+         * don't add horizontal edges to the Edge table.
+         */
+        if (bottom->y != top->y) {
+            pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */
+
+            /*
+             *  initialize integer edge algorithm
+             */
+            dy = bottom->y - top->y;
+            BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
+
+            if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) {
+                miFreeStorage(pSLLBlock->next);
+                return FALSE;
+            }
+
+            ET->ymax = max(ET->ymax, PrevPt->y);
+            ET->ymin = min(ET->ymin, PrevPt->y);
+            pETEs++;
+        }
+
+        PrevPt = CurrPt;
+    }
+    return TRUE;
+}
+
+/*
+ * This routine moves EdgeTableEntries from the EdgeTable into the Active Edge
+ * Table, leaving them sorted by smaller x coordinate.
+ */
+
+static void
+miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs)
+{
+    EdgeTableEntry *pPrevAET;
+    EdgeTableEntry *tmp;
+
+    pPrevAET = AET;
+    AET = AET->next;
+    while (ETEs) {
+        while (AET && (AET->bres.minor < ETEs->bres.minor)) {
+            pPrevAET = AET;
+            AET = AET->next;
+        }
+        tmp = ETEs->next;
+        ETEs->next = AET;
+        if (AET)
+            AET->back = ETEs;
+        ETEs->back = pPrevAET;
+        pPrevAET->next = ETEs;
+        pPrevAET = ETEs;
+
+        ETEs = tmp;
+    }
+}
+
+/*
+ * computeWAET
+ *
+ * This routine links the AET by the nextWETE (winding EdgeTableEntry) link for
+ * use by the winding number rule.  The final Active Edge Table (AET) might
+ * look something like:
+ *
+ * AET
+ * ----------  ---------   ---------
+ * |ymax    |  |ymax    |  |ymax    |
+ * | ...    |  |...     |  |...     |
+ * |next    |->|next    |->|next    |->...
+ * |nextWETE|  |nextWETE|  |nextWETE|
+ * ---------   ---------   ^--------
+ *     |                   |       |
+ *     V------------------->       V---> ...
+ *
+ */
+static void
+micomputeWAET(EdgeTableEntry * AET)
+{
+    EdgeTableEntry *pWETE;
+    int inside = 1;
+    int isInside = 0;
+
+    AET->nextWETE = NULL;
+    pWETE = AET;
+    AET = AET->next;
+    while (AET) {
+        if (AET->ClockWise)
+            isInside++;
+        else
+            isInside--;
+
+        if ((!inside && !isInside) || (inside && isInside)) {
+            pWETE->nextWETE = AET;
+            pWETE = AET;
+            inside = !inside;
+        }
+        AET = AET->next;
+    }
+    pWETE->nextWETE = NULL;
+}
+
+/*
+ * Just a simple insertion sort using pointers and back pointers to sort the
+ * Active Edge Table.
+ */
+
+static int
+miInsertionSort(EdgeTableEntry * AET)
+{
+    EdgeTableEntry *pETEchase;
+    EdgeTableEntry *pETEinsert;
+    EdgeTableEntry *pETEchaseBackTMP;
+    int changed = 0;
+
+    AET = AET->next;
+    while (AET) {
+        pETEinsert = AET;
+        pETEchase = AET;
+        while (pETEchase->back->bres.minor > AET->bres.minor)
+            pETEchase = pETEchase->back;
+
+        AET = AET->next;
+        if (pETEchase != pETEinsert) {
+            pETEchaseBackTMP = pETEchase->back;
+            pETEinsert->back->next = AET;
+            if (AET)
+                AET->back = pETEinsert->back;
+            pETEinsert->next = pETEchase;
+            pETEchase->back->next = pETEinsert;
+            pETEchase->back = pETEinsert;
+            pETEinsert->back = pETEchaseBackTMP;
+            changed = 1;
+        }
+    }
+    return changed;
+}
+
 /* Find the index of the point with the smallest y */
 static int
 getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty)
diff --git a/mi/mipoly.h b/mi/mipoly.h
index 02fcfc86d..fc5a5cf3f 100644
--- a/mi/mipoly.h
+++ b/mi/mipoly.h
@@ -171,20 +171,3 @@ typedef struct _ScanLineListBlock {
       pAET = pAET->next; \
    } \
 }
-
-/* mipolyutil.c */
-
-extern Bool miCreateETandAET(int /*count */ ,
-                             DDXPointPtr /*pts */ ,
-                             EdgeTable * /*ET*/,
-                             EdgeTableEntry * /*AET*/,
-                             EdgeTableEntry * /*pETEs */ ,
-                             ScanLineListBlock *      /*pSLLBlock */);
-
-extern void miloadAET(EdgeTableEntry * /*AET*/, EdgeTableEntry * /*ETEs */);
-
-extern void micomputeWAET(EdgeTableEntry * /*AET*/);
-
-extern int miInsertionSort(EdgeTableEntry * /*AET*/);
-
-extern void miFreeStorage(ScanLineListBlock * /*pSLLBlock */);
diff --git a/mi/mipolyutil.c b/mi/mipolyutil.c
deleted file mode 100644
index 5e6301d43..000000000
--- a/mi/mipolyutil.c
+++ /dev/null
@@ -1,369 +0,0 @@
-/***********************************************************
-
-Copyright 1987, 1998  The Open Group
-
-Permission to use, copy, modify, distribute, and sell this software and its
-documentation for any purpose is hereby granted without fee, provided that
-the above copyright notice appear in all copies and that both that
-copyright notice and this permission notice appear in supporting
-documentation.
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
-OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
-CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of The Open Group shall not be
-used in advertising or otherwise to promote the sale, use or other dealings
-in this Software without prior written authorization from The Open Group.
-
-Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
-
-                        All Rights Reserved
-
-Permission to use, copy, modify, and distribute this software and its 
-documentation for any purpose and without fee is hereby granted, 
-provided that the above copyright notice appear in all copies and that
-both that copyright notice and this permission notice appear in 
-supporting documentation, and that the name of Digital not be
-used in advertising or publicity pertaining to distribution of the
-software without specific, written prior permission.  
-
-DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
-ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
-DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
-ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
-WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
-ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
-SOFTWARE.
-
-******************************************************************/
-#ifdef HAVE_DIX_CONFIG_H
-#include <dix-config.h>
-#endif
-
-#include "regionstr.h"
-#include "gc.h"
-#include "miscanfill.h"
-#include "mipoly.h"
-#include "misc.h"               /* MAXINT */
-
-/*
- *     fillUtils.c
- *
- *     Written by Brian Kelleher;  Oct. 1985
- *
- *     This module contains all of the utility functions
- *     needed to scan convert a polygon.
- *
- */
-
-/*
- *     InsertEdgeInET
- *
- *     Insert the given edge into the edge table.
- *     First we must find the correct bucket in the
- *     Edge table, then find the right slot in the
- *     bucket.  Finally, we can insert it.
- *
- */
-static Bool
-miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline,
-                 ScanLineListBlock ** SLLBlock, int *iSLLBlock)
-{
-    EdgeTableEntry *start, *prev;
-    ScanLineList *pSLL, *pPrevSLL;
-    ScanLineListBlock *tmpSLLBlock;
-
-    /*
-     * find the right bucket to put the edge into
-     */
-    pPrevSLL = &ET->scanlines;
-    pSLL = pPrevSLL->next;
-    while (pSLL && (pSLL->scanline < scanline)) {
-        pPrevSLL = pSLL;
-        pSLL = pSLL->next;
-    }
-
-    /*
-     * reassign pSLL (pointer to ScanLineList) if necessary
-     */
-    if ((!pSLL) || (pSLL->scanline > scanline)) {
-        if (*iSLLBlock > SLLSPERBLOCK - 1) {
-            tmpSLLBlock = malloc(sizeof(ScanLineListBlock));
-            if (!tmpSLLBlock)
-                return FALSE;
-            (*SLLBlock)->next = tmpSLLBlock;
-            tmpSLLBlock->next = NULL;
-            *SLLBlock = tmpSLLBlock;
-            *iSLLBlock = 0;
-        }
-        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
-
-        pSLL->next = pPrevSLL->next;
-        pSLL->edgelist = NULL;
-        pPrevSLL->next = pSLL;
-    }
-    pSLL->scanline = scanline;
-
-    /*
-     * now insert the edge in the right bucket
-     */
-    prev = NULL;
-    start = pSLL->edgelist;
-    while (start && (start->bres.minor < ETE->bres.minor)) {
-        prev = start;
-        start = start->next;
-    }
-    ETE->next = start;
-
-    if (prev)
-        prev->next = ETE;
-    else
-        pSLL->edgelist = ETE;
-    return TRUE;
-}
-
-/*
- *     CreateEdgeTable
- *
- *     This routine creates the edge table for
- *     scan converting polygons. 
- *     The Edge Table (ET) looks like:
- *
- *    EdgeTable
- *     --------
- *    |  ymax  |        ScanLineLists
- *    |scanline|-->------------>-------------->...
- *     --------   |scanline|   |scanline|
- *                |edgelist|   |edgelist|
- *                ---------    ---------
- *                    |             |
- *                    |             |
- *                    V             V
- *              list of ETEs   list of ETEs
- *
- *     where ETE is an EdgeTableEntry data structure,
- *     and there is one ScanLineList per scanline at
- *     which an edge is initially entered.
- *
- */
-
-Bool
-miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET,
-                 EdgeTableEntry * AET, EdgeTableEntry * pETEs,
-                 ScanLineListBlock * pSLLBlock)
-{
-    DDXPointPtr top, bottom;
-    DDXPointPtr PrevPt, CurrPt;
-    int iSLLBlock = 0;
-
-    int dy;
-
-    if (count < 2)
-        return TRUE;
-
-    /*
-     *  initialize the Active Edge Table
-     */
-    AET->next = NULL;
-    AET->back = NULL;
-    AET->nextWETE = NULL;
-    AET->bres.minor = MININT;
-
-    /*
-     *  initialize the Edge Table.
-     */
-    ET->scanlines.next = NULL;
-    ET->ymax = MININT;
-    ET->ymin = MAXINT;
-    pSLLBlock->next = NULL;
-
-    PrevPt = &pts[count - 1];
-
-    /*
-     *  for each vertex in the array of points.
-     *  In this loop we are dealing with two vertices at
-     *  a time -- these make up one edge of the polygon.
-     */
-    while (count--) {
-        CurrPt = pts++;
-
-        /*
-         *  find out which point is above and which is below.
-         */
-        if (PrevPt->y > CurrPt->y) {
-            bottom = PrevPt, top = CurrPt;
-            pETEs->ClockWise = 0;
-        }
-        else {
-            bottom = CurrPt, top = PrevPt;
-            pETEs->ClockWise = 1;
-        }
-
-        /*
-         * don't add horizontal edges to the Edge table.
-         */
-        if (bottom->y != top->y) {
-            pETEs->ymax = bottom->y - 1;        /* -1 so we don't get last scanline */
-
-            /*
-             *  initialize integer edge algorithm
-             */
-            dy = bottom->y - top->y;
-            BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
-
-            if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) {
-                miFreeStorage(pSLLBlock->next);
-                return FALSE;
-            }
-
-            ET->ymax = max(ET->ymax, PrevPt->y);
-            ET->ymin = min(ET->ymin, PrevPt->y);
-            pETEs++;
-        }
-
-        PrevPt = CurrPt;
-    }
-    return TRUE;
-}
-
-/*
- *     loadAET
- *
- *     This routine moves EdgeTableEntries from the
- *     EdgeTable into the Active Edge Table,
- *     leaving them sorted by smaller x coordinate.
- *
- */
-
-void
-miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs)
-{
-    EdgeTableEntry *pPrevAET;
-    EdgeTableEntry *tmp;
-
-    pPrevAET = AET;
-    AET = AET->next;
-    while (ETEs) {
-        while (AET && (AET->bres.minor < ETEs->bres.minor)) {
-            pPrevAET = AET;
-            AET = AET->next;
-        }
-        tmp = ETEs->next;
-        ETEs->next = AET;
-        if (AET)
-            AET->back = ETEs;
-        ETEs->back = pPrevAET;
-        pPrevAET->next = ETEs;
-        pPrevAET = ETEs;
-
-        ETEs = tmp;
-    }
-}
-
-/*
- *     computeWAET
- *
- *     This routine links the AET by the
- *     nextWETE (winding EdgeTableEntry) link for
- *     use by the winding number rule.  The final 
- *     Active Edge Table (AET) might look something
- *     like:
- *
- *     AET
- *     ----------  ---------   ---------
- *     |ymax    |  |ymax    |  |ymax    | 
- *     | ...    |  |...     |  |...     |
- *     |next    |->|next    |->|next    |->...
- *     |nextWETE|  |nextWETE|  |nextWETE|
- *     ---------   ---------   ^--------
- *         |                   |       |
- *         V------------------->       V---> ...
- *
- */
-void
-micomputeWAET(EdgeTableEntry * AET)
-{
-    EdgeTableEntry *pWETE;
-    int inside = 1;
-    int isInside = 0;
-
-    AET->nextWETE = NULL;
-    pWETE = AET;
-    AET = AET->next;
-    while (AET) {
-        if (AET->ClockWise)
-            isInside++;
-        else
-            isInside--;
-
-        if ((!inside && !isInside) || (inside && isInside)) {
-            pWETE->nextWETE = AET;
-            pWETE = AET;
-            inside = !inside;
-        }
-        AET = AET->next;
-    }
-    pWETE->nextWETE = NULL;
-}
-
-/*
- *     InsertionSort
- *
- *     Just a simple insertion sort using
- *     pointers and back pointers to sort the Active
- *     Edge Table.
- *
- */
-
-int
-miInsertionSort(EdgeTableEntry * AET)
-{
-    EdgeTableEntry *pETEchase;
-    EdgeTableEntry *pETEinsert;
-    EdgeTableEntry *pETEchaseBackTMP;
-    int changed = 0;
-
-    AET = AET->next;
-    while (AET) {
-        pETEinsert = AET;
-        pETEchase = AET;
-        while (pETEchase->back->bres.minor > AET->bres.minor)
-            pETEchase = pETEchase->back;
-
-        AET = AET->next;
-        if (pETEchase != pETEinsert) {
-            pETEchaseBackTMP = pETEchase->back;
-            pETEinsert->back->next = AET;
-            if (AET)
-                AET->back = pETEinsert->back;
-            pETEinsert->next = pETEchase;
-            pETEchase->back->next = pETEinsert;
-            pETEchase->back = pETEinsert;
-            pETEinsert->back = pETEchaseBackTMP;
-            changed = 1;
-        }
-    }
-    return changed;
-}
-
-/*
- *     Clean up our act.
- */
-void
-miFreeStorage(ScanLineListBlock * pSLLBlock)
-{
-    ScanLineListBlock *tmpSLLBlock;
-
-    while (pSLLBlock) {
-        tmpSLLBlock = pSLLBlock->next;
-        free(pSLLBlock);
-        pSLLBlock = tmpSLLBlock;
-    }
-}