region.c

linux下的一款播放器

 *      second, the overlapFunc is called to process the entire band. It
 *      is responsible for clipping the rectangles in the band, though
 *      this function provides the boundaries.
 *      At the end of each band, the new region is coalesced, if possible,
 *      to reduce the number of rectangles in the region.
 *
 *-----------------------------------------------------------------------
 */
/* static void*/
static void miRegionOp(
    register _HXRegion  newReg,                 /* Place to store result */
    _HXRegion           reg1,                   /* First region in operation */
    _HXRegion           reg2,                   /* 2d region in operation */
    overlapFunc         fpOverlapFunc,            /* Function to call for over-
                                                 * lapping bands */
    nonOverlapFunc      nonOverlap1Func,        /* Function to call for non-
                                                 * overlapping bands in region
                                                 * 1 */
    nonOverlapFunc     nonOverlap2Func         /* Function to call for non-
                                                 * overlapping bands in region
                                                 * 2 */
    )
{
    register HXBoxPtr   r1;                     /* Pointer into first region */
    register HXBoxPtr   r2;                     /* Pointer into 2d region */
    HXBoxPtr            r1End;                  /* End of 1st region */
    HXBoxPtr            r2End;                  /* End of 2d region */
    register short      ybot;                   /* Bottom of intersection */
    register short      ytop;                   /* Top of intersection */
    HXBoxPtr            oldRects;               /* Old rects for newReg */
    int                 prevBand;               /* Index of start of
                                                 * previous band in newReg */
    int                 curBand;                /* Index of start of current
                                                 * band in newReg */
    register HXBoxPtr   r1BandEnd;              /* End of current band in r1 */
    register HXBoxPtr   r2BandEnd;              /* End of current band in r2 */
    short               top;                    /* Top of non-overlapping
                                                 * band */
    short               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->rects;
    r2 = reg2->rects;
    r1End = r1 + reg1->numRects;
    r2End = r2 + reg2->numRects;
    
    oldRects = newReg->rects;
    
    EMPTY_REGION(newReg);

    /*
     * 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 Xrealloc() at the end of this function eventually.
     */
    newReg->size = max(reg1->numRects,reg2->numRects) * 2;

    if (! (newReg->rects = (HXBoxPtr)
           malloc ((unsigned) (sizeof(HXBOX) * newReg->size)))) {
        newReg->size = 0;
        return;
    }
    
    /*
     * 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.y1 < reg2->extents.y1)
        ybot = reg1->extents.y1;
    else
        ybot = reg2->extents.y1;
    
    /*
     * 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 = newReg->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->y1 == r1->y1))
        {
            r1BandEnd++;
        }
        
        r2BandEnd = r2;
        while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
        {
            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->y1 < r2->y1)
        {
            top = max(r1->y1,ybot);
            bot = min(r1->y2,r2->y1);

            if ((top != bot) && (nonOverlap1Func != NULL))
            {
                (*nonOverlap1Func)(newReg, r1, r1BandEnd, top, bot);
            }

            ytop = r2->y1;
        }
        else if (r2->y1 < r1->y1)
        {
            top = max(r2->y1,ybot);
            bot = min(r2->y2,r1->y1);

            if ((top != bot) && (nonOverlap2Func != NULL ))
            {
                (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
            }

            ytop = r1->y1;
        }
        else
        {
            ytop = r1->y1;
        }

        /*
         * 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 (newReg->numRects != curBand)
        {
            prevBand = miCoalesce (newReg, prevBand, curBand);
        }

        /*
         * Now see if we've hit an intersecting band. The two bands only
         * intersect if ybot > ytop
         */
        ybot = min(r1->y2, r2->y2);
        curBand = newReg->numRects;
        if (ybot > ytop)
        {
            (* fpOverlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);

        }
        
        if (newReg->numRects != curBand)
        {
            prevBand = miCoalesce (newReg, prevBand, curBand);
        }

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

    /*
     * Deal with whichever region still has rectangles left.
     */
    curBand = newReg->numRects;
    if (r1 != r1End)
    {
        if (nonOverlap1Func != NULL)
        {
            do
            {
                r1BandEnd = r1;
                while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
                {
                    r1BandEnd++;
                }
                (* nonOverlap1Func) (newReg, r1, r1BandEnd,
                                     max(r1->y1,ybot), r1->y2);
                r1 = r1BandEnd;
            } while (r1 != r1End);
        }
    }
    else if ((r2 != r2End) && (nonOverlap2Func != NULL))
    {
        do
        {
            r2BandEnd = r2;
            while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
            {
                 r2BandEnd++;
            }
            (* nonOverlap2Func) (newReg, r2, r2BandEnd,
                                max(r2->y1,ybot), r2->y2);
            r2 = r2BandEnd;
        } while (r2 != r2End);
    }

    if (newReg->numRects != curBand)
    {
        (void) miCoalesce (newReg, 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. This never goes to 0, however...
     *
     * 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 (newReg->numRects < (newReg->size >> 1))
    {
        if (REGION_NOT_EMPTY(newReg))
        {
            HXBoxPtr prev_rects = newReg->rects;
            newReg->size = newReg->numRects;
            newReg->rects = (HXBoxPtr) realloc ((char *) newReg->rects,
                                   (unsigned) (sizeof(HXBOX) * newReg->size));
            if (! newReg->rects)
                newReg->rects = prev_rects;
        }
        else
        {
            /*
             * No point in doing the extra work involved in an Xrealloc if
             * the region is empty
             */
            newReg->size = 1;
            free((char *) newReg->rects);
            newReg->rects = (HXBoxPtr) malloc(sizeof(HXBOX));
        }
    }
    free ((char *) oldRects);
    return;
}


/*======================================================================
 *          _HXRegion Union
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * miUnionNonO --
 *      Handle a non-overlapping band for the union operation. Just
 *      Adds the rectangles into the region. Doesn't have to check for
 *      subsumption or anything.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      pReg->numRects is incremented and the final rectangles overwritten
 *      with the rectangles we're passed.
 *
 *-----------------------------------------------------------------------
 */
/* static void*/
static int
miUnionNonO( register _HXRegion  pReg,
             register HXBoxPtr   r,
             HXBoxPtr            rEnd,
             register short      y1,
             register short      y2
             )
{
    register HXBoxPtr   pNextRect;

    pNextRect = &pReg->rects[pReg->numRects];

    /* assert(y1 < y2); */

    while (r != rEnd)
    {
        /* assert(r->x1 < r->x2); */
        MEMCHECK(pReg, pNextRect, pReg->rects);
        pNextRect->x1 = r->x1;
        pNextRect->y1 = y1;
        pNextRect->x2 = r->x2;
        pNextRect->y2 = y2;
        pReg->numRects += 1;
        pNextRect++;

        /* assert(pReg->numRects<=pReg->size); */
        r++;
    }
    return 0;
}


/*-
 *-----------------------------------------------------------------------
 * 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 pReg->rects and pReg->numRects will
 *      be changed.
 *
 *-----------------------------------------------------------------------
 */

/* static void*/
static int miUnionO( register _HXRegion  pReg,
                     register HXBoxPtr   r1,
                     HXBoxPtr            r1End,
                     register HXBoxPtr   r2,
                     HXBoxPtr            r2End,
                     register short      y1,
                     register short      y2
                     )

{
    register HXBoxPtr   pNextRect;
    
    pNextRect = &pReg->rects[pReg->numRects];

#define MERGERECT(r) \
    if ((pReg->numRects != 0) &&  \
        (pNextRect[-1].y1 == y1) &&  \
        (pNextRect[-1].y2 == y2) &&  \
        (pNextRect[-1].x2 >= r->x1))  \
    {  \
        if (pNextRect[-1].x2 < r->x2)  \
        {  \
            pNextRect[-1].x2 = r->x2;  \
            /* assert(pNextRect[-1].x1<pNextRect[-1].x2); */ \
        }  \
    }  \
    else  \
    {  \
        MEMCHECK(pReg, pNextRect, pReg->rects);  \
        pNextRect->y1 = y1;  \
        pNextRect->y2 = y2;  \
        pNextRect->x1 = r->x1;  \
        pNextRect->x2 = r->x2;  \
        pReg->numRects += 1;  \
        pNextRect += 1;  \
    }  \
    /* assert(pReg->numRects<=pReg->size); */ \
    r++;
    
    /* assert (y1<y2); */
    while ((r1 != r1End) && (r2 != r2End))
    {
        if (r1->x1 < r2->x1)
        {
            MERGERECT(r1);
        }
        else
        {
            MERGERECT(r2);
        }
    }
    
    if (r1 != r1End)
    {
        do
        {
            MERGERECT(r1);
        } while (r1 != r1End);
    }
    else while (r2 != r2End)
    {
        MERGERECT(r2);
    }
    return 0;   /* lint */
}

int HXUnionRegion(_HXRegion reg1, _HXRegion reg2, _HXRegion newReg)
{
    /*  checks all the simple cases */

    /*
     * _HXRegion 1 and 2 are the same or region 1 is empty
     */
    if ( (reg1 == reg2) || (!(reg1->numRects)) )
    {
        if (newReg != reg2)
            miRegionCopy(newReg, reg2);
        return 1;
    }

    /*
     * if nothing to union (region 2 empty)
     */
    if (!(reg2->numRects))
    {
        if (newReg != reg1)
            miRegionCopy(newReg, reg1);
        return 1;
    }

    /*
     * _HXRegion 1 completely subsumes region 2
     */
    if ((reg1->numRects == 1) && 
        (reg1->extents.x1 <= reg2->extents.x1) &&
        (reg1->extents.y1 <= reg2->extents.y1) &&
        (reg1->extents.x2 >= reg2->extents.x2) &&
        (reg1->extents.y2 >= reg2->extents.y2))
    {
        if (newReg != reg1)
            miRegionCopy(newReg, reg1);
        return 1;
    }

    /*