/*********************************************************************** *           REGION_Coalesce * *      Attempt to merge the rects in the current band with those in the *      previous one. Used only by REGION_RegionOp. * * Results: *      The new index for the previous band. * * Side Effects: *      If coalescing takes place: *          - rectangles in the previous band will have their bottom fields *            altered. *          - some clipping rect will be deleted. * */static CLIPRECT* REGION_Coalesce (             CLIPRGN *region,      /* Region to coalesce */             CLIPRECT *prevStart,  /* start of previous band */             CLIPRECT *curStart    /* start of current band */) {    CLIPRECT *newStart;         /* Start of new band */    CLIPRECT *pPrevRect;        /* Current rect in previous band */    CLIPRECT *pCurRect;         /* Current rect in current band */    CLIPRECT *temp;             /* Temporary clipping rect */    int curNumRects;            /* Number of rectangles in current band */    int prevNumRects;           /* Number of rectangles in previous band */    int bandtop;                /* top coordinate for current band */    if (prevStart == NULL) prevStart = region->head;    if (curStart == NULL) curStart = region->head;    if (prevStart == curStart)        return prevStart;    newStart = pCurRect = curStart;    pPrevRect = prevStart;    temp = prevStart;    prevNumRects = 0;    while (temp != curStart) {        prevNumRects ++;        temp = temp->next;    }    /*     * Figure out how many rectangles are in the current band. Have to do     * this because multiple bands could have been added in REGION_RegionOp     * at the end when one region has been exhausted.     */    pCurRect = curStart;    bandtop = pCurRect->rc.top;    curNumRects = 0;    while (pCurRect && (pCurRect->rc.top == bandtop)) {        curNumRects ++;        pCurRect = pCurRect->next;    }        if (pCurRect) {        /*         * If more than one band was added, we have to find the start         * of the last band added so the next coalescing job can start         * at the right place... (given when multiple bands are added,         * this may be pointless -- see above).         */        temp = region->tail;        while (temp->prev->rc.top == temp->rc.top) {            temp = temp->prev;        }        newStart = temp;    }    if ((curNumRects == prevNumRects) && (curNumRects != 0)) {        pCurRect = curStart;        /*         * The bands may only be coalesced if the bottom of the previous         * matches the top scanline of the current.         */        if (pPrevRect->rc.bottom == pCurRect->rc.top) {            /*             * Make sure the bands have rects in the same places. This             * assumes that rects have been added in such a way that they             * cover the most area possible. I.e. two rects in a band must             * have some horizontal space between them.             */            do {                if ((pPrevRect->rc.left != pCurRect->rc.left) ||                    (pPrevRect->rc.right != pCurRect->rc.right))                {                    /*                     * The bands don't line up so they can't be coalesced.                     */                    return newStart;                }                pPrevRect = pPrevRect->next;                pCurRect = pCurRect->next;            } while (--prevNumRects);            /*             * If only one band was added to the region, we have to backup             * newStart to the start of the previous band.             */            if (pCurRect == NULL) {                newStart = prevStart;            }            /*             * The bands may be merged, so set the bottom of each rect             * in the previous band to that of the corresponding rect in             * the current band.             */            /*             * for implementation of MiniGUI, we should free              * the clipping rects merged.             */            pCurRect = curStart;            pPrevRect = prevStart;            do {                pPrevRect->rc.bottom = pCurRect->rc.bottom;                pPrevRect = pPrevRect->next;                if (pCurRect->next)                    pCurRect->next->prev = pCurRect->prev;                else                    region->tail = pCurRect->prev;                if (pCurRect->prev)                    pCurRect->prev->next = pCurRect->next;                else                    region->head = pCurRect->next;                temp = pCurRect->next;                FreeClipRect (region->heap, pCurRect);                pCurRect = temp;            } while (--curNumRects);            /*             *             * If more than one band was added to the region, copy the             * other bands down. The assumption here is that the other bands             * came from the same region as the current one and no further             * coalescing can be done on them since it's all been done             * already... newStart is already in the right place.             */            /* no need to copy for implementation of MiniGUI -- they are freed.            if (temp == regionEnd) {                newStart = prevStart;            }            else {                do {                    *pPrevRect++ = *pCurRect++;                } while (pCurRect != regionEnd);            }            */                    }    }    return (newStart);}/*********************************************************************** *           REGION_RegionOp * *      Apply an operation to two regions. Called by Union, *      Xor, Subtract, Intersect... * * Results: *      None. * * Side Effects: *      The new region is overwritten. * * Notes: *      The idea behind this function is to view the two regions as sets. *      Together they cover a rectangle of area that this function divides *      into horizontal bands where points are covered only by one region *      or by both. For the first case, the nonOverlapFunc is called with *      each the band and the band's upper and lower rcBound. For the *      second, the overlapFunc is called to process the entire band. It *      is responsible for clipping the rectangles in the band, though *      this function provides the boundaries. *      At the end of each band, the new region is coalesced, if possible, *      to reduce the number of rectangles in the region. * */static voidREGION_RegionOp(            CLIPRGN *newReg, /* Place to store result */            const CLIPRGN *reg1,   /* First region in operation */            const CLIPRGN *reg2,   /* 2nd region in operation */            voidProcp1 overlapFunc,     /* Function to call for over-lapping bands */            voidProcp2 nonOverlap1Func, /* Function to call for non-overlapping bands in region 1 */            voidProcp2 nonOverlap2Func  /* Function to call for non-overlapping bands in region 2 */) {    CLIPRGN my_dst;    CLIPRGN* pdst;    const CLIPRECT *r1;                 /* Pointer into first region */    const CLIPRECT *r2;                 /* Pointer into 2d region */    const CLIPRECT *r1BandEnd;          /* End of current band in r1 */    const CLIPRECT *r2BandEnd;          /* End of current band in r2 */    int ybot;                           /* Bottom of intersection */    int ytop;                           /* Top of intersection */    CLIPRECT* prevBand;                 /* start of previous band in newReg */    CLIPRECT* curBand;                  /* start of current band in newReg */    int top;                            /* Top of non-overlapping band */    int bot;                            /* Bottom of non-overlapping band */        /*     * Initialization:     *  set r1, r2, r1End and r2End appropriately, preserve the important     * parts of the destination region until the end in case it's one of     * the two source regions, then mark the "new" region empty, allocating     * another array of rectangles for it to use.     */    r1 = reg1->head;    r2 = reg2->head;    /*     * newReg may be one of the src regions so we can't empty it. We keep a      * note of its rects pointer (so that we can free them later), preserve its     * rcBound and simply set numRects to zero.      */    /*    oldRects = newReg->rects;    newReg->numRects = 0;     */    /*      * for implementation of MiniGUI, we create an empty region.     */    if (newReg == reg1 || newReg == reg2) {        InitClipRgn (&my_dst, newReg->heap);        pdst = &my_dst;    }    else {        EmptyClipRgn (newReg);        pdst = newReg;    }    /*     * Allocate a reasonable number of rectangles for the new region. The idea     * is to allocate enough so the individual functions don't need to     * reallocate and copy the array, which is time consuming, yet we don't     * have to worry about using too much memory. I hope to be able to     * nuke the Xrealloc() at the end of this function eventually.     */    /* for implementation of MiniGUI, dst always is an empty region.    newReg->size = MAX(reg1->numRects,reg2->numRects) * 2;    if (! (newReg->rects = malloc( sizeof(CLIPRECT) * newReg->size )))    {        newReg->size = 0;        return;    }     */        /*     * Initialize ybot and ytop.     * In the upcoming loop, ybot and ytop serve different functions depending     * on whether the band being handled is an overlapping or non-overlapping     * band.     *  In the case of a non-overlapping band (only one of the regions     * has points in the band), ybot is the bottom of the most recent     * intersection and thus clips the top of the rectangles in that band.     * ytop is the top of the next intersection between the two regions and     * serves to clip the bottom of the rectangles in the current band.     *  For an overlapping band (where the two regions intersect), ytop clips     * the top of the rectangles of both regions and ybot clips the bottoms.     */    if (reg1->rcBound.top < reg2->rcBound.top)        ybot = reg1->rcBound.top;    else        ybot = reg2->rcBound.top;        /*     * prevBand serves to mark the start of the previous band so rectangles     * can be coalesced into larger rectangles. qv. miCoalesce, above.     * In the beginning, there is no previous band, so prevBand == curBand     * (curBand is set later on, of course, but the first band will always     * start at index 0). prevBand and curBand must be indices because of     * the possible expansion, and resultant moving, of the new region's     * array of rectangles.     */    prevBand = pdst->head;        do {        curBand = pdst->tail;        /*         * This algorithm proceeds one source-band (as opposed to a         * destination band, which is determined by where the two regions         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the         * rectangle after the last one in the current band for their         * respective regions.         */        r1BandEnd = r1;        while (r1BandEnd && (r1BandEnd->rc.top == r1->rc.top))            r1BandEnd = r1BandEnd->next;                r2BandEnd = r2;        while (r2BandEnd && (r2BandEnd->rc.top == r2->rc.top))            r2BandEnd = r2BandEnd->next;                /*         * First handle the band that doesn't intersect, if any.         *         * Note that attention is restricted to one band in the         * non-intersecting region at once, so if a region has n         * bands between the current position and the next place it overlaps         * the other, this entire loop will be passed through n times.         */        if (r1->rc.top < r2->rc.top) {            top = MAX (r1->rc.top, ybot);            bot = MIN (r1->rc.bottom, r2->rc.top);            if ((top != bot) && (nonOverlap1Func != NULL))                (* nonOverlap1Func) (pdst, r1, r1BandEnd, top, bot);            ytop = r2->rc.top;        }        else if (r2->rc.top < r1->rc.top) {            top = MAX (r2->rc.top, ybot);            bot = MIN (r2->rc.bottom, r1->rc.top);            if ((top != bot) && (nonOverlap2Func != NULL))                (* nonOverlap2Func) (pdst, r2, r2BandEnd, top, bot);            ytop = r1->rc.top;        }        else {            ytop = r1->rc.top;        }        /*         * If any rectangles got added to the region, try and coalesce them         * with rectangles from the previous band. Note we could just do         * this test in miCoalesce, but some machines incur a not         * inconsiderable cost for function calls, so...         */        if (pdst->tail != curBand) {            prevBand = REGION_Coalesce (pdst, prevBand, curBand);        }        /*         * Now see if we've hit an intersecting band. The two bands only         * intersect if ybot > ytop         */        ybot = MIN (r1->rc.bottom, r2->rc.bottom);        curBand = pdst->tail;        if (ybot > ytop)            (* overlapFunc) (pdst, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);                if (pdst->tail != curBand)            prevBand = REGION_Coalesce (pdst, prevBand, curBand);        /*         * If we've finished with a band (bottom == ybot) we skip forward         * in the region to the next band.         */        if (r1->rc.bottom == ybot)            r1 = r1BandEnd;        if (r2->rc.bottom == ybot)            r2 = r2BandEnd;    } while (r1 && r2);    /*     * Deal with whichever region still has rectangles left.     */    curBand = pdst->tail;    if (r1) {        if (nonOverlap1Func != NULL) {            do {                r1BandEnd = r1;                while ((r1BandEnd) && (r1BandEnd->rc.top == r1->rc.top)) {                    r1BandEnd = r1BandEnd->next;                }                (* nonOverlap1Func) (pdst, r1, r1BandEnd,                                     MAX (r1->rc.top, ybot), r1->rc.bottom);                r1 = r1BandEnd;            } while (r1);        }    }    else if ((r2) && (nonOverlap2Func != NULL))    {        do {            r2BandEnd = r2;            while ((r2BandEnd) && (r2BandEnd->rc.top == r2->rc.top)) {                 r2BandEnd = r2BandEnd->next;            }            (* nonOverlap2Func) (pdst, r2, r2BandEnd,                                MAX (r2->rc.top, ybot), r2->rc.bottom);            r2 = r2BandEnd;        } while (r2);    }    if (pdst->tail != curBand)        (void) REGION_Coalesce (pdst, prevBand, curBand);    /*     * A bit of cleanup. To keep regions from growing without bound,     * we shrink the array of rectangles to match the new number of     * rectangles in the region. This never goes to 0, however...     *     * Only do this stuff if the number of rectangles allocated is more than     * twice the number of rectangles in the region (a simple optimization...).     */#if 0 // MiniGUI implementation does not need to do this    if (newReg->numRects < (newReg->size >> 1))