Back to index

lightning-sunbird  0.9+nobinonly
pixregion.c
Go to the documentation of this file.
00001 /***********************************************************
00002 
00003 Copyright 1987, 1988, 1989, 1998  The Open Group
00004 
00005 Permission to use, copy, modify, distribute, and sell this software and its
00006 documentation for any purpose is hereby granted without fee, provided that
00007 the above copyright notice appear in all copies and that both that
00008 copyright notice and this permission notice appear in supporting
00009 documentation.
00010 
00011 The above copyright notice and this permission notice shall be included in
00012 all copies or substantial portions of the Software.
00013 
00014 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00015 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00016 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
00017 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
00018 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
00019 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00020 
00021 Except as contained in this notice, the name of The Open Group shall not be
00022 used in advertising or otherwise to promote the sale, use or other dealings
00023 in this Software without prior written authorization from The Open Group.
00024  
00025 
00026 Copyright 1987, 1988, 1989 by 
00027 Digital Equipment Corporation, Maynard, Massachusetts. 
00028 
00029                         All Rights Reserved
00030 
00031 Permission to use, copy, modify, and distribute this software and its 
00032 documentation for any purpose and without fee is hereby granted, 
00033 provided that the above copyright notice appear in all copies and that
00034 both that copyright notice and this permission notice appear in 
00035 supporting documentation, and that the name of Digital not be
00036 used in advertising or publicity pertaining to distribution of the
00037 software without specific, written prior permission.  
00038 
00039 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
00040 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
00041 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
00042 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
00043 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
00044 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
00045 SOFTWARE.
00046 
00047 ******************************************************************/
00048 
00049 #include <stdlib.h>
00050 #include <limits.h>
00051 #include <string.h>
00052 
00053 #undef DEBUG
00054 
00055 #include "pixregionint.h"
00056 #include "slim_internal.h"
00057 
00058 #if defined (__GNUC__) && !defined (NO_INLINES)
00059 #define INLINE       __inline
00060 #else
00061 #define INLINE
00062 #endif
00063 
00064 #undef assert
00065 #ifdef DEBUG
00066 #define assert(expr) {if (!(expr)) \
00067               FatalError("Assertion failed file %s, line %d: expr\n", \
00068                      __FILE__, __LINE__); }
00069 #else
00070 #define assert(expr)
00071 #endif
00072 
00073 #define good(reg) assert(pixman_region16_valid(reg))
00074 
00075 #define MIN(a,b) ((a) < (b) ? (a) : (b))
00076 #define MAX(a,b) ((a) > (b) ? (a) : (b))
00077 
00078 static pixman_box16_t pixman_region_emptyBox = {0, 0, 0, 0};
00079 static pixman_region16_data_t pixman_region_emptyData = {0, 0};
00080 
00081 static pixman_region16_data_t  pixman_brokendata = {0, 0};
00082 static pixman_region16_t   pixman_brokenregion = { { 0, 0, 0, 0 }, &pixman_brokendata };
00083 
00084 static pixman_region_status_t
00085 pixman_break (pixman_region16_t *pReg);
00086 
00087 static void
00088 pixman_init (pixman_region16_t *region, pixman_box16_t *rect);
00089 
00090 static void
00091 pixman_uninit (pixman_region16_t *region);
00092 
00093 slim_hidden_proto(pixman_region_create_simple)
00094 slim_hidden_proto(pixman_region_copy)
00095 slim_hidden_proto(pixman_region_union)
00096 
00097 /*
00098  * The functions in this file implement the Region abstraction used extensively
00099  * throughout the X11 sample server. A Region is simply a set of disjoint
00100  * (non-overlapping) rectangles, plus an "extent" rectangle which is the
00101  * smallest single rectangle that contains all the non-overlapping rectangles.
00102  *
00103  * A Region is implemented as a "y-x-banded" array of rectangles.  This array
00104  * imposes two degrees of order.  First, all rectangles are sorted by top side
00105  * y coordinate first (y1), and then by left side x coordinate (x1).
00106  *
00107  * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a
00108  * band has the same top y coordinate (y1), and each has the same bottom y
00109  * coordinate (y2).  Thus all rectangles in a band differ only in their left
00110  * and right side (x1 and x2).  Bands are implicit in the array of rectangles:
00111  * there is no separate list of band start pointers.
00112  *
00113  * The y-x band representation does not minimize rectangles.  In particular,
00114  * if a rectangle vertically crosses a band (the rectangle has scanlines in 
00115  * the y1 to y2 area spanned by the band), then the rectangle may be broken
00116  * down into two or more smaller rectangles stacked one atop the other. 
00117  *
00118  *  -----------                               -----------
00119  *  |         |                               |         |                 band 0
00120  *  |         |  --------              -----------  --------
00121  *  |         |  |      |  in y-x banded    |         |  |      |   band 1
00122  *  |         |  |      |  form is     |         |  |      |
00123  *  -----------  |      |              -----------  --------
00124  *               |      |                         |      |   band 2
00125  *               --------                         --------
00126  *
00127  * An added constraint on the rectangles is that they must cover as much
00128  * horizontal area as possible: no two rectangles within a band are allowed
00129  * to touch.
00130  *
00131  * Whenever possible, bands will be merged together to cover a greater vertical
00132  * distance (and thus reduce the number of rectangles). Two bands can be merged
00133  * only if the bottom of one touches the top of the other and they have
00134  * rectangles in the same places (of the same width, of course).
00135  *
00136  * Adam de Boor wrote most of the original region code.  Joel McCormack
00137  * substantially modified or rewrote most of the core arithmetic routines, and
00138  * added pixman_region_validate in order to support several speed improvements to
00139  * pixman_region_validateTree.  Bob Scheifler changed the representation to be more
00140  * compact when empty or a single rectangle, and did a bunch of gratuitous
00141  * reformatting. Carl Worth did further gratuitous reformatting while re-merging
00142  * the server and client region code into libpixregion. 
00143  */
00144 
00145 /*  true iff two Boxes overlap */
00146 #define EXTENTCHECK(r1,r2) \
00147       (!( ((r1)->x2 <= (r2)->x1)  || \
00148           ((r1)->x1 >= (r2)->x2)  || \
00149           ((r1)->y2 <= (r2)->y1)  || \
00150           ((r1)->y1 >= (r2)->y2) ) )
00151 
00152 /* true iff (x,y) is in Box */
00153 #define INBOX(r,x,y) \
00154       ( ((r)->x2 >  x) && \
00155         ((r)->x1 <= x) && \
00156         ((r)->y2 >  y) && \
00157         ((r)->y1 <= y) )
00158 
00159 /* true iff Box r1 contains Box r2 */
00160 #define SUBSUMES(r1,r2) \
00161       ( ((r1)->x1 <= (r2)->x1) && \
00162         ((r1)->x2 >= (r2)->x2) && \
00163         ((r1)->y1 <= (r2)->y1) && \
00164         ((r1)->y2 >= (r2)->y2) )
00165 
00166 #define allocData(n) malloc(PIXREGION_SZOF(n))
00167 #define freeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)
00168 
00169 #define RECTALLOC_BAIL(pReg,n,bail) \
00170 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
00171     if (!pixman_rect_alloc(pReg, n)) { goto bail; }
00172 
00173 #define RECTALLOC(pReg,n) \
00174 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
00175     if (!pixman_rect_alloc(pReg, n)) { return PIXMAN_REGION_STATUS_FAILURE; }
00176 
00177 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2)       \
00178 {                                         \
00179     pNextRect->x1 = nx1;                  \
00180     pNextRect->y1 = ny1;                  \
00181     pNextRect->x2 = nx2;                  \
00182     pNextRect->y2 = ny2;                  \
00183     pNextRect++;                          \
00184 }
00185 
00186 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2)                \
00187 {                                                              \
00188     if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
00189     {                                                          \
00190        if (!pixman_rect_alloc(pReg, 1))                               \
00191            return PIXMAN_REGION_STATUS_FAILURE;                                     \
00192        pNextRect = PIXREGION_TOP(pReg);                               \
00193     }                                                          \
00194     ADDRECT(pNextRect,nx1,ny1,nx2,ny2);                               \
00195     pReg->data->numRects++;                                    \
00196     assert(pReg->data->numRects<=pReg->data->size);                   \
00197 }
00198 
00199 
00200 #define DOWNSIZE(reg,numRects)                                         \
00201 if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
00202 {                                                               \
00203     pixman_region16_data_t * NewData;                                                \
00204     NewData = (pixman_region16_data_t *)realloc((reg)->data, PIXREGION_SZOF(numRects));     \
00205     if (NewData)                                                \
00206     {                                                           \
00207        NewData->size = (numRects);                              \
00208        (reg)->data = NewData;                                          \
00209     }                                                           \
00210 }
00211 
00212 
00213 #ifdef DEBUG
00214 int
00215 pixman_region16_print(rgn)
00216     pixman_region16_t * rgn;
00217 {
00218     int num, size;
00219     int i;
00220     pixman_box16_t * rects;
00221 
00222     num = PIXREGION_NUM_RECTS(rgn);
00223     size = PIXREGION_SIZE(rgn);
00224     rects = PIXREGION_RECTS(rgn);
00225     ErrorF("num: %d size: %d\n", num, size);
00226     ErrorF("extents: %d %d %d %d\n",
00227           rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
00228     for (i = 0; i < num; i++)
00229       ErrorF("%d %d %d %d \n",
00230             rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
00231     ErrorF("\n");
00232     return(num);
00233 }
00234 
00235 
00236 pixman_region_status_t
00237 pixman_region16_tsEqual(reg1, reg2)
00238     pixman_region16_t * reg1;
00239     pixman_region16_t * reg2;
00240 {
00241     int i;
00242     pixman_box16_t * rects1, rects2;
00243 
00244     if (reg1->extents.x1 != reg2->extents.x1) return PIXMAN_REGION_STATUS_FAILURE;
00245     if (reg1->extents.x2 != reg2->extents.x2) return PIXMAN_REGION_STATUS_FAILURE;
00246     if (reg1->extents.y1 != reg2->extents.y1) return PIXMAN_REGION_STATUS_FAILURE;
00247     if (reg1->extents.y2 != reg2->extents.y2) return PIXMAN_REGION_STATUS_FAILURE;
00248     if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return PIXMAN_REGION_STATUS_FAILURE;
00249     
00250     rects1 = PIXREGION_RECTS(reg1);
00251     rects2 = PIXREGION_RECTS(reg2);
00252     for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
00253        if (rects1[i].x1 != rects2[i].x1) return PIXMAN_REGION_STATUS_FAILURE;
00254        if (rects1[i].x2 != rects2[i].x2) return PIXMAN_REGION_STATUS_FAILURE;
00255        if (rects1[i].y1 != rects2[i].y1) return PIXMAN_REGION_STATUS_FAILURE;
00256        if (rects1[i].y2 != rects2[i].y2) return PIXMAN_REGION_STATUS_FAILURE;
00257     }
00258     return PIXMAN_REGION_STATUS_SUCCESS;
00259 }
00260 
00261 pixman_region_status_t
00262 pixman_region16_valid(reg)
00263     pixman_region16_t * reg;
00264 {
00265     int i, numRects;
00266 
00267     if ((reg->extents.x1 > reg->extents.x2) ||
00268        (reg->extents.y1 > reg->extents.y2))
00269        return PIXMAN_REGION_STATUS_FAILURE;
00270     numRects = PIXREGION_NUM_RECTS(reg);
00271     if (!numRects)
00272        return ((reg->extents.x1 == reg->extents.x2) &&
00273               (reg->extents.y1 == reg->extents.y2) &&
00274               (reg->data->size || (reg->data == &pixman_region_emptyData)));
00275     else if (numRects == 1)
00276        return (!reg->data);
00277     else
00278     {
00279        pixman_box16_t * pboxP, pboxN;
00280        pixman_box16_t box;
00281 
00282        pboxP = PIXREGION_RECTS(reg);
00283        box = *pboxP;
00284        box.y2 = pboxP[numRects-1].y2;
00285        pboxN = pboxP + 1;
00286        for (i = numRects; --i > 0; pboxP++, pboxN++)
00287        {
00288            if ((pboxN->x1 >= pboxN->x2) ||
00289               (pboxN->y1 >= pboxN->y2))
00290               return PIXMAN_REGION_STATUS_FAILURE;
00291            if (pboxN->x1 < box.x1)
00292                box.x1 = pboxN->x1;
00293            if (pboxN->x2 > box.x2)
00294               box.x2 = pboxN->x2;
00295            if ((pboxN->y1 < pboxP->y1) ||
00296               ((pboxN->y1 == pboxP->y1) &&
00297                ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
00298               return PIXMAN_REGION_STATUS_FAILURE;
00299        }
00300        return ((box.x1 == reg->extents.x1) &&
00301               (box.x2 == reg->extents.x2) &&
00302               (box.y1 == reg->extents.y1) &&
00303               (box.y2 == reg->extents.y2));
00304     }
00305 }
00306 
00307 #endif /* DEBUG */
00308 
00309 
00310 /*     Create a new empty region   */
00311 pixman_region16_t *
00312 pixman_region_create (void)
00313 {
00314     return pixman_region_create_simple (NULL);
00315 }
00316 
00317 /*****************************************************************
00318  *   pixman_region_create_simple (extents)
00319  *     This routine creates a pixman_region16_t for a simple
00320  *     rectangular region.
00321  *****************************************************************/
00322 pixman_region16_t *
00323 pixman_region_create_simple (pixman_box16_t *extents)
00324 {
00325     pixman_region16_t *region;
00326    
00327     region = malloc (sizeof (pixman_region16_t));
00328     if (region == NULL)
00329        return &pixman_brokenregion;
00330 
00331     pixman_init (region, extents);
00332 
00333     return region;
00334 }
00335 slim_hidden_def(pixman_region_create_simple);
00336 
00337 /*****************************************************************
00338  *   RegionInit(pReg, rect, size)
00339  *     Outer region rect is statically allocated.
00340  *****************************************************************/
00341 
00342 static void
00343 pixman_init(pixman_region16_t *region, pixman_box16_t *extents)
00344 {
00345     if (extents)
00346     {
00347        region->extents = *extents;
00348        region->data = NULL;
00349     }
00350     else
00351     {
00352        region->extents = pixman_region_emptyBox;
00353        region->data = &pixman_region_emptyData;
00354     }
00355 }
00356 
00357 static void
00358 pixman_uninit (pixman_region16_t *region)
00359 {
00360     good (region);
00361     freeData (region);
00362 }
00363 
00364 void
00365 pixman_region_destroy (pixman_region16_t *region)
00366 {
00367     pixman_uninit (region);
00368 
00369     if (region != &pixman_brokenregion)
00370        free (region);
00371 }
00372 
00373 int
00374 pixman_region_num_rects (pixman_region16_t *region)
00375 {
00376     return PIXREGION_NUM_RECTS (region);
00377 }
00378 
00379 pixman_box16_t *
00380 pixman_region_rects (pixman_region16_t *region)
00381 {
00382     return PIXREGION_RECTS (region);
00383 }
00384 
00385 static pixman_region_status_t
00386 pixman_break (pixman_region16_t *region)
00387 {
00388     freeData (region);
00389     region->extents = pixman_region_emptyBox;
00390     region->data = &pixman_brokendata;
00391     return PIXMAN_REGION_STATUS_FAILURE;
00392 }
00393 
00394 static pixman_region_status_t
00395 pixman_rect_alloc(pixman_region16_t * region, int n)
00396 {
00397     pixman_region16_data_t *data;
00398     
00399     if (!region->data)
00400     {
00401        n++;
00402        region->data = allocData(n);
00403        if (!region->data)
00404            return pixman_break (region);
00405        region->data->numRects = 1;
00406        *PIXREGION_BOXPTR(region) = region->extents;
00407     }
00408     else if (!region->data->size)
00409     {
00410        region->data = allocData(n);
00411        if (!region->data)
00412            return pixman_break (region);
00413        region->data->numRects = 0;
00414     }
00415     else
00416     {
00417        if (n == 1)
00418        {
00419            n = region->data->numRects;
00420            if (n > 500) /* XXX pick numbers out of a hat */
00421               n = 250;
00422        }
00423        n += region->data->numRects;
00424        data = (pixman_region16_data_t *)realloc(region->data, PIXREGION_SZOF(n));
00425        if (!data)
00426            return pixman_break (region);
00427        region->data = data;
00428     }
00429     region->data->size = n;
00430     return PIXMAN_REGION_STATUS_SUCCESS;
00431 }
00432 
00433 pixman_region_status_t
00434 pixman_region_copy(pixman_region16_t *dst, pixman_region16_t *src)
00435 {
00436     good(dst);
00437     good(src);
00438     if (dst == src)
00439        return PIXMAN_REGION_STATUS_SUCCESS;
00440     dst->extents = src->extents;
00441     if (!src->data || !src->data->size)
00442     {
00443        freeData(dst);
00444        dst->data = src->data;
00445        return PIXMAN_REGION_STATUS_SUCCESS;
00446     }
00447     if (!dst->data || (dst->data->size < src->data->numRects))
00448     {
00449        freeData(dst);
00450        dst->data = allocData(src->data->numRects);
00451        if (!dst->data)
00452            return pixman_break (dst);
00453        dst->data->size = src->data->numRects;
00454     }
00455     dst->data->numRects = src->data->numRects;
00456     memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src), 
00457          dst->data->numRects * sizeof(pixman_box16_t));
00458     return PIXMAN_REGION_STATUS_SUCCESS;
00459 }
00460 slim_hidden_def(pixman_region_copy);
00461 
00462 
00463 /*======================================================================
00464  *         Generic Region Operator
00465  *====================================================================*/
00466 
00467 /*-
00468  *-----------------------------------------------------------------------
00469  * pixman_coalesce --
00470  *     Attempt to merge the boxes in the current band with those in the
00471  *     previous one.  We are guaranteed that the current band extends to
00472  *      the end of the rects array.  Used only by pixman_op.
00473  *
00474  * Results:
00475  *     The new index for the previous band.
00476  *
00477  * Side Effects:
00478  *     If coalescing takes place:
00479  *         - rectangles in the previous band will have their y2 fields
00480  *           altered.
00481  *         - region->data->numRects will be decreased.
00482  *
00483  *-----------------------------------------------------------------------
00484  */
00485 INLINE static int
00486 pixman_coalesce (
00487     pixman_region16_t *     region,              /* Region to coalesce                   */
00488     int                     prevStart,    /* Index of start of previous band   */
00489     int                     curStart)     /* Index of start of current band    */
00490 {
00491     pixman_box16_t * pPrevBox;     /* Current box in previous band         */
00492     pixman_box16_t * pCurBox;      /* Current box in current band       */
00493     int       numRects;     /* Number rectangles in both bands   */
00494     int       y2;           /* Bottom of current band        */
00495     /*
00496      * Figure out how many rectangles are in the band.
00497      */
00498     numRects = curStart - prevStart;
00499     assert(numRects == region->data->numRects - curStart);
00500 
00501     if (!numRects) return curStart;
00502 
00503     /*
00504      * The bands may only be coalesced if the bottom of the previous
00505      * matches the top scanline of the current.
00506      */
00507     pPrevBox = PIXREGION_BOX(region, prevStart);
00508     pCurBox = PIXREGION_BOX(region, curStart);
00509     if (pPrevBox->y2 != pCurBox->y1) return curStart;
00510 
00511     /*
00512      * Make sure the bands have boxes in the same places. This
00513      * assumes that boxes have been added in such a way that they
00514      * cover the most area possible. I.e. two boxes in a band must
00515      * have some horizontal space between them.
00516      */
00517     y2 = pCurBox->y2;
00518 
00519     do {
00520        if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
00521            return (curStart);
00522        }
00523        pPrevBox++;
00524        pCurBox++;
00525        numRects--;
00526     } while (numRects);
00527 
00528     /*
00529      * The bands may be merged, so set the bottom y of each box
00530      * in the previous band to the bottom y of the current band.
00531      */
00532     numRects = curStart - prevStart;
00533     region->data->numRects -= numRects;
00534     do {
00535        pPrevBox--;
00536        pPrevBox->y2 = y2;
00537        numRects--;
00538     } while (numRects);
00539     return prevStart;
00540 }
00541 
00542 
00543 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
00544 
00545 #define Coalesce(newReg, prevBand, curBand)                           \
00546     if (curBand - prevBand == newReg->data->numRects - curBand) {     \
00547        prevBand = pixman_coalesce(newReg, prevBand, curBand);         \
00548     } else {                                                   \
00549        prevBand = curBand;                                     \
00550     }
00551 
00552 /*-
00553  *-----------------------------------------------------------------------
00554  * pixman_region_appendNonO --
00555  *     Handle a non-overlapping band for the union and subtract operations.
00556  *      Just adds the (top/bottom-clipped) rectangles into the region.
00557  *      Doesn't have to check for subsumption or anything.
00558  *
00559  * Results:
00560  *     None.
00561  *
00562  * Side Effects:
00563  *     region->data->numRects is incremented and the rectangles overwritten
00564  *     with the rectangles we're passed.
00565  *
00566  *-----------------------------------------------------------------------
00567  */
00568 
00569 INLINE static pixman_region_status_t
00570 pixman_region_appendNonO (
00571     pixman_region16_t *     region,
00572     pixman_box16_t * r,
00573     pixman_box16_t *               rEnd,
00574     int       y1,
00575     int       y2)
00576 {
00577     pixman_box16_t * pNextRect;
00578     int       newRects;
00579 
00580     newRects = rEnd - r;
00581 
00582     assert(y1 < y2);
00583     assert(newRects != 0);
00584 
00585     /* Make sure we have enough space for all rectangles to be added */
00586     RECTALLOC(region, newRects);
00587     pNextRect = PIXREGION_TOP(region);
00588     region->data->numRects += newRects;
00589     do {
00590        assert(r->x1 < r->x2);
00591        ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
00592        r++;
00593     } while (r != rEnd);
00594 
00595     return PIXMAN_REGION_STATUS_SUCCESS;
00596 }
00597 
00598 #define FindBand(r, rBandEnd, rEnd, ry1)             \
00599 {                                                    \
00600     ry1 = r->y1;                                     \
00601     rBandEnd = r+1;                                  \
00602     while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) {   \
00603        rBandEnd++;                                   \
00604     }                                                \
00605 }
00606 
00607 #define       AppendRegions(newReg, r, rEnd)                                 \
00608 {                                                              \
00609     int newRects;                                              \
00610     if ((newRects = rEnd - r)) {                               \
00611        RECTALLOC(newReg, newRects);                                   \
00612        memmove((char *)PIXREGION_TOP(newReg),(char *)r,                      \
00613               newRects * sizeof(pixman_box16_t));                            \
00614        newReg->data->numRects += newRects;                            \
00615     }                                                          \
00616 }
00617 
00618 /*-
00619  *-----------------------------------------------------------------------
00620  * pixman_op --
00621  *     Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
00622  *     pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one
00623  *      rectangle, and cannot be the same object.
00624  *
00625  * Results:
00626  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
00627  *
00628  * Side Effects:
00629  *     The new region is overwritten.
00630  *     pOverlap set to PIXMAN_REGION_STATUS_SUCCESS if overlapFunc ever returns PIXMAN_REGION_STATUS_SUCCESS.
00631  *
00632  * Notes:
00633  *     The idea behind this function is to view the two regions as sets.
00634  *     Together they cover a rectangle of area that this function divides
00635  *     into horizontal bands where points are covered only by one region
00636  *     or by both. For the first case, the nonOverlapFunc is called with
00637  *     each the band and the band's upper and lower extents. For the
00638  *     second, the overlapFunc is called to process the entire band. It
00639  *     is responsible for clipping the rectangles in the band, though
00640  *     this function provides the boundaries.
00641  *     At the end of each band, the new region is coalesced, if possible,
00642  *     to reduce the number of rectangles in the region.
00643  *
00644  *-----------------------------------------------------------------------
00645  */
00646 
00647 typedef pixman_region_status_t (*OverlapProcPtr)(
00648     pixman_region16_t        *region,
00649     pixman_box16_t *r1,
00650     pixman_box16_t *r1End,
00651     pixman_box16_t *r2,
00652     pixman_box16_t *r2End,
00653     short      y1,
00654     short      y2,
00655     int               *pOverlap);
00656 
00657 static pixman_region_status_t
00658 pixman_op(
00659     pixman_region16_t *       newReg,                /* Place to store result            */
00660     pixman_region16_t *       reg1,                  /* First region in operation     */
00661     pixman_region16_t *       reg2,                  /* 2d region in operation        */
00662     OverlapProcPtr  overlapFunc,            /* Function to call for over-
00663                                         * lapping bands             */
00664     int           appendNon1,                 /* Append non-overlapping bands  */
00665                                        /* in region 1 ? */
00666     int           appendNon2,                 /* Append non-overlapping bands  */
00667                                        /* in region 2 ? */
00668     int           *pOverlap)
00669 {
00670     pixman_box16_t * r1;                      /* Pointer into first region     */
00671     pixman_box16_t * r2;                      /* Pointer into 2d region           */
00672     pixman_box16_t *     r1End;               /* End of 1st region         */
00673     pixman_box16_t *     r2End;               /* End of 2d region                 */
00674     short         ybot;                /* Bottom of intersection           */
00675     short         ytop;                /* Top of intersection       */
00676     pixman_region16_data_t *           oldData;             /* Old data for newReg       */
00677     int                  prevBand;            /* Index of start of
00678                                         * previous band in newReg       */
00679     int                  curBand;             /* Index of start of current
00680                                         * band in newReg                   */
00681     pixman_box16_t * r1BandEnd;               /* End of current band in r1     */
00682     pixman_box16_t * r2BandEnd;               /* End of current band in r2     */
00683     short         top;                 /* Top of non-overlapping band   */
00684     short         bot;                 /* Bottom of non-overlapping band*/
00685     int    r1y1;                /* Temps for r1->y1 and r2->y1   */
00686     int    r2y1;
00687     int                  newSize;
00688     int                  numRects;
00689 
00690     /*
00691      * Break any region computed from a broken region
00692      */
00693     if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2))
00694        return pixman_break (newReg);
00695     
00696     /*
00697      * Initialization:
00698      * set r1, r2, r1End and r2End appropriately, save the rectangles
00699      * of the destination region until the end in case it's one of
00700      * the two source regions, then mark the "new" region empty, allocating
00701      * another array of rectangles for it to use.
00702      */
00703 
00704     r1 = PIXREGION_RECTS(reg1);
00705     newSize = PIXREGION_NUM_RECTS(reg1);
00706     r1End = r1 + newSize;
00707     numRects = PIXREGION_NUM_RECTS(reg2);
00708     r2 = PIXREGION_RECTS(reg2);
00709     r2End = r2 + numRects;
00710     assert(r1 != r1End);
00711     assert(r2 != r2End);
00712 
00713     oldData = (pixman_region16_data_t *)NULL;
00714     if (((newReg == reg1) && (newSize > 1)) ||
00715        ((newReg == reg2) && (numRects > 1)))
00716     {
00717        oldData = newReg->data;
00718        newReg->data = &pixman_region_emptyData;
00719     }
00720     /* guess at new size */
00721     if (numRects > newSize)
00722        newSize = numRects;
00723     newSize <<= 1;
00724     if (!newReg->data)
00725        newReg->data = &pixman_region_emptyData;
00726     else if (newReg->data->size)
00727        newReg->data->numRects = 0;
00728     if (newSize > newReg->data->size)
00729        if (!pixman_rect_alloc(newReg, newSize))
00730            return PIXMAN_REGION_STATUS_FAILURE;
00731 
00732     /*
00733      * Initialize ybot.
00734      * In the upcoming loop, ybot and ytop serve different functions depending
00735      * on whether the band being handled is an overlapping or non-overlapping
00736      * band.
00737      *        In the case of a non-overlapping band (only one of the regions
00738      * has points in the band), ybot is the bottom of the most recent
00739      * intersection and thus clips the top of the rectangles in that band.
00740      * ytop is the top of the next intersection between the two regions and
00741      * serves to clip the bottom of the rectangles in the current band.
00742      * For an overlapping band (where the two regions intersect), ytop clips
00743      * the top of the rectangles of both regions and ybot clips the bottoms.
00744      */
00745 
00746     ybot = MIN(r1->y1, r2->y1);
00747     
00748     /*
00749      * prevBand serves to mark the start of the previous band so rectangles
00750      * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
00751      * In the beginning, there is no previous band, so prevBand == curBand
00752      * (curBand is set later on, of course, but the first band will always
00753      * start at index 0). prevBand and curBand must be indices because of
00754      * the possible expansion, and resultant moving, of the new region's
00755      * array of rectangles.
00756      */
00757     prevBand = 0;
00758     
00759     do {
00760        /*
00761         * This algorithm proceeds one source-band (as opposed to a
00762         * destination band, which is determined by where the two regions
00763         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
00764         * rectangle after the last one in the current band for their
00765         * respective regions.
00766         */
00767        assert(r1 != r1End);
00768        assert(r2 != r2End);
00769     
00770        FindBand(r1, r1BandEnd, r1End, r1y1);
00771        FindBand(r2, r2BandEnd, r2End, r2y1);
00772 
00773        /*
00774         * First handle the band that doesn't intersect, if any.
00775         *
00776         * Note that attention is restricted to one band in the
00777         * non-intersecting region at once, so if a region has n
00778         * bands between the current position and the next place it overlaps
00779         * the other, this entire loop will be passed through n times.
00780         */
00781        if (r1y1 < r2y1) {
00782            if (appendNon1) {
00783               top = MAX(r1y1, ybot);
00784               bot = MIN(r1->y2, r2y1);
00785               if (top != bot)      {
00786                   curBand = newReg->data->numRects;
00787                   pixman_region_appendNonO(newReg, r1, r1BandEnd, top, bot);
00788                   Coalesce(newReg, prevBand, curBand);
00789               }
00790            }
00791            ytop = r2y1;
00792        } else if (r2y1 < r1y1) {
00793            if (appendNon2) {
00794               top = MAX(r2y1, ybot);
00795               bot = MIN(r2->y2, r1y1);
00796               if (top != bot) {
00797                   curBand = newReg->data->numRects;
00798                   pixman_region_appendNonO(newReg, r2, r2BandEnd, top, bot);
00799                   Coalesce(newReg, prevBand, curBand);
00800               }
00801            }
00802            ytop = r1y1;
00803        } else {
00804            ytop = r1y1;
00805        }
00806 
00807        /*
00808         * Now see if we've hit an intersecting band. The two bands only
00809         * intersect if ybot > ytop
00810         */
00811        ybot = MIN(r1->y2, r2->y2);
00812        if (ybot > ytop) {
00813            curBand = newReg->data->numRects;
00814            (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
00815                          pOverlap);
00816            Coalesce(newReg, prevBand, curBand);
00817        }
00818 
00819        /*
00820         * If we've finished with a band (y2 == ybot) we skip forward
00821         * in the region to the next band.
00822         */
00823        if (r1->y2 == ybot) r1 = r1BandEnd;
00824        if (r2->y2 == ybot) r2 = r2BandEnd;
00825 
00826     } while (r1 != r1End && r2 != r2End);
00827 
00828     /*
00829      * Deal with whichever region (if any) still has rectangles left.
00830      *
00831      * We only need to worry about banding and coalescing for the very first
00832      * band left.  After that, we can just group all remaining boxes,
00833      * regardless of how many bands, into one final append to the list.
00834      */
00835 
00836     if ((r1 != r1End) && appendNon1) {
00837        /* Do first nonOverlap1Func call, which may be able to coalesce */
00838        FindBand(r1, r1BandEnd, r1End, r1y1);
00839        curBand = newReg->data->numRects;
00840        pixman_region_appendNonO(newReg, r1, r1BandEnd, MAX(r1y1, ybot), r1->y2);
00841        Coalesce(newReg, prevBand, curBand);
00842        /* Just append the rest of the boxes  */
00843        AppendRegions(newReg, r1BandEnd, r1End);
00844 
00845     } else if ((r2 != r2End) && appendNon2) {
00846        /* Do first nonOverlap2Func call, which may be able to coalesce */
00847        FindBand(r2, r2BandEnd, r2End, r2y1);
00848        curBand = newReg->data->numRects;
00849        pixman_region_appendNonO(newReg, r2, r2BandEnd, MAX(r2y1, ybot), r2->y2);
00850        Coalesce(newReg, prevBand, curBand);
00851        /* Append rest of boxes */
00852        AppendRegions(newReg, r2BandEnd, r2End);
00853     }
00854 
00855     if (oldData)
00856        free(oldData);
00857 
00858     if (!(numRects = newReg->data->numRects))
00859     {
00860        freeData(newReg);
00861        newReg->data = &pixman_region_emptyData;
00862     }
00863     else if (numRects == 1)
00864     {
00865        newReg->extents = *PIXREGION_BOXPTR(newReg);
00866        freeData(newReg);
00867        newReg->data = (pixman_region16_data_t *)NULL;
00868     }
00869     else
00870     {
00871        DOWNSIZE(newReg, numRects);
00872     }
00873 
00874     return PIXMAN_REGION_STATUS_SUCCESS;
00875 }
00876 
00877 /*-
00878  *-----------------------------------------------------------------------
00879  * pixman_set_extents --
00880  *     Reset the extents of a region to what they should be. Called by
00881  *     pixman_region_subtract and pixman_region_intersect as they can't figure it out along the
00882  *     way or do so easily, as pixman_region_union can.
00883  *
00884  * Results:
00885  *     None.
00886  *
00887  * Side Effects:
00888  *     The region's 'extents' structure is overwritten.
00889  *
00890  *-----------------------------------------------------------------------
00891  */
00892 static void
00893 pixman_set_extents (pixman_region16_t *region)
00894 {
00895     pixman_box16_t *box, *boxEnd;
00896 
00897     if (!region->data)
00898        return;
00899     if (!region->data->size)
00900     {
00901        region->extents.x2 = region->extents.x1;
00902        region->extents.y2 = region->extents.y1;
00903        return;
00904     }
00905 
00906     box = PIXREGION_BOXPTR(region);
00907     boxEnd = PIXREGION_END(region);
00908 
00909     /*
00910      * Since box is the first rectangle in the region, it must have the
00911      * smallest y1 and since boxEnd is the last rectangle in the region,
00912      * it must have the largest y2, because of banding. Initialize x1 and
00913      * x2 from  box and boxEnd, resp., as good things to initialize them
00914      * to...
00915      */
00916     region->extents.x1 = box->x1;
00917     region->extents.y1 = box->y1;
00918     region->extents.x2 = boxEnd->x2;
00919     region->extents.y2 = boxEnd->y2;
00920 
00921     assert(region->extents.y1 < region->extents.y2);
00922     while (box <= boxEnd) {
00923        if (box->x1 < region->extents.x1)
00924            region->extents.x1 = box->x1;
00925        if (box->x2 > region->extents.x2)
00926            region->extents.x2 = box->x2;
00927        box++;
00928     };
00929 
00930     assert(region->extents.x1 < region->extents.x2);
00931 }
00932 
00933 /*======================================================================
00934  *         Region Intersection
00935  *====================================================================*/
00936 /*-
00937  *-----------------------------------------------------------------------
00938  * pixman_region_intersectO --
00939  *     Handle an overlapping band for pixman_region_intersect.
00940  *
00941  * Results:
00942  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
00943  *
00944  * Side Effects:
00945  *     Rectangles may be added to the region.
00946  *
00947  *-----------------------------------------------------------------------
00948  */
00949 /*ARGSUSED*/
00950 static pixman_region_status_t
00951 pixman_region_intersectO (
00952     pixman_region16_t *     region,
00953     pixman_box16_t * r1,
00954     pixman_box16_t *        r1End,
00955     pixman_box16_t * r2,
00956     pixman_box16_t *        r2End,
00957     short            y1,
00958     short            y2,
00959     int              *pOverlap)
00960 {
00961     int       x1;
00962     int       x2;
00963     pixman_box16_t * pNextRect;
00964 
00965     pNextRect = PIXREGION_TOP(region);
00966 
00967     assert(y1 < y2);
00968     assert(r1 != r1End && r2 != r2End);
00969 
00970     do {
00971        x1 = MAX(r1->x1, r2->x1);
00972        x2 = MIN(r1->x2, r2->x2);
00973 
00974        /*
00975         * If there's any overlap between the two rectangles, add that
00976         * overlap to the new region.
00977         */
00978        if (x1 < x2)
00979            NEWRECT(region, pNextRect, x1, y1, x2, y2);
00980 
00981        /*
00982         * Advance the pointer(s) with the leftmost right side, since the next
00983         * rectangle on that list may still overlap the other region's
00984         * current rectangle.
00985         */
00986        if (r1->x2 == x2) {
00987            r1++;
00988        }
00989        if (r2->x2 == x2) {
00990            r2++;
00991        }
00992     } while ((r1 != r1End) && (r2 != r2End));
00993 
00994     return PIXMAN_REGION_STATUS_SUCCESS;
00995 }
00996 
00997 
00998 pixman_region_status_t
00999 pixman_region_intersect(newReg, reg1, reg2)
01000     pixman_region16_t *     newReg;     /* destination Region */
01001     pixman_region16_t *     reg1;
01002     pixman_region16_t *     reg2;       /* source regions     */
01003 {
01004     good(reg1);
01005     good(reg2);
01006     good(newReg);
01007    /* check for trivial reject */
01008     if (PIXREGION_NIL(reg1)  || PIXREGION_NIL(reg2) ||
01009        !EXTENTCHECK(&reg1->extents, &reg2->extents))
01010     {
01011        /* Covers about 20% of all cases */
01012        freeData(newReg);
01013        newReg->extents.x2 = newReg->extents.x1;
01014        newReg->extents.y2 = newReg->extents.y1;
01015        if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
01016        {
01017            newReg->data = &pixman_brokendata;
01018            return PIXMAN_REGION_STATUS_FAILURE;
01019        }
01020        else
01021            newReg->data = &pixman_region_emptyData;
01022     }
01023     else if (!reg1->data && !reg2->data)
01024     {
01025        /* Covers about 80% of cases that aren't trivially rejected */
01026        newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
01027        newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
01028        newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
01029        newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
01030        freeData(newReg);
01031        newReg->data = (pixman_region16_data_t *)NULL;
01032     }
01033     else if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
01034     {
01035        return pixman_region_copy(newReg, reg1);
01036     }
01037     else if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
01038     {
01039        return pixman_region_copy(newReg, reg2);
01040     }
01041     else if (reg1 == reg2)
01042     {
01043        return pixman_region_copy(newReg, reg1);
01044     }
01045     else
01046     {
01047        /* General purpose intersection */
01048        int overlap; /* result ignored */
01049        if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, PIXMAN_REGION_STATUS_FAILURE, PIXMAN_REGION_STATUS_FAILURE,
01050                      &overlap))
01051            return PIXMAN_REGION_STATUS_FAILURE;
01052        pixman_set_extents(newReg);
01053     }
01054 
01055     good(newReg);
01056     return(PIXMAN_REGION_STATUS_SUCCESS);
01057 }
01058 
01059 #define MERGERECT(r)                                    \
01060 {                                                       \
01061     if (r->x1 <= x2) {                                         \
01062        /* Merge with current rectangle */               \
01063        if (r->x1 < x2) *pOverlap = PIXMAN_REGION_STATUS_SUCCESS;                           \
01064        if (x2 < r->x2) x2 = r->x2;                      \
01065     } else {                                            \
01066        /* Add current rectangle, start new one */              \
01067        NEWRECT(region, pNextRect, x1, y1, x2, y2);             \
01068        x1 = r->x1;                                      \
01069        x2 = r->x2;                                      \
01070     }                                                   \
01071     r++;                                                \
01072 }
01073 
01074 /*======================================================================
01075  *         Region Union
01076  *====================================================================*/
01077 
01078 /*-
01079  *-----------------------------------------------------------------------
01080  * pixman_region_unionO --
01081  *     Handle an overlapping band for the union operation. Picks the
01082  *     left-most rectangle each time and merges it into the region.
01083  *
01084  * Results:
01085  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
01086  *
01087  * Side Effects:
01088  *     region is overwritten.
01089  *     pOverlap is set to PIXMAN_REGION_STATUS_SUCCESS if any boxes overlap.
01090  *
01091  *-----------------------------------------------------------------------
01092  */
01093 static pixman_region_status_t
01094 pixman_region_unionO (
01095     pixman_region16_t        *region,
01096     pixman_box16_t *r1,
01097     pixman_box16_t *r1End,
01098     pixman_box16_t *r2,
01099     pixman_box16_t *r2End,
01100     short       y1,
01101     short       y2,
01102     int                *pOverlap)
01103 {
01104     pixman_box16_t *     pNextRect;
01105     int        x1;     /* left and right side of current union */
01106     int        x2;
01107 
01108     assert (y1 < y2);
01109     assert(r1 != r1End && r2 != r2End);
01110 
01111     pNextRect = PIXREGION_TOP(region);
01112 
01113     /* Start off current rectangle */
01114     if (r1->x1 < r2->x1)
01115     {
01116        x1 = r1->x1;
01117        x2 = r1->x2;
01118        r1++;
01119     }
01120     else
01121     {
01122        x1 = r2->x1;
01123        x2 = r2->x2;
01124        r2++;
01125     }
01126     while (r1 != r1End && r2 != r2End)
01127     {
01128        if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
01129     }
01130 
01131     /* Finish off whoever (if any) is left */
01132     if (r1 != r1End)
01133     {
01134        do
01135        {
01136            MERGERECT(r1);
01137        } while (r1 != r1End);
01138     }
01139     else if (r2 != r2End)
01140     {
01141        do
01142        {
01143            MERGERECT(r2);
01144        } while (r2 != r2End);
01145     }
01146     
01147     /* Add current rectangle */
01148     NEWRECT(region, pNextRect, x1, y1, x2, y2);
01149 
01150     return PIXMAN_REGION_STATUS_SUCCESS;
01151 }
01152 
01153 /* Convenience function for performing union of region with a single rectangle */
01154 pixman_region_status_t
01155 pixman_region_union_rect(pixman_region16_t *dest, pixman_region16_t *source,
01156                  int x, int y, unsigned int width, unsigned int height)
01157 {
01158     pixman_region16_t region;
01159 
01160     if (!width || !height)
01161        return pixman_region_copy (dest, source);
01162     region.data = NULL;
01163     region.extents.x1 = x;
01164     region.extents.y1 = y;
01165     region.extents.x2 = x + width;
01166     region.extents.y2 = y + height;
01167 
01168     return pixman_region_union (dest, source, &region);
01169 }
01170 
01171 pixman_region_status_t
01172 pixman_region_union(pixman_region16_t *newReg, pixman_region16_t *reg1, pixman_region16_t *reg2)
01173 {
01174     int overlap; /* result ignored */
01175 
01176     /* Return PIXMAN_REGION_STATUS_SUCCESS if some overlap between reg1, reg2 */
01177     good(reg1);
01178     good(reg2);
01179     good(newReg);
01180     /*  checks all the simple cases */
01181 
01182     /*
01183      * Region 1 and 2 are the same
01184      */
01185     if (reg1 == reg2)
01186     {
01187        return pixman_region_copy(newReg, reg1);
01188     }
01189 
01190     /*
01191      * Region 1 is empty
01192      */
01193     if (PIXREGION_NIL(reg1))
01194     {
01195        if (PIXREGION_NAR(reg1))
01196            return pixman_break (newReg);
01197         if (newReg != reg2)
01198            return pixman_region_copy(newReg, reg2);
01199         return PIXMAN_REGION_STATUS_SUCCESS;
01200     }
01201 
01202     /*
01203      * Region 2 is empty
01204      */
01205     if (PIXREGION_NIL(reg2))
01206     {
01207        if (PIXREGION_NAR(reg2))
01208            return pixman_break (newReg);
01209         if (newReg != reg1)
01210            return pixman_region_copy(newReg, reg1);
01211         return PIXMAN_REGION_STATUS_SUCCESS;
01212     }
01213 
01214     /*
01215      * Region 1 completely subsumes region 2
01216      */
01217     if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
01218     {
01219         if (newReg != reg1)
01220            return pixman_region_copy(newReg, reg1);
01221         return PIXMAN_REGION_STATUS_SUCCESS;
01222     }
01223 
01224     /*
01225      * Region 2 completely subsumes region 1
01226      */
01227     if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
01228     {
01229         if (newReg != reg2)
01230            return pixman_region_copy(newReg, reg2);
01231         return PIXMAN_REGION_STATUS_SUCCESS;
01232     }
01233 
01234     if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_SUCCESS, &overlap))
01235        return PIXMAN_REGION_STATUS_FAILURE;
01236 
01237     newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
01238     newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
01239     newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
01240     newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
01241     good(newReg);
01242     return PIXMAN_REGION_STATUS_SUCCESS;
01243 }
01244 slim_hidden_def(pixman_region_union);
01245 
01246 
01247 /*======================================================================
01248  *         Batch Rectangle Union
01249  *====================================================================*/
01250 
01251 /*-
01252  *-----------------------------------------------------------------------
01253  * pixman_region_append --
01254  * 
01255  *      "Append" the rgn rectangles onto the end of dstrgn, maintaining
01256  *      knowledge of YX-banding when it's easy.  Otherwise, dstrgn just
01257  *      becomes a non-y-x-banded random collection of rectangles, and not
01258  *      yet a true region.  After a sequence of appends, the caller must
01259  *      call pixman_region_validate to ensure that a valid region is constructed.
01260  *
01261  * Results:
01262  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
01263  *
01264  * Side Effects:
01265  *      dstrgn is modified if rgn has rectangles.
01266  *
01267  */
01268 pixman_region_status_t
01269 pixman_region_append(dstrgn, rgn)
01270     pixman_region16_t * dstrgn;
01271     pixman_region16_t * rgn;
01272 {
01273     int numRects, dnumRects, size;
01274     pixman_box16_t *new, *old;
01275     int prepend;
01276 
01277     if (PIXREGION_NAR(rgn))
01278        return pixman_break (dstrgn);
01279     
01280     if (!rgn->data && (dstrgn->data == &pixman_region_emptyData))
01281     {
01282        dstrgn->extents = rgn->extents;
01283        dstrgn->data = (pixman_region16_data_t *)NULL;
01284        return PIXMAN_REGION_STATUS_SUCCESS;
01285     }
01286 
01287     numRects = PIXREGION_NUM_RECTS(rgn);
01288     if (!numRects)
01289        return PIXMAN_REGION_STATUS_SUCCESS;
01290     prepend = PIXMAN_REGION_STATUS_FAILURE;
01291     size = numRects;
01292     dnumRects = PIXREGION_NUM_RECTS(dstrgn);
01293     if (!dnumRects && (size < 200))
01294        size = 200; /* XXX pick numbers out of a hat */
01295     RECTALLOC(dstrgn, size);
01296     old = PIXREGION_RECTS(rgn);
01297     if (!dnumRects)
01298        dstrgn->extents = rgn->extents;
01299     else if (dstrgn->extents.x2 > dstrgn->extents.x1)
01300     {
01301        pixman_box16_t *first, *last;
01302 
01303        first = old;
01304        last = PIXREGION_BOXPTR(dstrgn) + (dnumRects - 1);
01305        if ((first->y1 > last->y2) ||
01306            ((first->y1 == last->y1) && (first->y2 == last->y2) &&
01307             (first->x1 > last->x2)))
01308        {
01309            if (rgn->extents.x1 < dstrgn->extents.x1)
01310               dstrgn->extents.x1 = rgn->extents.x1;
01311            if (rgn->extents.x2 > dstrgn->extents.x2)
01312               dstrgn->extents.x2 = rgn->extents.x2;
01313            dstrgn->extents.y2 = rgn->extents.y2;
01314        }
01315        else
01316        {
01317            first = PIXREGION_BOXPTR(dstrgn);
01318            last = old + (numRects - 1);
01319            if ((first->y1 > last->y2) ||
01320               ((first->y1 == last->y1) && (first->y2 == last->y2) &&
01321                (first->x1 > last->x2)))
01322            {
01323               prepend = PIXMAN_REGION_STATUS_SUCCESS;
01324               if (rgn->extents.x1 < dstrgn->extents.x1)
01325                   dstrgn->extents.x1 = rgn->extents.x1;
01326               if (rgn->extents.x2 > dstrgn->extents.x2)
01327                   dstrgn->extents.x2 = rgn->extents.x2;
01328               dstrgn->extents.y1 = rgn->extents.y1;
01329            }
01330            else
01331               dstrgn->extents.x2 = dstrgn->extents.x1;
01332        }
01333     }
01334     if (prepend)
01335     {
01336        new = PIXREGION_BOX(dstrgn, numRects);
01337        if (dnumRects == 1)
01338            *new = *PIXREGION_BOXPTR(dstrgn);
01339        else
01340            memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn), 
01341                 dnumRects * sizeof(pixman_box16_t));
01342        new = PIXREGION_BOXPTR(dstrgn);
01343     }
01344     else
01345        new = PIXREGION_BOXPTR(dstrgn) + dnumRects;
01346     if (numRects == 1)
01347        *new = *old;
01348     else
01349        memmove((char *)new, (char *)old, numRects * sizeof(pixman_box16_t));
01350     dstrgn->data->numRects += numRects;
01351     return PIXMAN_REGION_STATUS_SUCCESS;
01352 }
01353 
01354    
01355 #define ExchangeRects(a, b) \
01356 {                        \
01357     pixman_box16_t     t;       \
01358     t = rects[a];        \
01359     rects[a] = rects[b];    \
01360     rects[b] = t;        \
01361 }
01362 
01363 static void
01364 QuickSortRects(
01365     pixman_box16_t     rects[],
01366     int        numRects)
01367 {
01368     int       y1;
01369     int       x1;
01370     int        i, j;
01371     pixman_box16_t *r;
01372 
01373     /* Always called with numRects > 1 */
01374 
01375     do
01376     {
01377        if (numRects == 2)
01378        {
01379            if (rects[0].y1 > rects[1].y1 ||
01380                   (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
01381               ExchangeRects(0, 1);
01382            return;
01383        }
01384 
01385        /* Choose partition element, stick in location 0 */
01386         ExchangeRects(0, numRects >> 1);
01387        y1 = rects[0].y1;
01388        x1 = rects[0].x1;
01389 
01390         /* Partition array */
01391         i = 0;
01392         j = numRects;
01393         do
01394        {
01395            r = &(rects[i]);
01396            do
01397            {
01398               r++;
01399               i++;
01400             } while (i != numRects &&
01401                    (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
01402            r = &(rects[j]);
01403            do
01404            {
01405               r--;
01406               j--;
01407             } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
01408             if (i < j)
01409               ExchangeRects(i, j);
01410         } while (i < j);
01411 
01412         /* Move partition element back to middle */
01413         ExchangeRects(0, j);
01414 
01415        /* Recurse */
01416         if (numRects-j-1 > 1)
01417            QuickSortRects(&rects[j+1], numRects-j-1);
01418         numRects = j;
01419     } while (numRects > 1);
01420 }
01421 
01422 /*-
01423  *-----------------------------------------------------------------------
01424  * pixman_region_validate --
01425  * 
01426  *      Take a ``region'' which is a non-y-x-banded random collection of
01427  *      rectangles, and compute a nice region which is the union of all the
01428  *      rectangles.
01429  *
01430  * Results:
01431  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
01432  *
01433  * Side Effects:
01434  *      The passed-in ``region'' may be modified.
01435  *     pOverlap set to PIXMAN_REGION_STATUS_SUCCESS if any retangles overlapped, else PIXMAN_REGION_STATUS_FAILURE;
01436  *
01437  * Strategy:
01438  *      Step 1. Sort the rectangles into ascending order with primary key y1
01439  *            and secondary key x1.
01440  *
01441  *      Step 2. Split the rectangles into the minimum number of proper y-x
01442  *            banded regions.  This may require horizontally merging
01443  *            rectangles, and vertically coalescing bands.  With any luck,
01444  *            this step in an identity tranformation (ala the Box widget),
01445  *            or a coalescing into 1 box (ala Menus).
01446  *
01447  *     Step 3. Merge the separate regions down to a single region by calling
01448  *            pixman_region_union.  Maximize the work each pixman_region_union call does by using
01449  *            a binary merge.
01450  *
01451  *-----------------------------------------------------------------------
01452  */
01453 
01454 pixman_region_status_t
01455 pixman_region_validate(badreg, pOverlap)
01456     pixman_region16_t * badreg;
01457     int *pOverlap;
01458 {
01459     /* Descriptor for regions under construction  in Step 2. */
01460     typedef struct {
01461        pixman_region16_t   reg;
01462        int        prevBand;
01463        int        curBand;
01464     } RegionInfo;
01465 
01466             int      numRects;   /* Original numRects for badreg          */
01467             RegionInfo *ri;     /* Array of current regions               */
01468             int      numRI;      /* Number of entries used in ri          */
01469             int      sizeRI;           /* Number of entries available in ri    */
01470             int      i;         /* Index into rects                       */
01471     int       j;         /* Index into ri                   */
01472     RegionInfo *rit;       /* &ri[j]                               */
01473     pixman_region16_t *  reg;        /* ri[j].reg                         */
01474     pixman_box16_t * box;       /* Current box in rects            */
01475     pixman_box16_t * riBox;      /* Last box in ri[j].reg                 */
01476     pixman_region16_t *  hreg;       /* ri[j_half].reg                    */
01477     int              ret = PIXMAN_REGION_STATUS_SUCCESS;
01478 
01479     *pOverlap = PIXMAN_REGION_STATUS_FAILURE;
01480     if (!badreg->data)
01481     {
01482        good(badreg);
01483        return PIXMAN_REGION_STATUS_SUCCESS;
01484     }
01485     numRects = badreg->data->numRects;
01486     if (!numRects)
01487     {
01488        if (PIXREGION_NAR(badreg))
01489            return PIXMAN_REGION_STATUS_FAILURE;
01490        good(badreg);
01491        return PIXMAN_REGION_STATUS_SUCCESS;
01492     }
01493     if (badreg->extents.x1 < badreg->extents.x2)
01494     {
01495        if ((numRects) == 1)
01496        {
01497            freeData(badreg);
01498            badreg->data = (pixman_region16_data_t *) NULL;
01499        }
01500        else
01501        {
01502            DOWNSIZE(badreg, numRects);
01503        }
01504        good(badreg);
01505        return PIXMAN_REGION_STATUS_SUCCESS;
01506     }
01507 
01508     /* Step 1: Sort the rects array into ascending (y1, x1) order */
01509     QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);
01510 
01511     /* Step 2: Scatter the sorted array into the minimum number of regions */
01512 
01513     /* Set up the first region to be the first rectangle in badreg */
01514     /* Note that step 2 code will never overflow the ri[0].reg rects array */
01515     ri = (RegionInfo *) malloc(4 * sizeof(RegionInfo));
01516     if (!ri)
01517        return pixman_break (badreg);
01518     sizeRI = 4;
01519     numRI = 1;
01520     ri[0].prevBand = 0;
01521     ri[0].curBand = 0;
01522     ri[0].reg = *badreg;
01523     box = PIXREGION_BOXPTR(&ri[0].reg);
01524     ri[0].reg.extents = *box;
01525     ri[0].reg.data->numRects = 1;
01526 
01527     /* Now scatter rectangles into the minimum set of valid regions.  If the
01528        next rectangle to be added to a region would force an existing rectangle
01529        in the region to be split up in order to maintain y-x banding, just
01530        forget it.  Try the next region.  If it doesn't fit cleanly into any
01531        region, make a new one. */
01532 
01533     for (i = numRects; --i > 0;)
01534     {
01535        box++;
01536        /* Look for a region to append box to */
01537        for (j = numRI, rit = ri; --j >= 0; rit++)
01538        {
01539            reg = &rit->reg;
01540            riBox = PIXREGION_END(reg);
01541 
01542            if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
01543            {
01544               /* box is in same band as riBox.  Merge or append it */
01545               if (box->x1 <= riBox->x2)
01546               {
01547                   /* Merge it with riBox */
01548                   if (box->x1 < riBox->x2) *pOverlap = PIXMAN_REGION_STATUS_SUCCESS;
01549                   if (box->x2 > riBox->x2) riBox->x2 = box->x2;
01550               }
01551               else
01552               {
01553                   RECTALLOC_BAIL(reg, 1, bail);
01554                   *PIXREGION_TOP(reg) = *box;
01555                   reg->data->numRects++;
01556               }
01557               goto NextRect;   /* So sue me */
01558            }
01559            else if (box->y1 >= riBox->y2)
01560            {
01561               /* Put box into new band */
01562               if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
01563               if (reg->extents.x1 > box->x1)   reg->extents.x1 = box->x1;
01564               Coalesce(reg, rit->prevBand, rit->curBand);
01565               rit->curBand = reg->data->numRects;
01566               RECTALLOC_BAIL(reg, 1, bail);
01567               *PIXREGION_TOP(reg) = *box;
01568               reg->data->numRects++;
01569               goto NextRect;
01570            }
01571            /* Well, this region was inappropriate.  Try the next one. */
01572        } /* for j */
01573 
01574        /* Uh-oh.  No regions were appropriate.  Create a new one. */
01575        if (sizeRI == numRI)
01576        {
01577            /* Oops, allocate space for new region information */
01578            sizeRI <<= 1;
01579            rit = (RegionInfo *) realloc(ri, sizeRI * sizeof(RegionInfo));
01580            if (!rit)
01581               goto bail;
01582            ri = rit;
01583            rit = &ri[numRI];
01584        }
01585        numRI++;
01586        rit->prevBand = 0;
01587        rit->curBand = 0;
01588        rit->reg.extents = *box;
01589        rit->reg.data = (pixman_region16_data_t *)NULL;
01590        if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
01591            goto bail;
01592 NextRect: ;
01593     } /* for i */
01594 
01595     /* Make a final pass over each region in order to Coalesce and set
01596        extents.x2 and extents.y2 */
01597 
01598     for (j = numRI, rit = ri; --j >= 0; rit++)
01599     {
01600        reg = &rit->reg;
01601        riBox = PIXREGION_END(reg);
01602        reg->extents.y2 = riBox->y2;
01603        if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
01604        Coalesce(reg, rit->prevBand, rit->curBand);
01605        if (reg->data->numRects == 1) /* keep unions happy below */
01606        {
01607            freeData(reg);
01608            reg->data = (pixman_region16_data_t *)NULL;
01609        }
01610     }
01611 
01612     /* Step 3: Union all regions into a single region */
01613     while (numRI > 1)
01614     {
01615        int half = numRI/2;
01616        for (j = numRI & 1; j < (half + (numRI & 1)); j++)
01617        {
01618            reg = &ri[j].reg;
01619            hreg = &ri[j+half].reg;
01620            if (!pixman_op(reg, reg, hreg, pixman_region_unionO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_SUCCESS, pOverlap))
01621               ret = PIXMAN_REGION_STATUS_FAILURE;
01622            if (hreg->extents.x1 < reg->extents.x1)
01623               reg->extents.x1 = hreg->extents.x1;
01624            if (hreg->extents.y1 < reg->extents.y1)
01625               reg->extents.y1 = hreg->extents.y1;
01626            if (hreg->extents.x2 > reg->extents.x2)
01627               reg->extents.x2 = hreg->extents.x2;
01628            if (hreg->extents.y2 > reg->extents.y2)
01629               reg->extents.y2 = hreg->extents.y2;
01630            freeData(hreg);
01631        }
01632        numRI -= half;
01633     }
01634     *badreg = ri[0].reg;
01635     free(ri);
01636     good(badreg);
01637     return ret;
01638 bail:
01639     for (i = 0; i < numRI; i++)
01640        freeData(&ri[i].reg);
01641     free (ri);
01642     return pixman_break (badreg);
01643 }
01644 
01645 /* XXX: Need to fix this to not use any X data structure
01646 pixman_region16_t *
01647 pixman_region_rectsToRegion(nrects, prect, ctype)
01648     int                     nrects;
01649     xRectangle       *prect;
01650     int                     ctype;
01651 {
01652     pixman_region16_t *     region;
01653     pixman_region16_data_t *       pData;
01654     pixman_box16_t * box;
01655     int        i;
01656     int                     x1, y1, x2, y2;
01657 
01658     region = pixman_region_create(NullBox, 0);
01659     if (PIXREGION_NAR (region))
01660        return region;
01661     if (!nrects)
01662        return region;
01663     if (nrects == 1)
01664     {
01665        x1 = prect->x;
01666        y1 = prect->y;
01667        if ((x2 = x1 + (int) prect->width) > SHRT_MAX)
01668            x2 = SHRT_MAX;
01669        if ((y2 = y1 + (int) prect->height) > SHRT_MAX)
01670            y2 = SHRT_MAX;
01671        if (x1 != x2 && y1 != y2)
01672        {
01673            region->extents.x1 = x1;
01674            region->extents.y1 = y1;
01675            region->extents.x2 = x2;
01676            region->extents.y2 = y2;
01677            region->data = (pixman_region16_data_t *)NULL;
01678        }
01679        return region;
01680     }
01681     pData = allocData(nrects);
01682     if (!pData)
01683     {
01684        pixman_break (region);
01685        return region;
01686     }
01687     box = (pixman_box16_t *) (pData + 1);
01688     for (i = nrects; --i >= 0; prect++)
01689     {
01690        x1 = prect->x;
01691        y1 = prect->y;
01692        if ((x2 = x1 + (int) prect->width) > SHRT_MAX)
01693            x2 = SHRT_MAX;
01694        if ((y2 = y1 + (int) prect->height) > SHRT_MAX)
01695            y2 = SHRT_MAX;
01696        if (x1 != x2 && y1 != y2)
01697        {
01698            box->x1 = x1;
01699            box->y1 = y1;
01700            box->x2 = x2;
01701            box->y2 = y2;
01702            box++;
01703        }
01704     }
01705     if (box != (pixman_box16_t *) (pData + 1))
01706     {
01707        pData->size = nrects;
01708        pData->numRects = box - (pixman_box16_t *) (pData + 1);
01709        region->data = pData;
01710        if (ctype != CT_YXBANDED)
01711        {
01712            int overlap;
01713            region->extents.x1 = region->extents.x2 = 0;
01714            pixman_region_validate(region, &overlap);
01715        }
01716        else
01717            pixman_set_extents(region);
01718        good(region);
01719     }
01720     else
01721     {
01722        free (pData);
01723     }
01724     return region;
01725 }
01726 */
01727 
01728 /*======================================================================
01729  *              Region Subtraction
01730  *====================================================================*/
01731 
01732 
01733 /*-
01734  *-----------------------------------------------------------------------
01735  * pixman_region_subtractO --
01736  *     Overlapping band subtraction. x1 is the left-most point not yet
01737  *     checked.
01738  *
01739  * Results:
01740  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
01741  *
01742  * Side Effects:
01743  *     region may have rectangles added to it.
01744  *
01745  *-----------------------------------------------------------------------
01746  */
01747 /*ARGSUSED*/
01748 static pixman_region_status_t
01749 pixman_region_subtractO (
01750     pixman_region16_t *     region,
01751     pixman_box16_t * r1,
01752     pixman_box16_t *               r1End,
01753     pixman_box16_t * r2,
01754     pixman_box16_t *               r2End,
01755     short     y1,
01756              short   y2,
01757     int              *pOverlap)
01758 {
01759     pixman_box16_t * pNextRect;
01760     int       x1;
01761 
01762     x1 = r1->x1;
01763     
01764     assert(y1<y2);
01765     assert(r1 != r1End && r2 != r2End);
01766 
01767     pNextRect = PIXREGION_TOP(region);
01768 
01769     do
01770     {
01771        if (r2->x2 <= x1)
01772        {
01773            /*
01774             * Subtrahend entirely to left of minuend: go to next subtrahend.
01775             */
01776            r2++;
01777        }
01778        else if (r2->x1 <= x1)
01779        {
01780            /*
01781             * Subtrahend preceeds minuend: nuke left edge of minuend.
01782             */
01783            x1 = r2->x2;
01784            if (x1 >= r1->x2)
01785            {
01786               /*
01787                * Minuend completely covered: advance to next minuend and
01788                * reset left fence to edge of new minuend.
01789                */
01790               r1++;
01791               if (r1 != r1End)
01792                   x1 = r1->x1;
01793            }
01794            else
01795            {
01796               /*
01797                * Subtrahend now used up since it doesn't extend beyond
01798                * minuend
01799                */
01800               r2++;
01801            }
01802        }
01803        else if (r2->x1 < r1->x2)
01804        {
01805            /*
01806             * Left part of subtrahend covers part of minuend: add uncovered
01807             * part of minuend to region and skip to next subtrahend.
01808             */
01809            assert(x1<r2->x1);
01810            NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);
01811 
01812            x1 = r2->x2;
01813            if (x1 >= r1->x2)
01814            {
01815               /*
01816                * Minuend used up: advance to new...
01817                */
01818               r1++;
01819               if (r1 != r1End)
01820                   x1 = r1->x1;
01821            }
01822            else
01823            {
01824               /*
01825                * Subtrahend used up
01826                */
01827               r2++;
01828            }
01829        }
01830        else
01831        {
01832            /*
01833             * Minuend used up: add any remaining piece before advancing.
01834             */
01835            if (r1->x2 > x1)
01836               NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
01837            r1++;
01838            if (r1 != r1End)
01839               x1 = r1->x1;
01840        }
01841     } while ((r1 != r1End) && (r2 != r2End));
01842 
01843 
01844     /*
01845      * Add remaining minuend rectangles to region.
01846      */
01847     while (r1 != r1End)
01848     {
01849        assert(x1<r1->x2);
01850        NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
01851        r1++;
01852        if (r1 != r1End)
01853            x1 = r1->x1;
01854     }
01855     return PIXMAN_REGION_STATUS_SUCCESS;
01856 }
01857        
01858 /*-
01859  *-----------------------------------------------------------------------
01860  * pixman_region_subtract --
01861  *     Subtract regS from regM and leave the result in regD.
01862  *     S stands for subtrahend, M for minuend and D for difference.
01863  *
01864  * Results:
01865  *     PIXMAN_REGION_STATUS_SUCCESS if successful.
01866  *
01867  * Side Effects:
01868  *     regD is overwritten.
01869  *
01870  *-----------------------------------------------------------------------
01871  */
01872 pixman_region_status_t
01873 pixman_region_subtract(regD, regM, regS)
01874     pixman_region16_t *     regD;               
01875     pixman_region16_t *     regM;
01876     pixman_region16_t *     regS;          
01877 {
01878     int overlap; /* result ignored */
01879 
01880     good(regM);
01881     good(regS);
01882     good(regD);
01883    /* check for trivial rejects */
01884     if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
01885        !EXTENTCHECK(&regM->extents, &regS->extents))
01886     {
01887        if (PIXREGION_NAR (regS))
01888            return pixman_break (regD);
01889        return pixman_region_copy(regD, regM);
01890     }
01891     else if (regM == regS)
01892     {
01893        freeData(regD);
01894        regD->extents.x2 = regD->extents.x1;
01895        regD->extents.y2 = regD->extents.y1;
01896        regD->data = &pixman_region_emptyData;
01897        return PIXMAN_REGION_STATUS_SUCCESS;
01898     }
01899  
01900     /* Add those rectangles in region 1 that aren't in region 2,
01901        do yucky substraction for overlaps, and
01902        just throw away rectangles in region 2 that aren't in region 1 */
01903     if (!pixman_op(regD, regM, regS, pixman_region_subtractO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_FAILURE, &overlap))
01904        return PIXMAN_REGION_STATUS_FAILURE;
01905 
01906     /*
01907      * Can't alter RegD's extents before we call pixman_op because
01908      * it might be one of the source regions and pixman_op depends
01909      * on the extents of those regions being unaltered. Besides, this
01910      * way there's no checking against rectangles that will be nuked
01911      * due to coalescing, so we have to examine fewer rectangles.
01912      */
01913     pixman_set_extents(regD);
01914     good(regD);
01915     return PIXMAN_REGION_STATUS_SUCCESS;
01916 }
01917 
01918 /*======================================================================
01919  *         Region Inversion
01920  *====================================================================*/
01921 
01922 /*-
01923  *-----------------------------------------------------------------------
01924  * pixman_region_inverse --
01925  *     Take a region and a box and return a region that is everything
01926  *     in the box but not in the region. The careful reader will note
01927  *     that this is the same as subtracting the region from the box...
01928  *
01929  * Results:
01930  *     PIXMAN_REGION_STATUS_SUCCESS.
01931  *
01932  * Side Effects:
01933  *     newReg is overwritten.
01934  *
01935  *-----------------------------------------------------------------------
01936  */
01937 pixman_region_status_t
01938 pixman_region_inverse(newReg, reg1, invRect)
01939     pixman_region16_t *       newReg;       /* Destination region */
01940     pixman_region16_t *       reg1;         /* Region to invert */
01941     pixman_box16_t *          invRect;    /* Bounding box for inversion */
01942 {
01943     pixman_region16_t         invReg;     /* Quick and dirty region made from the
01944                              * bounding box */
01945     int         overlap;    /* result ignored */
01946 
01947     good(reg1);
01948     good(newReg);
01949    /* check for trivial rejects */
01950     if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, &reg1->extents))
01951     {
01952        if (PIXREGION_NAR(reg1))
01953            return pixman_break (newReg);
01954        newReg->extents = *invRect;
01955        freeData(newReg);
01956        newReg->data = (pixman_region16_data_t *)NULL;
01957         return PIXMAN_REGION_STATUS_SUCCESS;
01958     }
01959 
01960     /* Add those rectangles in region 1 that aren't in region 2,
01961        do yucky substraction for overlaps, and
01962        just throw away rectangles in region 2 that aren't in region 1 */
01963     invReg.extents = *invRect;
01964     invReg.data = (pixman_region16_data_t *)NULL;
01965     if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_FAILURE, &overlap))
01966        return PIXMAN_REGION_STATUS_FAILURE;
01967 
01968     /*
01969      * Can't alter newReg's extents before we call pixman_op because
01970      * it might be one of the source regions and pixman_op depends
01971      * on the extents of those regions being unaltered. Besides, this
01972      * way there's no checking against rectangles that will be nuked
01973      * due to coalescing, so we have to examine fewer rectangles.
01974      */
01975     pixman_set_extents(newReg);
01976     good(newReg);
01977     return PIXMAN_REGION_STATUS_SUCCESS;
01978 }
01979 
01980 /*
01981  *   RectIn(region, rect)
01982  *   This routine takes a pointer to a region and a pointer to a box
01983  *   and determines if the box is outside/inside/partly inside the region.
01984  *
01985  *   The idea is to travel through the list of rectangles trying to cover the
01986  *   passed box with them. Anytime a piece of the rectangle isn't covered
01987  *   by a band of rectangles, partOut is set PIXMAN_REGION_STATUS_SUCCESS. Any time a rectangle in
01988  *   the region covers part of the box, partIn is set PIXMAN_REGION_STATUS_SUCCESS. The process ends
01989  *   when either the box has been completely covered (we reached a band that
01990  *   doesn't overlap the box, partIn is PIXMAN_REGION_STATUS_SUCCESS and partOut is false), the
01991  *   box has been partially covered (partIn == partOut == PIXMAN_REGION_STATUS_SUCCESS -- because of
01992  *   the banding, the first time this is true we know the box is only
01993  *   partially in the region) or is outside the region (we reached a band
01994  *   that doesn't overlap the box at all and partIn is false)
01995  */
01996 
01997 int
01998 pixman_region_contains_rectangle(region, prect)
01999     pixman_region16_t *  region;
02000     pixman_box16_t *     prect;
02001 {
02002     int       x;
02003     int       y;
02004     pixman_box16_t *     pbox;
02005     pixman_box16_t *     pboxEnd;
02006     int                     partIn, partOut;
02007     int                     numRects;
02008 
02009     good(region);
02010     numRects = PIXREGION_NUM_RECTS(region);
02011     /* useful optimization */
02012     if (!numRects || !EXTENTCHECK(&region->extents, prect))
02013         return(rgnOUT);
02014 
02015     if (numRects == 1)
02016     {
02017        /* We know that it must be rgnIN or rgnPART */
02018        if (SUBSUMES(&region->extents, prect))
02019            return(rgnIN);
02020        else
02021            return(rgnPART);
02022     }
02023 
02024     partOut = PIXMAN_REGION_STATUS_FAILURE;
02025     partIn = PIXMAN_REGION_STATUS_FAILURE;
02026 
02027     /* (x,y) starts at upper left of rect, moving to the right and down */
02028     x = prect->x1;
02029     y = prect->y1;
02030 
02031     /* can stop when both partOut and partIn are PIXMAN_REGION_STATUS_SUCCESS, or we reach prect->y2 */
02032     for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
02033          pbox != pboxEnd;
02034          pbox++)
02035     {
02036 
02037         if (pbox->y2 <= y)
02038            continue;    /* getting up to speed or skipping remainder of band */
02039 
02040         if (pbox->y1 > y)
02041         {
02042            partOut = PIXMAN_REGION_STATUS_SUCCESS;      /* missed part of rectangle above */
02043            if (partIn || (pbox->y1 >= prect->y2))
02044               break;
02045            y = pbox->y1;        /* x guaranteed to be == prect->x1 */
02046         }
02047 
02048         if (pbox->x2 <= x)
02049            continue;            /* not far enough over yet */
02050 
02051         if (pbox->x1 > x)
02052         {
02053            partOut = PIXMAN_REGION_STATUS_SUCCESS;      /* missed part of rectangle to left */
02054            if (partIn)
02055               break;
02056         }
02057 
02058         if (pbox->x1 < prect->x2)
02059         {
02060             partIn = PIXMAN_REGION_STATUS_SUCCESS;      /* definitely overlap */
02061             if (partOut)
02062                break;
02063         }
02064 
02065         if (pbox->x2 >= prect->x2)
02066         {
02067            y = pbox->y2;        /* finished with this band */
02068            if (y >= prect->y2)
02069               break;
02070            x = prect->x1;       /* reset x out to left again */
02071         }
02072        else
02073        {
02074            /*
02075             * Because boxes in a band are maximal width, if the first box
02076             * to overlap the rectangle doesn't completely cover it in that
02077             * band, the rectangle must be partially out, since some of it
02078             * will be uncovered in that band. partIn will have been set true
02079             * by now...
02080             */
02081            partOut = PIXMAN_REGION_STATUS_SUCCESS;
02082            break;
02083        }
02084     }
02085 
02086     return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
02087 }
02088 
02089 /* pixman_region_translate (region, x, y)
02090    translates in place
02091 */
02092 
02093 void
02094 pixman_region_translate (pixman_region16_t * region, int x, int y)
02095 {
02096     int x1, x2, y1, y2;
02097     int nbox;
02098     pixman_box16_t * pbox;
02099 
02100     good(region);
02101     region->extents.x1 = x1 = region->extents.x1 + x;
02102     region->extents.y1 = y1 = region->extents.y1 + y;
02103     region->extents.x2 = x2 = region->extents.x2 + x;
02104     region->extents.y2 = y2 = region->extents.y2 + y;
02105     if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
02106     {
02107        if (region->data && (nbox = region->data->numRects))
02108        {
02109            for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
02110            {
02111               pbox->x1 += x;
02112               pbox->y1 += y;
02113               pbox->x2 += x;
02114               pbox->y2 += y;
02115            }
02116        }
02117        return;
02118     }
02119     if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
02120     {
02121        region->extents.x2 = region->extents.x1;
02122        region->extents.y2 = region->extents.y1;
02123        freeData(region);
02124        region->data = &pixman_region_emptyData;
02125        return;
02126     }
02127     if (x1 < SHRT_MIN)
02128        region->extents.x1 = SHRT_MIN;
02129     else if (x2 > SHRT_MAX)
02130        region->extents.x2 = SHRT_MAX;
02131     if (y1 < SHRT_MIN)
02132        region->extents.y1 = SHRT_MIN;
02133     else if (y2 > SHRT_MAX)
02134        region->extents.y2 = SHRT_MAX;
02135     if (region->data && (nbox = region->data->numRects))
02136     {
02137        pixman_box16_t * pboxout;
02138 
02139        for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
02140        {
02141            pboxout->x1 = x1 = pbox->x1 + x;
02142            pboxout->y1 = y1 = pbox->y1 + y;
02143            pboxout->x2 = x2 = pbox->x2 + x;
02144            pboxout->y2 = y2 = pbox->y2 + y;
02145            if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
02146                (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
02147            {
02148               region->data->numRects--;
02149               continue;
02150            }
02151            if (x1 < SHRT_MIN)
02152               pboxout->x1 = SHRT_MIN;
02153            else if (x2 > SHRT_MAX)
02154               pboxout->x2 = SHRT_MAX;
02155            if (y1 < SHRT_MIN)
02156               pboxout->y1 = SHRT_MIN;
02157            else if (y2 > SHRT_MAX)
02158               pboxout->y2 = SHRT_MAX;
02159            pboxout++;
02160        }
02161        if (pboxout != pbox)
02162        {
02163            if (region->data->numRects == 1)
02164            {
02165               region->extents = *PIXREGION_BOXPTR(region);
02166               freeData(region);
02167               region->data = (pixman_region16_data_t *)NULL;
02168            }
02169            else
02170               pixman_set_extents(region);
02171        }
02172     }
02173 }
02174 
02175 /* XXX: Do we need this?
02176 static pixman_region_status_t
02177 pixman_region16_data_copy(pixman_region16_t * dst, pixman_region16_t * src)
02178 {
02179     good(dst);
02180     good(src);
02181     if (dst->data) 
02182        return PIXMAN_REGION_STATUS_SUCCESS;
02183     if (dst == src)
02184        return PIXMAN_REGION_STATUS_SUCCESS;
02185     if (!src->data || !src->data->size)
02186     {
02187        freeData(dst);
02188        dst->data = (pixman_region16_data_t *)NULL;
02189        return PIXMAN_REGION_STATUS_SUCCESS;
02190     }
02191     if (!dst->data || (dst->data->size < src->data->numRects))
02192     {
02193        freeData(dst);
02194        dst->data = allocData(src->data->numRects);
02195        if (!dst->data)
02196            return pixman_break (dst);
02197     }
02198     dst->data->size = src->data->size;
02199     dst->data->numRects = src->data->numRects;
02200     return PIXMAN_REGION_STATUS_SUCCESS;
02201 }
02202 */
02203 
02204 void
02205 pixman_region_reset(pixman_region16_t *region, pixman_box16_t *box)
02206 {
02207     good(region);
02208     assert(box->x1<=box->x2);
02209     assert(box->y1<=box->y2);
02210     region->extents = *box;
02211     freeData(region);
02212     region->data = (pixman_region16_data_t *)NULL;
02213 }
02214 
02215 int
02216 pixman_region_contains_point(region, x, y, box)
02217     pixman_region16_t * region;
02218     int x, y;
02219     pixman_box16_t * box;     /* "return" value */
02220 {
02221     pixman_box16_t *pbox, *pboxEnd;
02222     int numRects;
02223 
02224     good(region);
02225     numRects = PIXREGION_NUM_RECTS(region);
02226     if (!numRects || !INBOX(&region->extents, x, y))
02227         return(PIXMAN_REGION_STATUS_FAILURE);
02228     if (numRects == 1)
02229     {
02230        *box = region->extents;
02231        return(PIXMAN_REGION_STATUS_SUCCESS);
02232     }
02233     for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
02234         pbox != pboxEnd;
02235         pbox++)
02236     {
02237         if (y >= pbox->y2)
02238           continue;         /* not there yet */
02239        if ((y < pbox->y1) || (x < pbox->x1))
02240           break;            /* missed it */
02241        if (x >= pbox->x2)
02242           continue;         /* not there yet */
02243        *box = *pbox;
02244        return(PIXMAN_REGION_STATUS_SUCCESS);
02245     }
02246     return(PIXMAN_REGION_STATUS_FAILURE);
02247 }
02248 
02249 int
02250 pixman_region_not_empty(region)
02251     pixman_region16_t * region;
02252 {
02253     good(region);
02254     return(!PIXREGION_NIL(region));
02255 }
02256 
02257 /* XXX: Do we need this?
02258 static int
02259 pixman_region16_broken(pixman_region16_t * region)
02260 {
02261     good(region);
02262     return (PIXREGION_NAR(region));
02263 }
02264 */
02265 
02266 void
02267 pixman_region_empty(region)
02268     pixman_region16_t * region;
02269 {
02270     good(region);
02271     freeData(region);
02272     region->extents.x2 = region->extents.x1;
02273     region->extents.y2 = region->extents.y1;
02274     region->data = &pixman_region_emptyData;
02275 }
02276 
02277 pixman_box16_t *
02278 pixman_region_extents(region)
02279     pixman_region16_t * region;
02280 {
02281     good(region);
02282     return(&region->extents);
02283 }
02284 
02285 #define ExchangeSpans(a, b)                          \
02286 {                                                    \
02287     pixman_region16_point_t tpt;                                   \
02288     int    tw;                                              \
02289                                                      \
02290     tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt;    \
02291     tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
02292 }
02293 
02294 /* ||| I should apply the merge sort code to rectangle sorting above, and see
02295    if mapping time can be improved.  But right now I've been at work 12 hours,
02296    so forget it.
02297 */
02298 
02299 static void QuickSortSpans(
02300     pixman_region16_point_t spans[],
02301     int           widths[],
02302     int           numSpans)
02303 {
02304     int           y;
02305     int           i, j, m;
02306     pixman_region16_point_t *r;
02307 
02308     /* Always called with numSpans > 1 */
02309     /* Sorts only by y, doesn't bother to sort by x */
02310 
02311     do
02312     {
02313        if (numSpans < 9)
02314        {
02315            /* Do insertion sort */
02316            int yprev;
02317 
02318            yprev = spans[0].y;
02319            i = 1;
02320            do
02321            { /* while i != numSpans */
02322               y = spans[i].y;
02323               if (yprev > y)
02324               {
02325                   /* spans[i] is out of order.  Move into proper location. */
02326                   pixman_region16_point_t tpt;
02327                   int           tw, k;
02328 
02329                   for (j = 0; y >= spans[j].y; j++) {}
02330                   tpt = spans[i];
02331                   tw  = widths[i];
02332                   for (k = i; k != j; k--)
02333                   {
02334                      spans[k] = spans[k-1];
02335                      widths[k] = widths[k-1];
02336                   }
02337                   spans[j] = tpt;
02338                   widths[j] = tw;
02339                   y = spans[i].y;
02340               } /* if out of order */
02341               yprev = y;
02342               i++;
02343            } while (i != numSpans);
02344            return;
02345        }
02346 
02347        /* Choose partition element, stick in location 0 */
02348        m = numSpans / 2;
02349        if (spans[m].y > spans[0].y)              ExchangeSpans(m, 0);
02350        if (spans[m].y > spans[numSpans-1].y)   ExchangeSpans(m, numSpans-1);
02351        if (spans[m].y > spans[0].y)              ExchangeSpans(m, 0);
02352        y = spans[0].y;
02353 
02354         /* Partition array */
02355         i = 0;
02356         j = numSpans;
02357         do
02358        {
02359            r = &(spans[i]);
02360            do
02361            {
02362               r++;
02363               i++;
02364             } while (i != numSpans && r->y < y);
02365            r = &(spans[j]);
02366            do
02367            {
02368               r--;
02369               j--;
02370             } while (y < r->y);
02371             if (i < j)
02372               ExchangeSpans(i, j);
02373         } while (i < j);
02374 
02375         /* Move partition element back to middle */
02376         ExchangeSpans(0, j);
02377 
02378        /* Recurse */
02379         if (numSpans-j-1 > 1)
02380            QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
02381         numSpans = j;
02382     } while (numSpans > 1);
02383 }
02384 
02385 #define NextBand()                                          \
02386 {                                                           \
02387     clipy1 = pboxBandStart->y1;                                    \
02388     clipy2 = pboxBandStart->y2;                                    \
02389     pboxBandEnd = pboxBandStart + 1;                               \
02390     while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) {  \
02391        pboxBandEnd++;                                              \
02392     }                                                       \
02393     for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
02394 }
02395 
02396 /*
02397     Clip a list of scanlines to a region.  The caller has allocated the
02398     space.  FSorted is non-zero if the scanline origins are in ascending
02399     order.
02400     returns the number of new, clipped scanlines.
02401 */
02402 
02403 #ifdef XXX_DO_WE_NEED_THIS
02404 static int
02405 pixman_region16_clip_spans(
02406     pixman_region16_t              *prgnDst,
02407     pixman_region16_point_t        *ppt,
02408     int                     *pwidth,
02409     int                     nspans,
02410     pixman_region16_point_t        *pptNew,
02411     int                     *pwidthNew,
02412     int                     fSorted)
02413 {
02414     pixman_region16_point_t        *pptLast;
02415     int                     *pwidthNewStart;     /* the vengeance of Xerox! */
02416     int       y, x1, x2;
02417     int       numRects;
02418 
02419     good(prgnDst);
02420     pptLast = ppt + nspans;
02421     pwidthNewStart = pwidthNew;
02422 
02423     if (!prgnDst->data)
02424     {
02425        /* Do special fast code with clip boundaries in registers(?) */
02426        /* It doesn't pay much to make use of fSorted in this case, 
02427           so we lump everything together. */
02428 
02429           int clipx1, clipx2, clipy1, clipy2;
02430 
02431        clipx1 = prgnDst->extents.x1;
02432        clipy1 = prgnDst->extents.y1;
02433        clipx2 = prgnDst->extents.x2;
02434        clipy2 = prgnDst->extents.y2;
02435            
02436        for (; ppt != pptLast; ppt++, pwidth++)
02437        {
02438            y = ppt->y;
02439            x1 = ppt->x;
02440            if (clipy1 <= y && y < clipy2)
02441            {
02442               x2 = x1 + *pwidth;
02443               if (x1 < clipx1)    x1 = clipx1;
02444               if (x2 > clipx2)    x2 = clipx2;
02445               if (x1 < x2)
02446               {
02447                   /* part of span in clip rectangle */
02448                   pptNew->x = x1;
02449                   pptNew->y = y;
02450                   *pwidthNew = x2 - x1;
02451                   pptNew++;
02452                   pwidthNew++;
02453               }
02454            }
02455        } /* end for */
02456 
02457     }
02458     else if ((numRects = prgnDst->data->numRects))
02459     {
02460        /* Have to clip against many boxes */
02461        pixman_box16_t *pboxBandStart, *pboxBandEnd;
02462        pixman_box16_t *pbox;
02463        pixman_box16_t *pboxLast;
02464        int    clipy1, clipy2;
02465 
02466        /* In this case, taking advantage of sorted spans gains more than
02467           the sorting costs. */
02468        if ((! fSorted) && (nspans > 1))
02469            QuickSortSpans(ppt, pwidth, nspans);
02470 
02471        pboxBandStart = PIXREGION_BOXPTR(prgnDst);
02472        pboxLast = pboxBandStart + numRects;
02473     
02474        NextBand();
02475 
02476        for (; ppt != pptLast; )
02477        {
02478            y = ppt->y;
02479            if (y < clipy2)
02480            {
02481               /* span is in the current band */
02482               pbox = pboxBandStart;
02483               x1 = ppt->x;
02484               x2 = x1 + *pwidth;
02485               do
02486               { /* For each box in band */
02487                   int    newx1, newx2;
02488 
02489                   newx1 = x1;
02490                   newx2 = x2;
02491                   if (newx1 < pbox->x1)   newx1 = pbox->x1;
02492                   if (newx2 > pbox->x2)   newx2 = pbox->x2;
02493                   if (newx1 < newx2)
02494                   {
02495                      /* Part of span in clip rectangle */
02496                      pptNew->x = newx1;
02497                      pptNew->y = y;
02498                      *pwidthNew = newx2 - newx1;
02499                      pptNew++;
02500                      pwidthNew++;
02501                   }
02502                   pbox++;
02503               } while (pbox != pboxBandEnd);
02504               ppt++;
02505               pwidth++;
02506            }
02507            else
02508            {
02509               /* Move to next band, adjust ppt as needed */
02510               pboxBandStart = pboxBandEnd;
02511               if (pboxBandStart == pboxLast)
02512                   break; /* We're completely done */
02513               NextBand();
02514            }
02515        }
02516     }
02517     return (pwidthNew - pwidthNewStart);
02518 }
02519 
02520 /* find the band in a region with the most rectangles */
02521 static int
02522 pixman_region16_find_max_band(pixman_region16_t * prgn)
02523 {
02524     int nbox;
02525     pixman_box16_t * pbox;
02526     int nThisBand;
02527     int nMaxBand = 0;
02528     short yThisBand;
02529 
02530     good(prgn);
02531     nbox = PIXREGION_NUM_RECTS(prgn);
02532     pbox = PIXREGION_RECTS(prgn);
02533 
02534     while(nbox > 0)
02535     {
02536        yThisBand = pbox->y1;
02537        nThisBand = 0;
02538        while((nbox > 0) && (pbox->y1 == yThisBand))
02539        {
02540            nbox--;
02541            pbox++;
02542            nThisBand++;
02543        }
02544        if (nThisBand > nMaxBand)
02545            nMaxBand = nThisBand;
02546     }
02547     return (nMaxBand);
02548 }
02549 #endif /* XXX_DO_WE_NEED_THIS */