src/gui/painting/qregion_qws.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtGui module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 // XXX - add appropriate friendship relationships
  43 #define private public
  44 #include "qregion.h"
  45 #undef private
  46 #include "qpainterpath.h"
  47 #include "qpolygon.h"
  48 #include "qbuffer.h"
  49 #include "qimage.h"
  50 #include <qdebug.h>
  51 #include "qbitmap.h"
  52 #include <stdlib.h>
  53 #include <qatomic.h>
  54 #include <qsemaphore.h>
  55
  56 QT_BEGIN_NAMESPACE
  57
  58 class QFastMutex
  59 {
  60     QAtomicInt contenders;
  61     QSemaphore semaphore;
  62 public:
  63     inline QFastMutex()
  64         : contenders(0), semaphore(0)
  65     { }
  66     inline void lock()
  67     {
  68         if (contenders.fetchAndAddAcquire(1) != 0) {
  69             semaphore.acquire();
  70             contenders.deref();
  71         }
  72     }
  73     inline bool tryLock()
  74     {
  75         return contenders.testAndSetAcquire(0, 1);
  76     }
  77     inline void unlock()
  78     {
  79         if (!contenders.testAndSetRelease(1, 0))
  80             semaphore.release();
  81     }
  82 };
  83
  84
  85 /*
  86  *  1 if r1 contains r2
  87  *  0 if r1 does not completely contain r2
  88  */
  89 #define CONTAINSCHECK(r1, r2) \
  90     ((r2).left() >= (r1).left() && (r2).right() <= (r1).right() && \
  91      (r2).top() >= (r1).top() && (r2).bottom() <= (r1).bottom())
  92
  93 /*
  94  *   clip region
  95  */
  96 struct QRegionPrivate : public QRegion::QRegionData {
  97     enum { Single, Vector } mode;
  98     int numRects;
  99     QVector<QRect> rects;
 100     QRect single;
 101     QRect extents;
 102     QRect innerRect;
 103     union {
 104         int innerArea;
 105         QRegionPrivate *next;
 106     };
 107
 108     inline void vector()
 109     {
 110         if(mode != Vector && numRects) {
 111             if(rects.size() < 1) rects.resize(1);
 112             rects[0] = single;
 113         }
 114         mode = Vector;
 115     }
 116
 117     inline QRegionPrivate() : mode(Single), numRects(0), innerArea(-1) {}
 118     inline QRegionPrivate(const QRect &r) : mode(Single) {
 119         numRects = 1;
 120 //        rects[0] = r;
 121         single = r;
 122         extents = r;
 123         innerRect = r;
 124         innerArea = r.width() * r.height();
 125     }
 126
 127     inline QRegionPrivate(const QRegionPrivate &r) {
 128         mode = r.mode;
 129         rects = r.rects;
 130         single = r.single;
 131         numRects = r.numRects;
 132         extents = r.extents;
 133         innerRect = r.innerRect;
 134         innerArea = r.innerArea;
 135     }
 136
 137     inline QRegionPrivate &operator=(const QRegionPrivate &r) {
 138         mode = r.mode;
 139         rects = r.rects;
 140         single = r.single;
 141         numRects = r.numRects;
 142         extents = r.extents;
 143         innerRect = r.innerRect;
 144         innerArea = r.innerArea;
 145         return *this;
 146     }
 147
 148     /*
 149      * Returns true if r is guaranteed to be fully contained in this region.
 150      * A false return value does not guarantee the opposite.
 151      */
 152     inline bool contains(const QRegionPrivate &r) const {
 153         const QRect &r1 = innerRect;
 154         const QRect &r2 = r.extents;
 155         return CONTAINSCHECK(r1, r2);
 156     }
 157
 158     inline void updateInnerRect(const QRect &rect) {
 159         const int area = rect.width() * rect.height();
 160         if (area > innerArea) {
 161             innerArea = area;
 162             innerRect = rect;
 163         }
 164     }
 165
 166     void append(const QRegionPrivate *r);
 167     void prepend(const QRegionPrivate *r);
 168     inline bool canAppend(const QRegionPrivate *r) const;
 169     inline bool canPrepend(const QRegionPrivate *r) const;
 170 };
 171
 172 static QRegionPrivate *qt_nextRegionPtr = 0;
 173 static QFastMutex qt_nextRegionLock;
 174
 175 static QRegionPrivate *qt_allocRegionMemory()
 176 {
 177     QRegionPrivate *rv = 0;
 178     qt_nextRegionLock.lock();
 179
 180     if(qt_nextRegionPtr) {
 181         rv = qt_nextRegionPtr;
 182         qt_nextRegionPtr = rv->next;
 183     } else {
 184         qt_nextRegionPtr =
 185             (QRegionPrivate *)malloc(256 * sizeof(QRegionPrivate));
 186         for(int ii = 0; ii < 256; ++ii) {
 187             if(ii == 255) {
 188                 qt_nextRegionPtr[ii].next = 0;
 189             } else {
 190                 qt_nextRegionPtr[ii].next = &qt_nextRegionPtr[ii + 1];
 191             }
 192         }
 193
 194         rv = qt_nextRegionPtr;
 195         qt_nextRegionPtr = rv->next;
 196     }
 197
 198     qt_nextRegionLock.unlock();
 199     return rv;
 200 }
 201
 202 static void qt_freeRegionMemory(QRegionPrivate *rp)
 203 {
 204     qt_nextRegionLock.lock();
 205     rp->next = qt_nextRegionPtr;
 206     qt_nextRegionPtr = rp;
 207     qt_nextRegionLock.unlock();
 208 }
 209
 210 static QRegionPrivate *qt_allocRegion()
 211 {
 212     QRegionPrivate *mem = qt_allocRegionMemory();
 213     return new (mem) QRegionPrivate;
 214 }
 215
 216 static QRegionPrivate *qt_allocRegion(const QRect &r)
 217 {
 218     QRegionPrivate *mem = qt_allocRegionMemory();
 219     return new (mem) QRegionPrivate(r);
 220 }
 221
 222 static QRegionPrivate *qt_allocRegion(const QRegionPrivate &r)
 223 {
 224     QRegionPrivate *mem = qt_allocRegionMemory();
 225     return new (mem) QRegionPrivate(r);
 226 }
 227
 228 void qt_freeRegion(QRegionPrivate *rp)
 229 {
 230     rp->~QRegionPrivate();
 231     qt_freeRegionMemory(rp);
 232 //    delete rp;
 233 }
 234
 235 static inline bool isEmptyHelper(const QRegionPrivate *preg)
 236 {
 237     return !preg || preg->numRects == 0;
 238 }
 239
 240 void QRegionPrivate::append(const QRegionPrivate *r)
 241 {
 242     Q_ASSERT(!isEmptyHelper(r));
 243
 244     vector();
 245     QRect *destRect = rects.data() + numRects;
 246     const QRect *srcRect = (r->mode==Vector)?r->rects.constData():&r->single;
 247     int numAppend = r->numRects;
 248
 249     // test for merge in x direction
 250     {
 251         const QRect *rFirst = srcRect;
 252         QRect *myLast = rects.data() + (numRects - 1);
 253         if (rFirst->top() == myLast->top()
 254             && rFirst->height() == myLast->height()
 255             && rFirst->left() == (myLast->right() + 1))
 256         {
 257             myLast->setWidth(myLast->width() + rFirst->width());
 258             updateInnerRect(*myLast);
 259             ++srcRect;
 260             --numAppend;
 261         }
 262     }
 263
 264     // append rectangles
 265     const int newNumRects = numRects + numAppend;
 266     if (newNumRects > rects.size()) {
 267         rects.resize(newNumRects);
 268         destRect = rects.data() + numRects;
 269     }
 270     memcpy(destRect, srcRect, numAppend * sizeof(QRect));
 271
 272     // update inner rectangle
 273     if (innerArea < r->innerArea) {
 274         innerArea = r->innerArea;
 275         innerRect = r->innerRect;
 276     }
 277
 278     // update extents
 279     destRect = &extents;
 280     srcRect = &r->extents;
 281     extents.setCoords(qMin(destRect->left(), srcRect->left()),
 282                       qMin(destRect->top(), srcRect->top()),
 283                       qMax(destRect->right(), srcRect->right()),
 284                       qMax(destRect->bottom(), srcRect->bottom()));
 285
 286     numRects = newNumRects;
 287 }
 288
 289 void QRegionPrivate::prepend(const QRegionPrivate *r)
 290 {
 291 #if 1
 292     Q_UNUSED(r);
 293 #else
 294     // XXX ak: does not respect vectorization of region
 295
 296     Q_ASSERT(!isEmpty(r));
 297
 298     // move existing rectangles
 299     memmove(rects.data() + r->numRects, rects.constData(),
 300             numRects * sizeof(QRect));
 301
 302     // prepend new rectangles
 303     memcpy(rects.data(), r->rects.constData(), r->numRects * sizeof(QRect));
 304
 305     // update inner rectangle
 306     if (innerArea < r->innerArea) {
 307         innerArea = r->innerArea;
 308         innerRect = r->innerRect;
 309     }
 310
 311     // update extents
 312     destRect = &extents;
 313     srcRect = &r->extents;
 314     extents.setCoords(qMin(destRect->left(), srcRect->left()),
 315                       qMin(destRect->top(), srcRect->top()),
 316                       qMax(destRect->right(), srcRect->right()),
 317                       qMax(destRect->bottom(), srcRect->bottom()));
 318
 319     numRects = newNumRects;
 320 #endif
 321 }
 322
 323 bool QRegionPrivate::canAppend(const QRegionPrivate *r) const
 324 {
 325     Q_ASSERT(!isEmptyHelper(r));
 326
 327     const QRect *rFirst = (r->mode==Vector)?r->rects.constData():&r->single;
 328     const QRect *myLast = (mode==Vector)?(rects.constData() + (numRects - 1)):&single;
 329     // XXX: possible improvements:
 330     //   - nFirst->top() == myLast->bottom() + 1, must possibly merge bands
 331     if (rFirst->top() > (myLast->bottom() + 1)
 332         || (rFirst->top() == myLast->top()
 333             && rFirst->height() == myLast->height()
 334             && rFirst->left() > myLast->right()))
 335     {
 336         return true;
 337     }
 338
 339     return false;
 340 }
 341
 342 bool QRegionPrivate::canPrepend(const QRegionPrivate *r) const
 343 {
 344 #if 1
 345     Q_UNUSED(r);
 346     return false;
 347 #else
 348     return r->canAppend(this);
 349 #endif
 350 }
 351
 352 #if defined(Q_WS_X11)
 353 QT_BEGIN_INCLUDE_NAMESPACE
 354 # include "qregion_x11.cpp"
 355 QT_END_INCLUDE_NAMESPACE
 356 #elif defined(Q_WS_MAC)
 357 QT_BEGIN_INCLUDE_NAMESPACE
 358 # include "qregion_mac.cpp"
 359 QT_END_INCLUDE_NAMESPACE
 360 #elif defined(Q_WS_QWS)
 361 static QRegionPrivate qrp;
 362 QRegion::QRegionData QRegion::shared_empty = {Q_BASIC_ATOMIC_INITIALIZER(1), &qrp};
 363 #endif
 364
 365 typedef void (*OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
 366                             register const QRect *r2, const QRect *r2End, register int y1, register int y2);
 367 typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
 368                                register int y1, register int y2);
 369
 370 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
 371 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
 372 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
 373                        OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
 374                        NonOverlapFunc nonOverlap2Func);
 375
 376 #define RectangleOut 0
 377 #define RectangleIn 1
 378 #define RectanglePart 2
 379 #define EvenOddRule 0
 380 #define WindingRule 1
 381
 382 // START OF region.h extract
 383 /* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */
 384 /************************************************************************
 385
 386 Copyright (c) 1987  X Consortium
 387
 388 Permission is hereby granted, free of charge, to any person obtaining a copy
 389 of this software and associated documentation files (the "Software"), to deal
 390 in the Software without restriction, including without limitation the rights
 391 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 392 copies of the Software, and to permit persons to whom the Software is
 393 furnished to do so, subject to the following conditions:
 394
 395 The above copyright notice and this permission notice shall be included in
 396 all copies or substantial portions of the Software.
 397
 398 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 399 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 400 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 401 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 402 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 403 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 404
 405 Except as contained in this notice, the name of the X Consortium shall not be
 406 used in advertising or otherwise to promote the sale, use or other dealings
 407 in this Software without prior written authorization from the X Consortium.
 408
 409
 410 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
 411
 412                         All Rights Reserved
 413
 414 Permission to use, copy, modify, and distribute this software and its
 415 documentation for any purpose and without fee is hereby granted,
 416 provided that the above copyright notice appear in all copies and that
 417 both that copyright notice and this permission notice appear in
 418 supporting documentation, and that the name of Digital not be
 419 used in advertising or publicity pertaining to distribution of the
 420 software without specific, written prior permission.
 421
 422 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 423 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
 424 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
 425 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
 426 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 427 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 428 SOFTWARE.
 429
 430 ************************************************************************/
 431
 432 #ifndef _XREGION_H
 433 #define _XREGION_H
 434
 435 QT_BEGIN_INCLUDE_NAMESPACE
 436 #include <limits.h>
 437 QT_END_INCLUDE_NAMESPACE
 438
 439 /*  1 if two BOXs overlap.
 440  *  0 if two BOXs do not overlap.
 441  *  Remember, x2 and y2 are not in the region
 442  */
 443 #define EXTENTCHECK(r1, r2) \
 444         ((r1)->right() >= (r2)->left() && \
 445          (r1)->left() <= (r2)->right() && \
 446          (r1)->bottom() >= (r2)->top() && \
 447          (r1)->top() <= (r2)->bottom())
 448
 449 /*
 450  *  update region extents
 451  */
 452 #define EXTENTS(r,idRect){\
 453             if((r)->left() < (idRect)->extents.left())\
 454               (idRect)->extents.setLeft((r)->left());\
 455             if((r)->top() < (idRect)->extents.top())\
 456               (idRect)->extents.setTop((r)->top());\
 457             if((r)->right() > (idRect)->extents.right())\
 458               (idRect)->extents.setRight((r)->right());\
 459             if((r)->bottom() > (idRect)->extents.bottom())\
 460               (idRect)->extents.setBottom((r)->bottom());\
 461         }
 462
 463 /*
 464  *   Check to see if there is enough memory in the present region.
 465  */
 466 #define MEMCHECK(dest, rect, firstrect){\
 467         if ((dest).numRects >= ((dest).rects.size()-1)){\
 468           firstrect.resize(firstrect.size() * 2); \
 469           (rect) = (firstrect).data() + (dest).numRects;\
 470         }\
 471       }
 472
 473
 474 /*
 475  * number of points to buffer before sending them off
 476  * to scanlines(): Must be an even number
 477  */
 478 #define NUMPTSTOBUFFER 200
 479
 480 /*
 481  * used to allocate buffers for points and link
 482  * the buffers together
 483  */
 484 typedef struct _POINTBLOCK {
 485     QPoint pts[NUMPTSTOBUFFER];
 486     struct _POINTBLOCK *next;
 487 } POINTBLOCK;
 488
 489 #endif
 490 // END OF region.h extract
 491
 492 // START OF Region.c extract
 493 /* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */
 494 /************************************************************************
 495
 496 Copyright (c) 1987, 1988  X Consortium
 497
 498 Permission is hereby granted, free of charge, to any person obtaining a copy
 499 of this software and associated documentation files (the "Software"), to deal
 500 in the Software without restriction, including without limitation the rights
 501 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 502 copies of the Software, and to permit persons to whom the Software is
 503 furnished to do so, subject to the following conditions:
 504
 505 The above copyright notice and this permission notice shall be included in
 506 all copies or substantial portions of the Software.
 507
 508 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 509 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 510 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 511 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 512 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 513 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 514
 515 Except as contained in this notice, the name of the X Consortium shall not be
 516 used in advertising or otherwise to promote the sale, use or other dealings
 517 in this Software without prior written authorization from the X Consortium.
 518
 519
 520 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
 521
 522                         All Rights Reserved
 523
 524 Permission to use, copy, modify, and distribute this software and its
 525 documentation for any purpose and without fee is hereby granted,
 526 provided that the above copyright notice appear in all copies and that
 527 both that copyright notice and this permission notice appear in
 528 supporting documentation, and that the name of Digital not be
 529 used in advertising or publicity pertaining to distribution of the
 530 software without specific, written prior permission.
 531
 532 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 533 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
 534 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
 535 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
 536 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 537 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 538 SOFTWARE.
 539
 540 ************************************************************************/
 541 /*
 542  * The functions in this file implement the Region abstraction, similar to one
 543  * used in the X11 sample server. A Region is simply an area, as the name
 544  * implies, and is implemented as a "y-x-banded" array of rectangles. To
 545  * explain: Each Region is made up of a certain number of rectangles sorted
 546  * by y coordinate first, and then by x coordinate.
 547  *
 548  * Furthermore, the rectangles are banded such that every rectangle with a
 549  * given upper-left y coordinate (y1) will have the same lower-right y
 550  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
 551  * will span the entire vertical distance of the band. This means that some
 552  * areas that could be merged into a taller rectangle will be represented as
 553  * several shorter rectangles to account for shorter rectangles to its left
 554  * or right but within its "vertical scope".
 555  *
 556  * An added constraint on the rectangles is that they must cover as much
 557  * horizontal area as possible. E.g. no two rectangles in a band are allowed
 558  * to touch.
 559  *
 560  * Whenever possible, bands will be merged together to cover a greater vertical
 561  * distance (and thus reduce the number of rectangles). Two bands can be merged
 562  * only if the bottom of one touches the top of the other and they have
 563  * rectangles in the same places (of the same width, of course). This maintains
 564  * the y-x-banding that's so nice to have...
 565  */
 566 /* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
 567
 568 static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source,
 569                                 QRegionPrivate &dest)
 570 {
 571     if (!rect->width() || !rect->height())
 572         return;
 573
 574     QRegionPrivate region(*rect);
 575
 576     Q_ASSERT(EqualRegion(source, &dest));
 577     Q_ASSERT(!isEmptyHelper(&region));
 578
 579     if (dest.numRects == 0)
 580         dest = region;
 581     else if (dest.canAppend(&region))
 582         dest.append(&region);
 583     else
 584         UnionRegion(&region, source, dest);
 585 }
 586
 587 /*-
 588  *-----------------------------------------------------------------------
 589  * miSetExtents --
 590  *      Reset the extents and innerRect of a region to what they should be.
 591  *      Called by miSubtract and miIntersect b/c they can't figure it out
 592  *      along the way or do so easily, as miUnion can.
 593  *
 594  * Results:
 595  *      None.
 596  *
 597  * Side Effects:
 598  *      The region's 'extents' and 'innerRect' structure is overwritten.
 599  *
 600  *-----------------------------------------------------------------------
 601  */
 602 static void miSetExtents(QRegionPrivate &dest)
 603 {
 604     register const QRect *pBox,
 605                          *pBoxEnd;
 606     register QRect *pExtents;
 607
 608     dest.innerRect.setCoords(0, 0, -1, -1);
 609     dest.innerArea = -1;
 610     if (dest.numRects == 0) {
 611         dest.extents.setCoords(0, 0, 0, 0);
 612         return;
 613     }
 614
 615     pExtents = &dest.extents;
 616     pBox = (dest.mode==QRegionPrivate::Vector)?(dest.rects.constData()):(&dest.single);
 617     pBoxEnd = (dest.mode==QRegionPrivate::Vector)?(&pBox[dest.numRects - 1]):(&dest.single);
 618
 619     /*
 620      * Since pBox is the first rectangle in the region, it must have the
 621      * smallest y1 and since pBoxEnd is the last rectangle in the region,
 622      * it must have the largest y2, because of banding. Initialize x1 and
 623      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
 624      * to...
 625      */
 626     pExtents->setLeft(pBox->left());
 627     pExtents->setTop(pBox->top());
 628     pExtents->setRight(pBoxEnd->right());
 629     pExtents->setBottom(pBoxEnd->bottom());
 630
 631     Q_ASSERT(pExtents->top() <= pExtents->bottom());
 632     while (pBox <= pBoxEnd) {
 633         if (pBox->left() < pExtents->left())
 634             pExtents->setLeft(pBox->left());
 635         if (pBox->right() > pExtents->right())
 636             pExtents->setRight(pBox->right());
 637         dest.updateInnerRect(*pBox);
 638         ++pBox;
 639     }
 640     Q_ASSERT(pExtents->left() <= pExtents->right());
 641 }
 642
 643 /* TranslateRegion(pRegion, x, y)
 644    translates in place
 645    added by raymond
 646 */
 647
 648 static void OffsetRegion(register QRegionPrivate &region, register int x, register int y)
 649 {
 650     register int nbox;
 651     register QRect *pbox;
 652
 653     if(region.mode == QRegionPrivate::Single) {
 654         region.single.translate(x, y);
 655     } else {
 656         pbox = region.rects.data();
 657         nbox = region.numRects;
 658
 659         while (nbox--) {
 660             pbox->translate(x, y);
 661             ++pbox;
 662         }
 663     }
 664     region.extents.translate(x, y);
 665     region.innerRect.translate(x, y);
 666 }
 667
 668 /*======================================================================
 669  *          Region Intersection
 670  *====================================================================*/
 671 /*-
 672  *-----------------------------------------------------------------------
 673  * miIntersectO --
 674  *      Handle an overlapping band for miIntersect.
 675  *
 676  * Results:
 677  *      None.
 678  *
 679  * Side Effects:
 680  *      Rectangles may be added to the region.
 681  *
 682  *-----------------------------------------------------------------------
 683  */
 684 static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
 685                          register const QRect *r2, const QRect *r2End, int y1, int y2)
 686 {
 687     register int x1;
 688     register int x2;
 689     register QRect *pNextRect;
 690
 691     pNextRect = dest.rects.data() + dest.numRects;
 692
 693     while (r1 != r1End && r2 != r2End) {
 694         x1 = qMax(r1->left(), r2->left());
 695         x2 = qMin(r1->right(), r2->right());
 696
 697         /*
 698          * If there's any overlap between the two rectangles, add that
 699          * overlap to the new region.
 700          * There's no need to check for subsumption because the only way
 701          * such a need could arise is if some region has two rectangles
 702          * right next to each other. Since that should never happen...
 703          */
 704         if (x1 <= x2) {
 705             Q_ASSERT(y1 <= y2);
 706             MEMCHECK(dest, pNextRect, dest.rects)
 707             pNextRect->setCoords(x1, y1, x2, y2);
 708             ++dest.numRects;
 709             ++pNextRect;
 710         }
 711
 712         /*
 713          * Need to advance the pointers. Shift the one that extends
 714          * to the right the least, since the other still has a chance to
 715          * overlap with that region's next rectangle, if you see what I mean.
 716          */
 717         if (r1->right() < r2->right()) {
 718             ++r1;
 719         } else if (r2->right() < r1->right()) {
 720             ++r2;
 721         } else {
 722             ++r1;
 723             ++r2;
 724         }
 725     }
 726 }
 727
 728 /*======================================================================
 729  *          Generic Region Operator
 730  *====================================================================*/
 731
 732 /*-
 733  *-----------------------------------------------------------------------
 734  * miCoalesce --
 735  *      Attempt to merge the boxes in the current band with those in the
 736  *      previous one. Used only by miRegionOp.
 737  *
 738  * Results:
 739  *      The new index for the previous band.
 740  *
 741  * Side Effects:
 742  *      If coalescing takes place:
 743  *          - rectangles in the previous band will have their y2 fields
 744  *            altered.
 745  *          - dest.numRects will be decreased.
 746  *
 747  *-----------------------------------------------------------------------
 748  */
 749 static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
 750 {
 751     register QRect *pPrevBox;   /* Current box in previous band */
 752     register QRect *pCurBox;    /* Current box in current band */
 753     register QRect *pRegEnd;    /* End of region */
 754     int curNumRects;    /* Number of rectangles in current band */
 755     int prevNumRects;   /* Number of rectangles in previous band */
 756     int bandY1;         /* Y1 coordinate for current band */
 757     QRect *rData = dest.rects.data();
 758
 759     pRegEnd = rData + dest.numRects;
 760
 761     pPrevBox = rData + prevStart;
 762     prevNumRects = curStart - prevStart;
 763
 764     /*
 765      * Figure out how many rectangles are in the current band. Have to do
 766      * this because multiple bands could have been added in miRegionOp
 767      * at the end when one region has been exhausted.
 768      */
 769     pCurBox = rData + curStart;
 770     bandY1 = pCurBox->top();
 771     for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
 772         ++pCurBox;
 773     }
 774
 775     if (pCurBox != pRegEnd) {
 776         /*
 777          * If more than one band was added, we have to find the start
 778          * of the last band added so the next coalescing job can start
 779          * at the right place... (given when multiple bands are added,
 780          * this may be pointless -- see above).
 781          */
 782         --pRegEnd;
 783         while ((pRegEnd - 1)->top() == pRegEnd->top())
 784             --pRegEnd;
 785         curStart = pRegEnd - rData;
 786         pRegEnd = rData + dest.numRects;
 787     }
 788
 789     if (curNumRects == prevNumRects && curNumRects != 0) {
 790         pCurBox -= curNumRects;
 791         /*
 792          * The bands may only be coalesced if the bottom of the previous
 793          * matches the top scanline of the current.
 794          */
 795         if (pPrevBox->bottom() == pCurBox->top() - 1) {
 796             /*
 797              * Make sure the bands have boxes in the same places. This
 798              * assumes that boxes have been added in such a way that they
 799              * cover the most area possible. I.e. two boxes in a band must
 800              * have some horizontal space between them.
 801              */
 802             do {
 803                 if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
 804                      // The bands don't line up so they can't be coalesced.
 805                     return curStart;
 806                 }
 807                 ++pPrevBox;
 808                 ++pCurBox;
 809                 --prevNumRects;
 810             } while (prevNumRects != 0);
 811
 812             dest.numRects -= curNumRects;
 813             pCurBox -= curNumRects;
 814             pPrevBox -= curNumRects;
 815
 816             /*
 817              * The bands may be merged, so set the bottom y of each box
 818              * in the previous band to that of the corresponding box in
 819              * the current band.
 820              */
 821             do {
 822                 pPrevBox->setBottom(pCurBox->bottom());
 823                 dest.updateInnerRect(*pPrevBox);
 824                 ++pPrevBox;
 825                 ++pCurBox;
 826                 curNumRects -= 1;
 827             } while (curNumRects != 0);
 828
 829             /*
 830              * If only one band was added to the region, we have to backup
 831              * curStart to the start of the previous band.
 832              *
 833              * If more than one band was added to the region, copy the
 834              * other bands down. The assumption here is that the other bands
 835              * came from the same region as the current one and no further
 836              * coalescing can be done on them since it's all been done
 837              * already... curStart is already in the right place.
 838              */
 839             if (pCurBox == pRegEnd) {
 840                 curStart = prevStart;
 841             } else {
 842                 do {
 843                     *pPrevBox++ = *pCurBox++;
 844                     dest.updateInnerRect(*pPrevBox);
 845                 } while (pCurBox != pRegEnd);
 846             }
 847         }
 848     }
 849     return curStart;
 850 }
 851
 852 /*-
 853  *-----------------------------------------------------------------------
 854  * miRegionOp --
 855  *      Apply an operation to two regions. Called by miUnion, miInverse,
 856  *      miSubtract, miIntersect...
 857  *
 858  * Results:
 859  *      None.
 860  *
 861  * Side Effects:
 862  *      The new region is overwritten.
 863  *
 864  * Notes:
 865  *      The idea behind this function is to view the two regions as sets.
 866  *      Together they cover a rectangle of area that this function divides
 867  *      into horizontal bands where points are covered only by one region
 868  *      or by both. For the first case, the nonOverlapFunc is called with
 869  *      each the band and the band's upper and lower extents. For the
 870  *      second, the overlapFunc is called to process the entire band. It
 871  *      is responsible for clipping the rectangles in the band, though
 872  *      this function provides the boundaries.
 873  *      At the end of each band, the new region is coalesced, if possible,
 874  *      to reduce the number of rectangles in the region.
 875  *
 876  *-----------------------------------------------------------------------
 877  */
 878 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
 879                        OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
 880                        NonOverlapFunc nonOverlap2Func)
 881 {
 882     register const QRect *r1;         // Pointer into first region
 883     register const QRect *r2;         // Pointer into 2d region
 884     const QRect *r1End;               // End of 1st region
 885     const QRect *r2End;               // End of 2d region
 886     register int ybot;          // Bottom of intersection
 887     register int ytop;          // Top of intersection
 888     int prevBand;               // Index of start of previous band in dest
 889     int curBand;                // Index of start of current band in dest
 890     register const QRect *r1BandEnd;  // End of current band in r1
 891     register const QRect *r2BandEnd;  // End of current band in r2
 892     int top;                    // Top of non-overlapping band
 893     int bot;                    // Bottom of non-overlapping band
 894
 895     /*
 896      * Initialization:
 897      *  set r1, r2, r1End and r2End appropriately, preserve the important
 898      * parts of the destination region until the end in case it's one of
 899      * the two source regions, then mark the "new" region empty, allocating
 900      * another array of rectangles for it to use.
 901      */
 902     r1 = (reg1->mode==QRegionPrivate::Vector)?reg1->rects.data():&reg1->single;
 903     r2 = (reg2->mode==QRegionPrivate::Vector)?reg2->rects.data():&reg2->single;
 904     r1End = r1 + reg1->numRects;
 905     r2End = r2 + reg2->numRects;
 906
 907     dest.vector();
 908     QVector<QRect> oldRects = dest.rects;
 909
 910     dest.numRects = 0;
 911
 912     /*
 913      * Allocate a reasonable number of rectangles for the new region. The idea
 914      * is to allocate enough so the individual functions don't need to
 915      * reallocate and copy the array, which is time consuming, yet we don't
 916      * have to worry about using too much memory. I hope to be able to
 917      * nuke the realloc() at the end of this function eventually.
 918      */
 919     dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
 920
 921     /*
 922      * Initialize ybot and ytop.
 923      * In the upcoming loop, ybot and ytop serve different functions depending
 924      * on whether the band being handled is an overlapping or non-overlapping
 925      * band.
 926      *  In the case of a non-overlapping band (only one of the regions
 927      * has points in the band), ybot is the bottom of the most recent
 928      * intersection and thus clips the top of the rectangles in that band.
 929      * ytop is the top of the next intersection between the two regions and
 930      * serves to clip the bottom of the rectangles in the current band.
 931      *  For an overlapping band (where the two regions intersect), ytop clips
 932      * the top of the rectangles of both regions and ybot clips the bottoms.
 933      */
 934     if (reg1->extents.top() < reg2->extents.top())
 935         ybot = reg1->extents.top() - 1;
 936     else
 937         ybot = reg2->extents.top() - 1;
 938
 939     /*
 940      * prevBand serves to mark the start of the previous band so rectangles
 941      * can be coalesced into larger rectangles. qv. miCoalesce, above.
 942      * In the beginning, there is no previous band, so prevBand == curBand
 943      * (curBand is set later on, of course, but the first band will always
 944      * start at index 0). prevBand and curBand must be indices because of
 945      * the possible expansion, and resultant moving, of the new region's
 946      * array of rectangles.
 947      */
 948     prevBand = 0;
 949
 950     do {
 951         curBand = dest.numRects;
 952
 953         /*
 954          * This algorithm proceeds one source-band (as opposed to a
 955          * destination band, which is determined by where the two regions
 956          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
 957          * rectangle after the last one in the current band for their
 958          * respective regions.
 959          */
 960         r1BandEnd = r1;
 961         while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
 962             ++r1BandEnd;
 963
 964         r2BandEnd = r2;
 965         while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
 966             ++r2BandEnd;
 967
 968         /*
 969          * First handle the band that doesn't intersect, if any.
 970          *
 971          * Note that attention is restricted to one band in the
 972          * non-intersecting region at once, so if a region has n
 973          * bands between the current position and the next place it overlaps
 974          * the other, this entire loop will be passed through n times.
 975          */
 976         if (r1->top() < r2->top()) {
 977             top = qMax(r1->top(), ybot + 1);
 978             bot = qMin(r1->bottom(), r2->top() - 1);
 979
 980             if (nonOverlap1Func != 0 && bot >= top)
 981                 (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
 982             ytop = r2->top();
 983         } else if (r2->top() < r1->top()) {
 984             top = qMax(r2->top(), ybot + 1);
 985             bot = qMin(r2->bottom(), r1->top() - 1);
 986
 987             if (nonOverlap2Func != 0 && bot >= top)
 988                 (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
 989             ytop = r1->top();
 990         } else {
 991             ytop = r1->top();
 992         }
 993
 994         /*
 995          * If any rectangles got added to the region, try and coalesce them
 996          * with rectangles from the previous band. Note we could just do
 997          * this test in miCoalesce, but some machines incur a not
 998          * inconsiderable cost for function calls, so...
 999          */
1000         if (dest.numRects != curBand)
1001             prevBand = miCoalesce(dest, prevBand, curBand);
1002
1003         /*
1004          * Now see if we've hit an intersecting band. The two bands only
1005          * intersect if ybot >= ytop
1006          */
1007         ybot = qMin(r1->bottom(), r2->bottom());
1008         curBand = dest.numRects;
1009         if (ybot >= ytop)
1010             (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1011
1012         if (dest.numRects != curBand)
1013             prevBand = miCoalesce(dest, prevBand, curBand);
1014
1015         /*
1016          * If we've finished with a band (y2 == ybot) we skip forward
1017          * in the region to the next band.
1018          */
1019         if (r1->bottom() == ybot)
1020             r1 = r1BandEnd;
1021         if (r2->bottom() == ybot)
1022             r2 = r2BandEnd;
1023     } while (r1 != r1End && r2 != r2End);
1024
1025     /*
1026      * Deal with whichever region still has rectangles left.
1027      */
1028     curBand = dest.numRects;
1029     if (r1 != r1End) {
1030         if (nonOverlap1Func != 0) {
1031             do {
1032                 r1BandEnd = r1;
1033                 while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
1034                     ++r1BandEnd;
1035                 (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
1036                 r1 = r1BandEnd;
1037             } while (r1 != r1End);
1038         }
1039     } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
1040         do {
1041             r2BandEnd = r2;
1042             while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
1043                  ++r2BandEnd;
1044             (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
1045             r2 = r2BandEnd;
1046         } while (r2 != r2End);
1047     }
1048
1049     if (dest.numRects != curBand)
1050         (void)miCoalesce(dest, prevBand, curBand);
1051
1052     /*
1053      * A bit of cleanup. To keep regions from growing without bound,
1054      * we shrink the array of rectangles to match the new number of
1055      * rectangles in the region.
1056      *
1057      * Only do this stuff if the number of rectangles allocated is more than
1058      * twice the number of rectangles in the region (a simple optimization).
1059      */
1060     if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
1061         dest.rects.resize(dest.numRects);
1062 }
1063
1064 /*======================================================================
1065  *          Region Union
1066  *====================================================================*/
1067
1068 /*-
1069  *-----------------------------------------------------------------------
1070  * miUnionNonO --
1071  *      Handle a non-overlapping band for the union operation. Just
1072  *      Adds the rectangles into the region. Doesn't have to check for
1073  *      subsumption or anything.
1074  *
1075  * Results:
1076  *      None.
1077  *
1078  * Side Effects:
1079  *      dest.numRects is incremented and the final rectangles overwritten
1080  *      with the rectangles we're passed.
1081  *
1082  *-----------------------------------------------------------------------
1083  */
1084
1085 static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
1086                         register int y1, register int y2)
1087 {
1088     register QRect *pNextRect;
1089
1090     pNextRect = dest.rects.data() + dest.numRects;
1091
1092     Q_ASSERT(y1 <= y2);
1093
1094     while (r != rEnd) {
1095         Q_ASSERT(r->left() <= r->right());
1096         MEMCHECK(dest, pNextRect, dest.rects)
1097         pNextRect->setCoords(r->left(), y1, r->right(), y2);
1098         dest.numRects++;
1099         ++pNextRect;
1100         ++r;
1101     }
1102 }
1103
1104
1105 /*-
1106  *-----------------------------------------------------------------------
1107  * miUnionO --
1108  *      Handle an overlapping band for the union operation. Picks the
1109  *      left-most rectangle each time and merges it into the region.
1110  *
1111  * Results:
1112  *      None.
1113  *
1114  * Side Effects:
1115  *      Rectangles are overwritten in dest.rects and dest.numRects will
1116  *      be changed.
1117  *
1118  *-----------------------------------------------------------------------
1119  */
1120
1121 static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1122                      register const QRect *r2, const QRect *r2End, register int y1, register int y2)
1123 {
1124     register QRect *pNextRect;
1125
1126     pNextRect = dest.rects.data() + dest.numRects;
1127
1128 #define MERGERECT(r)             \
1129     if ((dest.numRects != 0) &&  \
1130         (pNextRect[-1].top() == y1) &&  \
1131         (pNextRect[-1].bottom() == y2) &&  \
1132         (pNextRect[-1].right() >= r->left()-1)) { \
1133         if (pNextRect[-1].right() < r->right()) { \
1134             pNextRect[-1].setRight(r->right());  \
1135             dest.updateInnerRect(pNextRect[-1]); \
1136             Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
1137         }  \
1138     } else { \
1139         MEMCHECK(dest, pNextRect, dest.rects)  \
1140         pNextRect->setCoords(r->left(), y1, r->right(), y2); \
1141         dest.updateInnerRect(*pNextRect); \
1142         dest.numRects++;  \
1143         pNextRect++;  \
1144     }  \
1145     r++;
1146
1147     Q_ASSERT(y1 <= y2);
1148     while (r1 != r1End && r2 != r2End) {
1149         if (r1->left() < r2->left()) {
1150             MERGERECT(r1)
1151         } else {
1152             MERGERECT(r2)
1153         }
1154     }
1155
1156     if (r1 != r1End) {
1157         do {
1158             MERGERECT(r1)
1159         } while (r1 != r1End);
1160     } else {
1161         while (r2 != r2End) {
1162             MERGERECT(r2)
1163         }
1164     }
1165 }
1166
1167 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
1168 {
1169     Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2));
1170     Q_ASSERT(!reg1->contains(*reg2));
1171     Q_ASSERT(!reg2->contains(*reg1));
1172     Q_ASSERT(!EqualRegion(reg1, reg2));
1173     Q_ASSERT(!reg1->canAppend(reg2));
1174     Q_ASSERT(!reg2->canAppend(reg1));
1175
1176     if (reg1->innerArea > reg2->innerArea) {
1177         dest.innerArea = reg1->innerArea;
1178         dest.innerRect = reg1->innerRect;
1179     } else {
1180         dest.innerArea = reg2->innerArea;
1181         dest.innerRect = reg2->innerRect;
1182     }
1183     miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
1184
1185     dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
1186                            qMin(reg1->extents.top(), reg2->extents.top()),
1187                            qMax(reg1->extents.right(), reg2->extents.right()),
1188                            qMax(reg1->extents.bottom(), reg2->extents.bottom()));
1189 }
1190
1191 /*======================================================================
1192  *        Region Subtraction
1193  *====================================================================*/
1194
1195 /*-
1196  *-----------------------------------------------------------------------
1197  * miSubtractNonO --
1198  *      Deal with non-overlapping band for subtraction. Any parts from
1199  *      region 2 we discard. Anything from region 1 we add to the region.
1200  *
1201  * Results:
1202  *      None.
1203  *
1204  * Side Effects:
1205  *      dest may be affected.
1206  *
1207  *-----------------------------------------------------------------------
1208  */
1209
1210 static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
1211                             const QRect *rEnd, register int y1, register int y2)
1212 {
1213     register QRect *pNextRect;
1214
1215     pNextRect = dest.rects.data() + dest.numRects;
1216
1217     Q_ASSERT(y1<=y2);
1218
1219     while (r != rEnd) {
1220         Q_ASSERT(r->left() <= r->right());
1221         MEMCHECK(dest, pNextRect, dest.rects)
1222         pNextRect->setCoords(r->left(), y1, r->right(), y2);
1223         ++dest.numRects;
1224         ++pNextRect;
1225         ++r;
1226     }
1227 }
1228
1229 /*-
1230  *-----------------------------------------------------------------------
1231  * miSubtractO --
1232  *      Overlapping band subtraction. x1 is the left-most point not yet
1233  *      checked.
1234  *
1235  * Results:
1236  *      None.
1237  *
1238  * Side Effects:
1239  *      dest may have rectangles added to it.
1240  *
1241  *-----------------------------------------------------------------------
1242  */
1243
1244 static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1245                         register const QRect *r2, const QRect *r2End, register int y1, register int y2)
1246 {
1247     register QRect *pNextRect;
1248     register int x1;
1249
1250     x1 = r1->left();
1251
1252     Q_ASSERT(y1 <= y2);
1253     pNextRect = dest.rects.data() + dest.numRects;
1254
1255     while (r1 != r1End && r2 != r2End) {
1256         if (r2->right() < x1) {
1257             /*
1258              * Subtrahend missed the boat: go to next subtrahend.
1259              */
1260             ++r2;
1261         } else if (r2->left() <= x1) {
1262             /*
1263              * Subtrahend precedes minuend: nuke left edge of minuend.
1264              */
1265             x1 = r2->right() + 1;
1266             if (x1 > r1->right()) {
1267                 /*
1268                  * Minuend completely covered: advance to next minuend and
1269                  * reset left fence to edge of new minuend.
1270                  */
1271                 ++r1;
1272                 if (r1 != r1End)
1273                     x1 = r1->left();
1274             } else {
1275                 // Subtrahend now used up since it doesn't extend beyond minuend
1276                 ++r2;
1277             }
1278         } else if (r2->left() <= r1->right()) {
1279             /*
1280              * Left part of subtrahend covers part of minuend: add uncovered
1281              * part of minuend to region and skip to next subtrahend.
1282              */
1283             Q_ASSERT(x1 < r2->left());
1284             MEMCHECK(dest, pNextRect, dest.rects)
1285             pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
1286             ++dest.numRects;
1287             ++pNextRect;
1288
1289             x1 = r2->right() + 1;
1290             if (x1 > r1->right()) {
1291                 /*
1292                  * Minuend used up: advance to new...
1293                  */
1294                 ++r1;
1295                 if (r1 != r1End)
1296                     x1 = r1->left();
1297             } else {
1298                 // Subtrahend used up
1299                 ++r2;
1300             }
1301         } else {
1302             /*
1303              * Minuend used up: add any remaining piece before advancing.
1304              */
1305             if (r1->right() >= x1) {
1306                 MEMCHECK(dest, pNextRect, dest.rects)
1307                 pNextRect->setCoords(x1, y1, r1->right(), y2);
1308                 ++dest.numRects;
1309                 ++pNextRect;
1310             }
1311             ++r1;
1312             if (r1 != r1End)
1313                 x1 = r1->left();
1314         }
1315     }
1316
1317     /*
1318      * Add remaining minuend rectangles to region.
1319      */
1320     while (r1 != r1End) {
1321         Q_ASSERT(x1 <= r1->right());
1322         MEMCHECK(dest, pNextRect, dest.rects)
1323         pNextRect->setCoords(x1, y1, r1->right(), y2);
1324         ++dest.numRects;
1325         ++pNextRect;
1326
1327         ++r1;
1328         if (r1 != r1End)
1329             x1 = r1->left();
1330     }
1331 }
1332
1333 /*-
1334  *-----------------------------------------------------------------------
1335  * miSubtract --
1336  *      Subtract regS from regM and leave the result in regD.
1337  *      S stands for subtrahend, M for minuend and D for difference.
1338  *
1339  * Side Effects:
1340  *      regD is overwritten.
1341  *
1342  *-----------------------------------------------------------------------
1343  */
1344
1345 static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
1346                            register QRegionPrivate &dest)
1347 {
1348     Q_ASSERT(!isEmptyHelper(regM));
1349     Q_ASSERT(!isEmptyHelper(regS));
1350     Q_ASSERT(EXTENTCHECK(&regM->extents, &regS->extents));
1351     Q_ASSERT(!regS->contains(*regM));
1352     Q_ASSERT(!EqualRegion(regM, regS));
1353
1354     miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
1355
1356     /*
1357      * Can't alter dest's extents before we call miRegionOp because
1358      * it might be one of the source regions and miRegionOp depends
1359      * on the extents of those regions being the unaltered. Besides, this
1360      * way there's no checking against rectangles that will be nuked
1361      * due to coalescing, so we have to examine fewer rectangles.
1362      */
1363     miSetExtents(dest);
1364 }
1365
1366 static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
1367 {
1368     Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb));
1369     Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents));
1370     Q_ASSERT(!EqualRegion(sra, srb));
1371
1372     QRegionPrivate tra, trb;
1373
1374     if (!srb->contains(*sra))
1375         SubtractRegion(sra, srb, tra);
1376     if (!sra->contains(*srb))
1377         SubtractRegion(srb, sra, trb);
1378
1379     Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb));
1380     Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra));
1381
1382     if (isEmptyHelper(&tra)) {
1383         dest = trb;
1384     } else if (isEmptyHelper(&trb)) {
1385         dest = tra;
1386     } else if (tra.canAppend(&trb)) {
1387         dest = tra;
1388         dest.append(&trb);
1389     } else if (trb.canAppend(&tra)) {
1390         dest = trb;
1391         dest.append(&tra);
1392     } else {
1393         UnionRegion(&tra, &trb, dest);
1394     }
1395 }
1396
1397 /*
1398  *      Check to see if two regions are equal
1399  */
1400 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
1401 {
1402     if (r1->numRects != r2->numRects) {
1403         return false;
1404     } else if (r1->numRects == 0) {
1405         return true;
1406     } else if (r1->extents != r2->extents) {
1407         return false;
1408     } else if (r1->mode == QRegionPrivate::Single && r2->mode == QRegionPrivate::Single) {
1409         return r1->single == r2->single;
1410     } else {
1411         const QRect *rr1 = (r1->mode==QRegionPrivate::Vector)?r1->rects.constData():&r1->single;
1412         const QRect *rr2 = (r2->mode==QRegionPrivate::Vector)?r2->rects.constData():&r2->single;
1413         for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
1414             if (*rr1 != *rr2)
1415                 return false;
1416         }
1417     }
1418
1419     return true;
1420 }
1421
1422 static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
1423 {
1424     int i;
1425
1426     if (pRegion->mode == QRegionPrivate::Single)
1427         return pRegion->single.contains(x, y);
1428     if (isEmptyHelper(pRegion))
1429         return false;
1430     if (!pRegion->extents.contains(x, y))
1431         return false;
1432     if (pRegion->innerRect.contains(x, y))
1433         return true;
1434     for (i = 0; i < pRegion->numRects; ++i) {
1435         if (pRegion->rects[i].contains(x, y))
1436             return true;
1437     }
1438     return false;
1439 }
1440
1441 static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
1442 {
1443     register const QRect *pbox;
1444     register const QRect *pboxEnd;
1445     QRect rect(rx, ry, rwidth, rheight);
1446     register QRect *prect = &rect;
1447     int partIn, partOut;
1448
1449     if (!region || region->numRects == 0 || !EXTENTCHECK(&region->extents, prect))
1450         return RectangleOut;
1451
1452     partOut = false;
1453     partIn = false;
1454
1455     /* can stop when both partOut and partIn are true, or we reach prect->y2 */
1456     for (pbox = (region->mode==QRegionPrivate::Vector)?region->rects.constData():&region->single, pboxEnd = pbox + region->numRects;
1457          pbox < pboxEnd; ++pbox) {
1458         if (pbox->bottom() < ry)
1459            continue;
1460
1461         if (pbox->top() > ry) {
1462            partOut = true;
1463            if (partIn || pbox->top() > prect->bottom())
1464               break;
1465            ry = pbox->top();
1466         }
1467
1468         if (pbox->right() < rx)
1469            continue;            /* not far enough over yet */
1470
1471         if (pbox->left() > rx) {
1472            partOut = true;      /* missed part of rectangle to left */
1473            if (partIn)
1474               break;
1475         }
1476
1477         if (pbox->left() <= prect->right()) {
1478             partIn = true;      /* definitely overlap */
1479             if (partOut)
1480                break;
1481         }
1482
1483         if (pbox->right() >= prect->right()) {
1484            ry = pbox->bottom() + 1;     /* finished with this band */
1485            if (ry > prect->bottom())
1486               break;
1487            rx = prect->left();  /* reset x out to left again */
1488         } else {
1489             /*
1490              * Because boxes in a band are maximal width, if the first box
1491              * to overlap the rectangle doesn't completely cover it in that
1492              * band, the rectangle must be partially out, since some of it
1493              * will be uncovered in that band. partIn will have been set true
1494              * by now...
1495              */
1496             break;
1497         }
1498     }
1499     return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
1500 }
1501 // END OF Region.c extract
1502 // START OF poly.h extract
1503 /* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */
1504 /************************************************************************
1505
1506 Copyright (c) 1987  X Consortium
1507
1508 Permission is hereby granted, free of charge, to any person obtaining a copy
1509 of this software and associated documentation files (the "Software"), to deal
1510 in the Software without restriction, including without limitation the rights
1511 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1512 copies of the Software, and to permit persons to whom the Software is
1513 furnished to do so, subject to the following conditions:
1514
1515 The above copyright notice and this permission notice shall be included in
1516 all copies or substantial portions of the Software.
1517
1518 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1519 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1520 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
1521 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1522 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1523 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1524
1525 Except as contained in this notice, the name of the X Consortium shall not be
1526 used in advertising or otherwise to promote the sale, use or other dealings
1527 in this Software without prior written authorization from the X Consortium.
1528
1529
1530 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1531
1532                         All Rights Reserved
1533
1534 Permission to use, copy, modify, and distribute this software and its
1535 documentation for any purpose and without fee is hereby granted,
1536 provided that the above copyright notice appear in all copies and that
1537 both that copyright notice and this permission notice appear in
1538 supporting documentation, and that the name of Digital not be
1539 used in advertising or publicity pertaining to distribution of the
1540 software without specific, written prior permission.
1541
1542 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1543 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1544 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1545 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1546 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1547 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1548 SOFTWARE.
1549
1550 ************************************************************************/
1551
1552 /*
1553  *     This file contains a few macros to help track
1554  *     the edge of a filled object.  The object is assumed
1555  *     to be filled in scanline order, and thus the
1556  *     algorithm used is an extension of Bresenham's line
1557  *     drawing algorithm which assumes that y is always the
1558  *     major axis.
1559  *     Since these pieces of code are the same for any filled shape,
1560  *     it is more convenient to gather the library in one
1561  *     place, but since these pieces of code are also in
1562  *     the inner loops of output primitives, procedure call
1563  *     overhead is out of the question.
1564  *     See the author for a derivation if needed.
1565  */
1566
1567
1568 /*
1569  *  In scan converting polygons, we want to choose those pixels
1570  *  which are inside the polygon.  Thus, we add .5 to the starting
1571  *  x coordinate for both left and right edges.  Now we choose the
1572  *  first pixel which is inside the pgon for the left edge and the
1573  *  first pixel which is outside the pgon for the right edge.
1574  *  Draw the left pixel, but not the right.
1575  *
1576  *  How to add .5 to the starting x coordinate:
1577  *      If the edge is moving to the right, then subtract dy from the
1578  *  error term from the general form of the algorithm.
1579  *      If the edge is moving to the left, then add dy to the error term.
1580  *
1581  *  The reason for the difference between edges moving to the left
1582  *  and edges moving to the right is simple:  If an edge is moving
1583  *  to the right, then we want the algorithm to flip immediately.
1584  *  If it is moving to the left, then we don't want it to flip until
1585  *  we traverse an entire pixel.
1586  */
1587 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
1588     int dx;      /* local storage */ \
1589 \
1590     /* \
1591      *  if the edge is horizontal, then it is ignored \
1592      *  and assumed not to be processed.  Otherwise, do this stuff. \
1593      */ \
1594     if ((dy) != 0) { \
1595         xStart = (x1); \
1596         dx = (x2) - xStart; \
1597         if (dx < 0) { \
1598             m = dx / (dy); \
1599             m1 = m - 1; \
1600             incr1 = -2 * dx + 2 * (dy) * m1; \
1601             incr2 = -2 * dx + 2 * (dy) * m; \
1602             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
1603         } else { \
1604             m = dx / (dy); \
1605             m1 = m + 1; \
1606             incr1 = 2 * dx - 2 * (dy) * m1; \
1607             incr2 = 2 * dx - 2 * (dy) * m; \
1608             d = -2 * m * (dy) + 2 * dx; \
1609         } \
1610     } \
1611 }
1612
1613 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
1614     if (m1 > 0) { \
1615         if (d > 0) { \
1616             minval += m1; \
1617             d += incr1; \
1618         } \
1619         else { \
1620             minval += m; \
1621             d += incr2; \
1622         } \
1623     } else {\
1624         if (d >= 0) { \
1625             minval += m1; \
1626             d += incr1; \
1627         } \
1628         else { \
1629             minval += m; \
1630             d += incr2; \
1631         } \
1632     } \
1633 }
1634
1635
1636 /*
1637  *     This structure contains all of the information needed
1638  *     to run the bresenham algorithm.
1639  *     The variables may be hardcoded into the declarations
1640  *     instead of using this structure to make use of
1641  *     register declarations.
1642  */
1643 typedef struct {
1644     int minor_axis;     /* minor axis        */
1645     int d;              /* decision variable */
1646     int m, m1;          /* slope and slope+1 */
1647     int incr1, incr2;   /* error increments */
1648 } BRESINFO;
1649
1650
1651 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
1652         BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
1653                      bres.m, bres.m1, bres.incr1, bres.incr2)
1654
1655 #define BRESINCRPGONSTRUCT(bres) \
1656         BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
1657
1658
1659
1660 /*
1661  *     These are the data structures needed to scan
1662  *     convert regions.  Two different scan conversion
1663  *     methods are available -- the even-odd method, and
1664  *     the winding number method.
1665  *     The even-odd rule states that a point is inside
1666  *     the polygon if a ray drawn from that point in any
1667  *     direction will pass through an odd number of
1668  *     path segments.
1669  *     By the winding number rule, a point is decided
1670  *     to be inside the polygon if a ray drawn from that
1671  *     point in any direction passes through a different
1672  *     number of clockwise and counter-clockwise path
1673  *     segments.
1674  *
1675  *     These data structures are adapted somewhat from
1676  *     the algorithm in (Foley/Van Dam) for scan converting
1677  *     polygons.
1678  *     The basic algorithm is to start at the top (smallest y)
1679  *     of the polygon, stepping down to the bottom of
1680  *     the polygon by incrementing the y coordinate.  We
1681  *     keep a list of edges which the current scanline crosses,
1682  *     sorted by x.  This list is called the Active Edge Table (AET)
1683  *     As we change the y-coordinate, we update each entry in
1684  *     in the active edge table to reflect the edges new xcoord.
1685  *     This list must be sorted at each scanline in case
1686  *     two edges intersect.
1687  *     We also keep a data structure known as the Edge Table (ET),
1688  *     which keeps track of all the edges which the current
1689  *     scanline has not yet reached.  The ET is basically a
1690  *     list of ScanLineList structures containing a list of
1691  *     edges which are entered at a given scanline.  There is one
1692  *     ScanLineList per scanline at which an edge is entered.
1693  *     When we enter a new edge, we move it from the ET to the AET.
1694  *
1695  *     From the AET, we can implement the even-odd rule as in
1696  *     (Foley/Van Dam).
1697  *     The winding number rule is a little trickier.  We also
1698  *     keep the EdgeTableEntries in the AET linked by the
1699  *     nextWETE (winding EdgeTableEntry) link.  This allows
1700  *     the edges to be linked just as before for updating
1701  *     purposes, but only uses the edges linked by the nextWETE
1702  *     link as edges representing spans of the polygon to
1703  *     drawn (as with the even-odd rule).
1704  */
1705
1706 /*
1707  * for the winding number rule
1708  */
1709 #define CLOCKWISE          1
1710 #define COUNTERCLOCKWISE  -1
1711
1712 typedef struct _EdgeTableEntry {
1713      int ymax;             /* ycoord at which we exit this edge. */
1714      BRESINFO bres;        /* Bresenham info to run the edge     */
1715      struct _EdgeTableEntry *next;       /* next in the list     */
1716      struct _EdgeTableEntry *back;       /* for insertion sort   */
1717      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
1718      int ClockWise;        /* flag for winding number rule       */
1719 } EdgeTableEntry;
1720
1721
1722 typedef struct _ScanLineList{
1723      int scanline;              /* the scanline represented */
1724      EdgeTableEntry *edgelist;  /* header node              */
1725      struct _ScanLineList *next;  /* next in the list       */
1726 } ScanLineList;
1727
1728
1729 typedef struct {
1730      int ymax;                 /* ymax for the polygon     */
1731      int ymin;                 /* ymin for the polygon     */
1732      ScanLineList scanlines;   /* header node              */
1733 } EdgeTable;
1734
1735
1736 /*
1737  * Here is a struct to help with storage allocation
1738  * so we can allocate a big chunk at a time, and then take
1739  * pieces from this heap when we need to.
1740  */
1741 #define SLLSPERBLOCK 25
1742
1743 typedef struct _ScanLineListBlock {
1744      ScanLineList SLLs[SLLSPERBLOCK];
1745      struct _ScanLineListBlock *next;
1746 } ScanLineListBlock;
1747
1748
1749
1750 /*
1751  *
1752  *     a few macros for the inner loops of the fill code where
1753  *     performance considerations don't allow a procedure call.
1754  *
1755  *     Evaluate the given edge at the given scanline.
1756  *     If the edge has expired, then we leave it and fix up
1757  *     the active edge table; otherwise, we increment the
1758  *     x value to be ready for the next scanline.
1759  *     The winding number rule is in effect, so we must notify
1760  *     the caller when the edge has been removed so he
1761  *     can reorder the Winding Active Edge Table.
1762  */
1763 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
1764    if (pAET->ymax == y) {          /* leaving this edge */ \
1765       pPrevAET->next = pAET->next; \
1766       pAET = pPrevAET->next; \
1767       fixWAET = 1; \
1768       if (pAET) \
1769          pAET->back = pPrevAET; \
1770    } \
1771    else { \
1772       BRESINCRPGONSTRUCT(pAET->bres) \
1773       pPrevAET = pAET; \
1774       pAET = pAET->next; \
1775    } \
1776 }
1777
1778
1779 /*
1780  *     Evaluate the given edge at the given scanline.
1781  *     If the edge has expired, then we leave it and fix up
1782  *     the active edge table; otherwise, we increment the
1783  *     x value to be ready for the next scanline.
1784  *     The even-odd rule is in effect.
1785  */
1786 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
1787    if (pAET->ymax == y) {          /* leaving this edge */ \
1788       pPrevAET->next = pAET->next; \
1789       pAET = pPrevAET->next; \
1790       if (pAET) \
1791          pAET->back = pPrevAET; \
1792    } \
1793    else { \
1794       BRESINCRPGONSTRUCT(pAET->bres) \
1795       pPrevAET = pAET; \
1796       pAET = pAET->next; \
1797    } \
1798 }
1799 // END OF poly.h extract
1800 // START OF PolyReg.c extract
1801 /* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */
1802 /************************************************************************
1803
1804 Copyright (c) 1987  X Consortium
1805
1806 Permission is hereby granted, free of charge, to any person obtaining a copy
1807 of this software and associated documentation files (the "Software"), to deal
1808 in the Software without restriction, including without limitation the rights
1809 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1810 copies of the Software, and to permit persons to whom the Software is
1811 furnished to do so, subject to the following conditions:
1812
1813 The above copyright notice and this permission notice shall be included in
1814 all copies or substantial portions of the Software.
1815
1816 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1817 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1818 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
1819 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1820 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1821 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1822
1823 Except as contained in this notice, the name of the X Consortium shall not be
1824 used in advertising or otherwise to promote the sale, use or other dealings
1825 in this Software without prior written authorization from the X Consortium.
1826
1827
1828 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1829
1830                         All Rights Reserved
1831
1832 Permission to use, copy, modify, and distribute this software and its
1833 documentation for any purpose and without fee is hereby granted,
1834 provided that the above copyright notice appear in all copies and that
1835 both that copyright notice and this permission notice appear in
1836 supporting documentation, and that the name of Digital not be
1837 used in advertising or publicity pertaining to distribution of the
1838 software without specific, written prior permission.
1839
1840 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1841 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1842 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1843 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1844 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1845 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1846 SOFTWARE.
1847
1848 ************************************************************************/
1849 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */
1850
1851 #define LARGE_COORDINATE 1000000
1852 #define SMALL_COORDINATE -LARGE_COORDINATE
1853
1854 /*
1855  *     InsertEdgeInET
1856  *
1857  *     Insert the given edge into the edge table.
1858  *     First we must find the correct bucket in the
1859  *     Edge table, then find the right slot in the
1860  *     bucket.  Finally, we can insert it.
1861  *
1862  */
1863 static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
1864                            ScanLineListBlock **SLLBlock, int *iSLLBlock)
1865 {
1866     register EdgeTableEntry *start, *prev;
1867     register ScanLineList *pSLL, *pPrevSLL;
1868     ScanLineListBlock *tmpSLLBlock;
1869
1870     /*
1871      * find the right bucket to put the edge into
1872      */
1873     pPrevSLL = &ET->scanlines;
1874     pSLL = pPrevSLL->next;
1875     while (pSLL && (pSLL->scanline < scanline)) {
1876         pPrevSLL = pSLL;
1877         pSLL = pSLL->next;
1878     }
1879
1880     /*
1881      * reassign pSLL (pointer to ScanLineList) if necessary
1882      */
1883     if ((!pSLL) || (pSLL->scanline > scanline)) {
1884         if (*iSLLBlock > SLLSPERBLOCK-1)
1885         {
1886             tmpSLLBlock =
1887                   (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
1888             (*SLLBlock)->next = tmpSLLBlock;
1889             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
1890             *SLLBlock = tmpSLLBlock;
1891             *iSLLBlock = 0;
1892         }
1893         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
1894
1895         pSLL->next = pPrevSLL->next;
1896         pSLL->edgelist = (EdgeTableEntry *)NULL;
1897         pPrevSLL->next = pSLL;
1898     }
1899     pSLL->scanline = scanline;
1900
1901     /*
1902      * now insert the edge in the right bucket
1903      */
1904     prev = 0;
1905     start = pSLL->edgelist;
1906     while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
1907         prev = start;
1908         start = start->next;
1909     }
1910     ETE->next = start;
1911
1912     if (prev)
1913         prev->next = ETE;
1914     else
1915         pSLL->edgelist = ETE;
1916 }
1917
1918 /*
1919  *     CreateEdgeTable
1920  *
1921  *     This routine creates the edge table for
1922  *     scan converting polygons.
1923  *     The Edge Table (ET) looks like:
1924  *
1925  *    EdgeTable
1926  *     --------
1927  *    |  ymax  |        ScanLineLists
1928  *    |scanline|-->------------>-------------->...
1929  *     --------   |scanline|   |scanline|
1930  *                |edgelist|   |edgelist|
1931  *                ---------    ---------
1932  *                    |             |
1933  *                    |             |
1934  *                    V             V
1935  *              list of ETEs   list of ETEs
1936  *
1937  *     where ETE is an EdgeTableEntry data structure,
1938  *     and there is one ScanLineList per scanline at
1939  *     which an edge is initially entered.
1940  *
1941  */
1942
1943 static void CreateETandAET(register int count, register const QPoint *pts,
1944                            EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
1945                            ScanLineListBlock *pSLLBlock)
1946 {
1947     register const QPoint *top,
1948                           *bottom,
1949                           *PrevPt,
1950                           *CurrPt;
1951     int iSLLBlock = 0;
1952     int dy;
1953
1954     if (count < 2)
1955         return;
1956
1957     /*
1958      *  initialize the Active Edge Table
1959      */
1960     AET->next = 0;
1961     AET->back = 0;
1962     AET->nextWETE = 0;
1963     AET->bres.minor_axis = SMALL_COORDINATE;
1964
1965     /*
1966      *  initialize the Edge Table.
1967      */
1968     ET->scanlines.next = 0;
1969     ET->ymax = SMALL_COORDINATE;
1970     ET->ymin = LARGE_COORDINATE;
1971     pSLLBlock->next = 0;
1972
1973     PrevPt = &pts[count - 1];
1974
1975     /*
1976      *  for each vertex in the array of points.
1977      *  In this loop we are dealing with two vertices at
1978      *  a time -- these make up one edge of the polygon.
1979      */
1980     while (count--) {
1981         CurrPt = pts++;
1982
1983         /*
1984          *  find out which point is above and which is below.
1985          */
1986         if (PrevPt->y() > CurrPt->y()) {
1987             bottom = PrevPt;
1988             top = CurrPt;
1989             pETEs->ClockWise = 0;
1990         } else {
1991             bottom = CurrPt;
1992             top = PrevPt;
1993             pETEs->ClockWise = 1;
1994         }
1995
1996         /*
1997          * don't add horizontal edges to the Edge table.
1998          */
1999         if (bottom->y() != top->y()) {
2000             pETEs->ymax = bottom->y() - 1;  /* -1 so we don't get last scanline */
2001
2002             /*
2003              *  initialize integer edge algorithm
2004              */
2005             dy = bottom->y() - top->y();
2006             BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
2007
2008             InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
2009
2010             if (PrevPt->y() > ET->ymax)
2011                 ET->ymax = PrevPt->y();
2012             if (PrevPt->y() < ET->ymin)
2013                 ET->ymin = PrevPt->y();
2014             ++pETEs;
2015         }
2016
2017         PrevPt = CurrPt;
2018     }
2019 }
2020
2021 /*
2022  *     loadAET
2023  *
2024  *     This routine moves EdgeTableEntries from the
2025  *     EdgeTable into the Active Edge Table,
2026  *     leaving them sorted by smaller x coordinate.
2027  *
2028  */
2029
2030 static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
2031 {
2032     register EdgeTableEntry *pPrevAET;
2033     register EdgeTableEntry *tmp;
2034
2035     pPrevAET = AET;
2036     AET = AET->next;
2037     while (ETEs) {
2038         while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
2039             pPrevAET = AET;
2040             AET = AET->next;
2041         }
2042         tmp = ETEs->next;
2043         ETEs->next = AET;
2044         if (AET)
2045             AET->back = ETEs;
2046         ETEs->back = pPrevAET;
2047         pPrevAET->next = ETEs;
2048         pPrevAET = ETEs;
2049
2050         ETEs = tmp;
2051     }
2052 }
2053
2054 /*
2055  *     computeWAET
2056  *
2057  *     This routine links the AET by the
2058  *     nextWETE (winding EdgeTableEntry) link for
2059  *     use by the winding number rule.  The final
2060  *     Active Edge Table (AET) might look something
2061  *     like:
2062  *
2063  *     AET
2064  *     ----------  ---------   ---------
2065  *     |ymax    |  |ymax    |  |ymax    |
2066  *     | ...    |  |...     |  |...     |
2067  *     |next    |->|next    |->|next    |->...
2068  *     |nextWETE|  |nextWETE|  |nextWETE|
2069  *     ---------   ---------   ^--------
2070  *         |                   |       |
2071  *         V------------------->       V---> ...
2072  *
2073  */
2074 static void computeWAET(register EdgeTableEntry *AET)
2075 {
2076     register EdgeTableEntry *pWETE;
2077     register int inside = 1;
2078     register int isInside = 0;
2079
2080     AET->nextWETE = 0;
2081     pWETE = AET;
2082     AET = AET->next;
2083     while (AET) {
2084         if (AET->ClockWise)
2085             ++isInside;
2086         else
2087             --isInside;
2088
2089         if (!inside && !isInside || inside && isInside) {
2090             pWETE->nextWETE = AET;
2091             pWETE = AET;
2092             inside = !inside;
2093         }
2094         AET = AET->next;
2095     }
2096     pWETE->nextWETE = 0;
2097 }
2098
2099 /*
2100  *     InsertionSort
2101  *
2102  *     Just a simple insertion sort using
2103  *     pointers and back pointers to sort the Active
2104  *     Edge Table.
2105  *
2106  */
2107
2108 static int InsertionSort(register EdgeTableEntry *AET)
2109 {
2110     register EdgeTableEntry *pETEchase;
2111     register EdgeTableEntry *pETEinsert;
2112     register EdgeTableEntry *pETEchaseBackTMP;
2113     register int changed = 0;
2114
2115     AET = AET->next;
2116     while (AET) {
2117         pETEinsert = AET;
2118         pETEchase = AET;
2119         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2120             pETEchase = pETEchase->back;
2121
2122         AET = AET->next;
2123         if (pETEchase != pETEinsert) {
2124             pETEchaseBackTMP = pETEchase->back;
2125             pETEinsert->back->next = AET;
2126             if (AET)
2127                 AET->back = pETEinsert->back;
2128             pETEinsert->next = pETEchase;
2129             pETEchase->back->next = pETEinsert;
2130             pETEchase->back = pETEinsert;
2131             pETEinsert->back = pETEchaseBackTMP;
2132             changed = 1;
2133         }
2134     }
2135     return changed;
2136 }
2137
2138 /*
2139  *     Clean up our act.
2140  */
2141 static void FreeStorage(register ScanLineListBlock *pSLLBlock)
2142 {
2143     register ScanLineListBlock *tmpSLLBlock;
2144
2145     while (pSLLBlock) {
2146         tmpSLLBlock = pSLLBlock->next;
2147         free(pSLLBlock);
2148         pSLLBlock = tmpSLLBlock;
2149     }
2150 }
2151
2152 /*
2153  *     Create an array of rectangles from a list of points.
2154  *     If indeed these things (POINTS, RECTS) are the same,
2155  *     then this proc is still needed, because it allocates
2156  *     storage for the array, which was allocated on the
2157  *     stack by the calling procedure.
2158  *
2159  */
2160 static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
2161                        POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
2162 {
2163     register QRect *rects;
2164     register QPoint *pts;
2165     register POINTBLOCK *CurPtBlock;
2166     register int i;
2167     register QRect *extents;
2168     register int numRects;
2169
2170     extents = &reg->extents;
2171     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2172
2173     reg->rects.resize(numRects);
2174
2175     CurPtBlock = FirstPtBlock;
2176     rects = reg->rects.data() - 1;
2177     numRects = 0;
2178     extents->setLeft(INT_MAX);
2179     extents->setRight(INT_MIN);
2180     reg->innerArea = -1;
2181
2182     for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
2183         /* the loop uses 2 points per iteration */
2184         i = NUMPTSTOBUFFER >> 1;
2185         if (!numFullPtBlocks)
2186             i = iCurPtBlock >> 1;
2187         if(i) {
2188             for (pts = CurPtBlock->pts; i--; pts += 2) {
2189                 if (pts->x() == pts[1].x())
2190                     continue;
2191                 if (numRects && pts->x() == rects->left() && pts->y() == rects->bottom() + 1
2192                     && pts[1].x() == rects->right()+1 && (numRects == 1 || rects[-1].top() != rects->top())
2193                                                           && (i && pts[2].y() > pts[1].y())) {
2194                         rects->setBottom(pts[1].y());
2195                         reg->updateInnerRect(*rects);
2196                         continue;
2197                 }
2198                 ++numRects;
2199                 ++rects;
2200                 rects->setCoords(pts->x(), pts->y(), pts[1].x() - 1, pts[1].y());
2201                 if (rects->left() < extents->left())
2202                     extents->setLeft(rects->left());
2203                 if (rects->right() > extents->right())
2204                     extents->setRight(rects->right());
2205                 reg->updateInnerRect(*rects);
2206             }
2207         }
2208         CurPtBlock = CurPtBlock->next;
2209     }
2210
2211     if (numRects) {
2212         extents->setTop(reg->rects[0].top());
2213         extents->setBottom(rects->bottom());
2214     } else {
2215         extents->setCoords(0, 0, 0, 0);
2216     }
2217     reg->numRects = numRects;
2218 }
2219
2220 /*
2221  *     polytoregion
2222  *
2223  *     Scan converts a polygon by returning a run-length
2224  *     encoding of the resultant bitmap -- the run-length
2225  *     encoding is in the form of an array of rectangles.
2226  */
2227 static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule,
2228                                      QRegionPrivate *region)
2229     //Point     *Pts;                /* the pts                 */
2230     //int       Count;                 /* number of pts           */
2231     //int       rule;                        /* winding rule */
2232 {
2233     register EdgeTableEntry *pAET;   /* Active Edge Table       */
2234     register int y;                  /* current scanline        */
2235     register int iPts = 0;           /* number of pts in buffer */
2236     register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
2237     register ScanLineList *pSLL;     /* current scanLineList    */
2238     register QPoint *pts;             /* output buffer           */
2239     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
2240     EdgeTable ET;                    /* header node for ET      */
2241     EdgeTableEntry AET;              /* header node for AET     */
2242     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
2243     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
2244     int fixWAET = false;
2245     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
2246     POINTBLOCK *tmpPtBlock;
2247     int numFullPtBlocks = 0;
2248
2249     region->vector();
2250
2251     /* special case a rectangle */
2252     if (((Count == 4) ||
2253          ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
2254          && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
2255                && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
2256                && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
2257                && (Pts[3].y() == Pts[0].y())))) {
2258         int x = qMin(Pts[0].x(), Pts[2].x());
2259         region->extents.setLeft(x);
2260         int y = qMin(Pts[0].y(), Pts[2].y());
2261         region->extents.setTop(y);
2262         region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
2263         region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
2264         if ((region->extents.left() <= region->extents.right()) &&
2265             (region->extents.top() <= region->extents.bottom())) {
2266             region->numRects = 1;
2267             region->rects.resize(1);
2268             region->rects[0] = region->extents;
2269             region->innerRect = region->extents;
2270             region->innerArea = region->innerRect.width() * region->innerRect.height();
2271         }
2272         return region;
2273     }
2274
2275     if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
2276         return 0;
2277
2278     pts = FirstPtBlock.pts;
2279     CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
2280     pSLL = ET.scanlines.next;
2281     curPtBlock = &FirstPtBlock;
2282
2283     if (rule == EvenOddRule) {
2284         /*
2285          *  for each scanline
2286          */
2287         for (y = ET.ymin; y < ET.ymax; ++y) {
2288             /*
2289              *  Add a new edge to the active edge table when we
2290              *  get to the next edge.
2291              */
2292             if (pSLL && y == pSLL->scanline) {
2293                 loadAET(&AET, pSLL->edgelist);
2294                 pSLL = pSLL->next;
2295             }
2296             pPrevAET = &AET;
2297             pAET = AET.next;
2298
2299             /*
2300              *  for each active edge
2301              */
2302             while (pAET) {
2303                 pts->setX(pAET->bres.minor_axis);
2304                 pts->setY(y);
2305                 ++pts;
2306                 ++iPts;
2307
2308                 /*
2309                  *  send out the buffer
2310                  */
2311                 if (iPts == NUMPTSTOBUFFER) {
2312                     tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
2313                     curPtBlock->next = tmpPtBlock;
2314                     curPtBlock = tmpPtBlock;
2315                     pts = curPtBlock->pts;
2316                     ++numFullPtBlocks;
2317                     iPts = 0;
2318                 }
2319                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
2320             }
2321             InsertionSort(&AET);
2322         }
2323     } else {
2324         /*
2325          *  for each scanline
2326          */
2327         for (y = ET.ymin; y < ET.ymax; ++y) {
2328             /*
2329              *  Add a new edge to the active edge table when we
2330              *  get to the next edge.
2331              */
2332             if (pSLL && y == pSLL->scanline) {
2333                 loadAET(&AET, pSLL->edgelist);
2334                 computeWAET(&AET);
2335                 pSLL = pSLL->next;
2336             }
2337             pPrevAET = &AET;
2338             pAET = AET.next;
2339             pWETE = pAET;
2340
2341             /*
2342              *  for each active edge
2343              */
2344             while (pAET) {
2345                 /*
2346                  *  add to the buffer only those edges that
2347                  *  are in the Winding active edge table.
2348                  */
2349                 if (pWETE == pAET) {
2350                     pts->setX(pAET->bres.minor_axis);
2351                     pts->setY(y);
2352                     ++pts;
2353                     ++iPts;
2354
2355                     /*
2356                      *  send out the buffer
2357                      */
2358                     if (iPts == NUMPTSTOBUFFER) {
2359                         tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
2360                         curPtBlock->next = tmpPtBlock;
2361                         curPtBlock = tmpPtBlock;
2362                         pts = curPtBlock->pts;
2363                         ++numFullPtBlocks;
2364                         iPts = 0;
2365                     }
2366                     pWETE = pWETE->nextWETE;
2367                 }
2368                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
2369             }
2370
2371             /*
2372              *  recompute the winding active edge table if
2373              *  we just resorted or have exited an edge.
2374              */
2375             if (InsertionSort(&AET) || fixWAET) {
2376                 computeWAET(&AET);
2377                 fixWAET = false;
2378             }
2379         }
2380     }
2381     FreeStorage(SLLBlock.next);
2382     PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2383     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2384         tmpPtBlock = curPtBlock->next;
2385         free(curPtBlock);
2386         curPtBlock = tmpPtBlock;
2387     }
2388     free(pETEs);
2389     return region;
2390 }
2391 // END OF PolyReg.c extract
2392
2393 QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap, QRegionPrivate *region)
2394 {
2395     region->vector();
2396
2397     QImage image = bitmap.toImage();
2398
2399     QRect xr;
2400
2401 #define AddSpan \
2402         { \
2403             xr.setCoords(prev1, y, x-1, y); \
2404             UnionRectWithRegion(&xr, region, *region); \
2405         }
2406
2407     const uchar zero = 0;
2408     bool little = image.format() == QImage::Format_MonoLSB;
2409
2410     int x,
2411         y;
2412     for (y = 0; y < image.height(); ++y) {
2413         uchar *line = image.scanLine(y);
2414         int w = image.width();
2415         uchar all = zero;
2416         int prev1 = -1;
2417         for (x = 0; x < w;) {
2418             uchar byte = line[x / 8];
2419             if (x > w - 8 || byte!=all) {
2420                 if (little) {
2421                     for (int b = 8; b > 0 && x < w; --b) {
2422                         if (!(byte & 0x01) == !all) {
2423                             // More of the same
2424                         } else {
2425                             // A change.
2426                             if (all!=zero) {
2427                                 AddSpan
2428                                 all = zero;
2429                             } else {
2430                                 prev1 = x;
2431                                 all = ~zero;
2432                             }
2433                         }
2434                         byte >>= 1;
2435                         ++x;
2436                     }
2437                 } else {
2438                     for (int b = 8; b > 0 && x < w; --b) {
2439                         if (!(byte & 0x80) == !all) {
2440                             // More of the same
2441                         } else {
2442                             // A change.
2443                             if (all != zero) {
2444                                 AddSpan
2445                                 all = zero;
2446                             } else {
2447                                 prev1 = x;
2448                                 all = ~zero;
2449                             }
2450                         }
2451                         byte <<= 1;
2452                         ++x;
2453                     }
2454                 }
2455             } else {
2456                 x += 8;
2457             }
2458         }
2459         if (all != zero) {
2460             AddSpan
2461         }
2462     }
2463 #undef AddSpan
2464
2465     return region;
2466 }
2467
2468 /*
2469     Constructs an empty region.
2470
2471     \sa isEmpty()
2472 */
2473
2474 QRegion::QRegion()
2475     : d(&shared_empty)
2476 {
2477     d->ref.ref();
2478 }
2479
2480 /*
2481     \overload
2482
2483     Create a region based on the rectange \a r with region type \a t.
2484
2485     If the rectangle is invalid a null region will be created.
2486
2487     \sa QRegion::RegionType
2488 */
2489
2490 QRegion::QRegion(const QRect &r, RegionType t)
2491 {
2492     if (r.isEmpty()) {
2493         d = &shared_empty;
2494         d->ref.ref();
2495     } else {
2496 //        d = new QRegionData;
2497         QRegionPrivate *rp = 0;
2498         if (t == Rectangle) {
2499 //            rp = new QRegionPrivate(r);
2500             rp = qt_allocRegion(r);
2501         } else if (t == Ellipse) {
2502             QPainterPath path;
2503             path.addEllipse(r.x(), r.y(), r.width(), r.height());
2504             QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
2505             rp = qt_allocRegion();
2506 //            rp = new QRegionPrivate;
2507             PolygonRegion(a.constData(), a.size(), EvenOddRule, rp);
2508         }
2509         d = rp;
2510         d->ref = 1;
2511 #if defined(Q_WS_X11)
2512         d->rgn = 0;
2513         d->xrectangles = 0;
2514 #elif defined(Q_WS_MAC)
2515         d->rgn = 0;
2516 #endif
2517         d->qt_rgn = rp;
2518     }
2519 }
2520
2521 /*
2522     Constructs a polygon region from the point array \a a with the fill rule
2523     specified by \a fillRule.
2524
2525     If \a fillRule is \l{Qt::WindingFill}, the polygon region is defined
2526     using the winding algorithm; if it is \l{Qt::OddEvenFill}, the odd-even fill
2527     algorithm is used.
2528
2529     \warning This constructor can be used to create complex regions that will
2530     slow down painting when used.
2531 */
2532
2533 QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
2534 {
2535     if (a.count() > 2) {
2536         //d =  new QRegionData;
2537         // QRegionPrivate *rp = new QRegionPrivate;
2538         QRegionPrivate *rp = qt_allocRegion();
2539         PolygonRegion(a.constData(), a.size(),
2540                 fillRule == Qt::WindingFill ? WindingRule : EvenOddRule, rp);
2541         d = rp;
2542         d->ref = 1;
2543 #if defined(Q_WS_X11)
2544         d->rgn = 0;
2545         d->xrectangles = 0;
2546 #elif defined(Q_WS_MAC)
2547         d->rgn = 0;
2548 #endif
2549         d->qt_rgn = rp;
2550     } else {
2551         d = &shared_empty;
2552         d->ref.ref();
2553     }
2554 }
2555
2556
2557 /*
2558     Constructs a new region which is equal to region \a r.
2559 */
2560
2561 QRegion::QRegion(const QRegion &r)
2562 {
2563     d = r.d;
2564     d->ref.ref();
2565 }
2566
2567
2568 /*
2569     Constructs a region from the bitmap \a bm.
2570
2571     The resulting region consists of the pixels in bitmap \a bm that
2572     are Qt::color1, as if each pixel was a 1 by 1 rectangle.
2573
2574     This constructor may create complex regions that will slow down
2575     painting when used. Note that drawing masked pixmaps can be done
2576     much faster using QPixmap::setMask().
2577 */
2578 QRegion::QRegion(const QBitmap &bm)
2579 {
2580     if (bm.isNull()) {
2581         d = &shared_empty;
2582         d->ref.ref();
2583     } else {
2584         // d = new QRegionData;
2585 //        QRegionPrivate *rp = new QRegionPrivate;
2586         QRegionPrivate *rp = qt_allocRegion();
2587
2588         qt_bitmapToRegion(bm, rp);
2589         d = rp;
2590         d->ref = 1;
2591 #if defined(Q_WS_X11)
2592         d->rgn = 0;
2593         d->xrectangles = 0;
2594 #elif defined(Q_WS_MAC)
2595         d->rgn = 0;
2596 #endif
2597         d->qt_rgn = rp;
2598     }
2599 }
2600
2601 void QRegion::cleanUp(QRegion::QRegionData *x)
2602 {
2603     // delete x->qt_rgn;
2604 #if defined(Q_WS_X11)
2605     if (x->rgn)
2606         XDestroyRegion(x->rgn);
2607     if (x->xrectangles)
2608         free(x->xrectangles);
2609 #elif defined(Q_WS_MAC)
2610     if (x->rgn)
2611         qt_mac_dispose_rgn(x->rgn);
2612 #endif
2613     if(x->qt_rgn) {
2614 //        delete x->qt_rgn;
2615         qt_freeRegion(x->qt_rgn);
2616     } else {
2617         delete x;
2618     }
2619 }
2620
2621 /*
2622     Destroys the region.
2623 */
2624
2625 QRegion::~QRegion()
2626 {
2627     if (!d->ref.deref())
2628         cleanUp(d);
2629 }
2630
2631
2632 /*
2633     Assigns \a r to this region and returns a reference to the region.
2634 */
2635
2636 QRegion &QRegion::operator=(const QRegion &r)
2637 {
2638     r.d->ref.ref();
2639     if (!d->ref.deref())
2640         cleanUp(d);
2641     d = r.d;
2642     return *this;
2643 }
2644
2645
2646 /*
2647     \internal
2648 */
2649
2650 QRegion QRegion::copy() const
2651 {
2652     QRegion r;
2653     QRegionData *x = 0; // new QRegionData;
2654     QRegionPrivate *rp = 0;
2655     if (d->qt_rgn)
2656 //        rp = new QRegionPrivate(*d->qt_rgn);
2657         rp = qt_allocRegion(*d->qt_rgn);
2658     else
2659         rp = qt_allocRegion();
2660     x = rp;
2661     x->qt_rgn = rp;
2662     x->ref = 1;
2663 #if defined(Q_WS_X11)
2664     x->rgn = 0;
2665     x->xrectangles = 0;
2666 #elif defined(Q_WS_MAC)
2667     x->rgn = 0;
2668 #endif
2669
2670     if (!r.d->ref.deref())
2671         cleanUp(r.d);
2672     r.d = x;
2673     return r;
2674 }
2675
2676 /*
2677     Returns true if the region is empty; otherwise returns false. An
2678     empty region is a region that contains no points.
2679
2680     Example:
2681     \snippet doc/src/snippets/code/src.gui.painting.qregion_qws.cpp 0
2682 */
2683
2684 bool QRegion::isEmpty() const
2685 {
2686     return d == &shared_empty || d->qt_rgn->numRects == 0;
2687 }
2688
2689
2690 /*
2691     Returns true if the region contains the point \a p; otherwise
2692     returns false.
2693 */
2694
2695 bool QRegion::contains(const QPoint &p) const
2696 {
2697     return PointInRegion(d->qt_rgn, p.x(), p.y());
2698 }
2699
2700 /*
2701     \overload
2702
2703     Returns true if the region overlaps the rectangle \a r; otherwise
2704     returns false.
2705 */
2706
2707 bool QRegion::contains(const QRect &r) const
2708 {
2709     if(!d->qt_rgn)
2710         return false;
2711     if(d->qt_rgn->mode == QRegionPrivate::Single)
2712         return d->qt_rgn->single.contains(r);
2713
2714     return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
2715 }
2716
2717
2718
2719 /*
2720     Translates (moves) the region \a dx along the X axis and \a dy
2721     along the Y axis.
2722 */
2723
2724 void QRegion::translate(int dx, int dy)
2725 {
2726     if ((dx == 0 && dy == 0) || isEmptyHelper(d->qt_rgn))
2727         return;
2728
2729     detach();
2730     OffsetRegion(*d->qt_rgn, dx, dy);
2731 #if defined(Q_WS_X11)
2732     if (d->xrectangles) {
2733         free(d->xrectangles);
2734         d->xrectangles = 0;
2735     }
2736 #elif defined(Q_WS_MAC)
2737     if(d->rgn) {
2738         qt_mac_dispose_rgn(d->rgn);
2739         d->rgn = 0;
2740     }
2741 #endif
2742 }
2743
2744 /*
2745     \fn QRegion QRegion::unite(const QRegion &r) const
2746     \obsolete
2747
2748     Use united(\a r) instead.
2749 */
2750
2751 /*
2752     \fn QRegion QRegion::united(const QRegion &r) const
2753     \since 4.2
2754
2755     Returns a region which is the union of this region and \a r.
2756
2757     \img runion.png Region Union
2758
2759     The figure shows the union of two elliptical regions.
2760
2761     \sa intersected(), subtracted(), xored()
2762 */
2763
2764 QRegion QRegion::unite(const QRegion &r) const
2765 {
2766     if (isEmptyHelper(d->qt_rgn))
2767         return r;
2768     if (isEmptyHelper(r.d->qt_rgn))
2769         return *this;
2770
2771     if (d->qt_rgn->contains(*r.d->qt_rgn)) {
2772         return *this;
2773     } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
2774         return r;
2775     } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
2776         QRegion result(*this);
2777         result.detach();
2778         result.d->qt_rgn->append(r.d->qt_rgn);
2779         return result;
2780     } else if (r.d->qt_rgn->canAppend(d->qt_rgn)) {
2781         QRegion result(r);
2782         result.detach();
2783         result.d->qt_rgn->append(d->qt_rgn);
2784         return result;
2785     } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
2786         return *this;
2787     } else {
2788         QRegion result;
2789         result.detach();
2790         UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
2791         return result;
2792     }
2793 }
2794
2795 QRegion& QRegion::operator+=(const QRegion &r)
2796 {
2797     if (isEmptyHelper(d->qt_rgn))
2798         return *this = r;
2799     if (isEmptyHelper(r.d->qt_rgn))
2800         return *this;
2801
2802     if (d->qt_rgn->contains(*r.d->qt_rgn)) {
2803         return *this;
2804     } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
2805         return *this = r;
2806     } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
2807         detach();
2808         d->qt_rgn->append(r.d->qt_rgn);
2809         return *this;
2810     } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
2811         detach();
2812         d->qt_rgn->prepend(r.d->qt_rgn);
2813         return *this;
2814     } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
2815         return *this;
2816     }
2817
2818     return *this = unite(r);
2819 }
2820
2821 /*
2822     \fn QRegion QRegion::intersect(const QRegion &r) const
2823     \obsolete
2824
2825     Use intersected(\a r) instead.
2826 */
2827
2828 /*
2829     \fn QRegion QRegion::intersected(const QRegion &r) const
2830     \since 4.2
2831
2832     Returns a region which is the intersection of this region and \a r.
2833
2834     \img rintersect.png Region Intersection
2835
2836     The figure shows the intersection of two elliptical regions.
2837 */
2838
2839 QRegion QRegion::intersect(const QRegion &r) const
2840 {
2841     if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn)
2842         || !EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
2843         return QRegion();
2844
2845     /* this is fully contained in r */
2846     if (r.d->qt_rgn->contains(*d->qt_rgn))
2847         return *this;
2848
2849     /* r is fully contained in this */
2850     if (d->qt_rgn->contains(*r.d->qt_rgn))
2851         return r;
2852
2853     if(r.d->qt_rgn->mode == QRegionPrivate::Single &&
2854        d->qt_rgn->mode == QRegionPrivate::Single)
2855         return QRegion(r.d->qt_rgn->single.intersected(d->qt_rgn->single));
2856 #ifdef QT_GREENPHONE_OPT
2857     else if(r.d->qt_rgn->mode == QRegionPrivate::Single)
2858         return intersect(r.d->qt_rgn->single);
2859     else if(d->qt_rgn->mode == QRegionPrivate::Single)
2860         return r.intersect(d->qt_rgn->single);
2861 #endif
2862
2863     QRegion result;
2864     result.detach();
2865     miRegionOp(*result.d->qt_rgn, d->qt_rgn, r.d->qt_rgn, miIntersectO, 0, 0);
2866
2867     /*
2868      * Can't alter dest's extents before we call miRegionOp because
2869      * it might be one of the source regions and miRegionOp depends
2870      * on the extents of those regions being the same. Besides, this
2871      * way there's no checking against rectangles that will be nuked
2872      * due to coalescing, so we have to examine fewer rectangles.
2873      */
2874     miSetExtents(*result.d->qt_rgn);
2875     return result;
2876 }
2877
2878 #ifdef QT_GREENPHONE_OPT
2879 /*
2880   \overload
2881   */
2882 QRegion QRegion::intersect(const QRect &r) const
2883 {
2884     // No intersection
2885     if(r.isEmpty() || isEmpty() || !EXTENTCHECK(&r, &d->qt_rgn->extents))
2886         return QRegion();
2887
2888     // This is fully contained in r
2889     if(CONTAINSCHECK(r, d->qt_rgn->extents))
2890         return *this;
2891
2892     // r is fully contained in this
2893     if(CONTAINSCHECK(d->qt_rgn->innerRect, r))
2894         return QRegion(r);
2895
2896     if(d->qt_rgn->mode == QRegionPrivate::Single) {
2897         return QRegion(d->qt_rgn->single & r);
2898     } else {
2899         QRegion rv(*this);
2900         rv.detach();
2901
2902         rv.d->qt_rgn->extents &= r;
2903         rv.d->qt_rgn->innerRect &= r;
2904         rv.d->qt_rgn->innerArea = rv.d->qt_rgn->innerRect.height() *
2905                                   rv.d->qt_rgn->innerRect.width();
2906
2907         int numRects = 0;
2908         for(int ii = 0; ii < rv.d->qt_rgn->numRects; ++ii) {
2909             QRect result = rv.d->qt_rgn->rects[ii] & r;
2910             if(!result.isEmpty())
2911                 rv.d->qt_rgn->rects[numRects++] = result;
2912         }
2913         rv.d->qt_rgn->numRects = numRects;
2914         return rv;
2915     }
2916 }
2917
2918 /*
2919    \overload
2920  */
2921 const QRegion QRegion::operator&(const QRect &r) const
2922 {
2923     return intersect(r);
2924 }
2925
2926 /*
2927    \overload
2928  */
2929 QRegion& QRegion::operator&=(const QRect &r)
2930 {
2931     if(isEmpty() || CONTAINSCHECK(r, d->qt_rgn->extents)) {
2932         // Do nothing
2933     } else if(r.isEmpty() || !EXTENTCHECK(&r, &d->qt_rgn->extents)) {
2934         *this = QRegion();
2935     } else if(CONTAINSCHECK(d->qt_rgn->innerRect, r)) {
2936         *this = QRegion(r);
2937     } else {
2938         detach();
2939         if(d->qt_rgn->mode == QRegionPrivate::Single) {
2940             QRect result = d->qt_rgn->single & r;
2941             d->qt_rgn->single = result;
2942             d->qt_rgn->extents = result;
2943             d->qt_rgn->innerRect = result;
2944             d->qt_rgn->innerArea = result.height() * result.width();
2945         } else {
2946             d->qt_rgn->extents &= r;
2947             d->qt_rgn->innerRect &= r;
2948             d->qt_rgn->innerArea = d->qt_rgn->innerRect.height() *
2949                                    d->qt_rgn->innerRect.width();
2950
2951             int numRects = 0;
2952             for(int ii = 0; ii < d->qt_rgn->numRects; ++ii) {
2953                 QRect result = d->qt_rgn->rects[ii] & r;
2954                 if(!result.isEmpty())
2955                     d->qt_rgn->rects[numRects++] = result;
2956             }
2957             d->qt_rgn->numRects = numRects;
2958         }
2959     }
2960     return *this;
2961 }
2962 #endif
2963
2964 /*
2965     \fn QRegion QRegion::subtract(const QRegion &r) const
2966     \obsolete
2967
2968     Use subtracted(\a r) instead.
2969 */
2970
2971 /*
2972     \fn QRegion QRegion::subtracted(const QRegion &r) const
2973     \since 4.2
2974
2975     Returns a region which is \a r subtracted from this region.
2976
2977     \img rsubtract.png Region Subtraction
2978
2979     The figure shows the result when the ellipse on the right is
2980     subtracted from the ellipse on the left (\c {left - right}).
2981
2982     \sa intersected(), united(), xored()
2983 */
2984
2985 QRegion QRegion::subtract(const QRegion &r) const
2986 {
2987     if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn))
2988         return *this;
2989     if (r.d->qt_rgn->contains(*d->qt_rgn))
2990         return QRegion();
2991     if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
2992         return *this;
2993     if (EqualRegion(d->qt_rgn, r.d->qt_rgn))
2994         return QRegion();
2995
2996     QRegion result;
2997     result.detach();
2998     SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
2999     return result;
3000 }
3001
3002 /*
3003     \fn QRegion QRegion::eor(const QRegion &r) const
3004     \obsolete
3005
3006     Use xored(\a r) instead.
3007 */
3008
3009 /*
3010     \fn QRegion QRegion::xored(const QRegion &r) const
3011     \since 4.2
3012
3013     Returns a region which is the exclusive or (XOR) of this region
3014     and \a r.
3015
3016     \img rxor.png Region XORed
3017
3018     The figure shows the exclusive or of two elliptical regions.
3019
3020     \sa intersected(), united(), subtracted()
3021 */
3022
3023 QRegion QRegion::eor(const QRegion &r) const
3024 {
3025     if (isEmptyHelper(d->qt_rgn)) {
3026         return r;
3027     } else if (isEmptyHelper(r.d->qt_rgn)) {
3028         return *this;
3029     } else if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents)) {
3030         return (*this + r);
3031     } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
3032         return QRegion();
3033     } else {
3034         QRegion result;
3035         result.detach();
3036         XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
3037         return result;
3038     }
3039 }
3040
3041 /*
3042     Returns the bounding rectangle of this region. An empty region
3043     gives a rectangle that is QRect::isNull().
3044 */
3045
3046 QRect QRegion::boundingRect() const
3047 {
3048     if (isEmpty())
3049         return QRect();
3050     return d->qt_rgn->extents;
3051 }
3052
3053 /* \internal
3054     Returns true if \a rect is guaranteed to be fully contained in \a region.
3055     A false return value does not guarantee the opposite.
3056 */
3057 bool qt_region_strictContains(const QRegion &region, const QRect &rect)
3058 {
3059     if (isEmptyHelper(region.d->qt_rgn) || !rect.isValid())
3060         return false;
3061
3062 #if 0 // TEST_INNERRECT
3063     static bool guard = false;
3064     if (guard)
3065         return QRect();
3066     guard = true;
3067     QRegion inner = region.d->qt_rgn->innerRect;
3068     Q_ASSERT((inner - region).isEmpty());
3069     guard = false;
3070
3071     int maxArea = 0;
3072     for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
3073         const QRect r = region.d->qt_rgn->rects.at(i);
3074         if (r.width() * r.height() > maxArea)
3075             maxArea = r.width() * r.height();
3076     }
3077
3078     if (maxArea > region.d->qt_rgn->innerArea) {
3079         qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
3080     }
3081     Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
3082 #endif
3083
3084     const QRect r1 = region.d->qt_rgn->innerRect;
3085     return (rect.left() >= r1.left() && rect.right() <= r1.right()
3086             && rect.top() >= r1.top() && rect.bottom() <= r1.bottom());
3087 }
3088
3089 /*
3090     Returns an array of non-overlapping rectangles that make up the
3091     region.
3092
3093     The union of all the rectangles is equal to the original region.
3094 */
3095 QVector<QRect> QRegion::rects() const
3096 {
3097     if (d->qt_rgn) {
3098         d->qt_rgn->vector();
3099         d->qt_rgn->rects.resize(d->qt_rgn->numRects);
3100         return d->qt_rgn->rects;
3101     } else {
3102         return QVector<QRect>();
3103     }
3104 }
3105
3106 /*
3107   \fn void QRegion::setRects(const QRect *rects, int number)
3108
3109   Sets the region using the array of rectangles specified by \a rects and
3110   \a number.
3111   The rectangles \e must be optimally Y-X sorted and follow these restrictions:
3112
3113   \list
3114   \o The rectangles must not intersect.
3115   \o All rectangles with a given top coordinate must have the same height.
3116   \o No two rectangles may abut horizontally (they should be combined
3117      into a single wider rectangle in that case).
3118   \o The rectangles must be sorted in ascending order, with Y as the major
3119      sort key and X as the minor sort key.
3120   \endlist
3121   \omit
3122   Only some platforms have these restrictions (Qt for Embedded Linux, X11 and Mac OS X).
3123   \endomit
3124 */
3125 void QRegion::setRects(const QRect *rects, int num)
3126 {
3127     *this = QRegion();
3128     if (!rects || num == 0 || (num == 1 && rects->isEmpty()))
3129         return;
3130
3131     detach();
3132
3133     if(num == 1) {
3134         d->qt_rgn->single = *rects;
3135         d->qt_rgn->mode = QRegionPrivate::Single;
3136         d->qt_rgn->numRects = num;
3137         d->qt_rgn->extents = *rects;
3138         d->qt_rgn->innerRect = *rects;
3139     } else {
3140         d->qt_rgn->mode = QRegionPrivate::Vector;
3141         d->qt_rgn->rects.resize(num);
3142         d->qt_rgn->numRects = num;
3143         int left = INT_MAX,
3144             right = INT_MIN,
3145             top = INT_MAX,
3146             bottom = INT_MIN;
3147         for (int i = 0; i < num; ++i) {
3148             const QRect &rect = rects[i];
3149             d->qt_rgn->rects[i] = rect;
3150             left = qMin(rect.left(), left);
3151             right = qMax(rect.right(), right);
3152             top = qMin(rect.top(), top);
3153             bottom = qMax(rect.bottom(), bottom);
3154             d->qt_rgn->updateInnerRect(rect);
3155         }
3156         d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
3157     }
3158 }
3159
3160 /*
3161     Returns true if the region is equal to \a r; otherwise returns
3162     false.
3163 */
3164
3165 bool QRegion::operator==(const QRegion &r) const
3166 {
3167     if (!d->qt_rgn || !r.d->qt_rgn)
3168         return r.d->qt_rgn == d->qt_rgn;
3169
3170     if (d == r.d)
3171         return true;
3172     else
3173         return EqualRegion(d->qt_rgn, r.d->qt_rgn);
3174 }
3175
3176 #ifdef QT_GREENPHONE_OPT
3177 bool QRegion::isRect() const
3178 {
3179     return d->qt_rgn && d->qt_rgn->mode == QRegionPrivate::Single;
3180 }
3181 #endif
3182
3183 QT_END_NAMESPACE