qregion_qws.cpp File Reference

#include "qregion.h"
#include "qpainterpath.h"
#include "qpolygon.h"
#include "qbuffer.h"
#include "qimage.h"
#include <qdebug.h>
#include "qbitmap.h"
#include <stdlib.h>
#include <qatomic.h>
#include <qsemaphore.h>
#include "qregion_x11.cpp"
#include <limits.h>

Go to the source code of this file.

Classes
struct	_EdgeTableEntry
struct	_POINTBLOCK
struct	_ScanLineList
struct	_ScanLineListBlock
struct	BRESINFO
struct	EdgeTable
class	QFastMutex
struct	QRegionPrivate

Macros
#define	_XREGION_H
#define	AddSpan
#define	BRESINCRPGON(d, minval, m, m1, incr1, incr2)
#define	BRESINCRPGONSTRUCT(bres)   BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
#define	BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2)
#define	BRESINITPGONSTRUCT(dmaj, min1, min2, bres)
#define	CLOCKWISE   1
#define	CONTAINSCHECK(r1, r2)
#define	COUNTERCLOCKWISE   -1
#define	EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
#define	EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
#define	EvenOddRule   0
#define	EXTENTCHECK(r1, r2)
#define	EXTENTS(r, idRect)
#define	LARGE_COORDINATE   1000000
#define	MEMCHECK(dest, rect, firstrect)
#define	MERGERECT(r)
#define	NUMPTSTOBUFFER   200
#define	private   public
#define	RectangleIn   1
#define	RectangleOut   0
#define	RectanglePart   2
#define	SLLSPERBLOCK   25
#define	SMALL_COORDINATE   -LARGE_COORDINATE
#define	WindingRule   1

Typedefs
typedef struct _EdgeTableEntry	EdgeTableEntry
typedef void(*	NonOverlapFunc) (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
typedef 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)
typedef struct _POINTBLOCK	POINTBLOCK
typedef struct _ScanLineList	ScanLineList
typedef struct _ScanLineListBlock	ScanLineListBlock

Functions
static void	computeWAET (register EdgeTableEntry *AET)
static void	CreateETandAET (register int count, register const QPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
static bool	EqualRegion (const QRegionPrivate *r1, const QRegionPrivate *r2)
static void	FreeStorage (register ScanLineListBlock *pSLLBlock)
static void	InsertEdgeInET (EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
static int	InsertionSort (register EdgeTableEntry *AET)
static bool	isEmptyHelper (const QRegionPrivate *preg)
static void	loadAET (register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
static int	miCoalesce (register QRegionPrivate &dest, int prevStart, int curStart)
static void	miIntersectO (register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End, register const QRect *r2, const QRect *r2End, int y1, int y2)
static void	miRegionOp (register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2, OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func, NonOverlapFunc nonOverlap2Func)
static void	miSetExtents (QRegionPrivate &dest)
static void	miSubtractNonO1 (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
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)
static void	miUnionNonO (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)
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)
static void	OffsetRegion (register QRegionPrivate &region, register int x, register int y)
static bool	PointInRegion (QRegionPrivate *pRegion, int x, int y)
static QRegionPrivate *	PolygonRegion (const QPoint *Pts, int Count, int rule, QRegionPrivate *region)
static void	PtsToRegion (register int numFullPtBlocks, register int iCurPtBlock, POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
static QRegionPrivate *	qt_allocRegion ()
static QRegionPrivate *	qt_allocRegion (const QRect &r)
static QRegionPrivate *	qt_allocRegion (const QRegionPrivate &r)
static QRegionPrivate *	qt_allocRegionMemory ()
QRegionPrivate *	qt_bitmapToRegion (const QBitmap &bitmap, QRegionPrivate *region)
void	qt_freeRegion (QRegionPrivate *rp)
static void	qt_freeRegionMemory (QRegionPrivate *rp)
bool	qt_region_strictContains (const QRegion &region, const QRect &rect)
static bool	RectInRegion (register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
static void	SubtractRegion (QRegionPrivate *regM, QRegionPrivate *regS, register QRegionPrivate &dest)
static void	UnionRectWithRegion (register const QRect *rect, const QRegionPrivate *source, QRegionPrivate &dest)
static void	UnionRegion (const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
static void	XorRegion (QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)

Variables
static QFastMutex	qt_nextRegionLock
static QRegionPrivate *	qt_nextRegionPtr = 0

Macro Definition Documentation

_XREGION_H

#define _XREGION_H

Definition at line 433 of file qregion_qws.cpp.

AddSpan

#define AddSpan

Value:

{ \
            xr.setCoords(prev1, y, x-1, y); \
            UnionRectWithRegion(&xr, region, *region); \
        }

Referenced by qt_bitmapToRegion().

BRESINCRPGON

#define BRESINCRPGON	(		d,
			minval,
			m,
			m1,
			incr1,
			incr2
	)

Value:

{ \
    if (m1 > 0) { \
        if (d > 0) { \
            minval += m1; \
            d += incr1; \
        } \
        else { \
            minval += m; \
            d += incr2; \
        } \
    } else {\
        if (d >= 0) { \
            minval += m1; \
            d += incr1; \
        } \
        else { \
            minval += m; \
            d += incr2; \
        } \
    } \
}

Definition at line 1613 of file qregion_qws.cpp.

BRESINCRPGONSTRUCT

#define BRESINCRPGONSTRUCT

(

bres

)

BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)

Definition at line 1655 of file qregion_qws.cpp.

BRESINITPGON

#define BRESINITPGON	(		dy,
			x1,
			x2,
			xStart,
			d,
			m,
			m1,
			incr1,
			incr2
	)

Value:

{ \
    int dx;      /* local storage */ \
\
    /* \
     *  if the edge is horizontal, then it is ignored \
     *  and assumed not to be processed.  Otherwise, do this stuff. \
     */ \
    if ((dy) != 0) { \
        xStart = (x1); \
        dx = (x2) - xStart; \
        if (dx < 0) { \
            m = dx / (dy); \
            m1 = m - 1; \
            incr1 = -2 * dx + 2 * (dy) * m1; \
            incr2 = -2 * dx + 2 * (dy) * m; \
            d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
        } else { \
            m = dx / (dy); \
            m1 = m + 1; \
            incr1 = 2 * dx - 2 * (dy) * m1; \
            incr2 = 2 * dx - 2 * (dy) * m; \
            d = -2 * m * (dy) + 2 * dx; \
        } \
    } \
}

Definition at line 1587 of file qregion_qws.cpp.

BRESINITPGONSTRUCT

#define BRESINITPGONSTRUCT	(		dmaj,
			min1,
			min2,
			bres
	)

Value:

BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
                     bres.m, bres.m1, bres.incr1, bres.incr2)

Definition at line 1651 of file qregion_qws.cpp.

Referenced by CreateETandAET().

CLOCKWISE

#define CLOCKWISE   1

Definition at line 1709 of file qregion_qws.cpp.

CONTAINSCHECK

#define CONTAINSCHECK	(		r1,
			r2
	)

Value:

((r2).left() >= (r1).left() && (r2).right() <= (r1).right() && \
     (r2).top() >= (r1).top() && (r2).bottom() <= (r1).bottom())

Definition at line 89 of file qregion_qws.cpp.

Referenced by QRegionPrivate::contains(), and qt_bitmapToRegion().

COUNTERCLOCKWISE

#define COUNTERCLOCKWISE   -1

Definition at line 1710 of file qregion_qws.cpp.

EVALUATEEDGEEVENODD

#define EVALUATEEDGEEVENODD	(		pAET,
			pPrevAET,
			y
	)

Value:

{ \
   if (pAET->ymax == y) {          /* leaving this edge */ \
      pPrevAET->next = pAET->next; \
      pAET = pPrevAET->next; \
      if (pAET) \
         pAET->back = pPrevAET; \
   } \
   else { \
      BRESINCRPGONSTRUCT(pAET->bres) \
      pPrevAET = pAET; \
      pAET = pAET->next; \
   } \
}

Definition at line 1786 of file qregion_qws.cpp.

Referenced by PolygonRegion().

EVALUATEEDGEWINDING

#define EVALUATEEDGEWINDING	(		pAET,
			pPrevAET,
			y,
			fixWAET
	)

Value:

{ \
   if (pAET->ymax == y) {          /* leaving this edge */ \
      pPrevAET->next = pAET->next; \
      pAET = pPrevAET->next; \
      fixWAET = 1; \
      if (pAET) \
         pAET->back = pPrevAET; \
   } \
   else { \
      BRESINCRPGONSTRUCT(pAET->bres) \
      pPrevAET = pAET; \
      pAET = pAET->next; \
   } \
}

Definition at line 1763 of file qregion_qws.cpp.

Referenced by PolygonRegion().

EvenOddRule

#define EvenOddRule   0

Definition at line 379 of file qregion_qws.cpp.

Referenced by PolygonRegion(), and qt_bitmapToRegion().

EXTENTCHECK

#define EXTENTCHECK	(		r1,
			r2
	)

Value:

((r1)->right() >= (r2)->left() && \
         (r1)->left() <= (r2)->right() && \
         (r1)->bottom() >= (r2)->top() && \
         (r1)->top() <= (r2)->bottom())

Definition at line 443 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), RectInRegion(), SubtractRegion(), and XorRegion().

EXTENTS

#define EXTENTS	(		r,
			idRect
	)

Value:

{\
            if((r)->left() < (idRect)->extents.left())\
              (idRect)->extents.setLeft((r)->left());\
            if((r)->top() < (idRect)->extents.top())\
              (idRect)->extents.setTop((r)->top());\
            if((r)->right() > (idRect)->extents.right())\
              (idRect)->extents.setRight((r)->right());\
            if((r)->bottom() > (idRect)->extents.bottom())\
              (idRect)->extents.setBottom((r)->bottom());\
        }

Definition at line 452 of file qregion_qws.cpp.

LARGE_COORDINATE

#define LARGE_COORDINATE   1000000

Definition at line 1851 of file qregion_qws.cpp.

Referenced by CreateETandAET().

MEMCHECK

#define MEMCHECK	(		dest,
			rect,
			firstrect
	)

Value:

{\
        if ((dest).numRects >= ((dest).rects.size()-1)){\
          firstrect.resize(firstrect.size() * 2); \
          (rect) = (firstrect).data() + (dest).numRects;\
        }\
      }

Definition at line 466 of file qregion_qws.cpp.

Referenced by miIntersectO(), miSubtractNonO1(), miSubtractO(), and miUnionNonO().

MERGERECT

#define MERGERECT

(

r

)

Value:

if ((dest.numRects != 0) &&  \
        (pNextRect[-1].top() == y1) &&  \
        (pNextRect[-1].bottom() == y2) &&  \
        (pNextRect[-1].right() >= r->left()-1)) { \
        if (pNextRect[-1].right() < r->right()) { \
            pNextRect[-1].setRight(r->right());  \
            dest.updateInnerRect(pNextRect[-1]); \
            Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
        }  \
    } else { \
        MEMCHECK(dest, pNextRect, dest.rects)  \
        pNextRect->setCoords(r->left(), y1, r->right(), y2); \
        dest.updateInnerRect(*pNextRect); \
        dest.numRects++;  \
        pNextRect++;  \
    }  \
    r++;

Referenced by miUnionO().

NUMPTSTOBUFFER

#define NUMPTSTOBUFFER   200

Definition at line 478 of file qregion_qws.cpp.

Referenced by PolygonRegion(), and PtsToRegion().

private

#define private   public

Definition at line 43 of file qregion_qws.cpp.

RectangleIn

#define RectangleIn   1

Definition at line 377 of file qregion_qws.cpp.

Referenced by RectInRegion().

RectangleOut

#define RectangleOut   0

Definition at line 376 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), and RectInRegion().

RectanglePart

#define RectanglePart   2

Definition at line 378 of file qregion_qws.cpp.

Referenced by RectInRegion().

SLLSPERBLOCK

#define SLLSPERBLOCK   25

Definition at line 1741 of file qregion_qws.cpp.

Referenced by InsertEdgeInET().

SMALL_COORDINATE

#define SMALL_COORDINATE   -LARGE_COORDINATE

Definition at line 1852 of file qregion_qws.cpp.

Referenced by CreateETandAET().

WindingRule

#define WindingRule   1

Definition at line 380 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

Typedef Documentation

EdgeTableEntry

typedef struct _EdgeTableEntry EdgeTableEntry

NonOverlapFunc

typedef void(* NonOverlapFunc) (register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd, register int y1, register int y2)

Definition at line 367 of file qregion_qws.cpp.

OverlapFunc

typedef 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)

Definition at line 365 of file qregion_qws.cpp.

POINTBLOCK

typedef struct _POINTBLOCK POINTBLOCK

ScanLineList

typedef struct _ScanLineList ScanLineList

ScanLineListBlock

typedef struct _ScanLineListBlock ScanLineListBlock

Function Documentation

computeWAET()

static void computeWAET ( register EdgeTableEntry *  AET )

static

Definition at line 2074 of file qregion_qws.cpp.

Referenced by PolygonRegion().

{
    register EdgeTableEntry *pWETE;
    register int inside = 1;
    register int isInside = 0;

    AET->nextWETE = 0;
    pWETE = AET;
    AET = AET->next;
    while (AET) {
        if (AET->ClockWise)
            ++isInside;
        else
            --isInside;

        if (!inside && !isInside || inside && isInside) {
            pWETE->nextWETE = AET;
            pWETE = AET;
            inside = !inside;
        }
        AET = AET->next;
    }
    pWETE->nextWETE = 0;
}

CreateETandAET()

static void CreateETandAET ( register int  count, register const QPoint *  pts, EdgeTable *  ET, EdgeTableEntry *  AET, register EdgeTableEntry *  pETEs, ScanLineListBlock *  pSLLBlock  )

static

Definition at line 1943 of file qregion_qws.cpp.

Referenced by PolygonRegion().

{
    register const QPoint *top,
                          *bottom,
                          *PrevPt,
                          *CurrPt;
    int iSLLBlock = 0;
    int dy;

    if (count < 2)
        return;

    /*
     *  initialize the Active Edge Table
     */
    AET->next = 0;
    AET->back = 0;
    AET->nextWETE = 0;
    AET->bres.minor_axis = SMALL_COORDINATE;

    /*
     *  initialize the Edge Table.
     */
    ET->scanlines.next = 0;
    ET->ymax = SMALL_COORDINATE;
    ET->ymin = LARGE_COORDINATE;
    pSLLBlock->next = 0;

    PrevPt = &pts[count - 1];

    /*
     *  for each vertex in the array of points.
     *  In this loop we are dealing with two vertices at
     *  a time -- these make up one edge of the polygon.
     */
    while (count--) {
        CurrPt = pts++;

        /*
         *  find out which point is above and which is below.
         */
        if (PrevPt->y() > CurrPt->y()) {
            bottom = PrevPt;
            top = CurrPt;
            pETEs->ClockWise = 0;
        } else {
            bottom = CurrPt;
            top = PrevPt;
            pETEs->ClockWise = 1;
        }

        /*
         * don't add horizontal edges to the Edge table.
         */
        if (bottom->y() != top->y()) {
            pETEs->ymax = bottom->y() - 1;  /* -1 so we don't get last scanline */

            /*
             *  initialize integer edge algorithm
             */
            dy = bottom->y() - top->y();
            BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)

            InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);

            if (PrevPt->y() > ET->ymax)
                ET->ymax = PrevPt->y();
            if (PrevPt->y() < ET->ymin)
                ET->ymin = PrevPt->y();
            ++pETEs;
        }

        PrevPt = CurrPt;
    }
}

EqualRegion()

static bool EqualRegion ( const QRegionPrivate *  r1, const QRegionPrivate *  r2  )

static

Definition at line 1400 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), qt_region_strictContains(), SubtractRegion(), UnionRectWithRegion(), UnionRegion(), and XorRegion().

{
    if (r1->numRects != r2->numRects) {
        return false;
    } else if (r1->numRects == 0) {
        return true;
    } else if (r1->extents != r2->extents) {
        return false;
    } else if (r1->mode == QRegionPrivate::Single && r2->mode == QRegionPrivate::Single) {
        return r1->single == r2->single;
    } else {
        const QRect *rr1 = (r1->mode==QRegionPrivate::Vector)?r1->rects.constData():&r1->single;
        const QRect *rr2 = (r2->mode==QRegionPrivate::Vector)?r2->rects.constData():&r2->single;
        for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
            if (*rr1 != *rr2)
                return false;
        }
    }

    return true;
}

FreeStorage()

static void FreeStorage ( register ScanLineListBlock *  pSLLBlock )

static

Definition at line 2141 of file qregion_qws.cpp.

Referenced by PolygonRegion().

{
    register ScanLineListBlock *tmpSLLBlock;

    while (pSLLBlock) {
        tmpSLLBlock = pSLLBlock->next;
        free(pSLLBlock);
        pSLLBlock = tmpSLLBlock;
    }
}

InsertEdgeInET()

static void InsertEdgeInET ( EdgeTable *  ET, EdgeTableEntry *  ETE, int  scanline, ScanLineListBlock **  SLLBlock, int *  iSLLBlock  )

static

Definition at line 1863 of file qregion_qws.cpp.

Referenced by CreateETandAET().

{
    register EdgeTableEntry *start, *prev;
    register ScanLineList *pSLL, *pPrevSLL;
    ScanLineListBlock *tmpSLLBlock;

    /*
     * find the right bucket to put the edge into
     */
    pPrevSLL = &ET->scanlines;
    pSLL = pPrevSLL->next;
    while (pSLL && (pSLL->scanline < scanline)) {
        pPrevSLL = pSLL;
        pSLL = pSLL->next;
    }

    /*
     * reassign pSLL (pointer to ScanLineList) if necessary
     */
    if ((!pSLL) || (pSLL->scanline > scanline)) {
        if (*iSLLBlock > SLLSPERBLOCK-1)
        {
            tmpSLLBlock =
                  (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
            (*SLLBlock)->next = tmpSLLBlock;
            tmpSLLBlock->next = (ScanLineListBlock *)NULL;
            *SLLBlock = tmpSLLBlock;
            *iSLLBlock = 0;
        }
        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);

        pSLL->next = pPrevSLL->next;
        pSLL->edgelist = (EdgeTableEntry *)NULL;
        pPrevSLL->next = pSLL;
    }
    pSLL->scanline = scanline;

    /*
     * now insert the edge in the right bucket
     */
    prev = 0;
    start = pSLL->edgelist;
    while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
        prev = start;
        start = start->next;
    }
    ETE->next = start;

    if (prev)
        prev->next = ETE;
    else
        pSLL->edgelist = ETE;
}

InsertionSort()

static int InsertionSort ( register EdgeTableEntry *  AET )

static

Definition at line 2108 of file qregion_qws.cpp.

Referenced by PolygonRegion().

{
    register EdgeTableEntry *pETEchase;
    register EdgeTableEntry *pETEinsert;
    register EdgeTableEntry *pETEchaseBackTMP;
    register int changed = 0;

    AET = AET->next;
    while (AET) {
        pETEinsert = AET;
        pETEchase = AET;
        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
            pETEchase = pETEchase->back;

        AET = AET->next;
        if (pETEchase != pETEinsert) {
            pETEchaseBackTMP = pETEchase->back;
            pETEinsert->back->next = AET;
            if (AET)
                AET->back = pETEinsert->back;
            pETEinsert->next = pETEchase;
            pETEchase->back->next = pETEinsert;
            pETEchase->back = pETEinsert;
            pETEinsert->back = pETEchaseBackTMP;
            changed = 1;
        }
    }
    return changed;
}

isEmptyHelper()

static bool isEmptyHelper ( const QRegionPrivate *  preg )

inlinestatic

Definition at line 235 of file qregion_qws.cpp.

Referenced by PointInRegion(), qt_bitmapToRegion(), qt_region_strictContains(), SubtractRegion(), UnionRectWithRegion(), UnionRegion(), and XorRegion().

{
    return !preg || preg->numRects == 0;
}

loadAET()

static void loadAET ( register EdgeTableEntry *  AET, register EdgeTableEntry *  ETEs  )

static

Definition at line 2030 of file qregion_qws.cpp.

Referenced by PolygonRegion().

{
    register EdgeTableEntry *pPrevAET;
    register EdgeTableEntry *tmp;

    pPrevAET = AET;
    AET = AET->next;
    while (ETEs) {
        while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
            pPrevAET = AET;
            AET = AET->next;
        }
        tmp = ETEs->next;
        ETEs->next = AET;
        if (AET)
            AET->back = ETEs;
        ETEs->back = pPrevAET;
        pPrevAET->next = ETEs;
        pPrevAET = ETEs;

        ETEs = tmp;
    }
}

miCoalesce()

static int miCoalesce ( register QRegionPrivate &  dest, int  prevStart, int  curStart  )

static

Definition at line 749 of file qregion_qws.cpp.

Referenced by miRegionOp().

{
    register QRect *pPrevBox;   /* Current box in previous band */
    register QRect *pCurBox;    /* Current box in current band */
    register QRect *pRegEnd;    /* End of region */
    int curNumRects;    /* Number of rectangles in current band */
    int prevNumRects;   /* Number of rectangles in previous band */
    int bandY1;         /* Y1 coordinate for current band */
    QRect *rData = dest.rects.data();

    pRegEnd = rData + dest.numRects;

    pPrevBox = rData + prevStart;
    prevNumRects = curStart - prevStart;

    /*
     * Figure out how many rectangles are in the current band. Have to do
     * this because multiple bands could have been added in miRegionOp
     * at the end when one region has been exhausted.
     */
    pCurBox = rData + curStart;
    bandY1 = pCurBox->top();
    for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
        ++pCurBox;
    }

    if (pCurBox != pRegEnd) {
        /*
         * If more than one band was added, we have to find the start
         * of the last band added so the next coalescing job can start
         * at the right place... (given when multiple bands are added,
         * this may be pointless -- see above).
         */
        --pRegEnd;
        while ((pRegEnd - 1)->top() == pRegEnd->top())
            --pRegEnd;
        curStart = pRegEnd - rData;
        pRegEnd = rData + dest.numRects;
    }

    if (curNumRects == prevNumRects && curNumRects != 0) {
        pCurBox -= curNumRects;
        /*
         * The bands may only be coalesced if the bottom of the previous
         * matches the top scanline of the current.
         */
        if (pPrevBox->bottom() == pCurBox->top() - 1) {
            /*
             * Make sure the bands have boxes in the same places. This
             * assumes that boxes have been added in such a way that they
             * cover the most area possible. I.e. two boxes in a band must
             * have some horizontal space between them.
             */
            do {
                if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
                     // The bands don't line up so they can't be coalesced.
                    return curStart;
                }
                ++pPrevBox;
                ++pCurBox;
                --prevNumRects;
            } while (prevNumRects != 0);

            dest.numRects -= curNumRects;
            pCurBox -= curNumRects;
            pPrevBox -= curNumRects;

            /*
             * The bands may be merged, so set the bottom y of each box
             * in the previous band to that of the corresponding box in
             * the current band.
             */
            do {
                pPrevBox->setBottom(pCurBox->bottom());
                dest.updateInnerRect(*pPrevBox);
                ++pPrevBox;
                ++pCurBox;
                curNumRects -= 1;
            } while (curNumRects != 0);

            /*
             * If only one band was added to the region, we have to backup
             * curStart to the start of the previous band.
             *
             * If more than one band was added to the region, copy the
             * other bands down. The assumption here is that the other bands
             * came from the same region as the current one and no further
             * coalescing can be done on them since it's all been done
             * already... curStart is already in the right place.
             */
            if (pCurBox == pRegEnd) {
                curStart = prevStart;
            } else {
                do {
                    *pPrevBox++ = *pCurBox++;
                    dest.updateInnerRect(*pPrevBox);
                } while (pCurBox != pRegEnd);
            }
        }
    }
    return curStart;
}

miIntersectO()

static void miIntersectO ( register QRegionPrivate &  dest, register const QRect *  r1, const QRect *  r1End, register const QRect *  r2, const QRect *  r2End, int  y1, int  y2  )

static

Definition at line 684 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    register int x1;
    register int x2;
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

    while (r1 != r1End && r2 != r2End) {
        x1 = qMax(r1->left(), r2->left());
        x2 = qMin(r1->right(), r2->right());

        /*
         * If there's any overlap between the two rectangles, add that
         * overlap to the new region.
         * There's no need to check for subsumption because the only way
         * such a need could arise is if some region has two rectangles
         * right next to each other. Since that should never happen...
         */
        if (x1 <= x2) {
            Q_ASSERT(y1 <= y2);
            MEMCHECK(dest, pNextRect, dest.rects)
            pNextRect->setCoords(x1, y1, x2, y2);
            ++dest.numRects;
            ++pNextRect;
        }

        /*
         * Need to advance the pointers. Shift the one that extends
         * to the right the least, since the other still has a chance to
         * overlap with that region's next rectangle, if you see what I mean.
         */
        if (r1->right() < r2->right()) {
            ++r1;
        } else if (r2->right() < r1->right()) {
            ++r2;
        } else {
            ++r1;
            ++r2;
        }
    }
}

miRegionOp()

static void miRegionOp ( register QRegionPrivate &  dest, const QRegionPrivate *  reg1, const QRegionPrivate *  reg2, OverlapFunc  overlapFunc, NonOverlapFunc  nonOverlap1Func, NonOverlapFunc  nonOverlap2Func  )

static

Definition at line 878 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), SubtractRegion(), and UnionRegion().

{
    register const QRect *r1;         // Pointer into first region
    register const QRect *r2;         // Pointer into 2d region
    const QRect *r1End;               // End of 1st region
    const QRect *r2End;               // End of 2d region
    register int ybot;          // Bottom of intersection
    register int ytop;          // Top of intersection
    int prevBand;               // Index of start of previous band in dest
    int curBand;                // Index of start of current band in dest
    register const QRect *r1BandEnd;  // End of current band in r1
    register const QRect *r2BandEnd;  // End of current band in r2
    int top;                    // Top of non-overlapping band
    int bot;                    // Bottom of non-overlapping band

    /*
     * Initialization:
     *  set r1, r2, r1End and r2End appropriately, preserve the important
     * parts of the destination region until the end in case it's one of
     * the two source regions, then mark the "new" region empty, allocating
     * another array of rectangles for it to use.
     */
    r1 = (reg1->mode==QRegionPrivate::Vector)?reg1->rects.data():&reg1->single;
    r2 = (reg2->mode==QRegionPrivate::Vector)?reg2->rects.data():&reg2->single;
    r1End = r1 + reg1->numRects;
    r2End = r2 + reg2->numRects;

    dest.vector();
    QVector<QRect> oldRects = dest.rects;

    dest.numRects = 0;

    /*
     * Allocate a reasonable number of rectangles for the new region. The idea
     * is to allocate enough so the individual functions don't need to
     * reallocate and copy the array, which is time consuming, yet we don't
     * have to worry about using too much memory. I hope to be able to
     * nuke the realloc() at the end of this function eventually.
     */
    dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);

    /*
     * Initialize ybot and ytop.
     * In the upcoming loop, ybot and ytop serve different functions depending
     * on whether the band being handled is an overlapping or non-overlapping
     * band.
     *  In the case of a non-overlapping band (only one of the regions
     * has points in the band), ybot is the bottom of the most recent
     * intersection and thus clips the top of the rectangles in that band.
     * ytop is the top of the next intersection between the two regions and
     * serves to clip the bottom of the rectangles in the current band.
     *  For an overlapping band (where the two regions intersect), ytop clips
     * the top of the rectangles of both regions and ybot clips the bottoms.
     */
    if (reg1->extents.top() < reg2->extents.top())
        ybot = reg1->extents.top() - 1;
    else
        ybot = reg2->extents.top() - 1;

    /*
     * prevBand serves to mark the start of the previous band so rectangles
     * can be coalesced into larger rectangles. qv. miCoalesce, above.
     * In the beginning, there is no previous band, so prevBand == curBand
     * (curBand is set later on, of course, but the first band will always
     * start at index 0). prevBand and curBand must be indices because of
     * the possible expansion, and resultant moving, of the new region's
     * array of rectangles.
     */
    prevBand = 0;

    do {
        curBand = dest.numRects;

        /*
         * This algorithm proceeds one source-band (as opposed to a
         * destination band, which is determined by where the two regions
         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
         * rectangle after the last one in the current band for their
         * respective regions.
         */
        r1BandEnd = r1;
        while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
            ++r1BandEnd;

        r2BandEnd = r2;
        while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
            ++r2BandEnd;

        /*
         * First handle the band that doesn't intersect, if any.
         *
         * Note that attention is restricted to one band in the
         * non-intersecting region at once, so if a region has n
         * bands between the current position and the next place it overlaps
         * the other, this entire loop will be passed through n times.
         */
        if (r1->top() < r2->top()) {
            top = qMax(r1->top(), ybot + 1);
            bot = qMin(r1->bottom(), r2->top() - 1);

            if (nonOverlap1Func != 0 && bot >= top)
                (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
            ytop = r2->top();
        } else if (r2->top() < r1->top()) {
            top = qMax(r2->top(), ybot + 1);
            bot = qMin(r2->bottom(), r1->top() - 1);

            if (nonOverlap2Func != 0 && bot >= top)
                (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
            ytop = r1->top();
        } else {
            ytop = r1->top();
        }

        /*
         * If any rectangles got added to the region, try and coalesce them
         * with rectangles from the previous band. Note we could just do
         * this test in miCoalesce, but some machines incur a not
         * inconsiderable cost for function calls, so...
         */
        if (dest.numRects != curBand)
            prevBand = miCoalesce(dest, prevBand, curBand);

        /*
         * Now see if we've hit an intersecting band. The two bands only
         * intersect if ybot >= ytop
         */
        ybot = qMin(r1->bottom(), r2->bottom());
        curBand = dest.numRects;
        if (ybot >= ytop)
            (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);

        if (dest.numRects != curBand)
            prevBand = miCoalesce(dest, prevBand, curBand);

        /*
         * If we've finished with a band (y2 == ybot) we skip forward
         * in the region to the next band.
         */
        if (r1->bottom() == ybot)
            r1 = r1BandEnd;
        if (r2->bottom() == ybot)
            r2 = r2BandEnd;
    } while (r1 != r1End && r2 != r2End);

    /*
     * Deal with whichever region still has rectangles left.
     */
    curBand = dest.numRects;
    if (r1 != r1End) {
        if (nonOverlap1Func != 0) {
            do {
                r1BandEnd = r1;
                while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
                    ++r1BandEnd;
                (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
                r1 = r1BandEnd;
            } while (r1 != r1End);
        }
    } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
        do {
            r2BandEnd = r2;
            while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
                 ++r2BandEnd;
            (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
            r2 = r2BandEnd;
        } while (r2 != r2End);
    }

    if (dest.numRects != curBand)
        (void)miCoalesce(dest, prevBand, curBand);

    /*
     * A bit of cleanup. To keep regions from growing without bound,
     * we shrink the array of rectangles to match the new number of
     * rectangles in the region.
     *
     * Only do this stuff if the number of rectangles allocated is more than
     * twice the number of rectangles in the region (a simple optimization).
     */
    if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
        dest.rects.resize(dest.numRects);
}

miSetExtents()

static void miSetExtents ( QRegionPrivate &  dest )

static

Definition at line 602 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), and SubtractRegion().

{
    register const QRect *pBox,
                         *pBoxEnd;
    register QRect *pExtents;

    dest.innerRect.setCoords(0, 0, -1, -1);
    dest.innerArea = -1;
    if (dest.numRects == 0) {
        dest.extents.setCoords(0, 0, 0, 0);
        return;
    }

    pExtents = &dest.extents;
    pBox = (dest.mode==QRegionPrivate::Vector)?(dest.rects.constData()):(&dest.single);
    pBoxEnd = (dest.mode==QRegionPrivate::Vector)?(&pBox[dest.numRects - 1]):(&dest.single);

    /*
     * Since pBox is the first rectangle in the region, it must have the
     * smallest y1 and since pBoxEnd is the last rectangle in the region,
     * it must have the largest y2, because of banding. Initialize x1 and
     * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
     * to...
     */
    pExtents->setLeft(pBox->left());
    pExtents->setTop(pBox->top());
    pExtents->setRight(pBoxEnd->right());
    pExtents->setBottom(pBoxEnd->bottom());

    Q_ASSERT(pExtents->top() <= pExtents->bottom());
    while (pBox <= pBoxEnd) {
        if (pBox->left() < pExtents->left())
            pExtents->setLeft(pBox->left());
        if (pBox->right() > pExtents->right())
            pExtents->setRight(pBox->right());
        dest.updateInnerRect(*pBox);
        ++pBox;
    }
    Q_ASSERT(pExtents->left() <= pExtents->right());
}

miSubtractNonO1()

static void miSubtractNonO1 ( register QRegionPrivate &  dest, register const QRect *  r, const QRect *  rEnd, register int  y1, register int  y2  )

static

Definition at line 1210 of file qregion_qws.cpp.

Referenced by SubtractRegion().

{
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

    Q_ASSERT(y1<=y2);

    while (r != rEnd) {
        Q_ASSERT(r->left() <= r->right());
        MEMCHECK(dest, pNextRect, dest.rects)
        pNextRect->setCoords(r->left(), y1, r->right(), y2);
        ++dest.numRects;
        ++pNextRect;
        ++r;
    }
}

miSubtractO()

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  )

static

Definition at line 1244 of file qregion_qws.cpp.

Referenced by SubtractRegion().

{
    register QRect *pNextRect;
    register int x1;

    x1 = r1->left();

    Q_ASSERT(y1 <= y2);
    pNextRect = dest.rects.data() + dest.numRects;

    while (r1 != r1End && r2 != r2End) {
        if (r2->right() < x1) {
            /*
             * Subtrahend missed the boat: go to next subtrahend.
             */
            ++r2;
        } else if (r2->left() <= x1) {
            /*
             * Subtrahend precedes minuend: nuke left edge of minuend.
             */
            x1 = r2->right() + 1;
            if (x1 > r1->right()) {
                /*
                 * Minuend completely covered: advance to next minuend and
                 * reset left fence to edge of new minuend.
                 */
                ++r1;
                if (r1 != r1End)
                    x1 = r1->left();
            } else {
                // Subtrahend now used up since it doesn't extend beyond minuend
                ++r2;
            }
        } else if (r2->left() <= r1->right()) {
            /*
             * Left part of subtrahend covers part of minuend: add uncovered
             * part of minuend to region and skip to next subtrahend.
             */
            Q_ASSERT(x1 < r2->left());
            MEMCHECK(dest, pNextRect, dest.rects)
            pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
            ++dest.numRects;
            ++pNextRect;

            x1 = r2->right() + 1;
            if (x1 > r1->right()) {
                /*
                 * Minuend used up: advance to new...
                 */
                ++r1;
                if (r1 != r1End)
                    x1 = r1->left();
            } else {
                // Subtrahend used up
                ++r2;
            }
        } else {
            /*
             * Minuend used up: add any remaining piece before advancing.
             */
            if (r1->right() >= x1) {
                MEMCHECK(dest, pNextRect, dest.rects)
                pNextRect->setCoords(x1, y1, r1->right(), y2);
                ++dest.numRects;
                ++pNextRect;
            }
            ++r1;
            if (r1 != r1End)
                x1 = r1->left();
        }
    }

    /*
     * Add remaining minuend rectangles to region.
     */
    while (r1 != r1End) {
        Q_ASSERT(x1 <= r1->right());
        MEMCHECK(dest, pNextRect, dest.rects)
        pNextRect->setCoords(x1, y1, r1->right(), y2);
        ++dest.numRects;
        ++pNextRect;

        ++r1;
        if (r1 != r1End)
            x1 = r1->left();
    }
}

miUnionNonO()

static void miUnionNonO ( register QRegionPrivate &  dest, register const QRect *  r, const QRect *  rEnd, register int  y1, register int  y2  )

static

Definition at line 1085 of file qregion_qws.cpp.

Referenced by UnionRegion().

{
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

    Q_ASSERT(y1 <= y2);

    while (r != rEnd) {
        Q_ASSERT(r->left() <= r->right());
        MEMCHECK(dest, pNextRect, dest.rects)
        pNextRect->setCoords(r->left(), y1, r->right(), y2);
        dest.numRects++;
        ++pNextRect;
        ++r;
    }
}

miUnionO()

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  )

static

Definition at line 1121 of file qregion_qws.cpp.

Referenced by UnionRegion().

{
    register QRect *pNextRect;

    pNextRect = dest.rects.data() + dest.numRects;

#define MERGERECT(r)             \
    if ((dest.numRects != 0) &&  \
        (pNextRect[-1].top() == y1) &&  \
        (pNextRect[-1].bottom() == y2) &&  \
        (pNextRect[-1].right() >= r->left()-1)) { \
        if (pNextRect[-1].right() < r->right()) { \
            pNextRect[-1].setRight(r->right());  \
            dest.updateInnerRect(pNextRect[-1]); \
            Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
        }  \
    } else { \
        MEMCHECK(dest, pNextRect, dest.rects)  \
        pNextRect->setCoords(r->left(), y1, r->right(), y2); \
        dest.updateInnerRect(*pNextRect); \
        dest.numRects++;  \
        pNextRect++;  \
    }  \
    r++;

    Q_ASSERT(y1 <= y2);
    while (r1 != r1End && r2 != r2End) {
        if (r1->left() < r2->left()) {
            MERGERECT(r1)
        } else {
            MERGERECT(r2)
        }
    }

    if (r1 != r1End) {
        do {
            MERGERECT(r1)
        } while (r1 != r1End);
    } else {
        while (r2 != r2End) {
            MERGERECT(r2)
        }
    }
}

OffsetRegion()

static void OffsetRegion ( register QRegionPrivate &  region, register int  x, register int  y  )

static

Definition at line 648 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    register int nbox;
    register QRect *pbox;

    if(region.mode == QRegionPrivate::Single) {
        region.single.translate(x, y);
    } else {
        pbox = region.rects.data();
        nbox = region.numRects;

        while (nbox--) {
            pbox->translate(x, y);
            ++pbox;
        }
    } 
    region.extents.translate(x, y);
    region.innerRect.translate(x, y);
}

PointInRegion()

static bool PointInRegion ( QRegionPrivate *  pRegion, int  x, int  y  )

static

Definition at line 1422 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    int i;

    if (pRegion->mode == QRegionPrivate::Single)
        return pRegion->single.contains(x, y);
    if (isEmptyHelper(pRegion))
        return false;
    if (!pRegion->extents.contains(x, y))
        return false;
    if (pRegion->innerRect.contains(x, y))
        return true;
    for (i = 0; i < pRegion->numRects; ++i) {
        if (pRegion->rects[i].contains(x, y))
            return true;
    }
    return false;
}

PolygonRegion()

static QRegionPrivate* PolygonRegion ( const QPoint *  Pts, int  Count, int  rule, QRegionPrivate *  region  )

static

Definition at line 2227 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    register EdgeTableEntry *pAET;   /* Active Edge Table       */
    register int y;                  /* current scanline        */
    register int iPts = 0;           /* number of pts in buffer */
    register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
    register ScanLineList *pSLL;     /* current scanLineList    */
    register QPoint *pts;             /* output buffer           */
    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
    EdgeTable ET;                    /* header node for ET      */
    EdgeTableEntry AET;              /* header node for AET     */
    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
    int fixWAET = false;
    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
    POINTBLOCK *tmpPtBlock;
    int numFullPtBlocks = 0;

    region->vector();

    /* special case a rectangle */
    if (((Count == 4) ||
         ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
         && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
               && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
               && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
               && (Pts[3].y() == Pts[0].y())))) {
        int x = qMin(Pts[0].x(), Pts[2].x());
        region->extents.setLeft(x);
        int y = qMin(Pts[0].y(), Pts[2].y());
        region->extents.setTop(y);
        region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
        region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
        if ((region->extents.left() <= region->extents.right()) &&
            (region->extents.top() <= region->extents.bottom())) {
            region->numRects = 1;
            region->rects.resize(1);
            region->rects[0] = region->extents;
            region->innerRect = region->extents;
            region->innerArea = region->innerRect.width() * region->innerRect.height();
        }
        return region;
    }

    if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
        return 0;

    pts = FirstPtBlock.pts;
    CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
    pSLL = ET.scanlines.next;
    curPtBlock = &FirstPtBlock;

    if (rule == EvenOddRule) {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; ++y) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL && y == pSLL->scanline) {
                loadAET(&AET, pSLL->edgelist);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;

            /*
             *  for each active edge
             */
            while (pAET) {
                pts->setX(pAET->bres.minor_axis);
                pts->setY(y);
                ++pts;
                ++iPts;

                /*
                 *  send out the buffer
                 */
                if (iPts == NUMPTSTOBUFFER) {
                    tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
                    curPtBlock->next = tmpPtBlock;
                    curPtBlock = tmpPtBlock;
                    pts = curPtBlock->pts;
                    ++numFullPtBlocks;
                    iPts = 0;
                }
                EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
            }
            InsertionSort(&AET);
        }
    } else {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; ++y) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL && y == pSLL->scanline) {
                loadAET(&AET, pSLL->edgelist);
                computeWAET(&AET);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;
            pWETE = pAET;

            /*
             *  for each active edge
             */
            while (pAET) {
                /*
                 *  add to the buffer only those edges that
                 *  are in the Winding active edge table.
                 */
                if (pWETE == pAET) {
                    pts->setX(pAET->bres.minor_axis);
                    pts->setY(y);
                    ++pts;
                    ++iPts;

                    /*
                     *  send out the buffer
                     */
                    if (iPts == NUMPTSTOBUFFER) {
                        tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
                        curPtBlock->next = tmpPtBlock;
                        curPtBlock = tmpPtBlock;
                        pts = curPtBlock->pts;
                        ++numFullPtBlocks;
                        iPts = 0;
                    }
                    pWETE = pWETE->nextWETE;
                }
                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
            }

            /*
             *  recompute the winding active edge table if
             *  we just resorted or have exited an edge.
             */
            if (InsertionSort(&AET) || fixWAET) {
                computeWAET(&AET);
                fixWAET = false;
            }
        }
    }
    FreeStorage(SLLBlock.next);
    PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
        tmpPtBlock = curPtBlock->next;
        free(curPtBlock);
        curPtBlock = tmpPtBlock;
    }
    free(pETEs);
    return region;
}

PtsToRegion()

static void PtsToRegion ( register int  numFullPtBlocks, register int  iCurPtBlock, POINTBLOCK *  FirstPtBlock, QRegionPrivate *  reg  )

static

Definition at line 2160 of file qregion_qws.cpp.

Referenced by PolygonRegion().

{
    register QRect *rects;
    register QPoint *pts;
    register POINTBLOCK *CurPtBlock;
    register int i;
    register QRect *extents;
    register int numRects;

    extents = &reg->extents;
    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;

    reg->rects.resize(numRects);

    CurPtBlock = FirstPtBlock;
    rects = reg->rects.data() - 1;
    numRects = 0;
    extents->setLeft(INT_MAX);
    extents->setRight(INT_MIN);
    reg->innerArea = -1;

    for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
        /* the loop uses 2 points per iteration */
        i = NUMPTSTOBUFFER >> 1;
        if (!numFullPtBlocks)
            i = iCurPtBlock >> 1;
        if(i) {
            for (pts = CurPtBlock->pts; i--; pts += 2) {
                if (pts->x() == pts[1].x())
                    continue;
                if (numRects && pts->x() == rects->left() && pts->y() == rects->bottom() + 1
                    && pts[1].x() == rects->right()+1 && (numRects == 1 || rects[-1].top() != rects->top())
                                                          && (i && pts[2].y() > pts[1].y())) {
                        rects->setBottom(pts[1].y());
                        reg->updateInnerRect(*rects);
                        continue;
                }
                ++numRects;
                ++rects;
                rects->setCoords(pts->x(), pts->y(), pts[1].x() - 1, pts[1].y());
                if (rects->left() < extents->left())
                    extents->setLeft(rects->left());
                if (rects->right() > extents->right())
                    extents->setRight(rects->right());
                reg->updateInnerRect(*rects);
            }
        }
        CurPtBlock = CurPtBlock->next;
    }

    if (numRects) {
        extents->setTop(reg->rects[0].top());
        extents->setBottom(rects->bottom());
    } else {
        extents->setCoords(0, 0, 0, 0);
    }
    reg->numRects = numRects;
}

qt_allocRegion() [1/3]

static QRegionPrivate* qt_allocRegion ( )

static

Definition at line 210 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    QRegionPrivate *mem = qt_allocRegionMemory();
    return new (mem) QRegionPrivate;
}

qt_allocRegion() [2/3]

static QRegionPrivate* qt_allocRegion ( const QRect &  r )

static

Definition at line 216 of file qregion_qws.cpp.

{
    QRegionPrivate *mem = qt_allocRegionMemory();
    return new (mem) QRegionPrivate(r);
}

qt_allocRegion() [3/3]

static QRegionPrivate* qt_allocRegion ( const QRegionPrivate &  r )

static

Definition at line 222 of file qregion_qws.cpp.

{
    QRegionPrivate *mem = qt_allocRegionMemory();
    return new (mem) QRegionPrivate(r);
}

qt_allocRegionMemory()

static QRegionPrivate* qt_allocRegionMemory ( )

static

Definition at line 175 of file qregion_qws.cpp.

Referenced by qt_allocRegion().

{
    QRegionPrivate *rv = 0;
    qt_nextRegionLock.lock();

    if(qt_nextRegionPtr) {
        rv = qt_nextRegionPtr;
        qt_nextRegionPtr = rv->next;
    } else {
        qt_nextRegionPtr = 
            (QRegionPrivate *)malloc(256 * sizeof(QRegionPrivate));
        for(int ii = 0; ii < 256; ++ii) {
            if(ii == 255) {
                qt_nextRegionPtr[ii].next = 0;
            } else {
                qt_nextRegionPtr[ii].next = &qt_nextRegionPtr[ii + 1];
            }
        }

        rv = qt_nextRegionPtr;
        qt_nextRegionPtr = rv->next;
    }

    qt_nextRegionLock.unlock();
    return rv;
}

qt_bitmapToRegion()

QRegionPrivate* qt_bitmapToRegion	(	const QBitmap &	bitmap,
		QRegionPrivate *	region
	)

Definition at line 2393 of file qregion_qws.cpp.

{
    region->vector();

    QImage image = bitmap.toImage();

    QRect xr;

#define AddSpan \
        { \
            xr.setCoords(prev1, y, x-1, y); \
            UnionRectWithRegion(&xr, region, *region); \
        }

    const uchar zero = 0;
    bool little = image.format() == QImage::Format_MonoLSB;

    int x,
        y;
    for (y = 0; y < image.height(); ++y) {
        uchar *line = image.scanLine(y);
        int w = image.width();
        uchar all = zero;
        int prev1 = -1;
        for (x = 0; x < w;) {
            uchar byte = line[x / 8];
            if (x > w - 8 || byte!=all) {
                if (little) {
                    for (int b = 8; b > 0 && x < w; --b) {
                        if (!(byte & 0x01) == !all) {
                            // More of the same
                        } else {
                            // A change.
                            if (all!=zero) {
                                AddSpan
                                all = zero;
                            } else {
                                prev1 = x;
                                all = ~zero;
                            }
                        }
                        byte >>= 1;
                        ++x;
                    }
                } else {
                    for (int b = 8; b > 0 && x < w; --b) {
                        if (!(byte & 0x80) == !all) {
                            // More of the same
                        } else {
                            // A change.
                            if (all != zero) {
                                AddSpan
                                all = zero;
                            } else {
                                prev1 = x;
                                all = ~zero;
                            }
                        }
                        byte <<= 1;
                        ++x;
                    }
                }
            } else {
                x += 8;
            }
        }
        if (all != zero) {
            AddSpan
        }
    }
#undef AddSpan

    return region;
}

qt_freeRegion()

void qt_freeRegion

(

QRegionPrivate *

rp

)

Definition at line 228 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    rp->~QRegionPrivate();
    qt_freeRegionMemory(rp);
//    delete rp;
}

qt_freeRegionMemory()

static void qt_freeRegionMemory ( QRegionPrivate *  rp )

static

Definition at line 202 of file qregion_qws.cpp.

Referenced by qt_freeRegion().

{
    qt_nextRegionLock.lock();
    rp->next = qt_nextRegionPtr;
    qt_nextRegionPtr = rp;
    qt_nextRegionLock.unlock();
}

qt_region_strictContains()

bool qt_region_strictContains	(	const QRegion &	region,
		const QRect &	rect
	)

Warning

This function is not part of the public interface.

A false return value does not guarantee the opposite.

Definition at line 3057 of file qregion_qws.cpp.

{
    if (isEmptyHelper(region.d->qt_rgn) || !rect.isValid())
        return false;

#if 0 // TEST_INNERRECT
    static bool guard = false;
    if (guard)
        return QRect();
    guard = true;
    QRegion inner = region.d->qt_rgn->innerRect;
    Q_ASSERT((inner - region).isEmpty());
    guard = false;

    int maxArea = 0;
    for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
        const QRect r = region.d->qt_rgn->rects.at(i);
        if (r.width() * r.height() > maxArea)
            maxArea = r.width() * r.height();
    }

    if (maxArea > region.d->qt_rgn->innerArea) {
        qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
    }
    Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
#endif

    const QRect r1 = region.d->qt_rgn->innerRect;
    return (rect.left() >= r1.left() && rect.right() <= r1.right()
            && rect.top() >= r1.top() && rect.bottom() <= r1.bottom());
}

RectInRegion()

static bool RectInRegion ( register QRegionPrivate *  region, int  rx, int  ry, uint  rwidth, uint  rheight  )

static

Definition at line 1441 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    register const QRect *pbox;
    register const QRect *pboxEnd;
    QRect rect(rx, ry, rwidth, rheight);
    register QRect *prect = ▭
    int partIn, partOut;

    if (!region || region->numRects == 0 || !EXTENTCHECK(&region->extents, prect))
        return RectangleOut;

    partOut = false;
    partIn = false;

    /* can stop when both partOut and partIn are true, or we reach prect->y2 */
    for (pbox = (region->mode==QRegionPrivate::Vector)?region->rects.constData():&region->single, pboxEnd = pbox + region->numRects;
         pbox < pboxEnd; ++pbox) {
        if (pbox->bottom() < ry)
           continue;

        if (pbox->top() > ry) {
           partOut = true;
           if (partIn || pbox->top() > prect->bottom())
              break;
           ry = pbox->top();
        }

        if (pbox->right() < rx)
           continue;            /* not far enough over yet */

        if (pbox->left() > rx) {
           partOut = true;      /* missed part of rectangle to left */
           if (partIn)
              break;
        }

        if (pbox->left() <= prect->right()) {
            partIn = true;      /* definitely overlap */
            if (partOut)
               break;
        }

        if (pbox->right() >= prect->right()) {
           ry = pbox->bottom() + 1;     /* finished with this band */
           if (ry > prect->bottom())
              break;
           rx = prect->left();  /* reset x out to left again */
        } else {
            /*
             * Because boxes in a band are maximal width, if the first box
             * to overlap the rectangle doesn't completely cover it in that
             * band, the rectangle must be partially out, since some of it
             * will be uncovered in that band. partIn will have been set true
             * by now...
             */
            break;
        }
    }
    return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
}

SubtractRegion()

static void SubtractRegion ( QRegionPrivate *  regM, QRegionPrivate *  regS, register QRegionPrivate &  dest  )

static

Definition at line 1345 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), and XorRegion().

{
    Q_ASSERT(!isEmptyHelper(regM));
    Q_ASSERT(!isEmptyHelper(regS));
    Q_ASSERT(EXTENTCHECK(&regM->extents, &regS->extents));
    Q_ASSERT(!regS->contains(*regM));
    Q_ASSERT(!EqualRegion(regM, regS));

    miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);

    /*
     * Can't alter dest's extents before we call miRegionOp because
     * it might be one of the source regions and miRegionOp depends
     * on the extents of those regions being the unaltered. Besides, this
     * way there's no checking against rectangles that will be nuked
     * due to coalescing, so we have to examine fewer rectangles.
     */
    miSetExtents(dest);
}

UnionRectWithRegion()

static void UnionRectWithRegion ( register const QRect *  rect, const QRegionPrivate *  source, QRegionPrivate &  dest  )

static

Definition at line 568 of file qregion_qws.cpp.

{
    if (!rect->width() || !rect->height())
        return;

    QRegionPrivate region(*rect);

    Q_ASSERT(EqualRegion(source, &dest));
    Q_ASSERT(!isEmptyHelper(&region));

    if (dest.numRects == 0)
        dest = region;
    else if (dest.canAppend(&region))
        dest.append(&region);
    else
        UnionRegion(&region, source, dest);
}

UnionRegion()

static void UnionRegion ( const QRegionPrivate *  reg1, const QRegionPrivate *  reg2, QRegionPrivate &  dest  )

static

Definition at line 1167 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion(), UnionRectWithRegion(), and XorRegion().

{
    Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2));
    Q_ASSERT(!reg1->contains(*reg2));
    Q_ASSERT(!reg2->contains(*reg1));
    Q_ASSERT(!EqualRegion(reg1, reg2));
    Q_ASSERT(!reg1->canAppend(reg2));
    Q_ASSERT(!reg2->canAppend(reg1));

    if (reg1->innerArea > reg2->innerArea) {
        dest.innerArea = reg1->innerArea;
        dest.innerRect = reg1->innerRect;
    } else {
        dest.innerArea = reg2->innerArea;
        dest.innerRect = reg2->innerRect;
    }
    miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);

    dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
                           qMin(reg1->extents.top(), reg2->extents.top()),
                           qMax(reg1->extents.right(), reg2->extents.right()),
                           qMax(reg1->extents.bottom(), reg2->extents.bottom()));
}

XorRegion()

static void XorRegion ( QRegionPrivate *  sra, QRegionPrivate *  srb, QRegionPrivate &  dest  )

static

Definition at line 1366 of file qregion_qws.cpp.

Referenced by qt_bitmapToRegion().

{
    Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb));
    Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents));
    Q_ASSERT(!EqualRegion(sra, srb));

    QRegionPrivate tra, trb;

    if (!srb->contains(*sra))
        SubtractRegion(sra, srb, tra);
    if (!sra->contains(*srb))
        SubtractRegion(srb, sra, trb);

    Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb));
    Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra));

    if (isEmptyHelper(&tra)) {
        dest = trb;
    } else if (isEmptyHelper(&trb)) {
        dest = tra;
    } else if (tra.canAppend(&trb)) {
        dest = tra;
        dest.append(&trb);
    } else if (trb.canAppend(&tra)) {
        dest = trb;
        dest.append(&tra);
    } else {
        UnionRegion(&tra, &trb, dest);
    }
}

Variable Documentation

qt_nextRegionLock

QFastMutex qt_nextRegionLock

static

Definition at line 173 of file qregion_qws.cpp.

qt_nextRegionPtr

QRegionPrivate* qt_nextRegionPtr = 0

static

Definition at line 172 of file qregion_qws.cpp.

Referenced by qt_allocRegionMemory(), and qt_freeRegionMemory().