[deb_xorg-server.git] / mi / mispans.c

/***********************************************************

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;
}
Commit	Line	Data
a09e091a JB	1	/***********************************************************
	2
	3	Copyright 1989, 1998 The Open Group
	4
	5	Permission to use, copy, modify, distribute, and sell this software and its
	6	documentation for any purpose is hereby granted without fee, provided that
	7	the above copyright notice appear in all copies and that both that
	8	copyright notice and this permission notice appear in supporting
	9	documentation.
	10
	11	The above copyright notice and this permission notice shall be included in
	12	all copies or substantial portions of the Software.
	13
	14	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	15	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	16	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	17	OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
	18	AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
	19	CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	20
	21	Except as contained in this notice, the name of The Open Group shall not be
	22	used in advertising or otherwise to promote the sale, use or other dealings
	23	in this Software without prior written authorization from The Open Group.
	24
	25	Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
	26
	27	All Rights Reserved
	28
	29	Permission to use, copy, modify, and distribute this software and its
	30	documentation for any purpose and without fee is hereby granted,
	31	provided that the above copyright notice appear in all copies and that
	32	both that copyright notice and this permission notice appear in
	33	supporting documentation, and that the name of Digital not be
	34	used in advertising or publicity pertaining to distribution of the
	35	software without specific, written prior permission.
	36
	37	DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
	38	ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
	39	DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
	40	ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
	41	WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
	42	ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
	43	SOFTWARE.
	44
	45	******************************************************************/
	46
	47	#ifdef HAVE_DIX_CONFIG_H
	48	#include <dix-config.h>
	49	#endif
	50
	51	#include "misc.h"
	52	#include "pixmapstr.h"
	53	#include "gcstruct.h"
	54	#include "mispans.h"
	55
	56	/*
	57
	58	These routines maintain lists of Spans, in order to implement the
	59	``touch-each-pixel-once'' rules of wide lines and arcs.
	60
	61	Written by Joel McCormack, Summer 1989.
	62
	63	*/
	64
65	void
66	miInitSpanGroup(SpanGroup * spanGroup)
67	{
68	spanGroup->size = 0;
69	spanGroup->count = 0;
70	spanGroup->group = NULL;
71	spanGroup->ymin = MAXSHORT;
72	spanGroup->ymax = MINSHORT;
73	} /* InitSpanGroup */
74
75	#define YMIN(spans) (spans->points[0].y)
76	#define YMAX(spans) (spans->points[spans->count-1].y)
77
78	static void
79	miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
80	{
81	int i, subCount, spansCount;
82	int ymin, ymax, xmin, xmax;
83	Spans *spans;
84	DDXPointPtr subPt, spansPt;
85	int subWid, spansWid;
86	int extra;
87
88	ymin = YMIN(sub);
89	ymax = YMAX(sub);
90	spans = spanGroup->group;
91	for (i = spanGroup->count; i; i--, spans++) {
92	if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
93	subCount = sub->count;
94	subPt = sub->points;
95	subWid = sub->widths;
96	spansCount = spans->count;
97	spansPt = spans->points;
98	spansWid = spans->widths;
99	extra = 0;
100	for (;;) {
101	while (spansCount && spansPt->y < subPt->y) {
102	spansPt++;
103	spansWid++;
104	spansCount--;
105	}
106	if (!spansCount)
107	break;
108	while (subCount && subPt->y < spansPt->y) {
109	subPt++;
110	subWid++;
111	subCount--;
112	}
113	if (!subCount)
114	break;
115	if (subPt->y == spansPt->y) {
116	xmin = subPt->x;
117	xmax = xmin + *subWid;
118	if (xmin >= spansPt->x + *spansWid \|\| spansPt->x >= xmax) {
119	;
120	}
121	else if (xmin <= spansPt->x) {
122	if (xmax >= spansPt->x + *spansWid) {
123	memmove(spansPt, spansPt + 1,
124	sizeof spansPt (spansCount - 1));
125	memmove(spansWid, spansWid + 1,
126	sizeof spansWid (spansCount - 1));
127	spansPt--;
128	spansWid--;
129	spans->count--;
130	extra++;
131	}
132	else {
133	spansWid = spansWid - (xmax - spansPt->x);
134	spansPt->x = xmax;
135	}
136	}
137	else {
138	if (xmax >= spansPt->x + *spansWid) {
139	*spansWid = xmin - spansPt->x;
140	}
141	else {
142	if (!extra) {
143	DDXPointPtr newPt;
144	int *newwid;
145
146	#define EXTRA 8
147	newPt =
148	(DDXPointPtr) realloc(spans->points,
149	(spans->count +
150	EXTRA) *
151	sizeof(DDXPointRec));
152	if (!newPt)
153	break;
154	spansPt = newPt + (spansPt - spans->points);
155	spans->points = newPt;
156	newwid =
157	(int *) realloc(spans->widths,
158	(spans->count +
159	EXTRA) * sizeof(int));
160	if (!newwid)
161	break;
162	spansWid = newwid + (spansWid - spans->widths);
163	spans->widths = newwid;
164	extra = EXTRA;
165	}
166	memmove(spansPt + 1, spansPt,
167	sizeof spansPt (spansCount));
168	memmove(spansWid + 1, spansWid,
169	sizeof spansWid (spansCount));
170	spans->count++;
171	extra--;
172	*spansWid = xmin - spansPt->x;
173	spansWid++;
174	spansPt++;
175	spansWid = spansWid - (xmax - spansPt->x);
176	spansPt->x = xmax;
177	}
178	}
179	}
180	spansPt++;
181	spansWid++;
182	spansCount--;
183	}
184	}
185	}
186	}
187
188	void
189	miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
190	{
191	int ymin, ymax;
192	int spansCount;
193
194	spansCount = spans->count;
195	if (spansCount > 0) {
196	if (spanGroup->size == spanGroup->count) {
197	spanGroup->size = (spanGroup->size + 8) * 2;
198	spanGroup->group = (Spans *)
199	realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
200	}
201
202	spanGroup->group[spanGroup->count] = *spans;
203	(spanGroup->count)++;
204	ymin = spans->points[0].y;
205	if (ymin < spanGroup->ymin)
206	spanGroup->ymin = ymin;
207	ymax = spans->points[spansCount - 1].y;
208	if (ymax > spanGroup->ymax)
209	spanGroup->ymax = ymax;
210	if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
211	miSubtractSpans(otherGroup, spans);
212	}
213	}
214	else {
215	free(spans->points);
216	free(spans->widths);
217	}
218	} /* AppendSpans */
219
220	void
221	miFreeSpanGroup(SpanGroup * spanGroup)
222	{
223	free(spanGroup->group);
224	}
225
226	static void
227	QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
228	{
229	int x;
230	int i, j, m;
231	DDXPointPtr r;
232
233	/* Always called with numSpans > 1 */
234	/* Sorts only by x, as all y should be the same */
235
236	#define ExchangeSpans(a, b) \
237	{ \
238	DDXPointRec tpt; \
239	int tw; \
240	\
241	tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
242	tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
243	}
244
245	do {
246	if (numSpans < 9) {
247	/* Do insertion sort */
248	int xprev;
249
250	xprev = points[0].x;
251	i = 1;
252	do { /* while i != numSpans */
253	x = points[i].x;
254	if (xprev > x) {
255	/* points[i] is out of order. Move into proper location. */
256	DDXPointRec tpt;
257	int tw, k;
258
259	for (j = 0; x >= points[j].x; j++) {
260	}
261	tpt = points[i];
262	tw = widths[i];
263	for (k = i; k != j; k--) {
264	points[k] = points[k - 1];
265	widths[k] = widths[k - 1];
266	}
267	points[j] = tpt;
268	widths[j] = tw;
269	x = points[i].x;
270	} /* if out of order */
271	xprev = x;
272	i++;
273	} while (i != numSpans);
274	return;
275	}
276
277	/* Choose partition element, stick in location 0 */
278	m = numSpans / 2;
279	if (points[m].x > points[0].x)
280	ExchangeSpans(m, 0);
281	if (points[m].x > points[numSpans - 1].x)
282	ExchangeSpans(m, numSpans - 1);
283	if (points[m].x > points[0].x)
284	ExchangeSpans(m, 0);
285	x = points[0].x;
286
287	/* Partition array */
288	i = 0;
289	j = numSpans;
290	do {
291	r = &(points[i]);
292	do {
293	r++;
294	i++;
295	} while (i != numSpans && r->x < x);
296	r = &(points[j]);
297	do {
298	r--;
299	j--;
300	} while (x < r->x);
301	if (i < j)
302	ExchangeSpans(i, j);
303	} while (i < j);
304
305	/* Move partition element back to middle */
306	ExchangeSpans(0, j);
307
308	/* Recurse */
309	if (numSpans - j - 1 > 1)
310	QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
311	numSpans = j;
312	} while (numSpans > 1);
313	} /* QuickSortSpans */
314
315	static int
316	UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
317	{
318	int newx1, newx2, oldpt, i, y;
319	DDXPointRec *oldPoints;
320	int *oldWidths;
321	int *startNewWidths;
322
323	/* Always called with numSpans > 1 */
324	/* Uniquify the spans, and stash them into newPoints and newWidths. Return the
325	number of unique spans. */
326
327	startNewWidths = newWidths;
328
329	oldPoints = spans->points;
330	oldWidths = spans->widths;
331
332	y = oldPoints->y;
333	newx1 = oldPoints->x;
334	newx2 = newx1 + *oldWidths;
335
336	for (i = spans->count - 1; i != 0; i--) {
337	oldPoints++;
338	oldWidths++;
339	oldpt = oldPoints->x;
340	if (oldpt > newx2) {
341	/* Write current span, start a new one */
342	newPoints->x = newx1;
343	newPoints->y = y;
344	*newWidths = newx2 - newx1;
345	newPoints++;
346	newWidths++;
347	newx1 = oldpt;
348	newx2 = oldpt + *oldWidths;
349	}
350	else {
351	/* extend current span, if old extends beyond new */
352	oldpt = oldpt + *oldWidths;
353	if (oldpt > newx2)
354	newx2 = oldpt;
355	}
356	} /* for */
357
358	/* Write final span */
359	newPoints->x = newx1;
360	*newWidths = newx2 - newx1;
361	newPoints->y = y;
362
363	return (newWidths - startNewWidths) + 1;
364	} /* UniquifySpansX */
365
366	static void
367	miDisposeSpanGroup(SpanGroup * spanGroup)
368	{
369	int i;
370	Spans *spans;
371
372	for (i = 0; i < spanGroup->count; i++) {
373	spans = spanGroup->group + i;
374	free(spans->points);
375	free(spans->widths);
376	}
377	}
378
379	void
380	miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
381	{
382	int i;
383	Spans *spans;
384	Spans *yspans;
385	int *ysizes;
386	int ymin, ylength;
387
388	/* Outgoing spans for one big call to FillSpans */
389	DDXPointPtr points;
390	int *widths;
391	int count;
392
393	if (spanGroup->count == 0)
394	return;
395
396	if (spanGroup->count == 1) {
397	/* Already should be sorted, unique */
398	spans = spanGroup->group;
399	(*pGC->ops->FillSpans)
400	(pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
401	free(spans->points);
402	free(spans->widths);
403	}
404	else {
405	/* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */
406	/* This seems to be the fastest thing to do. I've tried sorting on
407	both x and y at the same time rather than creating into all those
408	y buckets, but it was somewhat slower. */
409
410	ymin = spanGroup->ymin;
411	ylength = spanGroup->ymax - ymin + 1;
412
413	/* Allocate Spans for y buckets */
414	yspans = malloc(ylength * sizeof(Spans));
415	ysizes = malloc(ylength * sizeof(int));
416
417	if (!yspans \|\| !ysizes) {
418	free(yspans);
419	free(ysizes);
420	miDisposeSpanGroup(spanGroup);
421	return;
422	}
423
424	for (i = 0; i != ylength; i++) {
425	ysizes[i] = 0;
426	yspans[i].count = 0;
427	yspans[i].points = NULL;
428	yspans[i].widths = NULL;
429	}
430
431	/* Go through every single span and put it into the correct bucket */
432	count = 0;
433	for (i = 0, spans = spanGroup->group;
434	i != spanGroup->count; i++, spans++) {
435	int index;
436	int j;
437
438	for (j = 0, points = spans->points, widths = spans->widths;
439	j != spans->count; j++, points++, widths++) {
440	index = points->y - ymin;
441	if (index >= 0 && index < ylength) {
442	Spans *newspans = &(yspans[index]);
443
444	if (newspans->count == ysizes[index]) {
445	DDXPointPtr newpoints;
446	int *newwidths;
447
448	ysizes[index] = (ysizes[index] + 8) * 2;
449	newpoints = (DDXPointPtr) realloc(newspans->points,
450	ysizes[index] *
451	sizeof(DDXPointRec));
452	newwidths =
453	(int *) realloc(newspans->widths,
454	ysizes[index] * sizeof(int));
455	if (!newpoints \|\| !newwidths) {
456	for (i = 0; i < ylength; i++) {
457	free(yspans[i].points);
458	free(yspans[i].widths);
459	}
460	free(yspans);
461	free(ysizes);
462	free(newpoints);
463	free(newwidths);
464	miDisposeSpanGroup(spanGroup);
465	return;
466	}
467	newspans->points = newpoints;
468	newspans->widths = newwidths;
469	}
470	newspans->points[newspans->count] = *points;
471	newspans->widths[newspans->count] = *widths;
472	(newspans->count)++;
473	} /* if y value of span in range */
474	} /* for j through spans */
475	count += spans->count;
476	free(spans->points);
477	spans->points = NULL;
478	free(spans->widths);
479	spans->widths = NULL;
480	} /* for i thorough Spans */
481
482	/* Now sort by x and uniquify each bucket into the final array */
483	points = malloc(count * sizeof(DDXPointRec));
484	widths = malloc(count * sizeof(int));
485	if (!points \|\| !widths) {
486	for (i = 0; i < ylength; i++) {
487	free(yspans[i].points);
488	free(yspans[i].widths);
489	}
490	free(yspans);
491	free(ysizes);
492	free(points);
493	free(widths);
494	return;
495	}
496	count = 0;
497	for (i = 0; i != ylength; i++) {
498	int ycount = yspans[i].count;
499
500	if (ycount > 0) {
501	if (ycount > 1) {
502	QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
503	count += UniquifySpansX
504	(&(yspans[i]), &(points[count]), &(widths[count]));
505	}
506	else {
507	points[count] = yspans[i].points[0];
508	widths[count] = yspans[i].widths[0];
509	count++;
510	}
511	free(yspans[i].points);
512	free(yspans[i].widths);
513	}
514	}
515
516	(*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
517	free(points);
518	free(widths);
519	free(yspans);
520	free(ysizes); /* use (DE)xalloc for these? */
521	}
522
523	spanGroup->count = 0;
524	spanGroup->ymin = MAXSHORT;
525	spanGroup->ymax = MINSHORT;
526	}