pixregion.c

超强的嵌入式GUI系统

	memmove((char *)new, (char *)old, numRects * sizeof(pixman_box16_t));
    dstrgn->data->numRects += numRects;
    return PIXMAN_REGION_STATUS_SUCCESS;
}

#define ExchangeRects(a, b) \
{			    \
    pixman_box16_t     t;	    \
    t = rects[a];	    \
    rects[a] = rects[b];    \
    rects[b] = t;	    \
}

static void
QuickSortRects(
    pixman_box16_t     rects[],
    int        numRects)
{
    int	y1;
    int	x1;
    int        i, j;
    pixman_box16_t *r;

    /* Always called with numRects > 1 */

    do
    {
	if (numRects == 2)
	{
	    if (rects[0].y1 > rects[1].y1 ||
		    (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
		ExchangeRects(0, 1);
	    return;
	}

	/* Choose partition element, stick in location 0 */
        ExchangeRects(0, numRects >> 1);
	y1 = rects[0].y1;
	x1 = rects[0].x1;

        /* Partition array */
        i = 0;
        j = numRects;
        do
	{
	    r = &(rects[i]);
	    do
	    {
		r++;
		i++;
            } while (i != numRects &&
		     (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
	    r = &(rects[j]);
	    do
	    {
		r--;
		j--;
            } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
            if (i < j)
		ExchangeRects(i, j);
        } while (i < j);

        /* Move partition element back to middle */
        ExchangeRects(0, j);

	/* Recurse */
        if (numRects-j-1 > 1)
	    QuickSortRects(&rects[j+1], numRects-j-1);
        numRects = j;
    } while (numRects > 1);
}

/*-
 *-----------------------------------------------------------------------
 * pixman_region_validate --
 *
 *      Take a ``region'' which is a non-y-x-banded random collection of
 *      rectangles, and compute a nice region which is the union of all the
 *      rectangles.
 *
 * Results:
 *	PIXMAN_REGION_STATUS_SUCCESS if successful.
 *
 * Side Effects:
 *      The passed-in ``region'' may be modified.
 *	pOverlap set to PIXMAN_REGION_STATUS_SUCCESS if any retangles overlapped, else PIXMAN_REGION_STATUS_FAILURE;
 *
 * Strategy:
 *      Step 1. Sort the rectangles into ascending order with primary key y1
 *		and secondary key x1.
 *
 *      Step 2. Split the rectangles into the minimum number of proper y-x
 *		banded regions.  This may require horizontally merging
 *		rectangles, and vertically coalescing bands.  With any luck,
 *		this step in an identity transformation (ala the Box widget),
 *		or a coalescing into 1 box (ala Menus).
 *
 *	Step 3. Merge the separate regions down to a single region by calling
 *		pixman_region_union.  Maximize the work each pixman_region_union call does by using
 *		a binary merge.
 *
 *-----------------------------------------------------------------------
 */

pixman_region_status_t
pixman_region_validate(pixman_region16_t * badreg,
		       int *pOverlap)
{
    /* Descriptor for regions under construction  in Step 2. */
    typedef struct {
	pixman_region16_t   reg;
	int	    prevBand;
	int	    curBand;
    } RegionInfo;

	     int	numRects;   /* Original numRects for badreg	    */
	     RegionInfo *ri;	    /* Array of current regions		    */
    	     int	numRI;      /* Number of entries used in ri	    */
	     int	sizeRI;	    /* Number of entries available in ri    */
	     int	i;	    /* Index into rects			    */
    int	j;	    /* Index into ri			    */
    RegionInfo *rit;       /* &ri[j]				    */
    pixman_region16_t *  reg;        /* ri[j].reg			    */
    pixman_box16_t *	box;	    /* Current box in rects		    */
    pixman_box16_t *	riBox;      /* Last box in ri[j].reg		    */
    pixman_region16_t *  hreg;       /* ri[j_half].reg			    */
    pixman_region_status_t ret = PIXMAN_REGION_STATUS_SUCCESS;

    *pOverlap = PIXMAN_REGION_STATUS_FAILURE;
    if (!badreg->data)
    {
	good(badreg);
	return PIXMAN_REGION_STATUS_SUCCESS;
    }
    numRects = badreg->data->numRects;
    if (!numRects)
    {
	if (PIXREGION_NAR(badreg))
	    return PIXMAN_REGION_STATUS_FAILURE;
	good(badreg);
	return PIXMAN_REGION_STATUS_SUCCESS;
    }
    if (badreg->extents.x1 < badreg->extents.x2)
    {
	if ((numRects) == 1)
	{
	    freeData(badreg);
	    badreg->data = (pixman_region16_data_t *) NULL;
	}
	else
	{
	    DOWNSIZE(badreg, numRects);
	}
	good(badreg);
	return PIXMAN_REGION_STATUS_SUCCESS;
    }

    /* Step 1: Sort the rects array into ascending (y1, x1) order */
    QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);

    /* Step 2: Scatter the sorted array into the minimum number of regions */

    /* Set up the first region to be the first rectangle in badreg */
    /* Note that step 2 code will never overflow the ri[0].reg rects array */
    ri = (RegionInfo *) malloc(4 * sizeof(RegionInfo));
    if (!ri)
	return pixman_break (badreg);
    sizeRI = 4;
    numRI = 1;
    ri[0].prevBand = 0;
    ri[0].curBand = 0;
    ri[0].reg = *badreg;
    box = PIXREGION_BOXPTR(&ri[0].reg);
    ri[0].reg.extents = *box;
    ri[0].reg.data->numRects = 1;

    /* Now scatter rectangles into the minimum set of valid regions.  If the
       next rectangle to be added to a region would force an existing rectangle
       in the region to be split up in order to maintain y-x banding, just
       forget it.  Try the next region.  If it doesn't fit cleanly into any
       region, make a new one. */

    for (i = numRects; --i > 0;)
    {
	box++;
	/* Look for a region to append box to */
	for (j = numRI, rit = ri; --j >= 0; rit++)
	{
	    reg = &rit->reg;
	    riBox = PIXREGION_END(reg);

	    if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
	    {
		/* box is in same band as riBox.  Merge or append it */
		if (box->x1 <= riBox->x2)
		{
		    /* Merge it with riBox */
		    if (box->x1 < riBox->x2) *pOverlap = PIXMAN_REGION_STATUS_SUCCESS;
		    if (box->x2 > riBox->x2) riBox->x2 = box->x2;
		}
		else
		{
		    RECTALLOC_BAIL(reg, 1, bail);
		    *PIXREGION_TOP(reg) = *box;
		    reg->data->numRects++;
		}
		goto NextRect;   /* So sue me */
	    }
	    else if (box->y1 >= riBox->y2)
	    {
		/* Put box into new band */
		if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
		if (reg->extents.x1 > box->x1)   reg->extents.x1 = box->x1;
		Coalesce(reg, rit->prevBand, rit->curBand);
		rit->curBand = reg->data->numRects;
		RECTALLOC_BAIL(reg, 1, bail);
		*PIXREGION_TOP(reg) = *box;
		reg->data->numRects++;
		goto NextRect;
	    }
	    /* Well, this region was inappropriate.  Try the next one. */
	} /* for j */

	/* Uh-oh.  No regions were appropriate.  Create a new one. */
	if (sizeRI == numRI)
	{
	    /* Oops, allocate space for new region information */
	    sizeRI <<= 1;
	    rit = (RegionInfo *) realloc(ri, sizeRI * sizeof(RegionInfo));
	    if (!rit)
		goto bail;
	    ri = rit;
	    rit = &ri[numRI];
	}
	numRI++;
	rit->prevBand = 0;
	rit->curBand = 0;
	rit->reg.extents = *box;
	rit->reg.data = (pixman_region16_data_t *)NULL;
	if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
	    goto bail;
NextRect: ;
    } /* for i */

    /* Make a final pass over each region in order to Coalesce and set
       extents.x2 and extents.y2 */

    for (j = numRI, rit = ri; --j >= 0; rit++)
    {
	reg = &rit->reg;
	riBox = PIXREGION_END(reg);
	reg->extents.y2 = riBox->y2;
	if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
	Coalesce(reg, rit->prevBand, rit->curBand);
	if (reg->data->numRects == 1) /* keep unions happy below */
	{
	    freeData(reg);
	    reg->data = (pixman_region16_data_t *)NULL;
	}
    }

    /* Step 3: Union all regions into a single region */
    while (numRI > 1)
    {
	int half = numRI/2;
	for (j = numRI & 1; j < (half + (numRI & 1)); j++)
	{
	    reg = &ri[j].reg;
	    hreg = &ri[j+half].reg;
	    if (!pixman_op(reg, reg, hreg, pixman_region_unionO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_SUCCESS, pOverlap))
		ret = PIXMAN_REGION_STATUS_FAILURE;
	    if (hreg->extents.x1 < reg->extents.x1)
		reg->extents.x1 = hreg->extents.x1;
	    if (hreg->extents.y1 < reg->extents.y1)
		reg->extents.y1 = hreg->extents.y1;
	    if (hreg->extents.x2 > reg->extents.x2)
		reg->extents.x2 = hreg->extents.x2;
	    if (hreg->extents.y2 > reg->extents.y2)
		reg->extents.y2 = hreg->extents.y2;
	    freeData(hreg);
	}
	numRI -= half;
    }
    *badreg = ri[0].reg;
    free(ri);
    good(badreg);
    return ret;
bail:
    for (i = 0; i < numRI; i++)
	freeData(&ri[i].reg);
    free (ri);
    return pixman_break (badreg);
}

/* XXX: Need to fix this to not use any X data structure
pixman_region16_t *
pixman_region_rectsToRegion(nrects, prect, ctype)
    int			nrects;
    xRectangle	*prect;
    int			ctype;
{
    pixman_region16_t *	region;
    pixman_region16_data_t *	pData;
    pixman_box16_t *	box;
    int        i;
    int			x1, y1, x2, y2;

    region = pixman_region_create(NullBox, 0);
    if (PIXREGION_NAR (region))
	return region;
    if (!nrects)
	return region;
    if (nrects == 1)
    {
	x1 = prect->x;
	y1 = prect->y;
	if ((x2 = x1 + (int) prect->width) > SHRT_MAX)
	    x2 = SHRT_MAX;
	if ((y2 = y1 + (int) prect->height) > SHRT_MAX)
	    y2 = SHRT_MAX;
	if (x1 != x2 && y1 != y2)
	{
	    region->extents.x1 = x1;
	    region->extents.y1 = y1;
	    region->extents.x2 = x2;
	    region->extents.y2 = y2;
	    region->data = (pixman_region16_data_t *)NULL;
	}
	return region;
    }
    pData = allocData(nrects);
    if (!pData)
    {
	pixman_break (region);
	return region;
    }
    box = (pixman_box16_t *) (pData + 1);
    for (i = nrects; --i >= 0; prect++)
    {
	x1 = prect->x;
	y1 = prect->y;
	if ((x2 = x1 + (int) prect->width) > SHRT_MAX)
	    x2 = SHRT_MAX;
	if ((y2 = y1 + (int) prect->height) > SHRT_MAX)
	    y2 = SHRT_MAX;
	if (x1 != x2 && y1 != y2)
	{
	    box->x1 = x1;
	    box->y1 = y1;
	    box->x2 = x2;
	    box->y2 = y2;
	    box++;
	}
    }
    if (box != (pixman_box16_t *) (pData + 1))
    {
	pData->size = nrects;
	pData->numRects = box - (pixman_box16_t *) (pData + 1);
    	region->data = pData;
    	if (ctype != CT_YXBANDED)
    	{
	    int overlap;
	    region->extents.x1 = region->extents.x2 = 0;
	    pixman_region_validate(region, &overlap);
    	}
    	else
	    pixman_set_extents(region);
    	good(region);
    }
    else
    {
	free (pData);
    }
    return region;
}
*/

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

/*-
 *-----------------------------------------------------------------------
 * pixman_region_subtractO --
 *	Overlapping band subtraction. x1 is the left-most point not yet
 *	checked.
 *
 * Results:
 *	PIXMAN_REGION_STATUS_SUCCESS if successful.
 *
 * Side Effects:
 *	region may have rectangles added to it.
 *
 *-----------------------------------------------------------------------
 */
/*ARGSUSED*/
static pixman_region_status_t
pixman_region_subtractO (
    pixman_region16_t *	region,
    pixman_box16_t *	r1,
    pixman_box16_t *  	  	r1End,
    pixman_box16_t *	r2,
    pixman_box16_t *  	  	r2End,
    short  	y1,
             short  	y2,
    int		*pOverlap)
{
    pixman_box16_t *	pNextRect;
    int  	x1;

    x1 = r1->x1;

    assert(y1<y2);
    assert(r1 != r1End && r2 != r2End);

    pNextRect = PIXREGION_TOP(region);

    do
    {
	if (r2->x2 <= x1)
	{
	    /*
	     * Subtrahend entirely to left of minuend: go to next subtrahend.
	     */
	    r2++;
	}
	else if (r2->x1 <= x1)
	{
	    /*
	     * Subtrahend preceeds minuend: nuke left edge of minuend.
	     */
	    x1 = r2->x2;
	    if (x1 >= r1->x2)
	    {
		/*
		 * Minuend completely covered: advance to next minuend and
		 * reset left fence to edge of new minuend.
		 */
		r1++;
		if (r1 != r1End)
		    x1 = r1->x1;
	    }
	    else
	    {
		/*
		 * Subtrahend now used up since it doesn't extend beyond