qregion_unix.cpp

qt-x11-opensource-src-4.1.4.tar.gz源码

 *      Adds the rectangles into the region. Doesn't have to check for
 *      subsumption or anything.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      dest.numRects is incremented and the final rectangles overwritten
 *      with the rectangles we're passed.
 *
 *-----------------------------------------------------------------------
 */

static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
                        register int y1, register int y2)
{
    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 --
 *      Handle an overlapping band for the union operation. Picks the
 *      left-most rectangle each time and merges it into the region.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      Rectangles are overwritten in dest.rects and dest.numRects will
 *      be changed.
 *
 *-----------------------------------------------------------------------
 */

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)
{
    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());  \
            Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
        }  \
    } else { \
        MEMCHECK(dest, pNextRect, dest.rects)  \
        pNextRect->setCoords(r->left(), y1, r->right(), y2); \
        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)
        }
    }
}

static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
{
    /*
      Region 1 is empty or is equal to region 2.
    */
    if (reg1 == reg2 || isEmpty(reg1)) {
        if (!isEmpty(reg2))
            dest = *reg2;
        return;
    }

    /*
      Region 2 is empty (and region 1 isn't).
    */
    if (isEmpty(reg2)) {
        dest = *reg1;
        return;
    }

    /*
      Region 1 completely subsumes region 2.
     */
    if (reg1->numRects == 1 && reg1->extents.left() <= reg2->extents.left()
            && reg1->extents.top() <= reg2->extents.top()
            && reg1->extents.right() >= reg2->extents.right()
            && reg1->extents.bottom() >= reg2->extents.bottom()) {
        dest = *reg1;
        return;
    }

    /*
      Region 2 completely subsumes region 1.
     */
    if (reg2->numRects == 1 && reg2->extents.left() <= reg1->extents.left()
            && reg2->extents.top() <= reg1->extents.top()
            && reg2->extents.right() >= reg1->extents.right()
            && reg2->extents.bottom() >= reg1->extents.bottom()) {
        dest = *reg2;
        return;
    }

    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()));
}

/*======================================================================
 *        Region Subtraction
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * miSubtractNonO --
 *      Deal with non-overlapping band for subtraction. Any parts from
 *      region 2 we discard. Anything from region 1 we add to the region.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      dest may be affected.
 *
 *-----------------------------------------------------------------------
 */

static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
                            const QRect *rEnd, register int y1, register int y2)
{
    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 --
 *      Overlapping band subtraction. x1 is the left-most point not yet
 *      checked.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      dest may have rectangles added to it.
 *
 *-----------------------------------------------------------------------
 */

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)
{
    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();
    }
}

/*-
 *-----------------------------------------------------------------------
 * miSubtract --
 *      Subtract regS from regM and leave the result in regD.
 *      S stands for subtrahend, M for minuend and D for difference.
 *
 * Side Effects:
 *      regD is overwritten.
 *
 *-----------------------------------------------------------------------
 */

static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
                           register QRegionPrivate &dest)
{
   /* check for trivial reject */
    if (isEmpty(regM))
        return;

    if (isEmpty(regS) || !EXTENTCHECK(&regM->extents, &regS->extents)) {
        dest = *regM;
        return;
    }
    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);
}

static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
{
    QRegionPrivate tra, trb;

    SubtractRegion(sra, srb, tra);
    SubtractRegion(srb, sra, trb);
    UnionRegion(&tra, &trb, dest);
}

/*
 *      Check to see if two regions are equal
 */
static bool EqualRegion(QRegionPrivate *r1, QRegionPrivate *r2)
{
    if (r1->numRects != r2->numRects) {
        return false;
    } else if (r1->numRects == 0) {
        return true;
    } else if (r1->extents != r2->extents) {
        return false;
    } else {
        const QRect *rr1 = r1->rects.constData();
        const QRect *rr2 = r2->rects.constData();
        for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
            if (*rr1 != *rr2)
                return false;
        }
    }
    return true;
}

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

    if (isEmpty(pRegion))
        return false;
    if (!pRegion->extents.contains(x, y))
        return false;
    for (i = 0; i < pRegion->numRects; ++i) {
        if (pRegion->rects[i].contains(x, y))
            return true;
    }
    return false;
}

static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
{
    register const QRect *pbox;
    register const QRect *pboxEnd;
    QRect rect(rx, ry, rwidth, rheight);
    register QRect *prect = &rect;
    int partIn, partOut;

    if (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->rects.constData(), pboxEnd = pbox + region->numRects;
         pbox < pboxEnd; ++pbox) {
        if (pbox->bottom() < ry)