Return to miregion.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/miregion.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: miregion.c,v 1.27 87/09/03 13:25:15 toddb Exp $ */
        !            25: 
        !            26: #include "miscstruct.h"
        !            27: #include "regionstr.h"
        !            28: 
        !            29: #ifdef DEBUG
        !            30: #define assert(expr) {if (!(expr)) \
        !            31:                FatalError("Assertion failed file %s, line %d: expr\n", \
        !            32:                        __FILE__, __LINE__); }
        !            33: #else
        !            34: #define assert(expr)
        !            35: #endif
        !            36: 
        !            37: /*
        !            38:  * The functions in this file implement the Region abstraction used extensively
        !            39:  * throughout the X11 sample server. A Region is simply an area, as the name
        !            40:  * implies, and is implemented as a "y-x-banded" array of rectangles. To
        !            41:  * explain: Each Region is made up of a certain number of rectangles sorted
        !            42:  * by y coordinate first, and then by x coordinate.
        !            43:  *
        !            44:  * Furthermore, the rectangles are banded such that every rectangle with a
        !            45:  * given upper-left y coordinate (y1) will have the same lower-right y
        !            46:  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
        !            47:  * will span the entire vertical distance of the band. This means that some
        !            48:  * areas that could be merged into a taller rectangle will be represented as
        !            49:  * several shorter rectangles to account for shorter rectangles to its left
        !            50:  * or right but within its "vertical scope".
        !            51:  *
        !            52:  * An added constraint on the rectangles is that they must cover as much
        !            53:  * horizontal area as possible. E.g. no two rectangles in a band are allowed
        !            54:  * to touch.
        !            55:  *
        !            56:  * Whenever possible, bands will be merged together to cover a greater vertical
        !            57:  * distance (and thus reduce the number of rectangles). Two bands can be merged
        !            58:  * only if the bottom of one touches the top of the other and they have
        !            59:  * rectangles in the same places (of the same width, of course). This maintains
        !            60:  * the y-x-banding that's so nice to have...
        !            61:  */
        !            62: 
        !            63: typedef BoxRec BOX;    /* this is to cut down on some gratuitous edits */
        !            64: 
        !            65: /*  1: if two BOXs overlap.
        !            66: /*  0: if two BOXs do not overlap.
        !            67:  *  Remember, x2 and y2 are not in the region 
        !            68:  */
        !            69: #define EXTENTCHECK(r1, r2) \
        !            70:       (!( ((r1)->x2 <= (r2)->x1)  || \
        !            71:         ( ((r1)->x1 >= (r2)->x2)) || \
        !            72:         ( ((r1)->y2 <= (r2)->y1)) || \
        !            73:         ( ((r1)->y1 >= (r2)->y2)) ) )
        !            74: 
        !            75: 
        !            76: void
        !            77: miprintRects(rgn)
        !            78:     RegionPtr rgn;
        !            79: {
        !            80:     register int i;
        !            81: 
        !            82:     ErrorF(  "num: %d size: %d \n", rgn->numRects, rgn->size);
        !            83:     ErrorF(  "   extents: %d %d %d %d\n",rgn->extents.x1, 
        !            84:            rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
        !            85:     for (i = 0; i < rgn->numRects; i++)
        !            86:       ErrorF(  "%d %d %d %d \n", rgn->rects[i].x1,rgn->rects[i].y1,
        !            87:              rgn->rects[i].x2,rgn->rects[i].y2);
        !            88:     ErrorF(  "\n");
        !            89: }
        !            90: 
        !            91: /*****************************************************************
        !            92:  *   RegionCreate(rect, size)
        !            93:  *     This routine does a simple malloc to make a structure of
        !            94:  *     REGION of "size" number of rectangles.
        !            95:  *****************************************************************/
        !            96: 
        !            97: RegionPtr
        !            98: miRegionCreate(rect, size)
        !            99:     register BOX *rect;
        !           100:     register int size;
        !           101: {
        !           102:     register RegionPtr temp;       /*   new region  */
        !           103:    
        !           104:     size = max(1, size);
        !           105:     temp = (RegionPtr ) Xalloc (sizeof (RegionRec));
        !           106:     temp->rects = (BOX *) Xalloc (size * (sizeof(BOX)));
        !           107:     if (rect == (BOX *)NULL)
        !           108:     {
        !           109:         temp->numRects = 0;
        !           110:         temp->extents.x1 = 0;
        !           111:         temp->extents.y1 = 0;
        !           112:         temp->extents.x2 = 0;
        !           113:         temp->extents.y2 = 0;
        !           114:     }
        !           115:     else
        !           116:     {
        !           117:         temp->extents = *rect;
        !           118:         temp->rects[0] = *rect;
        !           119:         temp->numRects = 1;
        !           120:     }
        !           121:     temp->size = size;
        !           122:     return(temp);
        !           123: }
        !           124: 
        !           125: 
        !           126: void
        !           127: miRegionCopy(dstrgn, rgn)
        !           128:     register RegionPtr dstrgn;
        !           129:     register RegionPtr rgn;
        !           130: 
        !           131: {
        !           132:     if (dstrgn != rgn) /*  don't want to copy to itself */
        !           133:     {  
        !           134:         if (dstrgn->size < rgn->numRects)
        !           135:         {
        !           136:             if (dstrgn->rects)
        !           137:             {
        !           138:                 dstrgn->rects = (BOX *) Xrealloc(dstrgn->rects, 
        !           139:                                  rgn->numRects * (sizeof(BOX)));
        !           140:             }
        !           141:            else
        !           142:                ErrorF(  "RC HORRIBLE ERROR...\n");
        !           143:             dstrgn->size = rgn->numRects;
        !           144:        }
        !           145:         dstrgn->numRects = rgn->numRects;
        !           146:         dstrgn->extents.x1 = rgn->extents.x1;
        !           147:         dstrgn->extents.y1 = rgn->extents.y1;
        !           148:         dstrgn->extents.x2 = rgn->extents.x2;
        !           149:         dstrgn->extents.y2 = rgn->extents.y2;
        !           150: 
        !           151:        bcopy(rgn->rects, dstrgn->rects, rgn->numRects * sizeof(BOX));   
        !           152:     }
        !           153: }
        !           154: 
        !           155: 
        !           156: /*======================================================================
        !           157:  *         Generic Region Operator
        !           158:  *====================================================================*/
        !           159: 
        !           160: /*-
        !           161:  *-----------------------------------------------------------------------
        !           162:  * miCoalesce --
        !           163:  *     Attempt to merge the boxes in the current band with those in the
        !           164:  *     previous one. Used only by miRegionOp.
        !           165:  *
        !           166:  * Results:
        !           167:  *     The new index for the previous band.
        !           168:  *
        !           169:  * Side Effects:
        !           170:  *     If coalescing takes place:
        !           171:  *         - rectangles in the previous band will have their y2 fields
        !           172:  *           altered.
        !           173:  *         - pReg->numRects will be decreased.
        !           174:  *
        !           175:  *-----------------------------------------------------------------------
        !           176:  */
        !           177: static int
        !           178: miCoalesce (pReg, prevStart, curStart)
        !           179:     register RegionPtr pReg;           /* Region to coalesce */
        !           180:     int                        prevStart;      /* Index of start of previous band */
        !           181:     int                        curStart;       /* Index of start of current band */
        !           182: {
        !           183:     register BoxPtr    pPrevBox;       /* Current box in previous band */
        !           184:     register BoxPtr    pCurBox;        /* Current box in current band */
        !           185:     register BoxPtr    pRegEnd;        /* End of region */
        !           186:     int                        curNumRects;    /* Number of rectangles in current
        !           187:                                         * band */
        !           188:     int                        prevNumRects;   /* Number of rectangles in previous
        !           189:                                         * band */
        !           190:     int                        bandY1;         /* Y1 coordinate for current band */
        !           191: 
        !           192:     pRegEnd = &pReg->rects[pReg->numRects];
        !           193: 
        !           194:     pPrevBox = &pReg->rects[prevStart];
        !           195:     prevNumRects = curStart - prevStart;
        !           196: 
        !           197:     /*
        !           198:      * Figure out how many rectangles are in the current band. Have to do
        !           199:      * this because multiple bands could have been added in miRegionOp
        !           200:      * at the end when one region has been exhausted.
        !           201:      */
        !           202:     pCurBox = &pReg->rects[curStart];
        !           203:     bandY1 = pCurBox->y1;
        !           204:     for (curNumRects = 0;
        !           205:         (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
        !           206:         curNumRects++)
        !           207:     {
        !           208:        pCurBox++;
        !           209:     }
        !           210:     
        !           211:     if (pCurBox != pRegEnd)
        !           212:     {
        !           213:        /*
        !           214:         * If more than one band was added, we have to find the start
        !           215:         * of the last band added so the next coalescing job can start
        !           216:         * at the right place... (given when multiple bands are added,
        !           217:         * this may be pointless -- see above).
        !           218:         */
        !           219:        pRegEnd--;
        !           220:        while (pRegEnd[-1].y1 == pRegEnd->y1)
        !           221:        {
        !           222:            pRegEnd--;
        !           223:        }
        !           224:        curStart = pRegEnd - pReg->rects;
        !           225:        pRegEnd = pReg->rects + pReg->numRects;
        !           226:     }
        !           227:        
        !           228:     if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
        !           229:        pCurBox -= curNumRects;
        !           230:        /*
        !           231:         * The bands may only be coalesced if the bottom of the previous
        !           232:         * matches the top scanline of the current.
        !           233:         */
        !           234:        if (pPrevBox->y2 == pCurBox->y1)
        !           235:        {
        !           236:            /*
        !           237:             * Make sure the bands have boxes in the same places. This
        !           238:             * assumes that boxes have been added in such a way that they
        !           239:             * cover the most area possible. I.e. two boxes in a band must
        !           240:             * have some horizontal space between them.
        !           241:             */
        !           242:            do
        !           243:            {
        !           244:                if ((pPrevBox->x1 != pCurBox->x1) ||
        !           245:                    (pPrevBox->x2 != pCurBox->x2))
        !           246:                {
        !           247:                    /*
        !           248:                     * The bands don't line up so they can't be coalesced.
        !           249:                     */
        !           250:                    return (curStart);
        !           251:                }
        !           252:                pPrevBox++;
        !           253:                pCurBox++;
        !           254:                prevNumRects -= 1;
        !           255:            } while (prevNumRects != 0);
        !           256: 
        !           257:            pReg->numRects -= curNumRects;
        !           258:            pCurBox -= curNumRects;
        !           259:            pPrevBox -= curNumRects;
        !           260: 
        !           261:            /*
        !           262:             * The bands may be merged, so set the bottom y of each box
        !           263:             * in the previous band to that of the corresponding box in
        !           264:             * the current band.
        !           265:             */
        !           266:            do
        !           267:            {
        !           268:                pPrevBox->y2 = pCurBox->y2;
        !           269:                pPrevBox++;
        !           270:                pCurBox++;
        !           271:                curNumRects -= 1;
        !           272:            } while (curNumRects != 0);
        !           273: 
        !           274:            /*
        !           275:             * If only one band was added to the region, we have to backup
        !           276:             * curStart to the start of the previous band.
        !           277:             *
        !           278:             * If more than one band was added to the region, copy the
        !           279:             * other bands down. The assumption here is that the other bands
        !           280:             * came from the same region as the current one and no further
        !           281:             * coalescing can be done on them since it's all been done
        !           282:             * already... curStart is already in the right place.
        !           283:             */
        !           284:            if (pCurBox == pRegEnd)
        !           285:            {
        !           286:                curStart = prevStart;
        !           287:            }
        !           288:            else
        !           289:            {
        !           290:                do
        !           291:                {
        !           292:                    *pPrevBox++ = *pCurBox++;
        !           293:                } while (pCurBox != pRegEnd);
        !           294:            }
        !           295:            
        !           296:        }
        !           297:     }
        !           298:     return (curStart);
        !           299: }
        !           300: 
        !           301: /*-
        !           302:  *-----------------------------------------------------------------------
        !           303:  * miRegionOp --
        !           304:  *     Apply an operation to two regions. Called by miUnion, miInverse,
        !           305:  *     miSubtract, miIntersect...
        !           306:  *
        !           307:  * Results:
        !           308:  *     None.
        !           309:  *
        !           310:  * Side Effects:
        !           311:  *     The new region is overwritten.
        !           312:  *
        !           313:  * Notes:
        !           314:  *     The idea behind this function is to view the two regions as sets.
        !           315:  *     Together they cover a rectangle of area that this function divides
        !           316:  *     into horizontal bands where points are covered only by one region
        !           317:  *     or by both. For the first case, the nonOverlapFunc is called with
        !           318:  *     each the band and the band's upper and lower extents. For the
        !           319:  *     second, the overlapFunc is called to process the entire band. It
        !           320:  *     is responsible for clipping the rectangles in the band, though
        !           321:  *     this function provides the boundaries.
        !           322:  *     At the end of each band, the new region is coalesced, if possible,
        !           323:  *     to reduce the number of rectangles in the region.
        !           324:  *
        !           325:  *-----------------------------------------------------------------------
        !           326:  */
        !           327: static void
        !           328: miRegionOp(newReg, reg1, reg2, overlapFunc,  nonOverlap1Func, nonOverlap2Func)
        !           329:     register RegionPtr         newReg;                 /* Place to store result */
        !           330:     RegionPtr          reg1;                   /* First region in operation */
        !           331:     RegionPtr          reg2;                   /* 2d region in operation */
        !           332:     void               (*overlapFunc)();       /* Function to call for over-
        !           333:                                                 * lapping bands */
        !           334:     void               (*nonOverlap1Func)();   /* Function to call for non-
        !           335:                                                 * overlapping bands in region
        !           336:                                                 * 1 */
        !           337:     void               (*nonOverlap2Func)();   /* Function to call for non-
        !           338:                                                 * overlapping bands in region
        !           339:                                                 * 2 */
        !           340: {
        !           341:     register BoxPtr    r1;                     /* Pointer into first region */
        !           342:     register BoxPtr    r2;                     /* Pointer into 2d region */
        !           343:     BoxPtr             r1End;                  /* End of 1st region */
        !           344:     BoxPtr             r2End;                  /* End of 2d region */
        !           345:     register short     ybot;                   /* Bottom of intersection */
        !           346:     register short     ytop;                   /* Top of intersection */
        !           347:     BoxPtr             oldRects;               /* Old rects for newReg */
        !           348:     int                        oldSize;                /* Old size of newReg */
        !           349:     int                        prevBand;               /* Index of start of
        !           350:                                                 * previous band in newReg */
        !           351:     int                        curBand;                /* Index of start of current
        !           352:                                                 * band in newReg */
        !           353:     register BoxPtr    r1BandEnd;              /* End of current band in r1 */
        !           354:     register BoxPtr    r2BandEnd;              /* End of current band in r2 */
        !           355:     short              top;                    /* Top of non-overlapping
        !           356:                                                 * band */
        !           357:     short              bot;                    /* Bottom of non-overlapping
        !           358:                                                 * band */
        !           359:     
        !           360:     /*
        !           361:      * Initialization:
        !           362:      * set r1, r2, r1End and r2End appropriately, preserve the important
        !           363:      * parts of the destination region until the end in case it's one of
        !           364:      * the two source regions, then mark the "new" region empty, allocating
        !           365:      * another array of rectangles for it to use.
        !           366:      */
        !           367:     r1 = reg1->rects;
        !           368:     r2 = reg2->rects;
        !           369:     r1End = r1 + reg1->numRects;
        !           370:     r2End = r2 + reg2->numRects;
        !           371:     
        !           372:     oldSize = newReg->size;
        !           373:     oldRects = newReg->rects;
        !           374:     
        !           375:     EMPTY_REGION(newReg);
        !           376: 
        !           377:     /*
        !           378:      * Allocate a reasonable number of rectangles for the new region. The idea
        !           379:      * is to allocate enough so the individual functions don't need to
        !           380:      * reallocate and copy the array, which is time consuming, yet we don't
        !           381:      * have to worry about using too much memory. I hope to be able to
        !           382:      * nuke the Xrealloc() at the end of this function eventually.
        !           383:      */
        !           384:     newReg->size = max(reg1->numRects,reg2->numRects) * 2;
        !           385: 
        !           386:     newReg->rects = (BoxPtr) Xalloc (sizeof(BoxRec) * newReg->size);
        !           387:     
        !           388:     /*
        !           389:      * Initialize ybot and ytop.
        !           390:      * In the upcoming loop, ybot and ytop serve different functions depending
        !           391:      * on whether the band being handled is an overlapping or non-overlapping
        !           392:      * band.
        !           393:      *         In the case of a non-overlapping band (only one of the regions
        !           394:      * has points in the band), ybot is the bottom of the most recent
        !           395:      * intersection and thus clips the top of the rectangles in that band.
        !           396:      * ytop is the top of the next intersection between the two regions and
        !           397:      * serves to clip the bottom of the rectangles in the current band.
        !           398:      * For an overlapping band (where the two regions intersect), ytop clips
        !           399:      * the top of the rectangles of both regions and ybot clips the bottoms.
        !           400:      */
        !           401:     if (reg1->extents.y1 < reg2->extents.y1)
        !           402:     {
        !           403:        ybot = reg1->extents.y1;
        !           404:        ytop = reg2->extents.y1;
        !           405:     }
        !           406:     else
        !           407:     {
        !           408:        ybot = reg2->extents.y1;
        !           409:        ytop = reg1->extents.y1;
        !           410:     }
        !           411:     
        !           412:     /*
        !           413:      * prevBand serves to mark the start of the previous band so rectangles
        !           414:      * can be coalesced into larger rectangles. qv. miCoalesce, above.
        !           415:      * In the beginning, there is no previous band, so prevBand == curBand
        !           416:      * (curBand is set later on, of course, but the first band will always
        !           417:      * start at index 0). prevBand and curBand must be indices because of
        !           418:      * the possible expansion, and resultant moving, of the new region's
        !           419:      * array of rectangles.
        !           420:      */
        !           421:     prevBand = 0;
        !           422:     
        !           423:     do
        !           424:     {
        !           425:        curBand = newReg->numRects;
        !           426: 
        !           427:        /*
        !           428:         * This algorithm proceeds one source-band (as opposed to a
        !           429:         * destination band, which is determined by where the two regions
        !           430:         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
        !           431:         * rectangle after the last one in the current band for their
        !           432:         * respective regions.
        !           433:         */
        !           434:        r1BandEnd = r1;
        !           435:        while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
        !           436:        {
        !           437:            r1BandEnd++;
        !           438:        }
        !           439:        
        !           440:        r2BandEnd = r2;
        !           441:        while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
        !           442:        {
        !           443:            r2BandEnd++;
        !           444:        }
        !           445:        
        !           446:        /*
        !           447:         * First handle the band that doesn't intersect, if any.
        !           448:         *
        !           449:         * Note that attention is restricted to one band in the
        !           450:         * non-intersecting region at once, so if a region has n
        !           451:         * bands between the current position and the next place it overlaps
        !           452:         * the other, this entire loop will be passed through n times.
        !           453:         */
        !           454:        if (r1->y1 < r2->y1)
        !           455:        {
        !           456:            top = max(r1->y1,ybot);
        !           457:            bot = min(r1->y2,r2->y1);
        !           458: 
        !           459:            if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
        !           460:            {
        !           461:                (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
        !           462:            }
        !           463: 
        !           464:            ytop = r2->y1;
        !           465:        }
        !           466:        else if (r2->y1 < r1->y1)
        !           467:        {
        !           468:            top = max(r2->y1,ybot);
        !           469:            bot = min(r2->y2,r1->y1);
        !           470: 
        !           471:            if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
        !           472:            {
        !           473:                (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
        !           474:            }
        !           475: 
        !           476:            ytop = r1->y1;
        !           477:        }
        !           478:        else
        !           479:        {
        !           480:            ytop = r1->y1;
        !           481:        }
        !           482: 
        !           483:        /*
        !           484:         * If any rectangles got added to the region, try and coalesce them
        !           485:         * with rectangles from the previous band. Note we could just do
        !           486:         * this test in miCoalesce, but some machines incur a not
        !           487:         * inconsiderable cost for function calls, so...
        !           488:         */
        !           489:        if (newReg->numRects != curBand)
        !           490:        {
        !           491:            prevBand = miCoalesce (newReg, prevBand, curBand);
        !           492:        }
        !           493: 
        !           494:        /*
        !           495:         * Now see if we've hit an intersecting band. The two bands only
        !           496:         * intersect if ybot > ytop
        !           497:         */
        !           498:        ybot = min(r1->y2, r2->y2);
        !           499:        curBand = newReg->numRects;
        !           500:        if (ybot > ytop)
        !           501:        {
        !           502:            (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
        !           503: 
        !           504:        }
        !           505:        
        !           506:        if (newReg->numRects != curBand)
        !           507:        {
        !           508:            prevBand = miCoalesce (newReg, prevBand, curBand);
        !           509:        }
        !           510: 
        !           511:        /*
        !           512:         * If we've finished with a band (y2 == ybot) we skip forward
        !           513:         * in the region to the next band.
        !           514:         */
        !           515:        if (r1->y2 == ybot)
        !           516:        {
        !           517:            r1 = r1BandEnd;
        !           518:        }
        !           519:        if (r2->y2 == ybot)
        !           520:        {
        !           521:            r2 = r2BandEnd;
        !           522:        }
        !           523:     } while ((r1 != r1End) && (r2 != r2End));
        !           524: 
        !           525:     /*
        !           526:      * Deal with whichever region still has rectangles left.
        !           527:      */
        !           528:     curBand = newReg->numRects;
        !           529:     if (r1 != r1End)
        !           530:     {
        !           531:        if (nonOverlap1Func != (void (*)())NULL)
        !           532:        {
        !           533:            do
        !           534:            {
        !           535:                r1BandEnd = r1;
        !           536:                while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
        !           537:                {
        !           538:                    r1BandEnd++;
        !           539:                }
        !           540:                (* nonOverlap1Func) (newReg, r1, r1BandEnd,
        !           541:                                     max(r1->y1,ybot), r1->y2);
        !           542:                r1 = r1BandEnd;
        !           543:            } while (r1 != r1End);
        !           544:        }
        !           545:     }
        !           546:     else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
        !           547:     {
        !           548:        do
        !           549:        {
        !           550:            r2BandEnd = r2;
        !           551:            while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
        !           552:            {
        !           553:                 r2BandEnd++;
        !           554:            }
        !           555:            (* nonOverlap2Func) (newReg, r2, r2BandEnd,
        !           556:                                max(r2->y1,ybot), r2->y2);
        !           557:            r2 = r2BandEnd;
        !           558:        } while (r2 != r2End);
        !           559:     }
        !           560: 
        !           561:     if (newReg->numRects != curBand)
        !           562:     {
        !           563:        (void) miCoalesce (newReg, prevBand, curBand);
        !           564:     }
        !           565: 
        !           566:     /*
        !           567:      * A bit of cleanup. To keep regions from growing without bound,
        !           568:      * we shrink the array of rectangles to match the new number of
        !           569:      * rectangles in the region. This never goes to 0, however...
        !           570:      *
        !           571:      * Only do this stuff if the number of rectangles allocated is more than
        !           572:      * twice the number of rectangles in the region (a simple optimization...).
        !           573:      */
        !           574:     if (newReg->numRects < (newReg->size >> 1))
        !           575:     {
        !           576:        if (REGION_NOT_EMPTY(newReg))
        !           577:        {
        !           578:            newReg->size = newReg->numRects;
        !           579:            newReg->rects = (BoxPtr) Xrealloc (newReg->rects,
        !           580:                                               sizeof(BoxRec) * newReg->size);
        !           581:        }
        !           582:        else
        !           583:        {
        !           584:            /*
        !           585:             * No point in doing the extra work involved in an Xrealloc if
        !           586:             * the region is empty
        !           587:             */
        !           588:            newReg->size = 1;
        !           589:            Xfree(newReg->rects);
        !           590:            newReg->rects = (BoxPtr) Xalloc(sizeof(BoxRec));
        !           591:        }
        !           592:     }
        !           593:     Xfree (oldRects);
        !           594: }
        !           595: 
        !           596: /*-
        !           597:  *-----------------------------------------------------------------------
        !           598:  * miSetExtents --
        !           599:  *     Reset the extents of a region to what they should be. Called by
        !           600:  *     miSubtract and miIntersect b/c they can't figure it out along the
        !           601:  *     way or do so easily, as miUnion can.
        !           602:  *
        !           603:  * Results:
        !           604:  *     None.
        !           605:  *
        !           606:  * Side Effects:
        !           607:  *     The region's 'extents' structure is overwritten.
        !           608:  *
        !           609:  *-----------------------------------------------------------------------
        !           610:  */
        !           611: static void
        !           612: miSetExtents (pReg)
        !           613:     RegionPtr          pReg;
        !           614: {
        !           615:     register BoxPtr    pBox,
        !           616:                        pBoxEnd,
        !           617:                        pExtents;
        !           618: 
        !           619:     pExtents = &pReg->extents;
        !           620:     pBox = pReg->rects;
        !           621:     pBoxEnd = &pBox[pReg->numRects - 1];
        !           622: 
        !           623:     /*
        !           624:      * Since pBox is the first rectangle in the region, it must have the
        !           625:      * smallest y1 and since pBoxEnd is the last rectangle in the region,
        !           626:      * it must have the largest y2, because of banding. Initialize x1 and
        !           627:      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
        !           628:      * to...
        !           629:      */
        !           630:     pExtents->x1 = pBox->x1;
        !           631:     pExtents->y1 = pBox->y1;
        !           632:     pExtents->x2 = pBoxEnd->x2;
        !           633:     pExtents->y2 = pBoxEnd->y2;
        !           634: 
        !           635:     assert(pExtents->y1 < pExtents->y2);
        !           636:     while (pBox <= pBoxEnd)
        !           637:     {
        !           638:        if (pBox->x1 < pExtents->x1)
        !           639:        {
        !           640:            pExtents->x1 = pBox->x1;
        !           641:        }
        !           642:        if (pBox->x2 > pExtents->x2)
        !           643:        {
        !           644:            pExtents->x2 = pBox->x2;
        !           645:        }
        !           646:        pBox++;
        !           647:     }
        !           648:     assert(pExtents->x1 < pExtents->x2);
        !           649: }
        !           650: 
        !           651: 
        !           652: /*======================================================================
        !           653:  *         Region Inversion
        !           654:  *====================================================================*/
        !           655: 
        !           656: /*-
        !           657:  *-----------------------------------------------------------------------
        !           658:  * miInverse --
        !           659:  *     Take a region and a box and return a region that is everything
        !           660:  *     in the box but not in the region. The careful reader will note
        !           661:  *     that this is the same as subtracting the region from the box...
        !           662:  *
        !           663:  * Results:
        !           664:  *     TRUE.
        !           665:  *
        !           666:  * Side Effects:
        !           667:  *     newReg is overwritten.
        !           668:  *
        !           669:  *-----------------------------------------------------------------------
        !           670:  */
        !           671: int 
        !           672: miInverse(newReg, reg1, invRect)
        !           673:     RegionPtr    newReg;       /* Destination region */
        !           674:     RegionPtr    reg1;         /* Region to invert */
        !           675:     BOX          *invRect;     /* Bounding box for inversion */
        !           676: {
        !           677:     RegionRec    invReg;       /* Quick and dirty region made from the
        !           678:                                 * bounding box */
        !           679: 
        !           680:     invReg.size =      1;
        !           681:     invReg.numRects =  1;
        !           682:     invReg.extents =   *invRect;
        !           683:     invReg.rects =     invRect;
        !           684:     return (miSubtract (newReg, &invReg, reg1));
        !           685: }
        !           686: 
        !           687: 
        !           688: /*======================================================================
        !           689:  *         Region Intersection
        !           690:  *====================================================================*/
        !           691: /*-
        !           692:  *-----------------------------------------------------------------------
        !           693:  * miIntersectO --
        !           694:  *     Handle an overlapping band for miIntersect.
        !           695:  *
        !           696:  * Results:
        !           697:  *     None.
        !           698:  *
        !           699:  * Side Effects:
        !           700:  *     Rectangles may be added to the region.
        !           701:  *
        !           702:  *-----------------------------------------------------------------------
        !           703:  */
        !           704: static void
        !           705: miIntersectO (pReg, r1, r1End, r2, r2End, y1, y2)
        !           706:     register RegionPtr pReg;
        !           707:     register BoxPtr    r1;
        !           708:     BoxPtr             r1End;
        !           709:     register BoxPtr    r2;
        !           710:     BoxPtr             r2End;
        !           711:     short              y1;
        !           712:     short              y2;
        !           713: {
        !           714:     register short     x1;
        !           715:     register short     x2;
        !           716:     register BoxPtr    pNextRect;
        !           717: 
        !           718:     pNextRect = &pReg->rects[pReg->numRects];
        !           719: 
        !           720:     while ((r1 != r1End) && (r2 != r2End))
        !           721:     {
        !           722:        x1 = max(r1->x1,r2->x1);
        !           723:        x2 = min(r1->x2,r2->x2);
        !           724: 
        !           725:        /*
        !           726:         * If there's any overlap between the two rectangles, add that
        !           727:         * overlap to the new region.
        !           728:         * There's no need to check for subsumption because the only way
        !           729:         * such a need could arise is if some region has two rectangles
        !           730:         * right next to each other. Since that should never happen...
        !           731:         */
        !           732:        if (x1 < x2)
        !           733:        {
        !           734:            assert(y1<y2);
        !           735: 
        !           736:            MEMCHECK(pReg, pNextRect, pReg->rects);
        !           737:            pNextRect->x1 = x1;
        !           738:            pNextRect->y1 = y1;
        !           739:            pNextRect->x2 = x2;
        !           740:            pNextRect->y2 = y2;
        !           741:            pReg->numRects += 1;
        !           742:            pNextRect++;
        !           743:            assert(pReg->numRects <= pReg->size);
        !           744:        }
        !           745: 
        !           746:        /*
        !           747:         * Need to advance the pointers. Shift the one that extends
        !           748:         * to the right the least, since the other still has a chance to
        !           749:         * overlap with that region's next rectangle, if you see what I mean.
        !           750:         */
        !           751:        if (r1->x2 < r2->x2)
        !           752:        {
        !           753:            r1++;
        !           754:        }
        !           755:        else if (r2->x2 < r1->x2)
        !           756:        {
        !           757:            r2++;
        !           758:        }
        !           759:        else
        !           760:        {
        !           761:            r1++;
        !           762:            r2++;
        !           763:        }
        !           764:     }
        !           765: }
        !           766: 
        !           767: 
        !           768: int 
        !           769: miIntersect(newReg, reg1, reg2)
        !           770:     register RegionPtr         newReg;               /* destination Region */
        !           771:     RegionPtr          reg1;
        !           772:     RegionPtr          reg2;          /* source regions     */
        !           773: {
        !           774:    /* check for trivial reject */
        !           775:     if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
        !           776:        (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
        !           777:     {
        !           778:         newReg->numRects = 0;
        !           779:         return(1);
        !           780:     }
        !           781: 
        !           782:     miRegionOp (newReg, reg1, reg2, miIntersectO, NULL, NULL);
        !           783:     
        !           784:     if (newReg->numRects != 0)
        !           785:     {
        !           786:        /*
        !           787:         * Can't alter newReg's extents before we call miRegionOp because
        !           788:         * it might be one of the source regions and miRegionOp depends
        !           789:         * on the extents of those regions being the same. Besides, this
        !           790:         * way there's no checking against rectangles that will be nuked
        !           791:         * due to coalescing, so we have to examine fewer rectangles.
        !           792:         */
        !           793:        miSetExtents(newReg);
        !           794:     }
        !           795:     return(1);
        !           796: }
        !           797: 
        !           798: 
        !           799: /*======================================================================
        !           800:  *         Region Union
        !           801:  *====================================================================*/
        !           802: 
        !           803: /*-
        !           804:  *-----------------------------------------------------------------------
        !           805:  * miUnionNonO --
        !           806:  *     Handle a non-overlapping band for the union operation. Just
        !           807:  *     Adds the rectangles into the region. Doesn't have to check for
        !           808:  *     subsumption or anything.
        !           809:  *
        !           810:  * Results:
        !           811:  *     None.
        !           812:  *
        !           813:  * Side Effects:
        !           814:  *     pReg->numRects is incremented and the final rectangles overwritten
        !           815:  *     with the rectangles we're passed.
        !           816:  *
        !           817:  *-----------------------------------------------------------------------
        !           818:  */
        !           819: static void
        !           820: miUnionNonO (pReg, r, rEnd, y1, y2)
        !           821:     register RegionPtr pReg;
        !           822:     register BoxPtr    r;
        !           823:     BoxPtr             rEnd;
        !           824:     register short     y1;
        !           825:     register short     y2;
        !           826: {
        !           827:     register BoxPtr    pNextRect;
        !           828: 
        !           829:     pNextRect = &pReg->rects[pReg->numRects];
        !           830: 
        !           831:     assert(y1 < y2);
        !           832: 
        !           833:     while (r != rEnd)
        !           834:     {
        !           835:        assert(r->x1 < r->x2);
        !           836:        MEMCHECK(pReg, pNextRect, pReg->rects);
        !           837:        pNextRect->x1 = r->x1;
        !           838:        pNextRect->y1 = y1;
        !           839:        pNextRect->x2 = r->x2;
        !           840:        pNextRect->y2 = y2;
        !           841:        pReg->numRects += 1;
        !           842:        pNextRect++;
        !           843: 
        !           844:        assert(pReg->numRects<=pReg->size);
        !           845:        r++;
        !           846:     }
        !           847: 
        !           848: }
        !           849: 
        !           850: /*-
        !           851:  *-----------------------------------------------------------------------
        !           852:  * miUnionO --
        !           853:  *     Handle an overlapping band for the union operation. Picks the
        !           854:  *     left-most rectangle each time and merges it into the region.
        !           855:  *
        !           856:  * Results:
        !           857:  *     None.
        !           858:  *
        !           859:  * Side Effects:
        !           860:  *     Rectangles are overwritten in pReg->rects and pReg->numRects will
        !           861:  *     be changed.
        !           862:  *
        !           863:  *-----------------------------------------------------------------------
        !           864:  */
        !           865: static void
        !           866: miUnionO (pReg, r1, r1End, r2, r2End, y1, y2)
        !           867:     register RegionPtr pReg;
        !           868:     register BoxPtr    r1;
        !           869:     BoxPtr             r1End;
        !           870:     register BoxPtr    r2;
        !           871:     BoxPtr             r2End;
        !           872:     register short     y1;
        !           873:     register short     y2;
        !           874: {
        !           875:     register BoxPtr    pNextRect;
        !           876:     
        !           877:     pNextRect = &pReg->rects[pReg->numRects];
        !           878: 
        !           879: #define MERGERECT(r) \
        !           880:     if ((pReg->numRects != 0) &&  \
        !           881:        (pNextRect[-1].y1 == y1) &&  \
        !           882:        (pNextRect[-1].y2 == y2) &&  \
        !           883:        (pNextRect[-1].x2 >= r->x1))  \
        !           884:     {  \
        !           885:        if (pNextRect[-1].x2 < r->x2)  \
        !           886:        {  \
        !           887:            pNextRect[-1].x2 = r->x2;  \
        !           888:            assert(pNextRect[-1].x1<pNextRect[-1].x2); \
        !           889:        }  \
        !           890:     }  \
        !           891:     else  \
        !           892:     {  \
        !           893:        MEMCHECK(pReg, pNextRect, pReg->rects);  \
        !           894:        pNextRect->y1 = y1;  \
        !           895:        pNextRect->y2 = y2;  \
        !           896:        pNextRect->x1 = r->x1;  \
        !           897:        pNextRect->x2 = r->x2;  \
        !           898:        pReg->numRects += 1;  \
        !           899:         pNextRect += 1;  \
        !           900:     }  \
        !           901:     assert(pReg->numRects<=pReg->size);\
        !           902:     r++;
        !           903:     
        !           904:     assert (y1<y2);
        !           905:     while ((r1 != r1End) && (r2 != r2End))
        !           906:     {
        !           907:        if (r1->x1 < r2->x1)
        !           908:        {
        !           909:            MERGERECT(r1);
        !           910:        }
        !           911:        else
        !           912:        {
        !           913:            MERGERECT(r2);
        !           914:        }
        !           915:     }
        !           916:     
        !           917:     if (r1 != r1End)
        !           918:     {
        !           919:        do
        !           920:        {
        !           921:            MERGERECT(r1);
        !           922:        } while (r1 != r1End);
        !           923:     }
        !           924:     else while (r2 != r2End)
        !           925:     {
        !           926:        MERGERECT(r2);
        !           927:     }
        !           928: }
        !           929: 
        !           930: int 
        !           931: miUnion(newReg, reg1, reg2)
        !           932:     RegionPtr    newReg;                  /* destination Region */
        !           933:     RegionPtr    reg1;
        !           934:     RegionPtr    reg2;             /* source regions     */
        !           935: {
        !           936:     /*  checks all the simple cases */
        !           937: 
        !           938:     /*
        !           939:      * Region 1 and 2 are the same or region 1 is empty
        !           940:      */
        !           941:     if ( (reg1 == reg2) || (!(reg1->numRects)) )
        !           942:     {
        !           943:         if (newReg != reg2)
        !           944:             miRegionCopy(newReg, reg2);
        !           945:         return(TRUE);
        !           946:     }
        !           947: 
        !           948:     /*
        !           949:      * if nothing to union (region 2 empty)
        !           950:      */
        !           951:     if (!(reg2->numRects))
        !           952:     {
        !           953:         if (newReg != reg1)
        !           954:             miRegionCopy(newReg, reg1);
        !           955:         return(TRUE);
        !           956:     }
        !           957: 
        !           958:     /*
        !           959:      * Region 1 completely subsumes region 2
        !           960:      */
        !           961:     if ((reg1->numRects == 1) && 
        !           962:        (reg1->extents.x1 <= reg2->extents.x1) &&
        !           963:        (reg1->extents.y1 <= reg2->extents.y1) &&
        !           964:        (reg1->extents.x2 >= reg2->extents.x2) &&
        !           965:        (reg1->extents.y2 >= reg2->extents.y2))
        !           966:     {
        !           967:         if (newReg != reg1)
        !           968:             miRegionCopy(newReg, reg1);
        !           969:         return(TRUE);
        !           970:     }
        !           971: 
        !           972:     /*
        !           973:      * Region 2 completely subsumes region 1
        !           974:      */
        !           975:     if ((reg2->numRects == 1) && 
        !           976:        (reg2->extents.x1 <= reg1->extents.x1) &&
        !           977:        (reg2->extents.y1 <= reg1->extents.y1) &&
        !           978:        (reg2->extents.x2 >= reg1->extents.x2) &&
        !           979:        (reg2->extents.y2 >= reg1->extents.y2))
        !           980:     {
        !           981:         if (newReg != reg2)
        !           982:             miRegionCopy(newReg, reg2);
        !           983:         return(TRUE);
        !           984:     }
        !           985: 
        !           986:     miRegionOp (newReg, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
        !           987: 
        !           988:     newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
        !           989:     newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
        !           990:     newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
        !           991:     newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
        !           992: 
        !           993:     return(1);
        !           994: }
        !           995: 
        !           996: 
        !           997: 
        !           998: /*======================================================================
        !           999:  *               Region Subtraction
        !          1000:  *====================================================================*/
        !          1001: 
        !          1002: /*-
        !          1003:  *-----------------------------------------------------------------------
        !          1004:  * miSubtractNonO --
        !          1005:  *     Deal with non-overlapping band for subtraction. Any parts from
        !          1006:  *     region 2 we discard. Anything from region 1 we add to the region.
        !          1007:  *
        !          1008:  * Results:
        !          1009:  *     None.
        !          1010:  *
        !          1011:  * Side Effects:
        !          1012:  *     pReg may be affected.
        !          1013:  *
        !          1014:  *-----------------------------------------------------------------------
        !          1015:  */
        !          1016: static void
        !          1017: miSubtractNonO1 (pReg, r, rEnd, y1, y2)
        !          1018:     register RegionPtr pReg;
        !          1019:     register BoxPtr    r;
        !          1020:     BoxPtr             rEnd;
        !          1021:     register short     y1;
        !          1022:     register short     y2;
        !          1023: {
        !          1024:     register BoxPtr    pNextRect;
        !          1025:        
        !          1026:     pNextRect = &pReg->rects[pReg->numRects];
        !          1027:        
        !          1028:     assert(y1<y2);
        !          1029: 
        !          1030:     while (r != rEnd)
        !          1031:     {
        !          1032:        assert(r->x1<r->x2);
        !          1033:        MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1034:        pNextRect->x1 = r->x1;
        !          1035:        pNextRect->y1 = y1;
        !          1036:        pNextRect->x2 = r->x2;
        !          1037:        pNextRect->y2 = y2;
        !          1038:        pReg->numRects += 1;
        !          1039:        pNextRect++;
        !          1040: 
        !          1041:        assert(pReg->numRects <= pReg->size);
        !          1042: 
        !          1043:        r++;
        !          1044:     }
        !          1045: }
        !          1046: 
        !          1047: /*-
        !          1048:  *-----------------------------------------------------------------------
        !          1049:  * miSubtractO --
        !          1050:  *     Overlapping band subtraction. x1 is the left-most point not yet
        !          1051:  *     checked.
        !          1052:  *
        !          1053:  * Results:
        !          1054:  *     None.
        !          1055:  *
        !          1056:  * Side Effects:
        !          1057:  *     pReg may have rectangles added to it.
        !          1058:  *
        !          1059:  *-----------------------------------------------------------------------
        !          1060:  */
        !          1061: static void
        !          1062: miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2)
        !          1063:     register RegionPtr pReg;
        !          1064:     register BoxPtr    r1;
        !          1065:     BoxPtr             r1End;
        !          1066:     register BoxPtr    r2;
        !          1067:     BoxPtr             r2End;
        !          1068:     register short     y1;
        !          1069:     register short     y2;
        !          1070: {
        !          1071:     register BoxPtr    pNextRect;
        !          1072:     register int       x1;
        !          1073:     
        !          1074:     x1 = r1->x1;
        !          1075:     
        !          1076:     assert(y1<y2);
        !          1077:     pNextRect = &pReg->rects[pReg->numRects];
        !          1078: 
        !          1079:     while ((r1 != r1End) && (r2 != r2End))
        !          1080:     {
        !          1081:        if (r2->x2 <= x1)
        !          1082:        {
        !          1083:            /*
        !          1084:             * Subtrahend missed the boat: go to next subtrahend.
        !          1085:             */
        !          1086:            r2++;
        !          1087:        }
        !          1088:        else if (r2->x1 <= x1)
        !          1089:        {
        !          1090:            /*
        !          1091:             * Subtrahend preceeds minuend: nuke left edge of minuend.
        !          1092:             */
        !          1093:            x1 = r2->x2;
        !          1094:            if (x1 >= r1->x2)
        !          1095:            {
        !          1096:                /*
        !          1097:                 * Minuend completely covered: advance to next minuend and
        !          1098:                 * reset left fence to edge of new minuend.
        !          1099:                 */
        !          1100:                r1++;
        !          1101:                x1 = r1->x1;
        !          1102:            }
        !          1103:            else
        !          1104:            {
        !          1105:                /*
        !          1106:                 * Subtrahend now used up since it doesn't extend beyond
        !          1107:                 * minuend
        !          1108:                 */
        !          1109:                r2++;
        !          1110:            }
        !          1111:        }
        !          1112:        else if (r2->x1 < r1->x2)
        !          1113:        {
        !          1114:            /*
        !          1115:             * Left part of subtrahend covers part of minuend: add uncovered
        !          1116:             * part of minuend to region and skip to next subtrahend.
        !          1117:             */
        !          1118:            assert(x1<r2->x1);
        !          1119:            MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1120:            pNextRect->x1 = x1;
        !          1121:            pNextRect->y1 = y1;
        !          1122:            pNextRect->x2 = r2->x1;
        !          1123:            pNextRect->y2 = y2;
        !          1124:            pReg->numRects += 1;
        !          1125:            pNextRect++;
        !          1126: 
        !          1127:            assert(pReg->numRects<=pReg->size);
        !          1128: 
        !          1129:            x1 = r2->x2;
        !          1130:            if (x1 >= r1->x2)
        !          1131:            {
        !          1132:                /*
        !          1133:                 * Minuend used up: advance to new...
        !          1134:                 */
        !          1135:                r1++;
        !          1136:                x1 = r1->x1;
        !          1137:            }
        !          1138:            else
        !          1139:            {
        !          1140:                /*
        !          1141:                 * Subtrahend used up
        !          1142:                 */
        !          1143:                r2++;
        !          1144:            }
        !          1145:        }
        !          1146:        else
        !          1147:        {
        !          1148:            /*
        !          1149:             * Minuend used up: add any remaining piece before advancing.
        !          1150:             */
        !          1151:            if (r1->x2 > x1)
        !          1152:            {
        !          1153:                MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1154:                pNextRect->x1 = x1;
        !          1155:                pNextRect->y1 = y1;
        !          1156:                pNextRect->x2 = r1->x2;
        !          1157:                pNextRect->y2 = y2;
        !          1158:                pReg->numRects += 1;
        !          1159:                pNextRect++;
        !          1160:                assert(pReg->numRects<=pReg->size);
        !          1161:            }
        !          1162:            r1++;
        !          1163:            x1 = r1->x1;
        !          1164:        }
        !          1165:     }
        !          1166: 
        !          1167:     /*
        !          1168:      * Add remaining minuend rectangles to region.
        !          1169:      */
        !          1170:     while (r1 != r1End)
        !          1171:     {
        !          1172:        assert(x1<r1->x2);
        !          1173:        MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1174:        pNextRect->x1 = x1;
        !          1175:        pNextRect->y1 = y1;
        !          1176:        pNextRect->x2 = r1->x2;
        !          1177:        pNextRect->y2 = y2;
        !          1178:        pReg->numRects += 1;
        !          1179:        pNextRect++;
        !          1180: 
        !          1181:        assert(pReg->numRects<=pReg->size);
        !          1182: 
        !          1183:        r1++;
        !          1184:        if (r1 != r1End)
        !          1185:        {
        !          1186:            x1 = r1->x1;
        !          1187:        }
        !          1188:     }
        !          1189: }
        !          1190:        
        !          1191: /*-
        !          1192:  *-----------------------------------------------------------------------
        !          1193:  * miSubtract --
        !          1194:  *     Subtract regS from regM and leave the result in regD.
        !          1195:  *     S stands for subtrahend, M for minuend and D for difference.
        !          1196:  *
        !          1197:  * Results:
        !          1198:  *     TRUE.
        !          1199:  *
        !          1200:  * Side Effects:
        !          1201:  *     regD is overwritten.
        !          1202:  *
        !          1203:  *-----------------------------------------------------------------------
        !          1204:  */
        !          1205: int 
        !          1206: miSubtract(regD, regM, regS)
        !          1207:     register RegionPtr regD;               
        !          1208:     RegionPtr          regM;
        !          1209:     RegionPtr          regS;          
        !          1210: {
        !          1211:    /* check for trivial reject */
        !          1212:     if ( (!(regM->numRects)) || (!(regS->numRects))  ||
        !          1213:        (!EXTENTCHECK(&regM->extents, &regS->extents)) )
        !          1214:     {
        !          1215:        miRegionCopy(regD, regM);
        !          1216:         return(1);
        !          1217:     }
        !          1218:  
        !          1219:     miRegionOp (regD, regM, regS, miSubtractO, miSubtractNonO1, NULL);
        !          1220: 
        !          1221:     if (regD->numRects != 0)
        !          1222:     {
        !          1223:        /*
        !          1224:         * Can't alter newReg's extents before we call miRegionOp because
        !          1225:         * it might be one of the source regions and miRegionOp depends
        !          1226:         * on the extents of those regions being the unaltered. Besides, this
        !          1227:         * way there's no checking against rectangles that will be nuked
        !          1228:         * due to coalescing, so we have to examine fewer rectangles.
        !          1229:         */
        !          1230:        miSetExtents (regD);
        !          1231:     }
        !          1232:     return(1);
        !          1233: }
        !          1234: 
        !          1235: 
        !          1236: /*
        !          1237:  *   RectIn(region, rect)
        !          1238:  *   This routine takes a pointer to a region and a pointer to a box
        !          1239:  *   and determines if the box is outside/inside/partly inside the region.
        !          1240:  *
        !          1241:  *   The idea is to travel through the list of rectangles trying to cover the
        !          1242:  *   passed box with them. Anytime a piece of the rectangle isn't covered
        !          1243:  *   by a band of rectangles, partOut is set TRUE. Any time a rectangle in
        !          1244:  *   the region covers part of the box, partIn is set TRUE. The process ends
        !          1245:  *   when either the box has been completely covered (we reached a band that
        !          1246:  *   doesn't overlap the box, partIn is TRUE and partOut is false), the
        !          1247:  *   box has been partially covered (partIn == partOut == TRUE -- because of
        !          1248:  *   the banding, the first time this is true we know the box is only
        !          1249:  *   partially in the region) or is outside the region (we reached a band
        !          1250:  *   that doesn't overlap the box at all and partIn is false)
        !          1251:  */
        !          1252: 
        !          1253: int
        !          1254: miRectIn(region, prect)
        !          1255:     register RegionPtr  region;
        !          1256:     register BoxPtr     prect;
        !          1257: {
        !          1258:     register short x;
        !          1259:     register short y;
        !          1260:     register BoxPtr pbox;
        !          1261:     register BoxPtr pboxEnd;
        !          1262:     int      partIn, partOut;
        !          1263: 
        !          1264:     /* this is (just) a useful optimization */
        !          1265:     if ((region->numRects == 0) || !EXTENTCHECK(&region->extents, prect))
        !          1266:         return(rgnOUT);
        !          1267: 
        !          1268:     partOut = FALSE;
        !          1269:     partIn = FALSE;
        !          1270: 
        !          1271:     /* (x,y) starts at upper left of rect, moving to the right and down */
        !          1272:     x = prect->x1;
        !          1273:     y = prect->y1;
        !          1274: 
        !          1275:     /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
        !          1276:     for (pbox = region->rects, pboxEnd = pbox + region->numRects;
        !          1277:          pbox < pboxEnd;
        !          1278:          pbox++)
        !          1279:     {
        !          1280: 
        !          1281:         if (pbox->y2 <= y)
        !          1282:            continue;    /* getting up to speed or skipping remainder of band */
        !          1283: 
        !          1284:         if (pbox->y1 > y)
        !          1285:         {
        !          1286:            partOut = TRUE;      /* missed part of rectangle above */
        !          1287:            if (partIn || (pbox->y1 >= prect->y2))
        !          1288:               break;
        !          1289:            y = pbox->y1;        /* x guaranteed to be == prect->x1 */
        !          1290:         }
        !          1291: 
        !          1292:         if (pbox->x2 <= x)
        !          1293:            continue;            /* not far enough over yet */
        !          1294: 
        !          1295:         if (pbox->x1 > x)
        !          1296:         {
        !          1297:            partOut = TRUE;      /* missed part of rectangle to left */
        !          1298:            if (partIn)
        !          1299:               break;
        !          1300:         }
        !          1301: 
        !          1302:         if (pbox->x1 < prect->x2)
        !          1303:         {
        !          1304:             partIn = TRUE;      /* definitely overlap */
        !          1305:             if (partOut)
        !          1306:                break;
        !          1307:         }
        !          1308: 
        !          1309:         if (pbox->x2 >= prect->x2)
        !          1310:         {
        !          1311:            y = pbox->y2;        /* finished with this band */
        !          1312:            if (y >= prect->y2)
        !          1313:               break;
        !          1314:            x = prect->x1;       /* reset x out to left again */
        !          1315:         }
        !          1316:        else
        !          1317:        {
        !          1318:            /*
        !          1319:             * Because boxes in a band are maximal width, if the first box
        !          1320:             * to overlap the rectangle doesn't completely cover it in that
        !          1321:             * band, the rectangle must be partially out, since some of it
        !          1322:             * will be uncovered in that band. partIn will have been set true
        !          1323:             * by now...
        !          1324:             */
        !          1325:            partOut = TRUE;
        !          1326:            break;
        !          1327:        }
        !          1328:     }
        !          1329: 
        !          1330:     return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
        !          1331: }
        !          1332: 
        !          1333: /* TranslateRegion(pRegion, x, y)
        !          1334:    translates in place
        !          1335:    added by raymond
        !          1336: */
        !          1337: 
        !          1338: void
        !          1339: miTranslateRegion(pRegion, x, y)
        !          1340:     register RegionPtr pRegion;
        !          1341:     register int x;
        !          1342:     register int y;
        !          1343: {
        !          1344:     register int nbox;
        !          1345:     register BOX *pbox;
        !          1346: 
        !          1347:     pbox = pRegion->rects;
        !          1348:     nbox = pRegion->numRects;
        !          1349: 
        !          1350:     while(nbox--)
        !          1351:     {
        !          1352:        pbox->x1 += x;
        !          1353:        pbox->x2 += x;
        !          1354:        pbox->y1 += y;
        !          1355:        pbox->y2 += y;
        !          1356:        pbox++;
        !          1357:     }
        !          1358:     pRegion->extents.x1 += x;
        !          1359:     pRegion->extents.x2 += x;
        !          1360:     pRegion->extents.y1 += y;
        !          1361:     pRegion->extents.y2 += y;
        !          1362: }
        !          1363: 
        !          1364: void
        !          1365: miRegionDestroy(pRegion)
        !          1366:     RegionPtr pRegion;
        !          1367: {
        !          1368:     Xfree(pRegion->rects);
        !          1369:     Xfree(pRegion);
        !          1370: }
        !          1371: 
        !          1372: 
        !          1373: void
        !          1374: miRegionReset(pRegion, pBox)
        !          1375:     RegionPtr pRegion;
        !          1376:     BOX *pBox;
        !          1377: {
        !          1378:     assert(pBox->x1<pBox->x2);
        !          1379:     assert(pBox->y1<pBox->y2);
        !          1380:     pRegion->extents.x1 = pRegion->rects->x1 = pBox->x1;
        !          1381:     pRegion->extents.y1 = pRegion->rects->y1 = pBox->y1;
        !          1382:     pRegion->extents.x2 = pRegion->rects->x2 = pBox->x2;
        !          1383:     pRegion->extents.y2 = pRegion->rects->y2 = pBox->y2;
        !          1384: 
        !          1385:     pRegion->numRects = 1;
        !          1386: }
        !          1387: 
        !          1388: #define INBOX(r, x, y) \
        !          1389:       ( ( ((r).x2 >  x)) && \
        !          1390:         ( ((r).x1 <= x)) && \
        !          1391:         ( ((r).y2 >  y)) && \
        !          1392:         ( ((r).y1 <= y)) )
        !          1393: 
        !          1394: Bool
        !          1395: miPointInRegion(pRegion, x, y, box)
        !          1396:     register RegionPtr pRegion;
        !          1397:     register int x, y;
        !          1398:     BOX *box;     /* "return" value */
        !          1399: {
        !          1400:     register BOX *pbox, *pboxEnd;
        !          1401: 
        !          1402:     if (pRegion->numRects == 0)
        !          1403:         return(FALSE);
        !          1404:     if (!INBOX(pRegion->extents, x, y))
        !          1405:         return(FALSE);
        !          1406:     for (pbox = pRegion->rects, pboxEnd = pbox + pRegion->numRects;
        !          1407:         pbox < pboxEnd;
        !          1408:         pbox++)
        !          1409:     {
        !          1410:         if (y >= pbox->y2)
        !          1411:           continue;            /* not there yet */
        !          1412:        if ((y < pbox->y1) || (x < pbox->x1))
        !          1413:           break;               /* missed it */
        !          1414:        if (x >= pbox->x2)
        !          1415:           continue;            /* not there yet */
        !          1416:        *box = *pbox;
        !          1417:        return(TRUE);
        !          1418:     }
        !          1419:     return(FALSE);
        !          1420: }
        !          1421: 
        !          1422: Bool
        !          1423: miRegionNotEmpty(pRegion)
        !          1424:     RegionPtr pRegion;
        !          1425: {
        !          1426:     return(pRegion->numRects != 0);
        !          1427: }
        !          1428: 
        !          1429: 
        !          1430: void
        !          1431: miRegionEmpty(pRegion)
        !          1432:     RegionPtr pRegion;
        !          1433: {
        !          1434:     pRegion->numRects = 0;
        !          1435: }
        !          1436: 
        !          1437: BoxPtr
        !          1438: miRegionExtents(pReg)
        !          1439:     RegionPtr pReg;
        !          1440: {
        !          1441:     return((BoxPtr) &pReg->extents);
        !          1442: }
        !          1443: 
        !          1444: /*
        !          1445:     Clip a list of scanlines to a region.  The caller has allocated the
        !          1446:     spce.  FSorted is non-zero if the scanline origins are in ascending
        !          1447:     order.
        !          1448:     returns the number of new, clipped scanlines.
        !          1449: */
        !          1450: 
        !          1451: int
        !          1452: miClipSpans(prgnDst, ppt, pwidth, nspans, pptNew, pwidthNew, fSorted)
        !          1453:     RegionPtr          prgnDst;
        !          1454:     register DDXPointPtr ppt;
        !          1455:     int                       *pwidth;
        !          1456:     int                        nspans;
        !          1457:     register DDXPointPtr pptNew;
        !          1458:     int                       *pwidthNew;
        !          1459:     int                        fSorted;
        !          1460: {
        !          1461:     register BoxPtr    pbox, pboxLast, pboxTest;
        !          1462:     register DDXPointPtr pptLast;
        !          1463:     int                        xStart, xEnd;
        !          1464:     int                        yMax;
        !          1465:     int                        *pwidthNewThatWeWerePassed;     /* the vengeance
        !          1466:                                                           of Xerox! */
        !          1467: 
        !          1468:     pptLast = ppt + nspans;
        !          1469: 
        !          1470:     pbox =  prgnDst->rects;
        !          1471:     pboxLast = pbox + prgnDst->numRects;
        !          1472:     yMax = prgnDst->extents.y2;
        !          1473:     pwidthNewThatWeWerePassed = pwidthNew;
        !          1474: 
        !          1475:     if(fSorted)
        !          1476:     {
        !          1477:     /* scan lines sorted in ascending order. Because they are sorted, we
        !          1478:      * don't have to check each scanline against each clip box.  We can be
        !          1479:      * sure that this scanline only has to be clipped to boxes at or after the
        !          1480:      * beginning of this y-band 
        !          1481:      */
        !          1482:        pboxTest = pbox;
        !          1483:        while(ppt < pptLast)
        !          1484:        {
        !          1485:            pbox = pboxTest;
        !          1486:            if(ppt->y >= yMax)
        !          1487:                break;
        !          1488:            while(pbox < pboxLast)
        !          1489:            {
        !          1490:                if(*pwidth == 0)
        !          1491:                {
        !          1492:                    /* Null span */
        !          1493:                    break;
        !          1494:                }
        !          1495:                else if(pbox->y1 > ppt->y)
        !          1496:                {
        !          1497:                    /* scanline is before clip box */
        !          1498:                    break;
        !          1499:                }
        !          1500:                else if(pbox->y2 <= ppt->y)
        !          1501:                {
        !          1502:                    /* clip box is before scanline */
        !          1503:                    pboxTest = ++pbox;
        !          1504:                    continue;
        !          1505:                }
        !          1506:                else if(pbox->x1 > ppt->x + *pwidth) 
        !          1507:                {
        !          1508:                    /* clip box is to right of scanline */
        !          1509:                    break;
        !          1510:                }
        !          1511:                else if(pbox->x2 <= ppt->x)
        !          1512:                {
        !          1513:                    /* scanline is to right of clip box */
        !          1514:                    pbox++;
        !          1515:                    continue;
        !          1516:                }
        !          1517: 
        !          1518:                /* at least some of the scanline is in the current clip box */
        !          1519:                xStart = max(pbox->x1, ppt->x);
        !          1520:                xEnd = min(ppt->x + *pwidth, pbox->x2);
        !          1521:                pptNew->x = xStart;
        !          1522:                pptNew++->y = ppt->y;
        !          1523:                *pwidthNew++ = xEnd - xStart;
        !          1524: 
        !          1525:                if(ppt->x + *pwidth <= pbox->x2)
        !          1526:                {
        !          1527:                    /* End of the line, as it were */
        !          1528:                    break;
        !          1529:                }
        !          1530:                else
        !          1531:                    pbox++;
        !          1532:            }
        !          1533:            /* We've tried this span against every box; it must be outside them
        !          1534:             * all.  move on to the next span */
        !          1535:            ppt++;
        !          1536:            pwidth++;
        !          1537:        }
        !          1538:     }
        !          1539:     else
        !          1540:     {
        !          1541:     /* scan lines not sorted. We must clip each line against all the boxes */
        !          1542:        while(ppt < pptLast)
        !          1543:        {
        !          1544:            if(ppt->y >= 0 && ppt->y < yMax)
        !          1545:            {
        !          1546:                
        !          1547:                for(pbox = prgnDst->rects; pbox< pboxLast; pbox++)
        !          1548:                {
        !          1549:                    if(pbox->y1 > ppt->y)
        !          1550:                    {
        !          1551:                        /* rest of clip region is above this scanline,
        !          1552:                         * skip it */
        !          1553:                        break;
        !          1554:                    }
        !          1555:                    if(pbox->y2 <= ppt->y)
        !          1556:                    {
        !          1557:                        /* clip box is below scanline */
        !          1558:                        pbox++;
        !          1559:                        break;
        !          1560:                    }
        !          1561:                    if(pbox->x1 <= ppt->x + *pwidth &&
        !          1562:                       pbox->x2 > ppt->x)
        !          1563:                    {
        !          1564:                        xStart = max(pbox->x1, ppt->x);
        !          1565:                        xEnd = min(pbox->x2, ppt->x + *pwidth);
        !          1566:                        pptNew->x = xStart;
        !          1567:                        pptNew++->y = ppt->y;
        !          1568:                        *pwidthNew++ = xEnd - xStart;
        !          1569:                    }
        !          1570: 
        !          1571:                }
        !          1572:            }
        !          1573:        ppt++;
        !          1574:        pwidth++;
        !          1575:        }
        !          1576:     }
        !          1577:     return (pwidthNew - pwidthNewThatWeWerePassed);
        !          1578: }
        !          1579: 
        !          1580: /* find the band in a region with the most rectangles */
        !          1581: int
        !          1582: miFindMaxBand(prgn)
        !          1583: RegionPtr prgn;
        !          1584: {
        !          1585:     register int nbox;
        !          1586:     register BoxPtr pbox;
        !          1587:     register int nThisBand;
        !          1588:     register int nMaxBand = 0;
        !          1589:     short yThisBand;
        !          1590: 
        !          1591:     nbox = prgn->numRects;
        !          1592:     pbox = prgn->rects;
        !          1593: 
        !          1594:     while(nbox > 0)
        !          1595:     {
        !          1596:        yThisBand = pbox->y1;
        !          1597:        nThisBand = 0;
        !          1598:        while((nbox--) && (pbox->y1 == yThisBand))
        !          1599:        {
        !          1600:            pbox++;
        !          1601:            nThisBand++;
        !          1602:        }
        !          1603:        if (nThisBand > nMaxBand)
        !          1604:            nMaxBand = nThisBand;
        !          1605:     }
        !          1606:     return (nMaxBand);
        !          1607: }

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