Qt 4.8
qregion_qws.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
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 
57 
59 {
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;
101  QRect extents;
102  QRect innerRect;
103  union {
104  int innerArea;
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 
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 
174 
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 
203 {
204  qt_nextRegionLock.lock();
205  rp->next = qt_nextRegionPtr;
206  qt_nextRegionPtr = rp;
207  qt_nextRegionLock.unlock();
208 }
209 
211 {
213  return new (mem) QRegionPrivate;
214 }
215 
217 {
219  return new (mem) QRegionPrivate(r);
220 }
221 
223 {
225  return new (mem) QRegionPrivate(r);
226 }
227 
229 {
230  rp->~QRegionPrivate();
232 // delete rp;
233 }
234 
235 static inline bool isEmptyHelper(const QRegionPrivate *preg)
236 {
237  return !preg || preg->numRects == 0;
238 }
239 
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 
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)
354 # include "qregion_x11.cpp"
356 #elif defined(Q_WS_MAC)
358 # include "qregion_mac.cpp"
360 #elif defined(Q_WS_QWS)
361 static QRegionPrivate 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 
436 #include <limits.h>
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 {
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 
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 
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;
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;
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 
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 
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 \link Qt::WindingFill \endlink, the polygon region is defined
2526  using the winding algorithm; if it is \link Qt::OddEvenFill \endlink, 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;
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;
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 
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 
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 
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 
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  */
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 
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 */
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  <li> The rectangles must not intersect.
3115  <li> All rectangles with a given top coordinate must have the same height.
3116  <li> No two rectangles may abut horizontally (they should be combined
3117  into a single wider rectangle in that case).
3118  <li> 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 
static bool isEmptyHelper(const QRegionPrivate *preg)
void detach()
Definition: qregion.cpp:300
struct _ScanLineList * next
Definition: qregion.cpp:3136
double d
Definition: qnumeric_p.h:62
void append(const QRect *r)
Definition: qregion.cpp:1460
QImage toImage() const
Converts the pixmap to a QImage.
Definition: qpixmap.cpp:542
void setHeight(int h)
Sets the height of the rectangle to the given height.
Definition: qrect.h:445
void setBottom(int pos)
Sets the bottom edge of the rectangle to the given y coordinate.
Definition: qrect.h:267
QRegionPrivate(const QRect &r)
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
The QSemaphore class provides a general counting semaphore.
Definition: qsemaphore.h:57
~QRegion()
Destroys the region.
Definition: qregion.cpp:4057
The QAtomicInt class provides platform-independent atomic operations on integers. ...
Definition: qatomic.h:55
The QPainterPath class provides a container for painting operations, enabling graphical shapes to be ...
Definition: qpainterpath.h:67
static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
static QRegionPrivate * PolygonRegion(const QPoint *Pts, int Count, int rule, QRegionPrivate *region)
struct _ScanLineListBlock ScanLineListBlock
bool testAndSetAcquire(int expectedValue, int newValue)
Atomic test-and-set.
int minor_axis
Definition: qregion.cpp:3055
struct _POINTBLOCK * next
Definition: qregion.cpp:1890
FillRule
Definition: qnamespace.h:1485
static bool isRect(const T *pts, int elementCount)
struct _EdgeTableEntry * back
Definition: qregion.cpp:3127
static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
static QRegionPrivate * qt_allocRegion()
int left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:240
int width() const
Returns the width of the rectangle.
Definition: qrect.h:303
static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
#define QT_END_INCLUDE_NAMESPACE
This macro is equivalent to QT_BEGIN_NAMESPACE.
Definition: qglobal.h:92
static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock, POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
QRegionPrivate * qt_rgn
Definition: qregion.h:211
void release(int n=1)
Releases n resources guarded by the semaphore.
Definition: qsemaphore.cpp:161
long ASN1_INTEGER_get ASN1_INTEGER * a
QRect intersected(const QRect &other) const
Returns the intersection of this rectangle and the given rectangle.
Definition: qrect.h:481
QRect boundingRect() const
Returns the bounding rectangle of this region.
Definition: qregion.cpp:4363
#define RectangleIn
The QPolygon class provides a vector of points using integer precision.
Definition: qpolygon.h:60
QPoint * pts
Definition: qregion.cpp:1889
QRegion subtract(const QRegion &r) const
Use subtracted(r) instead.
Definition: qregion.cpp:4320
ScanLineList scanlines
Definition: qregion.cpp:3143
int height() const
Returns the height of the rectangle.
Definition: qrect.h:306
#define EXTENTCHECK(r1, r2)
int bottom() const
Returns the y-coordinate of the rectangle&#39;s bottom edge.
Definition: qrect.h:249
QRegion()
Constructs an empty region.
Definition: qregion.cpp:3961
static void miSetExtents(QRegionPrivate &dest)
static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
#define Q_BASIC_ATOMIC_INITIALIZER(a)
Definition: qbasicatomic.h:218
bool operator==(const QRegion &r) const
Returns true if the region is equal to r; otherwise returns false.
Definition: qregion.cpp:4467
static void CreateETandAET(register int count, register const QPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
static struct QRegionData shared_empty
Definition: qregion.h:218
struct _EdgeTableEntry * nextWETE
Definition: qregion.cpp:3128
struct _ScanLineList ScanLineList
Q_CORE_EXPORT QTextStream & right(QTextStream &s)
Format format() const
Returns the format of the image.
Definition: qimage.cpp:2305
bool testAndSetRelease(int expectedValue, int newValue)
Atomic test-and-set.
QRegion copy() const
Definition: qregion.cpp:4077
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
bool tryLock()
Definition: qregion_qws.cpp:73
static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, int y1, int y2)
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
BRESINFO bres
Definition: qregion.cpp:3125
const QRegion operator &(const QRegion &r) const
static QFastMutex qt_nextRegionLock
Q_CORE_EXPORT void qDebug(const char *,...)
#define MEMCHECK(dest, rect, firstrect)
unsigned char uchar
Definition: qglobal.h:994
The QBitmap class provides monochrome (1-bit depth) pixmaps.
Definition: qbitmap.h:55
struct _ScanLineListBlock * next
Definition: qregion.cpp:3156
static QRegionPrivate * qt_allocRegionMemory()
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
QRegionPrivate * qt_bitmapToRegion(const QBitmap &bitmap, QRegionPrivate *region)
static bool isEmpty(const char *str)
QRegionPrivate(const QRegionPrivate &r)
#define MERGERECT(r)
bool canPrepend(const QRect *r) const
Definition: qregion.cpp:1691
QRegion & operator+=(const QRegion &r)
Applies the united() function to this region and r and assigns the result to this region...
Definition: qregion.cpp:4158
The Rectangle item provides a filled rectangle with an optional border.
static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
bool isEmpty() const
Returns true if the region is empty; otherwise returns false.
Definition: qregion.cpp:4098
static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS, register QRegionPrivate &dest)
static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
void setTop(int pos)
Sets the top edge of the rectangle to the given y coordinate.
Definition: qrect.h:261
void updateInnerRect(const QRect &rect)
bool deref()
Atomically decrements the value of this QAtomicInt.
QRegion intersect(const QRegion &r) const
Use intersected(r) instead.
Definition: qregion.cpp:4249
static void computeWAET(register EdgeTableEntry *AET)
QRegionPrivate * next
void setRight(int pos)
Sets the right edge of the rectangle to the given x coordinate.
Definition: qrect.h:264
The QImage class provides a hardware-independent image representation that allows direct access to th...
Definition: qimage.h:87
static void OffsetRegion(register QRegionPrivate &region, register int x, register int y)
bool contains(const QPoint &p) const
Returns true if the region contains the point p; otherwise returns false.
Definition: qregion.cpp:4104
unsigned int uint
Definition: qglobal.h:996
enum QRegionPrivate::@253 mode
The QRegion class specifies a clip region for a painter.
Definition: qregion.h:68
#define NUMPTSTOBUFFER
void setCoords(int x1, int y1, int x2, int y2)
Sets the coordinates of the rectangle&#39;s top-left corner to (x1, y1), and the coordinates of its botto...
Definition: qrect.h:416
EdgeTableEntry * edgelist
Definition: qregion.cpp:3135
QRegion eor(const QRegion &r) const
Use xored(r) instead.
Definition: qregion.cpp:4345
bool canAppend(const QRect *r) const
Definition: qregion.cpp:1669
void(* OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)
bool contains(const QPoint &p, bool proper=false) const
Returns true if the given point is inside or on the edge of the rectangle, otherwise returns false...
Definition: qrect.cpp:1101
static int InsertionSort(register EdgeTableEntry *AET)
QRegion & operator=(const QRegion &)
Assigns r to this region and returns a reference to the region.
Definition: qregion.cpp:4064
int fetchAndAddAcquire(int valueToAdd)
Atomic fetch-and-add.
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
#define SMALL_COORDINATE
static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
static void cleanUp(QRegionData *x)
Definition: qregion.cpp:4042
QVector< QRect > rects
Definition: qregion.cpp:1227
QRegion unite(const QRegion &r) const
Use united(r) instead.
Definition: qregion.cpp:4125
bool isEmpty() const
Returns true if the rectangle is empty, otherwise returns false.
Definition: qrect.h:234
void acquire(int n=1)
Tries to acquire n resources guarded by the semaphore.
Definition: qsemaphore.cpp:142
static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2, OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func, NonOverlapFunc nonOverlap2Func)
#define SLLSPERBLOCK
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
void setY(int y)
Sets the y coordinate of this point to the given y coordinate.
Definition: qpoint.h:137
int top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:243
int width() const
Returns the width of the image.
Definition: qimage.cpp:1557
void setRects(const QRect *rect, int num)
Sets the region using the array of rectangles specified by rects and number.
Definition: qregion.cpp:4424
void qt_freeRegion(QRegionPrivate *rp)
int right() const
Returns the x-coordinate of the rectangle&#39;s right edge.
Definition: qrect.h:246
bool qt_region_strictContains(const QRegion &region, const QRect &rect)
void setLeft(int pos)
Sets the left edge of the rectangle to the given x coordinate.
Definition: qrect.h:258
int y() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:255
#define RectangleOut
static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
int x() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:252
void(* NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
The QPoint class defines a point in the plane using integer precision.
Definition: qpoint.h:53
QVector< QRect > rects() const
Returns an array of non-overlapping rectangles that make up the region.
Definition: qregion.cpp:4412
void setWidth(int w)
Sets the width of the rectangle to the given width.
Definition: qrect.h:442
QAtomicInt contenders
Definition: qregion_qws.cpp:60
static const int zero
The QRect class defines a rectangle in the plane using integer precision.
Definition: qrect.h:58
struct _EdgeTableEntry * next
Definition: qregion.cpp:3126
struct _EdgeTableEntry EdgeTableEntry
#define LARGE_COORDINATE
int height() const
Returns the height of the image.
Definition: qimage.cpp:1572
QRegionPrivate & operator=(const QRegionPrivate &r)
bool contains(const T &t) const
Returns true if the vector contains an occurrence of value; otherwise returns false.
Definition: qvector.h:731
int y() const
Returns the y coordinate of this point.
Definition: qpoint.h:131
#define QT_BEGIN_INCLUDE_NAMESPACE
This macro is equivalent to QT_END_NAMESPACE.
Definition: qglobal.h:91
QList< QPolygonF > toSubpathPolygons(const QMatrix &matrix=QMatrix()) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
QRegion & operator &=(const QRegion &r)
static void qt_freeRegionMemory(QRegionPrivate *rp)
void translate(int dx, int dy)
Translates (moves) the region dx along the X axis and dy along the Y axis.
Definition: qregion.cpp:4116
void lock()
Definition: qregion_qws.cpp:66
#define RectanglePart
T * data()
Returns a pointer to the data stored in the vector.
Definition: qvector.h:152
#define WindingRule
const T * constData() const
Returns a const pointer to the data stored in the vector.
Definition: qvector.h:154
int x() const
Returns the x coordinate of this point.
Definition: qpoint.h:128
QSemaphore semaphore
Definition: qregion_qws.cpp:61
bool isNull() const
Returns true if this is a null pixmap; otherwise returns false.
Definition: qpixmap.cpp:615
bool isValid() const
Returns true if the rectangle is valid, otherwise returns false.
Definition: qrect.h:237
#define AddSpan
void translate(int dx, int dy)
Moves the rectangle dx along the x axis and dy along the y axis, relative to the current position...
Definition: qrect.h:312
struct QRegionData * d
Definition: qregion.h:217
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres)
Q_CORE_EXPORT QTextStream & left(QTextStream &s)
void setX(int x)
Sets the x coordinate of this point to the given x coordinate.
Definition: qpoint.h:134
#define Q_UNUSED(x)
Indicates to the compiler that the parameter with the specified name is not used in the body of a fun...
Definition: qglobal.h:1729
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, register int y1, register int y2)
QBasicAtomicInt ref
Definition: qregion.h:201
void unlock()
Definition: qregion_qws.cpp:77
#define INT_MAX
static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source, QRegionPrivate &dest)
void prepend(const QRect *r)
Definition: qregion.cpp:1637
#define CONTAINSCHECK(r1, r2)
Definition: qregion_qws.cpp:89
bool contains(const QRegionPrivate &r) const
uchar * scanLine(int)
Returns a pointer to the pixel data at the scanline with index i.
Definition: qimage.cpp:1886
void addEllipse(const QRectF &rect)
Creates an ellipse within the specified boundingRectangle and adds it to the painter path as a closed...
static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
#define EvenOddRule
struct _POINTBLOCK POINTBLOCK
static int area(const QSize &s)
Definition: qicon.cpp:155
void qt_mac_dispose_rgn(RgnHandle r)
static void FreeStorage(register ScanLineListBlock *pSLLBlock)
static QRegionPrivate * qt_nextRegionPtr