Return to misetclip.c CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi

Annotation of researchv9/X11/src/X.V11R1/server/ddx/mi/misetclip.c, revision 1.1

1.1     ! root        1: /***********************************************************
        !             2: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
        !             3: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
        !             4: 
        !             5:                         All Rights Reserved
        !             6: 
        !             7: Permission to use, copy, modify, and distribute this software and its 
        !             8: documentation for any purpose and without fee is hereby granted, 
        !             9: provided that the above copyright notice appear in all copies and that
        !            10: both that copyright notice and this permission notice appear in 
        !            11: supporting documentation, and that the names of Digital or MIT not be
        !            12: used in advertising or publicity pertaining to distribution of the
        !            13: software without specific, written prior permission.  
        !            14: 
        !            15: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
        !            16: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
        !            17: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
        !            18: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
        !            19: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
        !            20: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
        !            21: SOFTWARE.
        !            22: 
        !            23: ******************************************************************/
        !            24: /* $Header: misetclip.c,v 1.4 87/09/11 07:20:53 toddb Exp $ */
        !            25: /* Author: Todd Newman */
        !            26: 
        !            27: #include "X.h"
        !            28: #include "Xprotostr.h"
        !            29: #include "miscstruct.h"
        !            30: #include "scrnintstr.h"
        !            31: #include "pixmap.h"
        !            32: #include "regionstr.h"
        !            33: #include "gcstruct.h"
        !            34: 
        !            35: /* The file name is something of a misnomer. Actually, this just contains 
        !            36:  * a routine to convert a set of rectangles into a region 
        !            37:  */
        !            38: 
        !            39: typedef struct _ybucket
        !            40: {
        !            41:     short      y;
        !            42:     short      count;
        !            43:     BoxPtr     boxes;
        !            44:     short      miny2;
        !            45:     short      fdiff;  /* do any have different y2s */
        !            46:     struct _ybucket    *next;
        !            47: } YBUCKET;
        !            48: 
        !            49: 
        !            50: /* NEWBUCKET -- a private helper to build a bucket for sorting */
        !            51: static
        !            52: YBUCKET *
        !            53: newbucket(y, miny2)
        !            54: {
        !            55:     YBUCKET    *pb;
        !            56: 
        !            57:     pb = (YBUCKET *) Xalloc( sizeof(YBUCKET));
        !            58:     pb->count = 0;
        !            59:     pb->y = y;
        !            60:     pb->miny2 = miny2;
        !            61:     pb->fdiff = FALSE;
        !            62:     pb->boxes = (BoxPtr)Xalloc(sizeof(BoxRec));
        !            63:     pb->next = (YBUCKET *) NULL;
        !            64:     return(pb);
        !            65: }
        !            66: 
        !            67: /* MIRECTSTOREGION -- helper called by the device private routine called when
        !            68:  * the clipmask changes.  Converts the set of rectangles to a region.  
        !            69:  * dix/gc/SetClipRects has already checked that the rectangles are sorted as
        !            70:  * advertised.
        !            71:  * We just take those rectangles and convert to a YX banded region.
        !            72:  * First we sort the rectangles by starting Y values. Then we make sure that
        !            73:  * all rectangles that start at a given line all end at the same line.  Bits
        !            74:  * that hang over fall into the next Y bucket. (Sort of Procrustean, isn't
        !            75:  * it?)  Next, we sort within each Y bucket by X starting values. Finally,
        !            76:  * we take the resulting set of rectangles and stuff it into a region.
        !            77:  */
        !            78: RegionPtr
        !            79: miRectsToRegion(pGC, nrects, prect, ordering)
        !            80:     GCPtr      pGC;
        !            81:     int                nrects;
        !            82:     xRectangle *prect;
        !            83:     int                ordering;
        !            84: {
        !            85:     register YBUCKET   *pb;
        !            86:     register BoxRec    *pbox, *pboxNew;
        !            87:     BoxRec              tbox;
        !            88:     RegionPtr          pReg;
        !            89:     YBUCKET            *pbFirst, *pbNew, *newbucket();
        !            90:     int                        count, miny2;
        !            91:     Bool               fInserted, fChanged;
        !            92:     int                        xMin, xMax, yMin, yMax;
        !            93:     BoxRec             b;
        !            94: 
        !            95:     /* if there's only one rectangle, we don't care about ordering */
        !            96:     if (nrects == 1)   
        !            97:     {
        !            98:         b.x1 = prect->x;
        !            99:         b.y1 = prect->y;
        !           100:         b.x2 = b.x1 + prect->width;
        !           101:         b.y2 = b.y1 + prect->height;
        !           102:         return ((* pGC->pScreen->RegionCreate)(&b, 1));
        !           103:     }
        !           104:     /* setting the number of rectangles to zero stops all output */
        !           105:     if (nrects == 0)   
        !           106:     {
        !           107:         b.x1 = 0;
        !           108:         b.y1 = 0;
        !           109:         b.x2 = 0;
        !           110:         b.y2 = 0;
        !           111:         return ((* pGC->pScreen->RegionCreate)(&b, 1));
        !           112:     }
        !           113: 
        !           114:     xMin = yMin = MAXSHORT;
        !           115:     xMax = yMax = -1;
        !           116:     if ((nrects < 0) ||
        !           117:        ((pReg = (* pGC->pScreen->RegionCreate)(NULL, 1)) == NullRegion))
        !           118:     {
        !           119:        return NullRegion;
        !           120:     }
        !           121: 
        !           122:     if (ordering == YXBanded)
        !           123:     {
        !           124:        pReg->rects = (BoxPtr)Xrealloc(pReg->rects, nrects * sizeof(BoxRec));
        !           125:        pbox = pReg->rects;
        !           126:        while(pbox < pReg->rects + nrects)
        !           127:        {
        !           128:            pbox->x1 = prect->x;
        !           129:            pbox->y1 = prect->y;
        !           130:            pbox->x2 = prect->x + prect->width;
        !           131:            pbox->y2 = prect->y + prect->height;
        !           132:            xMin = min(xMin, pbox->x1);
        !           133:            xMax = max(xMax, pbox->x2);
        !           134:            yMin = min(yMin, pbox->y1);
        !           135:            yMax = max(yMax, pbox->y2);
        !           136:            prect++;
        !           137:            pbox++;
        !           138:        }
        !           139:        pReg->numRects = nrects;
        !           140:        pReg->size = nrects;
        !           141:        pReg->extents.x1 = xMin;
        !           142:        pReg->extents.y1 = yMin;
        !           143:        pReg->extents.x2 = xMax;
        !           144:        pReg->extents.y2 = yMax;
        !           145:        return (pReg);
        !           146:     }
        !           147: 
        !           148:     pbFirst = (YBUCKET *) newbucket(prect->y, prect->y + prect->height);
        !           149:     pb = pbFirst;
        !           150:     count = nrects;
        !           151: 
        !           152:     /* Sort into Y buckets -- everthing in a bucket has the same starting
        !           153:      * scanline.  Also note the smallest box in the band and whether any
        !           154:      * boxes are of other sizes */
        !           155:     while(count--)
        !           156:     {
        !           157:        if(ordering == Unsorted)
        !           158:        {
        !           159:            /* We have to search from the top, otherwise we know no
        !           160:             * box will be before the current one */
        !           161:            pb = pbFirst;
        !           162:        }
        !           163: 
        !           164:        fInserted = FALSE;
        !           165:        while(!fInserted)
        !           166:        {
        !           167:            if(prect->y == pb->y)
        !           168:            {
        !           169:                /* add rectangle at the end of this bucket */
        !           170:                pb->count++;
        !           171:                pb->boxes = (BoxPtr)Xrealloc(pb->boxes,
        !           172:                                             pb->count * sizeof(BoxRec));
        !           173:                pbox = &pb->boxes[pb->count - 1];
        !           174: 
        !           175:                pbox->x1 = prect->x;
        !           176:                pbox->y1 = prect->y;
        !           177:                pbox->x2 = prect->x + prect->width;
        !           178:                pbox->y2 = prect->y + prect->height;
        !           179:                xMin = min(xMin, pbox->x1);
        !           180:                xMax = max(xMax, pbox->x2);
        !           181:                yMin = min(yMin, pbox->y1);
        !           182:                yMax = max(yMax, pbox->y2);
        !           183: 
        !           184:                if (pbox->y2 != pb->miny2)
        !           185:                    pb->fdiff = TRUE;
        !           186:                if (pbox->y2 < pb->miny2)
        !           187:                    pb->miny2 = pbox->y2;
        !           188:                fInserted = TRUE;
        !           189:            }
        !           190:            else if(prect->y < pbFirst->y)
        !           191:            {
        !           192:                /* Create a new first record in the list */
        !           193:                pbNew = newbucket(prect->y, prect->y + prect->height);
        !           194:                pbNew->next = pbFirst;
        !           195:                pbFirst = pbNew;
        !           196:                pb = pbNew;
        !           197:            }
        !           198:            else if ((pb->next == (YBUCKET *) NULL) ||
        !           199:                     (pb->next->y > prect->y))
        !           200:            {
        !           201:                /* create a new ybucket linked between this and the next.
        !           202:                 * set pb to new bucket */
        !           203:                 pbNew = newbucket(prect->y, prect->y + prect->height);
        !           204:                 pbNew->next = pb->next;
        !           205:                 pb->next = pbNew;
        !           206:                 pb = pbNew;
        !           207:                
        !           208:            }
        !           209:            else
        !           210:            {
        !           211:                /* try with next bucket */
        !           212:                pb = pb->next;
        !           213:            }
        !           214:        }
        !           215:        prect++;
        !           216:     }
        !           217: 
        !           218:     /* YBand the buckets */
        !           219:     pb = pbFirst;
        !           220:     while(pb)
        !           221:     {
        !           222:        if(pb->fdiff)
        !           223:        {
        !           224:            miny2 = pb->miny2;
        !           225: 
        !           226:            /* Figure out which ybucket the lopped-off part of these boxes
        !           227:             * will go in */
        !           228:            if(pb->next ? (miny2 < pb->next->y) : TRUE)
        !           229:            {
        !           230:                /* create new y bucket */
        !           231:                pbNew = newbucket(miny2, MAXSHORT);
        !           232:                pbNew->next = pb->next;
        !           233:                pb->next = pbNew;
        !           234:            }
        !           235:            else
        !           236:            {
        !           237:                pbNew = pb->next;
        !           238:            }
        !           239: 
        !           240:            /* if any rectangle is longer than the shortest in this ybucket,
        !           241:             * drop the rest of the rectangle into the next lowest bucket */
        !           242:            pbox = pb->boxes;
        !           243:            while(pbox < pb->boxes + pb->count)
        !           244:            {
        !           245:                if(pbox->y2 > miny2)
        !           246:                {
        !           247:                    if(pbNew->count == 0)
        !           248:                    {
        !           249:                        pbNew->miny2 = pbox->y2;
        !           250:                    }
        !           251:                    pbNew->count++;
        !           252:                    pbNew->boxes = (BoxPtr)Xrealloc(pbNew->boxes, pbNew->count *
        !           253:                                            sizeof(BoxRec));
        !           254:                    pboxNew = &pbNew->boxes[pbNew->count - 1];
        !           255:                    pboxNew->x1 = pbox->x1;
        !           256:                    pboxNew->y1 = pbNew->y;
        !           257:                    pboxNew->x2 = pbox->x2;
        !           258:                    pboxNew->y2 = pbox->y2;
        !           259:                    if(pboxNew->y2 !=pbNew->miny2)
        !           260:                        pbNew->fdiff = TRUE;
        !           261:                    if(pboxNew->y2 < pbNew->miny2)
        !           262:                        pbNew->miny2 = pboxNew->y2;
        !           263:                    
        !           264:                }
        !           265:                pbox++;
        !           266:            }
        !           267:        }
        !           268:        else
        !           269:        {
        !           270:           pbNew = pb->next;
        !           271:        }
        !           272: 
        !           273:        pb = pbNew;
        !           274:     }
        !           275: 
        !           276:     /* X sort the buckets, and tally total size */
        !           277:     pb = pbFirst;
        !           278:     count = 0;
        !           279:     while(pb)
        !           280:     {
        !           281:        count += pb->count;
        !           282:        /* Yes, it's a bubble sort.  I wanted something (a) in place,
        !           283:         * (b) with a low startup cost, because I expect to find few
        !           284:         * rectangles per yband and don't want to spend more effort setting
        !           285:         * up the sort than I do performing it.
        !           286:         */
        !           287:        fChanged = TRUE;
        !           288:        while(fChanged)
        !           289:        {
        !           290:            fChanged = FALSE;
        !           291:            pbox = pb->boxes;
        !           292:            while(pbox < pb->boxes + pb->count - 1)
        !           293:            {
        !           294:                if(pbox->x1 > (pbox+1)->x1)
        !           295:                {
        !           296:                    tbox = *pbox;
        !           297:                    *pbox = *(pbox + 1);
        !           298:                    *(pbox + 1) = tbox;
        !           299:                    fChanged = TRUE;
        !           300:                }
        !           301:                pbox++;
        !           302:            }
        !           303:        }
        !           304:        pb = pb->next;
        !           305:     }
        !           306: 
        !           307:     /* copy the rectangles into the region and free up the buckets */
        !           308:     pReg->rects = (BoxPtr) Xrealloc (pReg->rects, count * sizeof(BoxRec));
        !           309:     pReg->numRects = count;
        !           310:     pReg->size = count;
        !           311:     pboxNew = pReg->rects;
        !           312:     pb = pbFirst;
        !           313:     while(pb)
        !           314:     {
        !           315:        for(pbox = pb->boxes; pbox < pb->boxes + pb->count; pbox++)
        !           316:        {
        !           317:            *pboxNew++ = *pbox;
        !           318:        }
        !           319:        Xfree((char *)pb->boxes);
        !           320: 
        !           321:        pb = pb->next;
        !           322:        Xfree(pb);
        !           323:     }
        !           324:     pReg->extents.x1 = xMin;
        !           325:     pReg->extents.y1 = yMin;
        !           326:     pReg->extents.x2 = xMax;
        !           327:     pReg->extents.y2 = yMax;
        !           328:     return(pReg);
        !           329: 
        !           330: }
        !           331: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.