[PATCH 09/23] mi: Fold mipolyutil.c into mipoly.c
Adam Jackson
ajax at redhat.com
Mon Oct 27 12:51:57 PDT 2014
Reviewed-by: Keith Packard <keithp at keithp.com>
Signed-off-by: Adam Jackson <ajax at redhat.com>
---
mi/Makefile.am | 1 -
mi/mipoly.c | 285 +++++++++++++++++++++++++++++++++++++++++++
mi/mipoly.h | 17 ---
mi/mipolyutil.c | 369 --------------------------------------------------------
4 files changed, 285 insertions(+), 387 deletions(-)
delete mode 100644 mi/mipolyutil.c
diff --git a/mi/Makefile.am b/mi/Makefile.am
index 44e4f20..ce416c4 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 3d49789..0ed2edb 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 02fcfc8..fc5a5cf 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 5e6301d..0000000
--- 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;
- }
-}
--
1.9.3
More information about the xorg-devel
mailing list