← Back to branch summary

~brandontschaefer/+junk/break-x

« back to all changes in this revision

Viewing changes to dix/region.c

  • Committer: Brandon Schaefer
  • Date: 2014-09-30 19:38:40 UTC
  • Revision ID: brandon.schaefer@canonical.com-20140930193840-a65z6qk8ze02cgsb
* Init commit to back this up

Show diffs side-by-side

added added

removed removed

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