1/*********************************************************** 2 3Copyright 1987, 1988, 1989, 1998 The Open Group 4 5Permission to use, copy, modify, distribute, and sell this software and its 6documentation for any purpose is hereby granted without fee, provided that 7the above copyright notice appear in all copies and that both that 8copyright notice and this permission notice appear in supporting 9documentation. 10 11The above copyright notice and this permission notice shall be included in 12all copies or substantial portions of the Software. 13 14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 20 21Except as contained in this notice, the name of The Open Group shall not be 22used in advertising or otherwise to promote the sale, use or other dealings 23in this Software without prior written authorization from The Open Group. 24 25 26Copyright 1987, 1988, 1989 by 27Digital Equipment Corporation, Maynard, Massachusetts. 28 29 All Rights Reserved 30 31Permission to use, copy, modify, and distribute this software and its 32documentation for any purpose and without fee is hereby granted, 33provided that the above copyright notice appear in all copies and that 34both that copyright notice and this permission notice appear in 35supporting documentation, and that the name of Digital not be 36used in advertising or publicity pertaining to distribution of the 37software without specific, written prior permission. 38 39DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 40ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 41DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 42ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 43WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 44ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 45SOFTWARE. 46 47******************************************************************/ 48 49/* The panoramix components contained the following notice */ 50/***************************************************************** 51 52Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts. 53 54Permission is hereby granted, free of charge, to any person obtaining a copy 55of this software and associated documentation files (the "Software"), to deal 56in the Software without restriction, including without limitation the rights 57to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 58copies of the Software. 59 60The above copyright notice and this permission notice shall be included in 61all copies or substantial portions of the Software. 62 63THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 64IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 65FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 66DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING, 67BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY, 68WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR 69IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 70 71Except as contained in this notice, the name of Digital Equipment Corporation 72shall not be used in advertising or otherwise to promote the sale, use or other 73dealings in this Software without prior written authorization from Digital 74Equipment Corporation. 75 76******************************************************************/ 77 78#ifdef HAVE_DIX_CONFIG_H 79#include <dix-config.h> 80#endif 81 82#include "regionstr.h" 83#include <X11/Xprotostr.h> 84#include <X11/Xfuncproto.h> 85#include "gc.h" 86#include <pixman.h> 87 88#undef assert 89#ifdef REGION_DEBUG 90#define assert(expr) { \ 91 CARD32 *foo = NULL; \ 92 if (!(expr)) { \ 93 ErrorF("Assertion failed file %s, line %d: %s\n", \ 94 __FILE__, __LINE__, #expr); \ 95 *foo = 0xdeadbeef; /* to get a backtrace */ \ 96 } \ 97 } 98#else 99#define assert(expr) 100#endif 101 102#define good(reg) assert(RegionIsValid(reg)) 103 104/* 105 * The functions in this file implement the Region abstraction used extensively 106 * throughout the X11 sample server. A Region is simply a set of disjoint 107 * (non-overlapping) rectangles, plus an "extent" rectangle which is the 108 * smallest single rectangle that contains all the non-overlapping rectangles. 109 * 110 * A Region is implemented as a "y-x-banded" array of rectangles. This array 111 * imposes two degrees of order. First, all rectangles are sorted by top side 112 * y coordinate first (y1), and then by left side x coordinate (x1). 113 * 114 * Furthermore, the rectangles are grouped into "bands". Each rectangle in a 115 * band has the same top y coordinate (y1), and each has the same bottom y 116 * coordinate (y2). Thus all rectangles in a band differ only in their left 117 * and right side (x1 and x2). Bands are implicit in the array of rectangles: 118 * there is no separate list of band start pointers. 119 * 120 * The y-x band representation does not minimize rectangles. In particular, 121 * if a rectangle vertically crosses a band (the rectangle has scanlines in 122 * the y1 to y2 area spanned by the band), then the rectangle may be broken 123 * down into two or more smaller rectangles stacked one atop the other. 124 * 125 * ----------- ----------- 126 * | | | | band 0 127 * | | -------- ----------- -------- 128 * | | | | in y-x banded | | | | band 1 129 * | | | | form is | | | | 130 * ----------- | | ----------- -------- 131 * | | | | band 2 132 * -------- -------- 133 * 134 * An added constraint on the rectangles is that they must cover as much 135 * horizontal area as possible: no two rectangles within a band are allowed 136 * to touch. 137 * 138 * Whenever possible, bands will be merged together to cover a greater vertical 139 * distance (and thus reduce the number of rectangles). Two bands can be merged 140 * only if the bottom of one touches the top of the other and they have 141 * rectangles in the same places (of the same width, of course). 142 * 143 * Adam de Boor wrote most of the original region code. Joel McCormack 144 * substantially modified or rewrote most of the core arithmetic routines, 145 * and added RegionValidate in order to support several speed improvements 146 * to miValidateTree. Bob Scheifler changed the representation to be more 147 * compact when empty or a single rectangle, and did a bunch of gratuitous 148 * reformatting. 149 */ 150 151/* true iff two Boxes overlap */ 152#define EXTENTCHECK(r1,r2) \ 153 (!( ((r1)->x2 <= (r2)->x1) || \ 154 ((r1)->x1 >= (r2)->x2) || \ 155 ((r1)->y2 <= (r2)->y1) || \ 156 ((r1)->y1 >= (r2)->y2) ) ) 157 158/* true iff (x,y) is in Box */ 159#define INBOX(r,x,y) \ 160 ( ((r)->x2 > x) && \ 161 ((r)->x1 <= x) && \ 162 ((r)->y2 > y) && \ 163 ((r)->y1 <= y) ) 164 165/* true iff Box r1 contains Box r2 */ 166#define SUBSUMES(r1,r2) \ 167 ( ((r1)->x1 <= (r2)->x1) && \ 168 ((r1)->x2 >= (r2)->x2) && \ 169 ((r1)->y1 <= (r2)->y1) && \ 170 ((r1)->y2 >= (r2)->y2) ) 171 172#define xfreeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data) 173 174#define RECTALLOC_BAIL(pReg,n,bail) \ 175if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ 176 if (!RegionRectAlloc(pReg, n)) { goto bail; } 177 178#define RECTALLOC(pReg,n) \ 179if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ 180 if (!RegionRectAlloc(pReg, n)) { return FALSE; } 181 182#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \ 183{ \ 184 pNextRect->x1 = nx1; \ 185 pNextRect->y1 = ny1; \ 186 pNextRect->x2 = nx2; \ 187 pNextRect->y2 = ny2; \ 188 pNextRect++; \ 189} 190 191#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \ 192{ \ 193 if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\ 194 { \ 195 if (!RegionRectAlloc(pReg, 1)) \ 196 return FALSE; \ 197 pNextRect = RegionTop(pReg); \ 198 } \ 199 ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \ 200 pReg->data->numRects++; \ 201 assert(pReg->data->numRects<=pReg->data->size); \ 202} 203 204#define DOWNSIZE(reg,numRects) \ 205if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ 206{ \ 207 size_t NewSize = RegionSizeof(numRects); \ 208 RegDataPtr NewData = \ 209 (NewSize > 0) ? realloc((reg)->data, NewSize) : NULL ; \ 210 if (NewData) \ 211 { \ 212 NewData->size = (numRects); \ 213 (reg)->data = NewData; \ 214 } \ 215} 216 217BoxRec RegionEmptyBox = { 0, 0, 0, 0 }; 218RegDataRec RegionEmptyData = { 0, 0 }; 219 220RegDataRec RegionBrokenData = { 0, 0 }; 221static RegionRec RegionBrokenRegion = { {0, 0, 0, 0}, &RegionBrokenData }; 222 223void 224InitRegions(void) 225{ 226 pixman_region_set_static_pointers(&RegionEmptyBox, &RegionEmptyData, 227 &RegionBrokenData); 228} 229 230/***************************************************************** 231 * RegionCreate(rect, size) 232 * This routine does a simple malloc to make a structure of 233 * REGION of "size" number of rectangles. 234 *****************************************************************/ 235 236RegionPtr 237RegionCreate(BoxPtr rect, int size) 238{ 239 RegionPtr pReg; 240 241 pReg = (RegionPtr) malloc(sizeof(RegionRec)); 242 if (!pReg) 243 return &RegionBrokenRegion; 244 245 RegionInit(pReg, rect, size); 246 247 return pReg; 248} 249 250void 251RegionDestroy(RegionPtr pReg) 252{ 253 pixman_region_fini(pReg); 254 if (pReg != &RegionBrokenRegion) 255 free(pReg); 256} 257 258RegionPtr 259RegionDuplicate(RegionPtr pOld) 260{ 261 RegionPtr pNew; 262 263 pNew = RegionCreate(&pOld->extents, 0); 264 if (!pNew) 265 return NULL; 266 if (!RegionCopy(pNew, pOld)) { 267 RegionDestroy(pNew); 268 return NULL; 269 } 270 return pNew; 271} 272 273void 274RegionPrint(RegionPtr rgn) 275{ 276 int num, size; 277 int i; 278 BoxPtr rects; 279 280 num = RegionNumRects(rgn); 281 size = RegionSize(rgn); 282 rects = RegionRects(rgn); 283 ErrorF("[mi] num: %d size: %d\n", num, size); 284 ErrorF("[mi] extents: %d %d %d %d\n", 285 rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2); 286 for (i = 0; i < num; i++) 287 ErrorF("[mi] %d %d %d %d \n", 288 rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); 289 ErrorF("[mi] \n"); 290} 291 292#ifdef DEBUG 293Bool 294RegionIsValid(RegionPtr reg) 295{ 296 int i, numRects; 297 298 if ((reg->extents.x1 > reg->extents.x2) || 299 (reg->extents.y1 > reg->extents.y2)) 300 return FALSE; 301 numRects = RegionNumRects(reg); 302 if (!numRects) 303 return ((reg->extents.x1 == reg->extents.x2) && 304 (reg->extents.y1 == reg->extents.y2) && 305 (reg->data->size || (reg->data == &RegionEmptyData))); 306 else if (numRects == 1) 307 return !reg->data; 308 else { 309 BoxPtr pboxP, pboxN; 310 BoxRec box; 311 312 pboxP = RegionRects(reg); 313 box = *pboxP; 314 box.y2 = pboxP[numRects - 1].y2; 315 pboxN = pboxP + 1; 316 for (i = numRects; --i > 0; pboxP++, pboxN++) { 317 if ((pboxN->x1 >= pboxN->x2) || (pboxN->y1 >= pboxN->y2)) 318 return FALSE; 319 if (pboxN->x1 < box.x1) 320 box.x1 = pboxN->x1; 321 if (pboxN->x2 > box.x2) 322 box.x2 = pboxN->x2; 323 if ((pboxN->y1 < pboxP->y1) || 324 ((pboxN->y1 == pboxP->y1) && 325 ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2)))) 326 return FALSE; 327 } 328 return ((box.x1 == reg->extents.x1) && 329 (box.x2 == reg->extents.x2) && 330 (box.y1 == reg->extents.y1) && (box.y2 == reg->extents.y2)); 331 } 332} 333#endif /* DEBUG */ 334 335Bool 336RegionBreak(RegionPtr pReg) 337{ 338 xfreeData(pReg); 339 pReg->extents = RegionEmptyBox; 340 pReg->data = &RegionBrokenData; 341 return FALSE; 342} 343 344Bool 345RegionRectAlloc(RegionPtr pRgn, int n) 346{ 347 RegDataPtr data; 348 size_t rgnSize; 349 350 if (!pRgn->data) { 351 n++; 352 rgnSize = RegionSizeof(n); 353 pRgn->data = (rgnSize > 0) ? malloc(rgnSize) : NULL; 354 if (!pRgn->data) 355 return RegionBreak(pRgn); 356 pRgn->data->numRects = 1; 357 *RegionBoxptr(pRgn) = pRgn->extents; 358 } 359 else if (!pRgn->data->size) { 360 rgnSize = RegionSizeof(n); 361 pRgn->data = (rgnSize > 0) ? malloc(rgnSize) : NULL; 362 if (!pRgn->data) 363 return RegionBreak(pRgn); 364 pRgn->data->numRects = 0; 365 } 366 else { 367 if (n == 1) { 368 n = pRgn->data->numRects; 369 if (n > 500) /* XXX pick numbers out of a hat */ 370 n = 250; 371 } 372 n += pRgn->data->numRects; 373 rgnSize = RegionSizeof(n); 374 data = (rgnSize > 0) ? realloc(pRgn->data, rgnSize) : NULL; 375 if (!data) 376 return RegionBreak(pRgn); 377 pRgn->data = data; 378 } 379 pRgn->data->size = n; 380 return TRUE; 381} 382 383/*====================================================================== 384 * Generic Region Operator 385 *====================================================================*/ 386 387/*- 388 *----------------------------------------------------------------------- 389 * RegionCoalesce -- 390 * Attempt to merge the boxes in the current band with those in the 391 * previous one. We are guaranteed that the current band extends to 392 * the end of the rects array. Used only by RegionOp. 393 * 394 * Results: 395 * The new index for the previous band. 396 * 397 * Side Effects: 398 * If coalescing takes place: 399 * - rectangles in the previous band will have their y2 fields 400 * altered. 401 * - pReg->data->numRects will be decreased. 402 * 403 *----------------------------------------------------------------------- 404 */ 405_X_INLINE static int 406RegionCoalesce(RegionPtr pReg, /* Region to coalesce */ 407 int prevStart, /* Index of start of previous band */ 408 int curStart) 409{ /* Index of start of current band */ 410 BoxPtr pPrevBox; /* Current box in previous band */ 411 BoxPtr pCurBox; /* Current box in current band */ 412 int numRects; /* Number rectangles in both bands */ 413 int y2; /* Bottom of current band */ 414 415 /* 416 * Figure out how many rectangles are in the band. 417 */ 418 numRects = curStart - prevStart; 419 assert(numRects == pReg->data->numRects - curStart); 420 421 if (!numRects) 422 return curStart; 423 424 /* 425 * The bands may only be coalesced if the bottom of the previous 426 * matches the top scanline of the current. 427 */ 428 pPrevBox = RegionBox(pReg, prevStart); 429 pCurBox = RegionBox(pReg, curStart); 430 if (pPrevBox->y2 != pCurBox->y1) 431 return curStart; 432 433 /* 434 * Make sure the bands have boxes in the same places. This 435 * assumes that boxes have been added in such a way that they 436 * cover the most area possible. I.e. two boxes in a band must 437 * have some horizontal space between them. 438 */ 439 y2 = pCurBox->y2; 440 441 do { 442 if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { 443 return curStart; 444 } 445 pPrevBox++; 446 pCurBox++; 447 numRects--; 448 } while (numRects); 449 450 /* 451 * The bands may be merged, so set the bottom y of each box 452 * in the previous band to the bottom y of the current band. 453 */ 454 numRects = curStart - prevStart; 455 pReg->data->numRects -= numRects; 456 do { 457 pPrevBox--; 458 pPrevBox->y2 = y2; 459 numRects--; 460 } while (numRects); 461 return prevStart; 462} 463 464/* Quicky macro to avoid trivial reject procedure calls to RegionCoalesce */ 465 466#define Coalesce(newReg, prevBand, curBand) \ 467 if (curBand - prevBand == newReg->data->numRects - curBand) { \ 468 prevBand = RegionCoalesce(newReg, prevBand, curBand); \ 469 } else { \ 470 prevBand = curBand; \ 471 } 472 473/*- 474 *----------------------------------------------------------------------- 475 * RegionAppendNonO -- 476 * Handle a non-overlapping band for the union and subtract operations. 477 * Just adds the (top/bottom-clipped) rectangles into the region. 478 * Doesn't have to check for subsumption or anything. 479 * 480 * Results: 481 * None. 482 * 483 * Side Effects: 484 * pReg->data->numRects is incremented and the rectangles overwritten 485 * with the rectangles we're passed. 486 * 487 *----------------------------------------------------------------------- 488 */ 489 490_X_INLINE static Bool 491RegionAppendNonO(RegionPtr pReg, BoxPtr r, BoxPtr rEnd, int y1, int y2) 492{ 493 BoxPtr pNextRect; 494 int newRects; 495 496 newRects = rEnd - r; 497 498 assert(y1 < y2); 499 assert(newRects != 0); 500 501 /* Make sure we have enough space for all rectangles to be added */ 502 RECTALLOC(pReg, newRects); 503 pNextRect = RegionTop(pReg); 504 pReg->data->numRects += newRects; 505 do { 506 assert(r->x1 < r->x2); 507 ADDRECT(pNextRect, r->x1, y1, r->x2, y2); 508 r++; 509 } while (r != rEnd); 510 511 return TRUE; 512} 513 514#define FindBand(r, rBandEnd, rEnd, ry1) \ 515{ \ 516 ry1 = r->y1; \ 517 rBandEnd = r+1; \ 518 while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \ 519 rBandEnd++; \ 520 } \ 521} 522 523#define AppendRegions(newReg, r, rEnd) \ 524{ \ 525 int newRects; \ 526 if ((newRects = rEnd - r)) { \ 527 RECTALLOC(newReg, newRects); \ 528 memmove((char *)RegionTop(newReg),(char *)r, \ 529 newRects * sizeof(BoxRec)); \ 530 newReg->data->numRects += newRects; \ 531 } \ 532} 533 534/*- 535 *----------------------------------------------------------------------- 536 * RegionOp -- 537 * Apply an operation to two regions. Called by RegionUnion, RegionInverse, 538 * RegionSubtract, RegionIntersect.... Both regions MUST have at least one 539 * rectangle, and cannot be the same object. 540 * 541 * Results: 542 * TRUE if successful. 543 * 544 * Side Effects: 545 * The new region is overwritten. 546 * pOverlap set to TRUE if overlapFunc ever returns TRUE. 547 * 548 * Notes: 549 * The idea behind this function is to view the two regions as sets. 550 * Together they cover a rectangle of area that this function divides 551 * into horizontal bands where points are covered only by one region 552 * or by both. For the first case, the nonOverlapFunc is called with 553 * each the band and the band's upper and lower extents. For the 554 * second, the overlapFunc is called to process the entire band. It 555 * is responsible for clipping the rectangles in the band, though 556 * this function provides the boundaries. 557 * At the end of each band, the new region is coalesced, if possible, 558 * to reduce the number of rectangles in the region. 559 * 560 *----------------------------------------------------------------------- 561 */ 562 563typedef Bool (*OverlapProcPtr) (RegionPtr pReg, 564 BoxPtr r1, 565 BoxPtr r1End, 566 BoxPtr r2, 567 BoxPtr r2End, 568 short y1, short y2, Bool *pOverlap); 569 570static Bool 571RegionOp(RegionPtr newReg, /* Place to store result */ 572 RegionPtr reg1, /* First region in operation */ 573 RegionPtr reg2, /* 2d region in operation */ 574 OverlapProcPtr overlapFunc, /* Function to call for over- 575 * lapping bands */ 576 Bool appendNon1, /* Append non-overlapping bands */ 577 /* in region 1 ? */ 578 Bool appendNon2, /* Append non-overlapping bands */ 579 /* in region 2 ? */ 580 Bool *pOverlap) 581{ 582 BoxPtr r1; /* Pointer into first region */ 583 BoxPtr r2; /* Pointer into 2d region */ 584 BoxPtr r1End; /* End of 1st region */ 585 BoxPtr r2End; /* End of 2d region */ 586 short ybot; /* Bottom of intersection */ 587 short ytop; /* Top of intersection */ 588 RegDataPtr oldData; /* Old data for newReg */ 589 int prevBand; /* Index of start of 590 * previous band in newReg */ 591 int curBand; /* Index of start of current 592 * band in newReg */ 593 BoxPtr r1BandEnd; /* End of current band in r1 */ 594 BoxPtr r2BandEnd; /* End of current band in r2 */ 595 short top; /* Top of non-overlapping band */ 596 short bot; /* Bottom of non-overlapping band */ 597 int r1y1; /* Temps for r1->y1 and r2->y1 */ 598 int r2y1; 599 int newSize; 600 int numRects; 601 602 /* 603 * Break any region computed from a broken region 604 */ 605 if (RegionNar(reg1) || RegionNar(reg2)) 606 return RegionBreak(newReg); 607 608 /* 609 * Initialization: 610 * set r1, r2, r1End and r2End appropriately, save the rectangles 611 * of the destination region until the end in case it's one of 612 * the two source regions, then mark the "new" region empty, allocating 613 * another array of rectangles for it to use. 614 */ 615 616 r1 = RegionRects(reg1); 617 newSize = RegionNumRects(reg1); 618 r1End = r1 + newSize; 619 numRects = RegionNumRects(reg2); 620 r2 = RegionRects(reg2); 621 r2End = r2 + numRects; 622 assert(r1 != r1End); 623 assert(r2 != r2End); 624 625 oldData = NULL; 626 if (((newReg == reg1) && (newSize > 1)) || 627 ((newReg == reg2) && (numRects > 1))) { 628 oldData = newReg->data; 629 newReg->data = &RegionEmptyData; 630 } 631 /* guess at new size */ 632 if (numRects > newSize) 633 newSize = numRects; 634 newSize <<= 1; 635 if (!newReg->data) 636 newReg->data = &RegionEmptyData; 637 else if (newReg->data->size) 638 newReg->data->numRects = 0; 639 if (newSize > newReg->data->size) 640 if (!RegionRectAlloc(newReg, newSize)) 641 return FALSE; 642 643 /* 644 * Initialize ybot. 645 * In the upcoming loop, ybot and ytop serve different functions depending 646 * on whether the band being handled is an overlapping or non-overlapping 647 * band. 648 * In the case of a non-overlapping band (only one of the regions 649 * has points in the band), ybot is the bottom of the most recent 650 * intersection and thus clips the top of the rectangles in that band. 651 * ytop is the top of the next intersection between the two regions and 652 * serves to clip the bottom of the rectangles in the current band. 653 * For an overlapping band (where the two regions intersect), ytop clips 654 * the top of the rectangles of both regions and ybot clips the bottoms. 655 */ 656 657 ybot = min(r1->y1, r2->y1); 658 659 /* 660 * prevBand serves to mark the start of the previous band so rectangles 661 * can be coalesced into larger rectangles. qv. RegionCoalesce, above. 662 * In the beginning, there is no previous band, so prevBand == curBand 663 * (curBand is set later on, of course, but the first band will always 664 * start at index 0). prevBand and curBand must be indices because of 665 * the possible expansion, and resultant moving, of the new region's 666 * array of rectangles. 667 */ 668 prevBand = 0; 669 670 do { 671 /* 672 * This algorithm proceeds one source-band (as opposed to a 673 * destination band, which is determined by where the two regions 674 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the 675 * rectangle after the last one in the current band for their 676 * respective regions. 677 */ 678 assert(r1 != r1End); 679 assert(r2 != r2End); 680 681 FindBand(r1, r1BandEnd, r1End, r1y1); 682 FindBand(r2, r2BandEnd, r2End, r2y1); 683 684 /* 685 * First handle the band that doesn't intersect, if any. 686 * 687 * Note that attention is restricted to one band in the 688 * non-intersecting region at once, so if a region has n 689 * bands between the current position and the next place it overlaps 690 * the other, this entire loop will be passed through n times. 691 */ 692 if (r1y1 < r2y1) { 693 if (appendNon1) { 694 top = max(r1y1, ybot); 695 bot = min(r1->y2, r2y1); 696 if (top != bot) { 697 curBand = newReg->data->numRects; 698 RegionAppendNonO(newReg, r1, r1BandEnd, top, bot); 699 Coalesce(newReg, prevBand, curBand); 700 } 701 } 702 ytop = r2y1; 703 } 704 else if (r2y1 < r1y1) { 705 if (appendNon2) { 706 top = max(r2y1, ybot); 707 bot = min(r2->y2, r1y1); 708 if (top != bot) { 709 curBand = newReg->data->numRects; 710 RegionAppendNonO(newReg, r2, r2BandEnd, top, bot); 711 Coalesce(newReg, prevBand, curBand); 712 } 713 } 714 ytop = r1y1; 715 } 716 else { 717 ytop = r1y1; 718 } 719 720 /* 721 * Now see if we've hit an intersecting band. The two bands only 722 * intersect if ybot > ytop 723 */ 724 ybot = min(r1->y2, r2->y2); 725 if (ybot > ytop) { 726 curBand = newReg->data->numRects; 727 (*overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, 728 pOverlap); 729 Coalesce(newReg, prevBand, curBand); 730 } 731 732 /* 733 * If we've finished with a band (y2 == ybot) we skip forward 734 * in the region to the next band. 735 */ 736 if (r1->y2 == ybot) 737 r1 = r1BandEnd; 738 if (r2->y2 == ybot) 739 r2 = r2BandEnd; 740 741 } while (r1 != r1End && r2 != r2End); 742 743 /* 744 * Deal with whichever region (if any) still has rectangles left. 745 * 746 * We only need to worry about banding and coalescing for the very first 747 * band left. After that, we can just group all remaining boxes, 748 * regardless of how many bands, into one final append to the list. 749 */ 750 751 if ((r1 != r1End) && appendNon1) { 752 /* Do first nonOverlap1Func call, which may be able to coalesce */ 753 FindBand(r1, r1BandEnd, r1End, r1y1); 754 curBand = newReg->data->numRects; 755 RegionAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2); 756 Coalesce(newReg, prevBand, curBand); 757 /* Just append the rest of the boxes */ 758 AppendRegions(newReg, r1BandEnd, r1End); 759 760 } 761 else if ((r2 != r2End) && appendNon2) { 762 /* Do first nonOverlap2Func call, which may be able to coalesce */ 763 FindBand(r2, r2BandEnd, r2End, r2y1); 764 curBand = newReg->data->numRects; 765 RegionAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2); 766 Coalesce(newReg, prevBand, curBand); 767 /* Append rest of boxes */ 768 AppendRegions(newReg, r2BandEnd, r2End); 769 } 770 771 free(oldData); 772 773 if (!(numRects = newReg->data->numRects)) { 774 xfreeData(newReg); 775 newReg->data = &RegionEmptyData; 776 } 777 else if (numRects == 1) { 778 newReg->extents = *RegionBoxptr(newReg); 779 xfreeData(newReg); 780 newReg->data = NULL; 781 } 782 else { 783 DOWNSIZE(newReg, numRects); 784 } 785 786 return TRUE; 787} 788 789/*- 790 *----------------------------------------------------------------------- 791 * RegionSetExtents -- 792 * Reset the extents of a region to what they should be. Called by 793 * Subtract and Intersect as they can't figure it out along the 794 * way or do so easily, as Union can. 795 * 796 * Results: 797 * None. 798 * 799 * Side Effects: 800 * The region's 'extents' structure is overwritten. 801 * 802 *----------------------------------------------------------------------- 803 */ 804static void 805RegionSetExtents(RegionPtr pReg) 806{ 807 BoxPtr pBox, pBoxEnd; 808 809 if (!pReg->data) 810 return; 811 if (!pReg->data->size) { 812 pReg->extents.x2 = pReg->extents.x1; 813 pReg->extents.y2 = pReg->extents.y1; 814 return; 815 } 816 817 pBox = RegionBoxptr(pReg); 818 pBoxEnd = RegionEnd(pReg); 819 820 /* 821 * Since pBox is the first rectangle in the region, it must have the 822 * smallest y1 and since pBoxEnd is the last rectangle in the region, 823 * it must have the largest y2, because of banding. Initialize x1 and 824 * x2 from pBox and pBoxEnd, resp., as good things to initialize them 825 * to... 826 */ 827 pReg->extents.x1 = pBox->x1; 828 pReg->extents.y1 = pBox->y1; 829 pReg->extents.x2 = pBoxEnd->x2; 830 pReg->extents.y2 = pBoxEnd->y2; 831 832 assert(pReg->extents.y1 < pReg->extents.y2); 833 while (pBox <= pBoxEnd) { 834 if (pBox->x1 < pReg->extents.x1) 835 pReg->extents.x1 = pBox->x1; 836 if (pBox->x2 > pReg->extents.x2) 837 pReg->extents.x2 = pBox->x2; 838 pBox++; 839 }; 840 841 assert(pReg->extents.x1 < pReg->extents.x2); 842} 843 844/*====================================================================== 845 * Region Intersection 846 *====================================================================*/ 847/*- 848 *----------------------------------------------------------------------- 849 * RegionIntersectO -- 850 * Handle an overlapping band for RegionIntersect. 851 * 852 * Results: 853 * TRUE if successful. 854 * 855 * Side Effects: 856 * Rectangles may be added to the region. 857 * 858 *----------------------------------------------------------------------- 859 */ 860 /*ARGSUSED*/ 861#define MERGERECT(r) \ 862{ \ 863 if (r->x1 <= x2) { \ 864 /* Merge with current rectangle */ \ 865 if (r->x1 < x2) *pOverlap = TRUE; \ 866 if (x2 < r->x2) x2 = r->x2; \ 867 } else { \ 868 /* Add current rectangle, start new one */ \ 869 NEWRECT(pReg, pNextRect, x1, y1, x2, y2); \ 870 x1 = r->x1; \ 871 x2 = r->x2; \ 872 } \ 873 r++; \ 874} 875/*====================================================================== 876 * Region Union 877 *====================================================================*/ 878/*- 879 *----------------------------------------------------------------------- 880 * RegionUnionO -- 881 * Handle an overlapping band for the union operation. Picks the 882 * left-most rectangle each time and merges it into the region. 883 * 884 * Results: 885 * TRUE if successful. 886 * 887 * Side Effects: 888 * pReg is overwritten. 889 * pOverlap is set to TRUE if any boxes overlap. 890 * 891 *----------------------------------------------------------------------- 892 */ 893 static Bool 894RegionUnionO(RegionPtr pReg, 895 BoxPtr r1, 896 BoxPtr r1End, 897 BoxPtr r2, BoxPtr r2End, short y1, short y2, Bool *pOverlap) 898{ 899 BoxPtr pNextRect; 900 int x1; /* left and right side of current union */ 901 int x2; 902 903 assert(y1 < y2); 904 assert(r1 != r1End); 905 assert(r2 != r2End); 906 907 pNextRect = RegionTop(pReg); 908 909 /* Start off current rectangle */ 910 if (r1->x1 < r2->x1) { 911 x1 = r1->x1; 912 x2 = r1->x2; 913 r1++; 914 } 915 else { 916 x1 = r2->x1; 917 x2 = r2->x2; 918 r2++; 919 } 920 while (r1 != r1End && r2 != r2End) { 921 if (r1->x1 < r2->x1) 922 MERGERECT(r1) 923 else 924 MERGERECT(r2); 925 } 926 927 /* Finish off whoever (if any) is left */ 928 if (r1 != r1End) { 929 do { 930 MERGERECT(r1); 931 } while (r1 != r1End); 932 } 933 else if (r2 != r2End) { 934 do { 935 MERGERECT(r2); 936 } while (r2 != r2End); 937 } 938 939 /* Add current rectangle */ 940 NEWRECT(pReg, pNextRect, x1, y1, x2, y2); 941 942 return TRUE; 943} 944 945/*====================================================================== 946 * Batch Rectangle Union 947 *====================================================================*/ 948 949/*- 950 *----------------------------------------------------------------------- 951 * RegionAppend -- 952 * 953 * "Append" the rgn rectangles onto the end of dstrgn, maintaining 954 * knowledge of YX-banding when it's easy. Otherwise, dstrgn just 955 * becomes a non-y-x-banded random collection of rectangles, and not 956 * yet a true region. After a sequence of appends, the caller must 957 * call RegionValidate to ensure that a valid region is constructed. 958 * 959 * Results: 960 * TRUE if successful. 961 * 962 * Side Effects: 963 * dstrgn is modified if rgn has rectangles. 964 * 965 */ 966Bool 967RegionAppend(RegionPtr dstrgn, RegionPtr rgn) 968{ 969 int numRects, dnumRects, size; 970 BoxPtr new, old; 971 Bool prepend; 972 973 if (RegionNar(rgn)) 974 return RegionBreak(dstrgn); 975 976 if (!rgn->data && (dstrgn->data == &RegionEmptyData)) { 977 dstrgn->extents = rgn->extents; 978 dstrgn->data = NULL; 979 return TRUE; 980 } 981 982 numRects = RegionNumRects(rgn); 983 if (!numRects) 984 return TRUE; 985 prepend = FALSE; 986 size = numRects; 987 dnumRects = RegionNumRects(dstrgn); 988 if (!dnumRects && (size < 200)) 989 size = 200; /* XXX pick numbers out of a hat */ 990 RECTALLOC(dstrgn, size); 991 old = RegionRects(rgn); 992 if (!dnumRects) 993 dstrgn->extents = rgn->extents; 994 else if (dstrgn->extents.x2 > dstrgn->extents.x1) { 995 BoxPtr first, last; 996 997 first = old; 998 last = RegionBoxptr(dstrgn) + (dnumRects - 1); 999 if ((first->y1 > last->y2) || 1000 ((first->y1 == last->y1) && (first->y2 == last->y2) && 1001 (first->x1 > last->x2))) { 1002 if (rgn->extents.x1 < dstrgn->extents.x1) 1003 dstrgn->extents.x1 = rgn->extents.x1; 1004 if (rgn->extents.x2 > dstrgn->extents.x2) 1005 dstrgn->extents.x2 = rgn->extents.x2; 1006 dstrgn->extents.y2 = rgn->extents.y2; 1007 } 1008 else { 1009 first = RegionBoxptr(dstrgn); 1010 last = old + (numRects - 1); 1011 if ((first->y1 > last->y2) || 1012 ((first->y1 == last->y1) && (first->y2 == last->y2) && 1013 (first->x1 > last->x2))) { 1014 prepend = TRUE; 1015 if (rgn->extents.x1 < dstrgn->extents.x1) 1016 dstrgn->extents.x1 = rgn->extents.x1; 1017 if (rgn->extents.x2 > dstrgn->extents.x2) 1018 dstrgn->extents.x2 = rgn->extents.x2; 1019 dstrgn->extents.y1 = rgn->extents.y1; 1020 } 1021 else 1022 dstrgn->extents.x2 = dstrgn->extents.x1; 1023 } 1024 } 1025 if (prepend) { 1026 new = RegionBox(dstrgn, numRects); 1027 if (dnumRects == 1) 1028 *new = *RegionBoxptr(dstrgn); 1029 else 1030 memmove((char *) new, (char *) RegionBoxptr(dstrgn), 1031 dnumRects * sizeof(BoxRec)); 1032 new = RegionBoxptr(dstrgn); 1033 } 1034 else 1035 new = RegionBoxptr(dstrgn) + dnumRects; 1036 if (numRects == 1) 1037 *new = *old; 1038 else 1039 memmove((char *) new, (char *) old, numRects * sizeof(BoxRec)); 1040 dstrgn->data->numRects += numRects; 1041 return TRUE; 1042} 1043 1044#define ExchangeRects(a, b) \ 1045{ \ 1046 BoxRec t; \ 1047 t = rects[a]; \ 1048 rects[a] = rects[b]; \ 1049 rects[b] = t; \ 1050} 1051 1052static void 1053QuickSortRects(BoxRec rects[], int numRects) 1054{ 1055 int y1; 1056 int x1; 1057 int i, j; 1058 BoxPtr r; 1059 1060 /* Always called with numRects > 1 */ 1061 1062 do { 1063 if (numRects == 2) { 1064 if (rects[0].y1 > rects[1].y1 || 1065 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1)) 1066 ExchangeRects(0, 1); 1067 return; 1068 } 1069 1070 /* Choose partition element, stick in location 0 */ 1071 ExchangeRects(0, numRects >> 1); 1072 y1 = rects[0].y1; 1073 x1 = rects[0].x1; 1074 1075 /* Partition array */ 1076 i = 0; 1077 j = numRects; 1078 do { 1079 r = &(rects[i]); 1080 do { 1081 r++; 1082 i++; 1083 } while (i != numRects && 1084 (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1))); 1085 r = &(rects[j]); 1086 do { 1087 r--; 1088 j--; 1089 } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1)); 1090 if (i < j) 1091 ExchangeRects(i, j); 1092 } while (i < j); 1093 1094 /* Move partition element back to middle */ 1095 ExchangeRects(0, j); 1096 1097 /* Recurse */ 1098 if (numRects - j - 1 > 1) 1099 QuickSortRects(&rects[j + 1], numRects - j - 1); 1100 numRects = j; 1101 } while (numRects > 1); 1102} 1103 1104/*- 1105 *----------------------------------------------------------------------- 1106 * RegionValidate -- 1107 * 1108 * Take a ``region'' which is a non-y-x-banded random collection of 1109 * rectangles, and compute a nice region which is the union of all the 1110 * rectangles. 1111 * 1112 * Results: 1113 * TRUE if successful. 1114 * 1115 * Side Effects: 1116 * The passed-in ``region'' may be modified. 1117 * pOverlap set to TRUE if any rectangles overlapped, else FALSE; 1118 * 1119 * Strategy: 1120 * Step 1. Sort the rectangles into ascending order with primary key y1 1121 * and secondary key x1. 1122 * 1123 * Step 2. Split the rectangles into the minimum number of proper y-x 1124 * banded regions. This may require horizontally merging 1125 * rectangles, and vertically coalescing bands. With any luck, 1126 * this step in an identity transformation (ala the Box widget), 1127 * or a coalescing into 1 box (ala Menus). 1128 * 1129 * Step 3. Merge the separate regions down to a single region by calling 1130 * Union. Maximize the work each Union call does by using 1131 * a binary merge. 1132 * 1133 *----------------------------------------------------------------------- 1134 */ 1135 1136Bool 1137RegionValidate(RegionPtr badreg, Bool *pOverlap) 1138{ 1139 /* Descriptor for regions under construction in Step 2. */ 1140 typedef struct { 1141 RegionRec reg; 1142 int prevBand; 1143 int curBand; 1144 } RegionInfo; 1145 1146 int numRects; /* Original numRects for badreg */ 1147 RegionInfo *ri; /* Array of current regions */ 1148 int numRI; /* Number of entries used in ri */ 1149 int sizeRI; /* Number of entries available in ri */ 1150 int i; /* Index into rects */ 1151 int j; /* Index into ri */ 1152 RegionInfo *rit; /* &ri[j] */ 1153 RegionPtr reg; /* ri[j].reg */ 1154 BoxPtr box; /* Current box in rects */ 1155 BoxPtr riBox; /* Last box in ri[j].reg */ 1156 RegionPtr hreg; /* ri[j_half].reg */ 1157 Bool ret = TRUE; 1158 1159 *pOverlap = FALSE; 1160 if (!badreg->data) { 1161 good(badreg); 1162 return TRUE; 1163 } 1164 numRects = badreg->data->numRects; 1165 if (!numRects) { 1166 if (RegionNar(badreg)) 1167 return FALSE; 1168 good(badreg); 1169 return TRUE; 1170 } 1171 if (badreg->extents.x1 < badreg->extents.x2) { 1172 if ((numRects) == 1) { 1173 xfreeData(badreg); 1174 badreg->data = (RegDataPtr) NULL; 1175 } 1176 else { 1177 DOWNSIZE(badreg, numRects); 1178 } 1179 good(badreg); 1180 return TRUE; 1181 } 1182 1183 /* Step 1: Sort the rects array into ascending (y1, x1) order */ 1184 QuickSortRects(RegionBoxptr(badreg), numRects); 1185 1186 /* Step 2: Scatter the sorted array into the minimum number of regions */ 1187 1188 /* Set up the first region to be the first rectangle in badreg */ 1189 /* Note that step 2 code will never overflow the ri[0].reg rects array */ 1190 ri = (RegionInfo *) malloc(4 * sizeof(RegionInfo)); 1191 if (!ri) 1192 return RegionBreak(badreg); 1193 sizeRI = 4; 1194 numRI = 1; 1195 ri[0].prevBand = 0; 1196 ri[0].curBand = 0; 1197 ri[0].reg = *badreg; 1198 box = RegionBoxptr(&ri[0].reg); 1199 ri[0].reg.extents = *box; 1200 ri[0].reg.data->numRects = 1; 1201 1202 /* Now scatter rectangles into the minimum set of valid regions. If the 1203 next rectangle to be added to a region would force an existing rectangle 1204 in the region to be split up in order to maintain y-x banding, just 1205 forget it. Try the next region. If it doesn't fit cleanly into any 1206 region, make a new one. */ 1207 1208 for (i = numRects; --i > 0;) { 1209 box++; 1210 /* Look for a region to append box to */ 1211 for (j = numRI, rit = ri; --j >= 0; rit++) { 1212 reg = &rit->reg; 1213 riBox = RegionEnd(reg); 1214 1215 if (box->y1 == riBox->y1 && box->y2 == riBox->y2) { 1216 /* box is in same band as riBox. Merge or append it */ 1217 if (box->x1 <= riBox->x2) { 1218 /* Merge it with riBox */ 1219 if (box->x1 < riBox->x2) 1220 *pOverlap = TRUE; 1221 if (box->x2 > riBox->x2) 1222 riBox->x2 = box->x2; 1223 } 1224 else { 1225 RECTALLOC_BAIL(reg, 1, bail); 1226 *RegionTop(reg) = *box; 1227 reg->data->numRects++; 1228 } 1229 goto NextRect; /* So sue me */ 1230 } 1231 else if (box->y1 >= riBox->y2) { 1232 /* Put box into new band */ 1233 if (reg->extents.x2 < riBox->x2) 1234 reg->extents.x2 = riBox->x2; 1235 if (reg->extents.x1 > box->x1) 1236 reg->extents.x1 = box->x1; 1237 Coalesce(reg, rit->prevBand, rit->curBand); 1238 rit->curBand = reg->data->numRects; 1239 RECTALLOC_BAIL(reg, 1, bail); 1240 *RegionTop(reg) = *box; 1241 reg->data->numRects++; 1242 goto NextRect; 1243 } 1244 /* Well, this region was inappropriate. Try the next one. */ 1245 } /* for j */ 1246 1247 /* Uh-oh. No regions were appropriate. Create a new one. */ 1248 if (sizeRI == numRI) { 1249 /* Oops, allocate space for new region information */ 1250 sizeRI <<= 1; 1251 rit = (RegionInfo *) reallocarray(ri, sizeRI, sizeof(RegionInfo)); 1252 if (!rit) 1253 goto bail; 1254 ri = rit; 1255 rit = &ri[numRI]; 1256 } 1257 numRI++; 1258 rit->prevBand = 0; 1259 rit->curBand = 0; 1260 rit->reg.extents = *box; 1261 rit->reg.data = NULL; 1262 if (!RegionRectAlloc(&rit->reg, (i + numRI) / numRI)) /* MUST force allocation */ 1263 goto bail; 1264 NextRect:; 1265 } /* for i */ 1266 1267 /* Make a final pass over each region in order to Coalesce and set 1268 extents.x2 and extents.y2 */ 1269 1270 for (j = numRI, rit = ri; --j >= 0; rit++) { 1271 reg = &rit->reg; 1272 riBox = RegionEnd(reg); 1273 reg->extents.y2 = riBox->y2; 1274 if (reg->extents.x2 < riBox->x2) 1275 reg->extents.x2 = riBox->x2; 1276 Coalesce(reg, rit->prevBand, rit->curBand); 1277 if (reg->data->numRects == 1) { /* keep unions happy below */ 1278 xfreeData(reg); 1279 reg->data = NULL; 1280 } 1281 } 1282 1283 /* Step 3: Union all regions into a single region */ 1284 while (numRI > 1) { 1285 int half = numRI / 2; 1286 1287 for (j = numRI & 1; j < (half + (numRI & 1)); j++) { 1288 reg = &ri[j].reg; 1289 hreg = &ri[j + half].reg; 1290 if (!RegionOp(reg, reg, hreg, RegionUnionO, TRUE, TRUE, pOverlap)) 1291 ret = FALSE; 1292 if (hreg->extents.x1 < reg->extents.x1) 1293 reg->extents.x1 = hreg->extents.x1; 1294 if (hreg->extents.y1 < reg->extents.y1) 1295 reg->extents.y1 = hreg->extents.y1; 1296 if (hreg->extents.x2 > reg->extents.x2) 1297 reg->extents.x2 = hreg->extents.x2; 1298 if (hreg->extents.y2 > reg->extents.y2) 1299 reg->extents.y2 = hreg->extents.y2; 1300 xfreeData(hreg); 1301 } 1302 numRI -= half; 1303 } 1304 *badreg = ri[0].reg; 1305 free(ri); 1306 good(badreg); 1307 return ret; 1308 bail: 1309 for (i = 0; i < numRI; i++) 1310 xfreeData(&ri[i].reg); 1311 free(ri); 1312 return RegionBreak(badreg); 1313} 1314 1315RegionPtr 1316RegionFromRects(int nrects, xRectangle *prect, int ctype) 1317{ 1318 1319 RegionPtr pRgn; 1320 size_t rgnSize; 1321 RegDataPtr pData; 1322 BoxPtr pBox; 1323 int i; 1324 int x1, y1, x2, y2; 1325 1326 pRgn = RegionCreate(NullBox, 0); 1327 if (RegionNar(pRgn)) 1328 return pRgn; 1329 if (!nrects) 1330 return pRgn; 1331 if (nrects == 1) { 1332 x1 = prect->x; 1333 y1 = prect->y; 1334 if ((x2 = x1 + (int) prect->width) > MAXSHORT) 1335 x2 = MAXSHORT; 1336 if ((y2 = y1 + (int) prect->height) > MAXSHORT) 1337 y2 = MAXSHORT; 1338 if (x1 != x2 && y1 != y2) { 1339 pRgn->extents.x1 = x1; 1340 pRgn->extents.y1 = y1; 1341 pRgn->extents.x2 = x2; 1342 pRgn->extents.y2 = y2; 1343 pRgn->data = NULL; 1344 } 1345 return pRgn; 1346 } 1347 rgnSize = RegionSizeof(nrects); 1348 pData = (rgnSize > 0) ? malloc(rgnSize) : NULL; 1349 if (!pData) { 1350 RegionBreak(pRgn); 1351 return pRgn; 1352 } 1353 pBox = (BoxPtr) (pData + 1); 1354 for (i = nrects; --i >= 0; prect++) { 1355 x1 = prect->x; 1356 y1 = prect->y; 1357 if ((x2 = x1 + (int) prect->width) > MAXSHORT) 1358 x2 = MAXSHORT; 1359 if ((y2 = y1 + (int) prect->height) > MAXSHORT) 1360 y2 = MAXSHORT; 1361 if (x1 != x2 && y1 != y2) { 1362 pBox->x1 = x1; 1363 pBox->y1 = y1; 1364 pBox->x2 = x2; 1365 pBox->y2 = y2; 1366 pBox++; 1367 } 1368 } 1369 if (pBox != (BoxPtr) (pData + 1)) { 1370 pData->size = nrects; 1371 pData->numRects = pBox - (BoxPtr) (pData + 1); 1372 pRgn->data = pData; 1373 if (ctype != CT_YXBANDED) { 1374 Bool overlap; /* result ignored */ 1375 1376 pRgn->extents.x1 = pRgn->extents.x2 = 0; 1377 RegionValidate(pRgn, &overlap); 1378 } 1379 else 1380 RegionSetExtents(pRgn); 1381 good(pRgn); 1382 } 1383 else { 1384 free(pData); 1385 } 1386 return pRgn; 1387} 1388