mi: Fold mispans.c into miwideline.c

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

5 files changed, 518 insertions, 612 deletions

diff --git a/mi/Makefile.am b/mi/Makefile.am
index 4466f694d..149dc0671 100644
--- a/mi/Makefile.am
+++ b/mi/Makefile.am
@@ -47,8 +47,6 @@ libmi_la_SOURCES = 	\
 	mipushpxl.c	\
 	miscanfill.h	\
 	miscrinit.c	\
-	mispans.c	\
-	mispans.h	\
 	misprite.c	\
 	misprite.h	\
 	mistruct.h	\
diff --git a/mi/mispans.c b/mi/mispans.c
deleted file mode 100644
index 11c8a43d0..000000000
--- a/mi/mispans.c
+++ /dev/null
@@ -1,526 +0,0 @@
-/***********************************************************
-
-Copyright 1989, 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 1989 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 "misc.h"
-#include "pixmapstr.h"
-#include "gcstruct.h"
-#include "mispans.h"
-
-/*
-
-These routines maintain lists of Spans, in order to implement the
-``touch-each-pixel-once'' rules of wide lines and arcs.
-
-Written by Joel McCormack, Summer 1989.
-
-*/
-
-void
-miInitSpanGroup(SpanGroup * spanGroup)
-{
-    spanGroup->size = 0;
-    spanGroup->count = 0;
-    spanGroup->group = NULL;
-    spanGroup->ymin = MAXSHORT;
-    spanGroup->ymax = MINSHORT;
-}                               /* InitSpanGroup */
-
-#define YMIN(spans) (spans->points[0].y)
-#define YMAX(spans)  (spans->points[spans->count-1].y)
-
-static void
-miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
-{
-    int i, subCount, spansCount;
-    int ymin, ymax, xmin, xmax;
-    Spans *spans;
-    DDXPointPtr subPt, spansPt;
-    int *subWid, *spansWid;
-    int extra;
-
-    ymin = YMIN(sub);
-    ymax = YMAX(sub);
-    spans = spanGroup->group;
-    for (i = spanGroup->count; i; i--, spans++) {
-        if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
-            subCount = sub->count;
-            subPt = sub->points;
-            subWid = sub->widths;
-            spansCount = spans->count;
-            spansPt = spans->points;
-            spansWid = spans->widths;
-            extra = 0;
-            for (;;) {
-                while (spansCount && spansPt->y < subPt->y) {
-                    spansPt++;
-                    spansWid++;
-                    spansCount--;
-                }
-                if (!spansCount)
-                    break;
-                while (subCount && subPt->y < spansPt->y) {
-                    subPt++;
-                    subWid++;
-                    subCount--;
-                }
-                if (!subCount)
-                    break;
-                if (subPt->y == spansPt->y) {
-                    xmin = subPt->x;
-                    xmax = xmin + *subWid;
-                    if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) {
-                        ;
-                    }
-                    else if (xmin <= spansPt->x) {
-                        if (xmax >= spansPt->x + *spansWid) {
-                            memmove(spansPt, spansPt + 1,
-                                    sizeof *spansPt * (spansCount - 1));
-                            memmove(spansWid, spansWid + 1,
-                                    sizeof *spansWid * (spansCount - 1));
-                            spansPt--;
-                            spansWid--;
-                            spans->count--;
-                            extra++;
-                        }
-                        else {
-                            *spansWid = *spansWid - (xmax - spansPt->x);
-                            spansPt->x = xmax;
-                        }
-                    }
-                    else {
-                        if (xmax >= spansPt->x + *spansWid) {
-                            *spansWid = xmin - spansPt->x;
-                        }
-                        else {
-                            if (!extra) {
-                                DDXPointPtr newPt;
-                                int *newwid;
-
-#define EXTRA 8
-                                newPt =
-                                    (DDXPointPtr) realloc(spans->points,
-                                                          (spans->count +
-                                                           EXTRA) *
-                                                          sizeof(DDXPointRec));
-                                if (!newPt)
-                                    break;
-                                spansPt = newPt + (spansPt - spans->points);
-                                spans->points = newPt;
-                                newwid =
-                                    (int *) realloc(spans->widths,
-                                                    (spans->count +
-                                                     EXTRA) * sizeof(int));
-                                if (!newwid)
-                                    break;
-                                spansWid = newwid + (spansWid - spans->widths);
-                                spans->widths = newwid;
-                                extra = EXTRA;
-                            }
-                            memmove(spansPt + 1, spansPt,
-                                    sizeof *spansPt * (spansCount));
-                            memmove(spansWid + 1, spansWid,
-                                    sizeof *spansWid * (spansCount));
-                            spans->count++;
-                            extra--;
-                            *spansWid = xmin - spansPt->x;
-                            spansWid++;
-                            spansPt++;
-                            *spansWid = *spansWid - (xmax - spansPt->x);
-                            spansPt->x = xmax;
-                        }
-                    }
-                }
-                spansPt++;
-                spansWid++;
-                spansCount--;
-            }
-        }
-    }
-}
-
-void
-miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
-{
-    int ymin, ymax;
-    int spansCount;
-
-    spansCount = spans->count;
-    if (spansCount > 0) {
-        if (spanGroup->size == spanGroup->count) {
-            spanGroup->size = (spanGroup->size + 8) * 2;
-            spanGroup->group = (Spans *)
-                realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
-        }
-
-        spanGroup->group[spanGroup->count] = *spans;
-        (spanGroup->count)++;
-        ymin = spans->points[0].y;
-        if (ymin < spanGroup->ymin)
-            spanGroup->ymin = ymin;
-        ymax = spans->points[spansCount - 1].y;
-        if (ymax > spanGroup->ymax)
-            spanGroup->ymax = ymax;
-        if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
-            miSubtractSpans(otherGroup, spans);
-        }
-    }
-    else {
-        free(spans->points);
-        free(spans->widths);
-    }
-}                               /* AppendSpans */
-
-void
-miFreeSpanGroup(SpanGroup * spanGroup)
-{
-    free(spanGroup->group);
-}
-
-static void
-QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
-{
-    int x;
-    int i, j, m;
-    DDXPointPtr r;
-
-/* Always called with numSpans > 1 */
-/* Sorts only by x, as all y should be the same */
-
-#define ExchangeSpans(a, b)				    \
-{							    \
-    DDXPointRec 	tpt;				    \
-    int    		tw;				    \
-							    \
-    tpt = points[a]; points[a] = points[b]; points[b] = tpt;    \
-    tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
-}
-
-    do {
-        if (numSpans < 9) {
-            /* Do insertion sort */
-            int xprev;
-
-            xprev = points[0].x;
-            i = 1;
-            do {                /* while i != numSpans */
-                x = points[i].x;
-                if (xprev > x) {
-                    /* points[i] is out of order.  Move into proper location. */
-                    DDXPointRec tpt;
-                    int tw, k;
-
-                    for (j = 0; x >= points[j].x; j++) {
-                    }
-                    tpt = points[i];
-                    tw = widths[i];
-                    for (k = i; k != j; k--) {
-                        points[k] = points[k - 1];
-                        widths[k] = widths[k - 1];
-                    }
-                    points[j] = tpt;
-                    widths[j] = tw;
-                    x = points[i].x;
-                }               /* if out of order */
-                xprev = x;
-                i++;
-            } while (i != numSpans);
-            return;
-        }
-
-        /* Choose partition element, stick in location 0 */
-        m = numSpans / 2;
-        if (points[m].x > points[0].x)
-            ExchangeSpans(m, 0);
-        if (points[m].x > points[numSpans - 1].x)
-            ExchangeSpans(m, numSpans - 1);
-        if (points[m].x > points[0].x)
-            ExchangeSpans(m, 0);
-        x = points[0].x;
-
-        /* Partition array */
-        i = 0;
-        j = numSpans;
-        do {
-            r = &(points[i]);
-            do {
-                r++;
-                i++;
-            } while (i != numSpans && r->x < x);
-            r = &(points[j]);
-            do {
-                r--;
-                j--;
-            } while (x < r->x);
-            if (i < j)
-                ExchangeSpans(i, j);
-        } while (i < j);
-
-        /* Move partition element back to middle */
-        ExchangeSpans(0, j);
-
-        /* Recurse */
-        if (numSpans - j - 1 > 1)
-            QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
-        numSpans = j;
-    } while (numSpans > 1);
-}                               /* QuickSortSpans */
-
-static int
-UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
-{
-    int newx1, newx2, oldpt, i, y;
-    DDXPointRec *oldPoints;
-    int *oldWidths;
-    int *startNewWidths;
-
-/* Always called with numSpans > 1 */
-/* Uniquify the spans, and stash them into newPoints and newWidths.  Return the
-   number of unique spans. */
-
-    startNewWidths = newWidths;
-
-    oldPoints = spans->points;
-    oldWidths = spans->widths;
-
-    y = oldPoints->y;
-    newx1 = oldPoints->x;
-    newx2 = newx1 + *oldWidths;
-
-    for (i = spans->count - 1; i != 0; i--) {
-        oldPoints++;
-        oldWidths++;
-        oldpt = oldPoints->x;
-        if (oldpt > newx2) {
-            /* Write current span, start a new one */
-            newPoints->x = newx1;
-            newPoints->y = y;
-            *newWidths = newx2 - newx1;
-            newPoints++;
-            newWidths++;
-            newx1 = oldpt;
-            newx2 = oldpt + *oldWidths;
-        }
-        else {
-            /* extend current span, if old extends beyond new */
-            oldpt = oldpt + *oldWidths;
-            if (oldpt > newx2)
-                newx2 = oldpt;
-        }
-    }                           /* for */
-
-    /* Write final span */
-    newPoints->x = newx1;
-    *newWidths = newx2 - newx1;
-    newPoints->y = y;
-
-    return (newWidths - startNewWidths) + 1;
-}                               /* UniquifySpansX */
-
-static void
-miDisposeSpanGroup(SpanGroup * spanGroup)
-{
-    int i;
-    Spans *spans;
-
-    for (i = 0; i < spanGroup->count; i++) {
-        spans = spanGroup->group + i;
-        free(spans->points);
-        free(spans->widths);
-    }
-}
-
-void
-miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
-{
-    int i;
-    Spans *spans;
-    Spans *yspans;
-    int *ysizes;
-    int ymin, ylength;
-
-    /* Outgoing spans for one big call to FillSpans */
-    DDXPointPtr points;
-    int *widths;
-    int count;
-
-    if (spanGroup->count == 0)
-        return;
-
-    if (spanGroup->count == 1) {
-        /* Already should be sorted, unique */
-        spans = spanGroup->group;
-        (*pGC->ops->FillSpans)
-            (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
-        free(spans->points);
-        free(spans->widths);
-    }
-    else {
-        /* Yuck.  Gross.  Radix sort into y buckets, then sort x and uniquify */
-        /* This seems to be the fastest thing to do.  I've tried sorting on
-           both x and y at the same time rather than creating into all those
-           y buckets, but it was somewhat slower. */
-
-        ymin = spanGroup->ymin;
-        ylength = spanGroup->ymax - ymin + 1;
-
-        /* Allocate Spans for y buckets */
-        yspans = malloc(ylength * sizeof(Spans));
-        ysizes = malloc(ylength * sizeof(int));
-
-        if (!yspans || !ysizes) {
-            free(yspans);
-            free(ysizes);
-            miDisposeSpanGroup(spanGroup);
-            return;
-        }
-
-        for (i = 0; i != ylength; i++) {
-            ysizes[i] = 0;
-            yspans[i].count = 0;
-            yspans[i].points = NULL;
-            yspans[i].widths = NULL;
-        }
-
-        /* Go through every single span and put it into the correct bucket */
-        count = 0;
-        for (i = 0, spans = spanGroup->group;
-             i != spanGroup->count; i++, spans++) {
-            int index;
-            int j;
-
-            for (j = 0, points = spans->points, widths = spans->widths;
-                 j != spans->count; j++, points++, widths++) {
-                index = points->y - ymin;
-                if (index >= 0 && index < ylength) {
-                    Spans *newspans = &(yspans[index]);
-
-                    if (newspans->count == ysizes[index]) {
-                        DDXPointPtr newpoints;
-                        int *newwidths;
-
-                        ysizes[index] = (ysizes[index] + 8) * 2;
-                        newpoints = (DDXPointPtr) realloc(newspans->points,
-                                                          ysizes[index] *
-                                                          sizeof(DDXPointRec));
-                        newwidths =
-                            (int *) realloc(newspans->widths,
-                                            ysizes[index] * sizeof(int));
-                        if (!newpoints || !newwidths) {
-                            for (i = 0; i < ylength; i++) {
-                                free(yspans[i].points);
-                                free(yspans[i].widths);
-                            }
-                            free(yspans);
-                            free(ysizes);
-                            free(newpoints);
-                            free(newwidths);
-                            miDisposeSpanGroup(spanGroup);
-                            return;
-                        }
-                        newspans->points = newpoints;
-                        newspans->widths = newwidths;
-                    }
-                    newspans->points[newspans->count] = *points;
-                    newspans->widths[newspans->count] = *widths;
-                    (newspans->count)++;
-                }               /* if y value of span in range */
-            }                   /* for j through spans */
-            count += spans->count;
-            free(spans->points);
-            spans->points = NULL;
-            free(spans->widths);
-            spans->widths = NULL;
-        }                       /* for i thorough Spans */
-
-        /* Now sort by x and uniquify each bucket into the final array */
-        points = malloc(count * sizeof(DDXPointRec));
-        widths = malloc(count * sizeof(int));
-        if (!points || !widths) {
-            for (i = 0; i < ylength; i++) {
-                free(yspans[i].points);
-                free(yspans[i].widths);
-            }
-            free(yspans);
-            free(ysizes);
-            free(points);
-            free(widths);
-            return;
-        }
-        count = 0;
-        for (i = 0; i != ylength; i++) {
-            int ycount = yspans[i].count;
-
-            if (ycount > 0) {
-                if (ycount > 1) {
-                    QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
-                    count += UniquifySpansX
-                        (&(yspans[i]), &(points[count]), &(widths[count]));
-                }
-                else {
-                    points[count] = yspans[i].points[0];
-                    widths[count] = yspans[i].widths[0];
-                    count++;
-                }
-                free(yspans[i].points);
-                free(yspans[i].widths);
-            }
-        }
-
-        (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
-        free(points);
-        free(widths);
-        free(yspans);
-        free(ysizes);           /* use (DE)xalloc for these? */
-    }
-
-    spanGroup->count = 0;
-    spanGroup->ymin = MAXSHORT;
-    spanGroup->ymax = MINSHORT;
-}
diff --git a/mi/mispans.h b/mi/mispans.h
deleted file mode 100644
index 7c3fcef7e..000000000
--- a/mi/mispans.h
+++ /dev/null
@@ -1,83 +0,0 @@
-/***********************************************************
-
-Copyright 1989, 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 1989 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.
-
-******************************************************************/
-
-#ifndef MISPANS_H
-#define MISPANS_H
-
-typedef struct {
-    int count;                  /* number of spans                  */
-    DDXPointPtr points;         /* pointer to list of start points  */
-    int *widths;                /* pointer to list of widths        */
-} Spans;
-
-typedef struct {
-    int size;                   /* Total number of *Spans allocated     */
-    int count;                  /* Number of *Spans actually in group   */
-    Spans *group;               /* List of Spans                        */
-    int ymin, ymax;             /* Min, max y values encountered        */
-} SpanGroup;
-
-/* Initialize SpanGroup.  MUST BE DONE before use. */
-extern void miInitSpanGroup(SpanGroup *       /*spanGroup */);
-
-/* Add a Spans to a SpanGroup. The spans MUST BE in y-sorted order */
-extern void miAppendSpans(SpanGroup * /*spanGroup */ ,
-                          SpanGroup * /*otherGroup */ ,
-                          Spans *     /*spans */);
-
-/* Paint a span group, insuring that each pixel is painted at most once */
-extern void miFillUniqueSpanGroup(DrawablePtr /*pDraw */ ,
-                                  GCPtr /*pGC */ ,
-                                  SpanGroup * /*spanGroup */);
-
-/* Free up data in a span group.  MUST BE DONE or you'll suffer memory leaks */
-extern void miFreeSpanGroup(SpanGroup *       /*spanGroup */);
-
-/* Rops which must use span groups */
-#define miSpansCarefulRop(rop)	(((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2)
-#define miSpansEasyRop(rop)	(!miSpansCarefulRop(rop))
-
-#endif                          /* MISPANS_H */
diff --git a/mi/miwideline.c b/mi/miwideline.c
index 295a05a32..452d74fc1 100644
--- a/mi/miwideline.c
+++ b/mi/miwideline.c
@@ -24,6 +24,25 @@ 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 1989 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.
 */
 
 /* Author:  Keith Packard, MIT X Consortium */
@@ -52,6 +71,505 @@ from The Open Group.
 #include "miwideline.h"
 #include "mi.h"
 
+#if 0
+#ifdef HAVE_DIX_CONFIG_H
+#include <dix-config.h>
+#endif
+
+#include "misc.h"
+#include "pixmapstr.h"
+#include "gcstruct.h"
+#endif
+
+typedef struct {
+    int count;                  /* number of spans                  */
+    DDXPointPtr points;         /* pointer to list of start points  */
+    int *widths;                /* pointer to list of widths        */
+} Spans;
+
+typedef struct {
+    int size;                   /* Total number of *Spans allocated     */
+    int count;                  /* Number of *Spans actually in group   */
+    Spans *group;               /* List of Spans                        */
+    int ymin, ymax;             /* Min, max y values encountered        */
+} SpanGroup;
+
+/* Rops which must use span groups */
+#define miSpansCarefulRop(rop)	(((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2)
+#define miSpansEasyRop(rop)	(!miSpansCarefulRop(rop))
+
+/*
+
+These routines maintain lists of Spans, in order to implement the
+``touch-each-pixel-once'' rules of wide lines and arcs.
+
+Written by Joel McCormack, Summer 1989.
+
+*/
+
+static void
+miInitSpanGroup(SpanGroup * spanGroup)
+{
+    spanGroup->size = 0;
+    spanGroup->count = 0;
+    spanGroup->group = NULL;
+    spanGroup->ymin = MAXSHORT;
+    spanGroup->ymax = MINSHORT;
+}                               /* InitSpanGroup */
+
+#define YMIN(spans) (spans->points[0].y)
+#define YMAX(spans)  (spans->points[spans->count-1].y)
+
+static void
+miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
+{
+    int i, subCount, spansCount;
+    int ymin, ymax, xmin, xmax;
+    Spans *spans;
+    DDXPointPtr subPt, spansPt;
+    int *subWid, *spansWid;
+    int extra;
+
+    ymin = YMIN(sub);
+    ymax = YMAX(sub);
+    spans = spanGroup->group;
+    for (i = spanGroup->count; i; i--, spans++) {
+        if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
+            subCount = sub->count;
+            subPt = sub->points;
+            subWid = sub->widths;
+            spansCount = spans->count;
+            spansPt = spans->points;
+            spansWid = spans->widths;
+            extra = 0;
+            for (;;) {
+                while (spansCount && spansPt->y < subPt->y) {
+                    spansPt++;
+                    spansWid++;
+                    spansCount--;
+                }
+                if (!spansCount)
+                    break;
+                while (subCount && subPt->y < spansPt->y) {
+                    subPt++;
+                    subWid++;
+                    subCount--;
+                }
+                if (!subCount)
+                    break;
+                if (subPt->y == spansPt->y) {
+                    xmin = subPt->x;
+                    xmax = xmin + *subWid;
+                    if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) {
+                        ;
+                    }
+                    else if (xmin <= spansPt->x) {
+                        if (xmax >= spansPt->x + *spansWid) {
+                            memmove(spansPt, spansPt + 1,
+                                    sizeof *spansPt * (spansCount - 1));
+                            memmove(spansWid, spansWid + 1,
+                                    sizeof *spansWid * (spansCount - 1));
+                            spansPt--;
+                            spansWid--;
+                            spans->count--;
+                            extra++;
+                        }
+                        else {
+                            *spansWid = *spansWid - (xmax - spansPt->x);
+                            spansPt->x = xmax;
+                        }
+                    }
+                    else {
+                        if (xmax >= spansPt->x + *spansWid) {
+                            *spansWid = xmin - spansPt->x;
+                        }
+                        else {
+                            if (!extra) {
+                                DDXPointPtr newPt;
+                                int *newwid;
+
+#define EXTRA 8
+                                newPt =
+                                    (DDXPointPtr) realloc(spans->points,
+                                                          (spans->count +
+                                                           EXTRA) *
+                                                          sizeof(DDXPointRec));
+                                if (!newPt)
+                                    break;
+                                spansPt = newPt + (spansPt - spans->points);
+                                spans->points = newPt;
+                                newwid =
+                                    (int *) realloc(spans->widths,
+                                                    (spans->count +
+                                                     EXTRA) * sizeof(int));
+                                if (!newwid)
+                                    break;
+                                spansWid = newwid + (spansWid - spans->widths);
+                                spans->widths = newwid;
+                                extra = EXTRA;
+                            }
+                            memmove(spansPt + 1, spansPt,
+                                    sizeof *spansPt * (spansCount));
+                            memmove(spansWid + 1, spansWid,
+                                    sizeof *spansWid * (spansCount));
+                            spans->count++;
+                            extra--;
+                            *spansWid = xmin - spansPt->x;
+                            spansWid++;
+                            spansPt++;
+                            *spansWid = *spansWid - (xmax - spansPt->x);
+                            spansPt->x = xmax;
+                        }
+                    }
+                }
+                spansPt++;
+                spansWid++;
+                spansCount--;
+            }
+        }
+    }
+}
+
+static void
+miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
+{
+    int ymin, ymax;
+    int spansCount;
+
+    spansCount = spans->count;
+    if (spansCount > 0) {
+        if (spanGroup->size == spanGroup->count) {
+            spanGroup->size = (spanGroup->size + 8) * 2;
+            spanGroup->group = (Spans *)
+                realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
+        }
+
+        spanGroup->group[spanGroup->count] = *spans;
+        (spanGroup->count)++;
+        ymin = spans->points[0].y;
+        if (ymin < spanGroup->ymin)
+            spanGroup->ymin = ymin;
+        ymax = spans->points[spansCount - 1].y;
+        if (ymax > spanGroup->ymax)
+            spanGroup->ymax = ymax;
+        if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
+            miSubtractSpans(otherGroup, spans);
+        }
+    }
+    else {
+        free(spans->points);
+        free(spans->widths);
+    }
+}                               /* AppendSpans */
+
+static void
+miFreeSpanGroup(SpanGroup * spanGroup)
+{
+    free(spanGroup->group);
+}
+
+static void
+QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
+{
+    int x;
+    int i, j, m;
+    DDXPointPtr r;
+
+/* Always called with numSpans > 1 */
+/* Sorts only by x, as all y should be the same */
+
+#define ExchangeSpans(a, b)				    \
+{							    \
+    DDXPointRec 	tpt;				    \
+    int    		tw;				    \
+							    \
+    tpt = points[a]; points[a] = points[b]; points[b] = tpt;    \
+    tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
+}
+
+    do {
+        if (numSpans < 9) {
+            /* Do insertion sort */
+            int xprev;
+
+            xprev = points[0].x;
+            i = 1;
+            do {                /* while i != numSpans */
+                x = points[i].x;
+                if (xprev > x) {
+                    /* points[i] is out of order.  Move into proper location. */
+                    DDXPointRec tpt;
+                    int tw, k;
+
+                    for (j = 0; x >= points[j].x; j++) {
+                    }
+                    tpt = points[i];
+                    tw = widths[i];
+                    for (k = i; k != j; k--) {
+                        points[k] = points[k - 1];
+                        widths[k] = widths[k - 1];
+                    }
+                    points[j] = tpt;
+                    widths[j] = tw;
+                    x = points[i].x;
+                }               /* if out of order */
+                xprev = x;
+                i++;
+            } while (i != numSpans);
+            return;
+        }
+
+        /* Choose partition element, stick in location 0 */
+        m = numSpans / 2;
+        if (points[m].x > points[0].x)
+            ExchangeSpans(m, 0);
+        if (points[m].x > points[numSpans - 1].x)
+            ExchangeSpans(m, numSpans - 1);
+        if (points[m].x > points[0].x)
+            ExchangeSpans(m, 0);
+        x = points[0].x;
+
+        /* Partition array */
+        i = 0;
+        j = numSpans;
+        do {
+            r = &(points[i]);
+            do {
+                r++;
+                i++;
+            } while (i != numSpans && r->x < x);
+            r = &(points[j]);
+            do {
+                r--;
+                j--;
+            } while (x < r->x);
+            if (i < j)
+                ExchangeSpans(i, j);
+        } while (i < j);
+
+        /* Move partition element back to middle */
+        ExchangeSpans(0, j);
+
+        /* Recurse */
+        if (numSpans - j - 1 > 1)
+            QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
+        numSpans = j;
+    } while (numSpans > 1);
+}                               /* QuickSortSpans */
+
+static int
+UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
+{
+    int newx1, newx2, oldpt, i, y;
+    DDXPointRec *oldPoints;
+    int *oldWidths;
+    int *startNewWidths;
+
+/* Always called with numSpans > 1 */
+/* Uniquify the spans, and stash them into newPoints and newWidths.  Return the
+   number of unique spans. */
+
+    startNewWidths = newWidths;
+
+    oldPoints = spans->points;
+    oldWidths = spans->widths;
+
+    y = oldPoints->y;
+    newx1 = oldPoints->x;
+    newx2 = newx1 + *oldWidths;
+
+    for (i = spans->count - 1; i != 0; i--) {
+        oldPoints++;
+        oldWidths++;
+        oldpt = oldPoints->x;
+        if (oldpt > newx2) {
+            /* Write current span, start a new one */
+            newPoints->x = newx1;
+            newPoints->y = y;
+            *newWidths = newx2 - newx1;
+            newPoints++;
+            newWidths++;
+            newx1 = oldpt;
+            newx2 = oldpt + *oldWidths;
+        }
+        else {
+            /* extend current span, if old extends beyond new */
+            oldpt = oldpt + *oldWidths;
+            if (oldpt > newx2)
+                newx2 = oldpt;
+        }
+    }                           /* for */
+
+    /* Write final span */
+    newPoints->x = newx1;
+    *newWidths = newx2 - newx1;
+    newPoints->y = y;
+
+    return (newWidths - startNewWidths) + 1;
+}                               /* UniquifySpansX */
+
+static void
+miDisposeSpanGroup(SpanGroup * spanGroup)
+{
+    int i;
+    Spans *spans;
+
+    for (i = 0; i < spanGroup->count; i++) {
+        spans = spanGroup->group + i;
+        free(spans->points);
+        free(spans->widths);
+    }
+}
+
+static void
+miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
+{
+    int i;
+    Spans *spans;
+    Spans *yspans;
+    int *ysizes;
+    int ymin, ylength;
+
+    /* Outgoing spans for one big call to FillSpans */
+    DDXPointPtr points;
+    int *widths;
+    int count;
+
+    if (spanGroup->count == 0)
+        return;
+
+    if (spanGroup->count == 1) {
+        /* Already should be sorted, unique */
+        spans = spanGroup->group;
+        (*pGC->ops->FillSpans)
+            (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
+        free(spans->points);
+        free(spans->widths);
+    }
+    else {
+        /* Yuck.  Gross.  Radix sort into y buckets, then sort x and uniquify */
+        /* This seems to be the fastest thing to do.  I've tried sorting on
+           both x and y at the same time rather than creating into all those
+           y buckets, but it was somewhat slower. */
+
+        ymin = spanGroup->ymin;
+        ylength = spanGroup->ymax - ymin + 1;
+
+        /* Allocate Spans for y buckets */
+        yspans = malloc(ylength * sizeof(Spans));
+        ysizes = malloc(ylength * sizeof(int));
+
+        if (!yspans || !ysizes) {
+            free(yspans);
+            free(ysizes);
+            miDisposeSpanGroup(spanGroup);
+            return;
+        }
+
+        for (i = 0; i != ylength; i++) {
+            ysizes[i] = 0;
+            yspans[i].count = 0;
+            yspans[i].points = NULL;
+            yspans[i].widths = NULL;
+        }
+
+        /* Go through every single span and put it into the correct bucket */
+        count = 0;
+        for (i = 0, spans = spanGroup->group;
+             i != spanGroup->count; i++, spans++) {
+            int index;
+            int j;
+
+            for (j = 0, points = spans->points, widths = spans->widths;
+                 j != spans->count; j++, points++, widths++) {
+                index = points->y - ymin;
+                if (index >= 0 && index < ylength) {
+                    Spans *newspans = &(yspans[index]);
+
+                    if (newspans->count == ysizes[index]) {
+                        DDXPointPtr newpoints;
+                        int *newwidths;
+
+                        ysizes[index] = (ysizes[index] + 8) * 2;
+                        newpoints = (DDXPointPtr) realloc(newspans->points,
+                                                          ysizes[index] *
+                                                          sizeof(DDXPointRec));
+                        newwidths =
+                            (int *) realloc(newspans->widths,
+                                            ysizes[index] * sizeof(int));
+                        if (!newpoints || !newwidths) {
+                            for (i = 0; i < ylength; i++) {
+                                free(yspans[i].points);
+                                free(yspans[i].widths);
+                            }
+                            free(yspans);
+                            free(ysizes);
+                            free(newpoints);
+                            free(newwidths);
+                            miDisposeSpanGroup(spanGroup);
+                            return;
+                        }
+                        newspans->points = newpoints;
+                        newspans->widths = newwidths;
+                    }
+                    newspans->points[newspans->count] = *points;
+                    newspans->widths[newspans->count] = *widths;
+                    (newspans->count)++;
+                }               /* if y value of span in range */
+            }                   /* for j through spans */
+            count += spans->count;
+            free(spans->points);
+            spans->points = NULL;
+            free(spans->widths);
+            spans->widths = NULL;
+        }                       /* for i thorough Spans */
+
+        /* Now sort by x and uniquify each bucket into the final array */
+        points = malloc(count * sizeof(DDXPointRec));
+        widths = malloc(count * sizeof(int));
+        if (!points || !widths) {
+            for (i = 0; i < ylength; i++) {
+                free(yspans[i].points);
+                free(yspans[i].widths);
+            }
+            free(yspans);
+            free(ysizes);
+            free(points);
+            free(widths);
+            return;
+        }
+        count = 0;
+        for (i = 0; i != ylength; i++) {
+            int ycount = yspans[i].count;
+
+            if (ycount > 0) {
+                if (ycount > 1) {
+                    QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
+                    count += UniquifySpansX
+                        (&(yspans[i]), &(points[count]), &(widths[count]));
+                }
+                else {
+                    points[count] = yspans[i].points[0];
+                    widths[count] = yspans[i].widths[0];
+                    count++;
+                }
+                free(yspans[i].points);
+                free(yspans[i].widths);
+            }
+        }
+
+        (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
+        free(points);
+        free(widths);
+        free(yspans);
+        free(ysizes);           /* use (DE)xalloc for these? */
+    }
+
+    spanGroup->count = 0;
+    spanGroup->ymin = MAXSHORT;
+    spanGroup->ymax = MINSHORT;
+}
+
 static Bool
 InitSpans(Spans * spans, size_t nspans)
 {
diff --git a/mi/miwideline.h b/mi/miwideline.h
index a9f2740b5..88bc3d6c8 100644
--- a/mi/miwideline.h
+++ b/mi/miwideline.h
@@ -28,7 +28,6 @@ from The Open Group.
 
 /* Author:  Keith Packard, MIT X Consortium */
 
-#include "mispans.h"
 #include "mifpoly.h"            /* for ICEIL */
 
 /*