Merge remote-tracking branch 'origin/released'

Conflicts:
	fontconfig/.gitignore
	libX11/src/ConvSel.c
	libX11/src/CrGlCur.c
	libX11/src/CrWindow.c
	libX11/src/GetDflt.c
	libX11/src/Window.c
	libX11/src/xlibi18n/XimProto.h
	libX11/src/xlibi18n/lcDynamic.c
	libxcb/src/.gitignore
	libxcb/src/xcb_ext.c
	libxcb/src/xcb_xid.c
	mesalib/src/glsl/.gitignore
	mesalib/src/glsl/glcpp/.gitignore
	mesalib/src/mapi/glapi/gen/glX_API.xml
	mesalib/src/mapi/glapi/glapi_getproc.c
	mesalib/src/mesa/main/.gitignore
	mesalib/src/mesa/main/syncobj.c
	mesalib/src/mesa/program/.gitignore
	xkbcomp/listing.c
	xkbcomp/xkbpath.c
	xorg-server/.gitignore
	xorg-server/Xext/xvmain.c
	xorg-server/dix/dispatch.c
	xorg-server/hw/xwin/glx/winpriv.h
	xorg-server/hw/xwin/winprefsyacc.y
	xorg-server/hw/xwin/winscrinit.c
	xorg-server/xkeyboard-config/rules/bin/ml1_s.sh
	xorg-server/xkeyboard-config/rules/bin/ml1v1_s.sh
	xorg-server/xkeyboard-config/rules/bin/ml1v_s.sh
	xorg-server/xkeyboard-config/rules/bin/ml_s.sh
	xorg-server/xkeyboard-config/rules/bin/mlv_s.sh
	xorg-server/xkeyboard-config/rules/compat/.gitignore

1 files changed, 638 insertions, 638 deletions

diff --git a/libX11/src/PolyReg.c b/libX11/src/PolyReg.c
index 74c8765fe..af367cf6f 100644
--- a/libX11/src/PolyReg.c
+++ b/libX11/src/PolyReg.c
@@ -1,638 +1,638 @@
-/************************************************************************
-
-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.
-
-************************************************************************/
-
-#define LARGE_COORDINATE 1000000
-#define SMALL_COORDINATE -LARGE_COORDINATE
-
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
-#include "Xlibint.h"
-#include "Xutil.h"
-#include <X11/Xregion.h>
-#include "poly.h"
-
-/*
- *     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 void
-InsertEdgeInET(
-    EdgeTable *ET,
-    EdgeTableEntry *ETE,
-    int scanline,
-    ScanLineListBlock **SLLBlock,
-    int *iSLLBlock)
-{
-    register EdgeTableEntry *start, *prev;
-    register 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 =
-		  (ScanLineListBlock *)Xmalloc(sizeof(ScanLineListBlock));
-            (*SLLBlock)->next = tmpSLLBlock;
-            tmpSLLBlock->next = (ScanLineListBlock *)NULL;
-            *SLLBlock = tmpSLLBlock;
-            *iSLLBlock = 0;
-        }
-        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
-
-        pSLL->next = pPrevSLL->next;
-        pSLL->edgelist = (EdgeTableEntry *)NULL;
-        pPrevSLL->next = pSLL;
-    }
-    pSLL->scanline = scanline;
-
-    /*
-     * now insert the edge in the right bucket
-     */
-    prev = (EdgeTableEntry *)NULL;
-    start = pSLL->edgelist;
-    while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
-    {
-        prev = start;
-        start = start->next;
-    }
-    ETE->next = start;
-
-    if (prev)
-        prev->next = ETE;
-    else
-        pSLL->edgelist = ETE;
-}
-
-/*
- *     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 void
-CreateETandAET(
-    register int count,
-    register XPoint *pts,
-    EdgeTable *ET,
-    EdgeTableEntry *AET,
-    register EdgeTableEntry *pETEs,
-    ScanLineListBlock   *pSLLBlock)
-{
-    register XPoint *top, *bottom;
-    register XPoint *PrevPt, *CurrPt;
-    int iSLLBlock = 0;
-    int dy;
-
-    if (count < 2)  return;
-
-    /*
-     *  initialize the Active Edge Table
-     */
-    AET->next = (EdgeTableEntry *)NULL;
-    AET->back = (EdgeTableEntry *)NULL;
-    AET->nextWETE = (EdgeTableEntry *)NULL;
-    AET->bres.minor_axis = SMALL_COORDINATE;
-
-    /*
-     *  initialize the Edge Table.
-     */
-    ET->scanlines.next = (ScanLineList *)NULL;
-    ET->ymax = SMALL_COORDINATE;
-    ET->ymin = LARGE_COORDINATE;
-    pSLLBlock->next = (ScanLineListBlock *)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);
-
-            InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
-
-	    if (PrevPt->y > ET->ymax)
-		ET->ymax = PrevPt->y;
-	    if (PrevPt->y < ET->ymin)
-		ET->ymin = PrevPt->y;
-            pETEs++;
-        }
-
-        PrevPt = CurrPt;
-    }
-}
-
-/*
- *     loadAET
- *
- *     This routine moves EdgeTableEntries from the
- *     EdgeTable into the Active Edge Table,
- *     leaving them sorted by smaller x coordinate.
- *
- */
-
-static void
-loadAET(
-    register EdgeTableEntry *AET,
-    register EdgeTableEntry *ETEs)
-{
-    register EdgeTableEntry *pPrevAET;
-    register EdgeTableEntry *tmp;
-
-    pPrevAET = AET;
-    AET = AET->next;
-    while (ETEs)
-    {
-        while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
-        {
-            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
-computeWAET(
-    register EdgeTableEntry *AET)
-{
-    register EdgeTableEntry *pWETE;
-    register int inside = 1;
-    register int isInside = 0;
-
-    AET->nextWETE = (EdgeTableEntry *)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 = (EdgeTableEntry *)NULL;
-}
-
-/*
- *     InsertionSort
- *
- *     Just a simple insertion sort using
- *     pointers and back pointers to sort the Active
- *     Edge Table.
- *
- */
-
-static int
-InsertionSort(
-    register EdgeTableEntry *AET)
-{
-    register EdgeTableEntry *pETEchase;
-    register EdgeTableEntry *pETEinsert;
-    register EdgeTableEntry *pETEchaseBackTMP;
-    register int changed = 0;
-
-    AET = AET->next;
-    while (AET)
-    {
-        pETEinsert = AET;
-        pETEchase = AET;
-        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
-            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.
- */
-static void
-FreeStorage(
-    register ScanLineListBlock   *pSLLBlock)
-{
-    register ScanLineListBlock   *tmpSLLBlock;
-
-    while (pSLLBlock)
-    {
-        tmpSLLBlock = pSLLBlock->next;
-        Xfree((char *)pSLLBlock);
-        pSLLBlock = tmpSLLBlock;
-    }
-}
-
-/*
- *     Create an array of rectangles from a list of points.
- *     If indeed these things (POINTS, RECTS) are the same,
- *     then this proc is still needed, because it allocates
- *     storage for the array, which was allocated on the
- *     stack by the calling procedure.
- *
- */
-static int PtsToRegion(
-    register int numFullPtBlocks,
-    register int iCurPtBlock,
-    POINTBLOCK *FirstPtBlock,
-    REGION *reg)
-{
-    register BOX  *rects;
-    register XPoint *pts;
-    register POINTBLOCK *CurPtBlock;
-    register int i;
-    register BOX *extents;
-    register int numRects;
-    BOX *prevRects = reg->rects;
-
-    extents = &reg->extents;
-
-    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
-
-    if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects,
-	    (unsigned) (sizeof(BOX) * numRects))))  {
-	Xfree(prevRects);
-	return(0);
-    }
-
-    reg->size = numRects;
-    CurPtBlock = FirstPtBlock;
-    rects = reg->rects - 1;
-    numRects = 0;
-    extents->x1 = MAXSHORT,  extents->x2 = MINSHORT;
-
-    for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
-	/* the loop uses 2 points per iteration */
-	i = NUMPTSTOBUFFER >> 1;
-	if (!numFullPtBlocks)
-	    i = iCurPtBlock >> 1;
-	for (pts = CurPtBlock->pts; i--; pts += 2) {
-	    if (pts->x == pts[1].x)
-		continue;
-	    if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
-		pts[1].x == rects->x2 &&
-		(numRects == 1 || rects[-1].y1 != rects->y1) &&
-		(i && pts[2].y > pts[1].y)) {
-		rects->y2 = pts[1].y + 1;
-		continue;
-	    }
-	    numRects++;
-	    rects++;
-	    rects->x1 = pts->x;  rects->y1 = pts->y;
-	    rects->x2 = pts[1].x;  rects->y2 = pts[1].y + 1;
-	    if (rects->x1 < extents->x1)
-		extents->x1 = rects->x1;
-	    if (rects->x2 > extents->x2)
-		extents->x2 = rects->x2;
-        }
-	CurPtBlock = CurPtBlock->next;
-    }
-
-    if (numRects) {
-	extents->y1 = reg->rects->y1;
-	extents->y2 = rects->y2;
-    } else {
-	extents->x1 = 0;
-	extents->y1 = 0;
-	extents->x2 = 0;
-	extents->y2 = 0;
-    }
-    reg->numRects = numRects;
-
-    return(TRUE);
-}
-
-/*
- *     polytoregion
- *
- *     Scan converts a polygon by returning a run-length
- *     encoding of the resultant bitmap -- the run-length
- *     encoding is in the form of an array of rectangles.
- */
-Region
-XPolygonRegion(
-    XPoint     *Pts,		     /* the pts                 */
-    int       Count,                 /* number of pts           */
-    int	rule)			     /* winding rule */
-{
-    Region region;
-    register EdgeTableEntry *pAET;   /* Active Edge Table       */
-    register int y;                  /* current scanline        */
-    register int iPts = 0;           /* number of pts in buffer */
-    register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
-    register ScanLineList *pSLL;     /* current scanLineList    */
-    register XPoint *pts;             /* output buffer           */
-    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
-    EdgeTable ET;                    /* header node for ET      */
-    EdgeTableEntry AET;              /* header node for AET     */
-    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
-    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
-    int fixWAET = FALSE;
-    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
-    POINTBLOCK *tmpPtBlock;
-    int numFullPtBlocks = 0;
-
-    if (! (region = XCreateRegion())) return (Region) NULL;
-
-    /* special case a rectangle */
-    pts = Pts;
-    if (((Count == 4) ||
-	 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
-	(((pts[0].y == pts[1].y) &&
-	  (pts[1].x == pts[2].x) &&
-	  (pts[2].y == pts[3].y) &&
-	  (pts[3].x == pts[0].x)) ||
-	 ((pts[0].x == pts[1].x) &&
-	  (pts[1].y == pts[2].y) &&
-	  (pts[2].x == pts[3].x) &&
-	  (pts[3].y == pts[0].y)))) {
-	region->extents.x1 = min(pts[0].x, pts[2].x);
-	region->extents.y1 = min(pts[0].y, pts[2].y);
-	region->extents.x2 = max(pts[0].x, pts[2].x);
-	region->extents.y2 = max(pts[0].y, pts[2].y);
-	if ((region->extents.x1 != region->extents.x2) &&
-	    (region->extents.y1 != region->extents.y2)) {
-	    region->numRects = 1;
-	    *(region->rects) = region->extents;
-	}
-	return(region);
-    }
-
-    if (Count < 2) return region;
-
-    if (! (pETEs = (EdgeTableEntry *)
-	   Xmalloc((unsigned) (sizeof(EdgeTableEntry) * Count)))) {
-	XDestroyRegion(region);
-	return (Region) NULL;
-    }
-
-    pts = FirstPtBlock.pts;
-    CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
-    pSLL = ET.scanlines.next;
-    curPtBlock = &FirstPtBlock;
-
-    if (rule == EvenOddRule) {
-        /*
-         *  for each scanline
-         */
-        for (y = ET.ymin; y < ET.ymax; y++) {
-            /*
-             *  Add a new edge to the active edge table when we
-             *  get to the next edge.
-             */
-            if (pSLL != NULL && y == pSLL->scanline) {
-                loadAET(&AET, pSLL->edgelist);
-                pSLL = pSLL->next;
-            }
-            pPrevAET = &AET;
-            pAET = AET.next;
-
-            /*
-             *  for each active edge
-             */
-            while (pAET) {
-                pts->x = pAET->bres.minor_axis,  pts->y = y;
-                pts++, iPts++;
-
-                /*
-                 *  send out the buffer
-                 */
-                if (iPts == NUMPTSTOBUFFER) {
-                    tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
-                    curPtBlock->next = tmpPtBlock;
-                    curPtBlock = tmpPtBlock;
-                    pts = curPtBlock->pts;
-                    numFullPtBlocks++;
-                    iPts = 0;
-                }
-                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
-            }
-            (void) InsertionSort(&AET);
-        }
-    }
-    else {
-        /*
-         *  for each scanline
-         */
-        for (y = ET.ymin; y < ET.ymax; y++) {
-            /*
-             *  Add a new edge to the active edge table when we
-             *  get to the next edge.
-             */
-            if (pSLL != NULL && y == pSLL->scanline) {
-                loadAET(&AET, pSLL->edgelist);
-                computeWAET(&AET);
-                pSLL = pSLL->next;
-            }
-            pPrevAET = &AET;
-            pAET = AET.next;
-            pWETE = pAET;
-
-            /*
-             *  for each active edge
-             */
-            while (pAET) {
-                /*
-                 *  add to the buffer only those edges that
-                 *  are in the Winding active edge table.
-                 */
-                if (pWETE == pAET) {
-                    pts->x = pAET->bres.minor_axis,  pts->y = y;
-                    pts++, iPts++;
-
-                    /*
-                     *  send out the buffer
-                     */
-                    if (iPts == NUMPTSTOBUFFER) {
-                        tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
-                        curPtBlock->next = tmpPtBlock;
-                        curPtBlock = tmpPtBlock;
-                        pts = curPtBlock->pts;
-                        numFullPtBlocks++;    iPts = 0;
-                    }
-                    pWETE = pWETE->nextWETE;
-                }
-                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
-            }
-
-            /*
-             *  recompute the winding active edge table if
-             *  we just resorted or have exited an edge.
-             */
-            if (InsertionSort(&AET) || fixWAET) {
-                computeWAET(&AET);
-                fixWAET = FALSE;
-            }
-        }
-    }
-    FreeStorage(SLLBlock.next);
-    (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
-    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
-	tmpPtBlock = curPtBlock->next;
-	Xfree((char *)curPtBlock);
-	curPtBlock = tmpPtBlock;
-    }
-    Xfree((char *)pETEs);
-    return(region);
-}
+/************************************************************************

+

+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.

+

+************************************************************************/

+

+#define LARGE_COORDINATE 1000000

+#define SMALL_COORDINATE -LARGE_COORDINATE

+

+#ifdef HAVE_CONFIG_H

+#include <config.h>

+#endif

+#include "Xlibint.h"

+#include "Xutil.h"

+#include <X11/Xregion.h>

+#include "poly.h"

+

+/*

+ *     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 void

+InsertEdgeInET(

+    EdgeTable *ET,

+    EdgeTableEntry *ETE,

+    int scanline,

+    ScanLineListBlock **SLLBlock,

+    int *iSLLBlock)

+{

+    register EdgeTableEntry *start, *prev;

+    register 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 =

+		  (ScanLineListBlock *)Xmalloc(sizeof(ScanLineListBlock));

+            (*SLLBlock)->next = tmpSLLBlock;

+            tmpSLLBlock->next = (ScanLineListBlock *)NULL;

+            *SLLBlock = tmpSLLBlock;

+            *iSLLBlock = 0;

+        }

+        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);

+

+        pSLL->next = pPrevSLL->next;

+        pSLL->edgelist = (EdgeTableEntry *)NULL;

+        pPrevSLL->next = pSLL;

+    }

+    pSLL->scanline = scanline;

+

+    /*

+     * now insert the edge in the right bucket

+     */

+    prev = (EdgeTableEntry *)NULL;

+    start = pSLL->edgelist;

+    while (start && (start->bres.minor_axis < ETE->bres.minor_axis))

+    {

+        prev = start;

+        start = start->next;

+    }

+    ETE->next = start;

+

+    if (prev)

+        prev->next = ETE;

+    else

+        pSLL->edgelist = ETE;

+}

+

+/*

+ *     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 void

+CreateETandAET(

+    register int count,

+    register XPoint *pts,

+    EdgeTable *ET,

+    EdgeTableEntry *AET,

+    register EdgeTableEntry *pETEs,

+    ScanLineListBlock   *pSLLBlock)

+{

+    register XPoint *top, *bottom;

+    register XPoint *PrevPt, *CurrPt;

+    int iSLLBlock = 0;

+    int dy;

+

+    if (count < 2)  return;

+

+    /*

+     *  initialize the Active Edge Table

+     */

+    AET->next = (EdgeTableEntry *)NULL;

+    AET->back = (EdgeTableEntry *)NULL;

+    AET->nextWETE = (EdgeTableEntry *)NULL;

+    AET->bres.minor_axis = SMALL_COORDINATE;

+

+    /*

+     *  initialize the Edge Table.

+     */

+    ET->scanlines.next = (ScanLineList *)NULL;

+    ET->ymax = SMALL_COORDINATE;

+    ET->ymin = LARGE_COORDINATE;

+    pSLLBlock->next = (ScanLineListBlock *)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);

+

+            InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);

+

+	    if (PrevPt->y > ET->ymax)

+		ET->ymax = PrevPt->y;

+	    if (PrevPt->y < ET->ymin)

+		ET->ymin = PrevPt->y;

+            pETEs++;

+        }

+

+        PrevPt = CurrPt;

+    }

+}

+

+/*

+ *     loadAET

+ *

+ *     This routine moves EdgeTableEntries from the

+ *     EdgeTable into the Active Edge Table,

+ *     leaving them sorted by smaller x coordinate.

+ *

+ */

+

+static void

+loadAET(

+    register EdgeTableEntry *AET,

+    register EdgeTableEntry *ETEs)

+{

+    register EdgeTableEntry *pPrevAET;

+    register EdgeTableEntry *tmp;

+

+    pPrevAET = AET;

+    AET = AET->next;

+    while (ETEs)

+    {

+        while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))

+        {

+            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

+computeWAET(

+    register EdgeTableEntry *AET)

+{

+    register EdgeTableEntry *pWETE;

+    register int inside = 1;

+    register int isInside = 0;

+

+    AET->nextWETE = (EdgeTableEntry *)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 = (EdgeTableEntry *)NULL;

+}

+

+/*

+ *     InsertionSort

+ *

+ *     Just a simple insertion sort using

+ *     pointers and back pointers to sort the Active

+ *     Edge Table.

+ *

+ */

+

+static int

+InsertionSort(

+    register EdgeTableEntry *AET)

+{

+    register EdgeTableEntry *pETEchase;

+    register EdgeTableEntry *pETEinsert;

+    register EdgeTableEntry *pETEchaseBackTMP;

+    register int changed = 0;

+

+    AET = AET->next;

+    while (AET)

+    {

+        pETEinsert = AET;

+        pETEchase = AET;

+        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)

+            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.

+ */

+static void

+FreeStorage(

+    register ScanLineListBlock   *pSLLBlock)

+{

+    register ScanLineListBlock   *tmpSLLBlock;

+

+    while (pSLLBlock)

+    {

+        tmpSLLBlock = pSLLBlock->next;

+        Xfree((char *)pSLLBlock);

+        pSLLBlock = tmpSLLBlock;

+    }

+}

+

+/*

+ *     Create an array of rectangles from a list of points.

+ *     If indeed these things (POINTS, RECTS) are the same,

+ *     then this proc is still needed, because it allocates

+ *     storage for the array, which was allocated on the

+ *     stack by the calling procedure.

+ *

+ */

+static int PtsToRegion(

+    register int numFullPtBlocks,

+    register int iCurPtBlock,

+    POINTBLOCK *FirstPtBlock,

+    REGION *reg)

+{

+    register BOX  *rects;

+    register XPoint *pts;

+    register POINTBLOCK *CurPtBlock;

+    register int i;

+    register BOX *extents;

+    register int numRects;

+    BOX *prevRects = reg->rects;

+

+    extents = &reg->extents;

+

+    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;

+

+    if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects,

+	    (unsigned) (sizeof(BOX) * numRects))))  {

+	Xfree(prevRects);

+	return(0);

+    }

+

+    reg->size = numRects;

+    CurPtBlock = FirstPtBlock;

+    rects = reg->rects - 1;

+    numRects = 0;

+    extents->x1 = MAXSHORT,  extents->x2 = MINSHORT;

+

+    for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {

+	/* the loop uses 2 points per iteration */

+	i = NUMPTSTOBUFFER >> 1;

+	if (!numFullPtBlocks)

+	    i = iCurPtBlock >> 1;

+	for (pts = CurPtBlock->pts; i--; pts += 2) {

+	    if (pts->x == pts[1].x)

+		continue;

+	    if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&

+		pts[1].x == rects->x2 &&

+		(numRects == 1 || rects[-1].y1 != rects->y1) &&

+		(i && pts[2].y > pts[1].y)) {

+		rects->y2 = pts[1].y + 1;

+		continue;

+	    }

+	    numRects++;

+	    rects++;

+	    rects->x1 = pts->x;  rects->y1 = pts->y;

+	    rects->x2 = pts[1].x;  rects->y2 = pts[1].y + 1;

+	    if (rects->x1 < extents->x1)

+		extents->x1 = rects->x1;

+	    if (rects->x2 > extents->x2)

+		extents->x2 = rects->x2;

+        }

+	CurPtBlock = CurPtBlock->next;

+    }

+

+    if (numRects) {

+	extents->y1 = reg->rects->y1;

+	extents->y2 = rects->y2;

+    } else {

+	extents->x1 = 0;

+	extents->y1 = 0;

+	extents->x2 = 0;

+	extents->y2 = 0;

+    }

+    reg->numRects = numRects;

+

+    return(TRUE);

+}

+

+/*

+ *     polytoregion

+ *

+ *     Scan converts a polygon by returning a run-length

+ *     encoding of the resultant bitmap -- the run-length

+ *     encoding is in the form of an array of rectangles.

+ */

+Region

+XPolygonRegion(

+    XPoint     *Pts,		     /* the pts                 */

+    int       Count,                 /* number of pts           */

+    int	rule)			     /* winding rule */

+{

+    Region region;

+    register EdgeTableEntry *pAET;   /* Active Edge Table       */

+    register int y;                  /* current scanline        */

+    register int iPts = 0;           /* number of pts in buffer */

+    register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/

+    register ScanLineList *pSLL;     /* current scanLineList    */

+    register XPoint *pts;             /* output buffer           */

+    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */

+    EdgeTable ET;                    /* header node for ET      */

+    EdgeTableEntry AET;              /* header node for AET     */

+    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */

+    ScanLineListBlock SLLBlock;      /* header for scanlinelist */

+    int fixWAET = FALSE;

+    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */

+    POINTBLOCK *tmpPtBlock;

+    int numFullPtBlocks = 0;

+

+    if (! (region = XCreateRegion())) return (Region) NULL;

+

+    /* special case a rectangle */

+    pts = Pts;

+    if (((Count == 4) ||

+	 ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&

+	(((pts[0].y == pts[1].y) &&

+	  (pts[1].x == pts[2].x) &&

+	  (pts[2].y == pts[3].y) &&

+	  (pts[3].x == pts[0].x)) ||

+	 ((pts[0].x == pts[1].x) &&

+	  (pts[1].y == pts[2].y) &&

+	  (pts[2].x == pts[3].x) &&

+	  (pts[3].y == pts[0].y)))) {

+	region->extents.x1 = min(pts[0].x, pts[2].x);

+	region->extents.y1 = min(pts[0].y, pts[2].y);

+	region->extents.x2 = max(pts[0].x, pts[2].x);

+	region->extents.y2 = max(pts[0].y, pts[2].y);

+	if ((region->extents.x1 != region->extents.x2) &&

+	    (region->extents.y1 != region->extents.y2)) {

+	    region->numRects = 1;

+	    *(region->rects) = region->extents;

+	}

+	return(region);

+    }

+

+    if (Count < 2) return region;

+

+    if (! (pETEs = (EdgeTableEntry *)

+	   Xmalloc((unsigned) (sizeof(EdgeTableEntry) * Count)))) {

+	XDestroyRegion(region);

+	return (Region) NULL;

+    }

+

+    pts = FirstPtBlock.pts;

+    CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);

+    pSLL = ET.scanlines.next;

+    curPtBlock = &FirstPtBlock;

+

+    if (rule == EvenOddRule) {

+        /*

+         *  for each scanline

+         */

+        for (y = ET.ymin; y < ET.ymax; y++) {

+            /*

+             *  Add a new edge to the active edge table when we

+             *  get to the next edge.

+             */

+            if (pSLL != NULL && y == pSLL->scanline) {

+                loadAET(&AET, pSLL->edgelist);

+                pSLL = pSLL->next;

+            }

+            pPrevAET = &AET;

+            pAET = AET.next;

+

+            /*

+             *  for each active edge

+             */

+            while (pAET) {

+                pts->x = pAET->bres.minor_axis,  pts->y = y;

+                pts++, iPts++;

+

+                /*

+                 *  send out the buffer

+                 */

+                if (iPts == NUMPTSTOBUFFER) {

+                    tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));

+                    curPtBlock->next = tmpPtBlock;

+                    curPtBlock = tmpPtBlock;

+                    pts = curPtBlock->pts;

+                    numFullPtBlocks++;

+                    iPts = 0;

+                }

+                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);

+            }

+            (void) InsertionSort(&AET);

+        }

+    }

+    else {

+        /*

+         *  for each scanline

+         */

+        for (y = ET.ymin; y < ET.ymax; y++) {

+            /*

+             *  Add a new edge to the active edge table when we

+             *  get to the next edge.

+             */

+            if (pSLL != NULL && y == pSLL->scanline) {

+                loadAET(&AET, pSLL->edgelist);

+                computeWAET(&AET);

+                pSLL = pSLL->next;

+            }

+            pPrevAET = &AET;

+            pAET = AET.next;

+            pWETE = pAET;

+

+            /*

+             *  for each active edge

+             */

+            while (pAET) {

+                /*

+                 *  add to the buffer only those edges that

+                 *  are in the Winding active edge table.

+                 */

+                if (pWETE == pAET) {

+                    pts->x = pAET->bres.minor_axis,  pts->y = y;

+                    pts++, iPts++;

+

+                    /*

+                     *  send out the buffer

+                     */

+                    if (iPts == NUMPTSTOBUFFER) {

+                        tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));

+                        curPtBlock->next = tmpPtBlock;

+                        curPtBlock = tmpPtBlock;

+                        pts = curPtBlock->pts;

+                        numFullPtBlocks++;    iPts = 0;

+                    }

+                    pWETE = pWETE->nextWETE;

+                }

+                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);

+            }

+

+            /*

+             *  recompute the winding active edge table if

+             *  we just resorted or have exited an edge.

+             */

+            if (InsertionSort(&AET) || fixWAET) {

+                computeWAET(&AET);

+                fixWAET = FALSE;

+            }

+        }

+    }

+    FreeStorage(SLLBlock.next);

+    (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);

+    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {

+	tmpPtBlock = curPtBlock->next;

+	Xfree((char *)curPtBlock);

+	curPtBlock = tmpPtBlock;

+    }

+    Xfree((char *)pETEs);

+    return(region);

+}