region.c

这是一个开放源代码的与WINNT/WIN2K/WIN2003兼容的操作系统

 *
 * Side Effects:
 *      The new region is overwritten.
 *
 *\note The idea behind this function is to view the two regions as sets.
 *      Together they cover a rectangle of area that this function divides
 *      into horizontal bands where points are covered only by one region
 *      or by both. For the first case, the nonOverlapFunc is called with
 *      each the band and the band's upper and lower extents. For the
 *      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 FASTCALL
REGION_RegionOp(
	ROSRGNDATA *newReg, /* Place to store result */
	ROSRGNDATA *reg1,   /* First region in operation */
	ROSRGNDATA *reg2,   /* 2nd region in operation */
	overlapProcp overlapFunc,     /* Function to call for over-lapping bands */
	nonOverlapProcp nonOverlap1Func, /* Function to call for non-overlapping bands in region 1 */
	nonOverlapProcp nonOverlap2Func  /* Function to call for non-overlapping bands in region 2 */
	)
{
    RECT *r1;                         /* Pointer into first region */
    RECT *r2;                         /* Pointer into 2d region */
    RECT *r1End;                      /* End of 1st region */
    RECT *r2End;                      /* End of 2d region */
    INT ybot;                         /* Bottom of intersection */
    INT ytop;                         /* Top of intersection */
    RECT *oldRects;                   /* Old rects for newReg */
    ULONG prevBand;                   /* Index of start of
						 * previous band in newReg */
    ULONG curBand;                    /* Index of start of current band in newReg */
    RECT *r1BandEnd;                  /* End of current band in r1 */
    RECT *r2BandEnd;                  /* End of current band in r2 */
    ULONG top;                        /* Top of non-overlapping band */
    ULONG 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 = (PRECT)reg1->Buffer;
    r2 = (PRECT)reg2->Buffer;
    r1End = r1 + reg1->rdh.nCount;
    r2End = r2 + reg2->rdh.nCount;


    /*
     * newReg may be one of the src regions so we can't empty it. We keep a
     * note of its rects pointer (so that we can free them later), preserve its
     * extents and simply set numRects to zero.
     */

    oldRects = (PRECT)newReg->Buffer;
    newReg->rdh.nCount = 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 Xrealloc() at the end of this function eventually.
     */
    newReg->rdh.nRgnSize = max(reg1->rdh.nCount,reg2->rdh.nCount) * 2 * sizeof(RECT);

    if (! (newReg->Buffer = ExAllocatePoolWithTag( PagedPool, newReg->rdh.nRgnSize, TAG_REGION )))
    {
		newReg->rdh.nRgnSize = 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->rdh.rcBound.top < reg2->rdh.rcBound.top)
		ybot = reg1->rdh.rcBound.top;
    else
		ybot = reg2->rdh.rcBound.top;

    /*
     * 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->rdh.nCount;

		/*
		 * 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 = max(r1->top,ybot);
		    bot = min(r1->bottom,r2->top);

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

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

		    if ((top != bot) && (nonOverlap2Func != NULL))
		    {
				(* nonOverlap2Func) (newReg, 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 (newReg->rdh.nCount != curBand)
		{
		    prevBand = REGION_Coalesce (newReg, prevBand, curBand);
		}

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

		if (newReg->rdh.nCount != curBand)
		{
		    prevBand = REGION_Coalesce (newReg, prevBand, curBand);
		}

		/*
		 * If we've finished with a band (bottom == 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 = newReg->rdh.nCount;
    if (r1 != r1End)
    {
		if (nonOverlap1Func != NULL)
		{
		    do
		    {
				r1BandEnd = r1;
				while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
				{
				    r1BandEnd++;
				}
				(* nonOverlap1Func) (newReg, r1, r1BandEnd,
						     max(r1->top,ybot), r1->bottom);
				r1 = r1BandEnd;
		    } while (r1 != r1End);
		}
    }
    else if ((r2 != r2End) && (nonOverlap2Func != NULL))
    {
		do
		{
		    r2BandEnd = r2;
		    while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
		    {
			 r2BandEnd++;
		    }
		    (* nonOverlap2Func) (newReg, r2, r2BandEnd,
					max(r2->top,ybot), r2->bottom);
		    r2 = r2BandEnd;
		} while (r2 != r2End);
    }

    if (newReg->rdh.nCount != curBand)
    {
		(void) REGION_Coalesce (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 ((2 * newReg->rdh.nCount*sizeof(RECT) < newReg->rdh.nRgnSize && (newReg->rdh.nCount > 2)))
    {
		if (REGION_NOT_EMPTY(newReg))
		{
		    RECT *prev_rects = (PRECT)newReg->Buffer;
		    newReg->Buffer = ExAllocatePoolWithTag( PagedPool, newReg->rdh.nCount*sizeof(RECT), TAG_REGION );

		    if (! newReg->Buffer)
				newReg->Buffer = prev_rects;
			else{
				newReg->rdh.nRgnSize = newReg->rdh.nCount*sizeof(RECT);
				COPY_RECTS(newReg->Buffer, prev_rects, newReg->rdh.nCount);
				if (prev_rects != &newReg->rdh.rcBound)
					ExFreePool( prev_rects );
			}
		}
		else
		{
		    /*
		     * No point in doing the extra work involved in an Xrealloc if
		     * the region is empty
		     */
		    newReg->rdh.nRgnSize = sizeof(RECT);
		    if (newReg->Buffer != &newReg->rdh.rcBound)
			ExFreePool( newReg->Buffer );
		    newReg->Buffer = ExAllocatePoolWithTag( PagedPool, sizeof(RECT), TAG_REGION );
			ASSERT( newReg->Buffer );
		}
    }

	if( newReg->rdh.nCount == 0 )
		newReg->rdh.iType = NULLREGION;
	else
		newReg->rdh.iType = (newReg->rdh.nCount > 1)? COMPLEXREGION : SIMPLEREGION;

	if (oldRects != &newReg->rdh.rcBound)
		ExFreePool( oldRects );
    return;
}

/***********************************************************************
 *          Region Intersection
 ***********************************************************************/


/*!
 * Handle an overlapping band for REGION_Intersect.
 *
 * Results:
 *      None.
 *
 * \note Side Effects:
 *      Rectangles may be added to the region.
 *
 */
static void FASTCALL
REGION_IntersectO (
	PROSRGNDATA pReg,
	PRECT       r1,
	PRECT       r1End,
	PRECT       r2,
	PRECT       r2End,
	INT         top,
	INT         bottom
	)
{
    INT       left, right;
    RECT      *pNextRect;

    pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;

    while ((r1 != r1End) && (r2 != r2End))
    {
		left = max(r1->left, r2->left);
		right =	min(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 (left < right)
		{
		    MEMCHECK(pReg, pNextRect, pReg->Buffer);
		    pNextRect->left = left;
		    pNextRect->top = top;
		    pNextRect->right = right;
		    pNextRect->bottom = bottom;
		    pReg->rdh.nCount += 1;
		    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++;
		}
    }
    return;
}

/***********************************************************************
 *	     REGION_IntersectRegion
 */
static void FASTCALL REGION_IntersectRegion(ROSRGNDATA *newReg, ROSRGNDATA *reg1,
				   ROSRGNDATA *reg2)
{
  /* check for trivial reject */
  if ( (!(reg1->rdh.nCount)) || (!(reg2->rdh.nCount))  ||
    (!EXTENTCHECK(&reg1->rdh.rcBound, &reg2->rdh.rcBound)))
    newReg->rdh.nCount = 0;
  else
    REGION_RegionOp (newReg, reg1, reg2,
      REGION_IntersectO, NULL, NULL);

    /*
     * Can't alter newReg'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 same. Besides, this
     * way there's no checking against rectangles that will be nuked
     * due to coalescing, so we have to examine fewer rectangles.
     */

    REGION_SetExtents(newReg);
}

/***********************************************************************
 *	     Region Union
 ***********************************************************************/

/*!
 *      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.
 *
 * \note Side Effects:
 *      pReg->numRects is incremented and the final rectangles overwritten
 *      with the rectangles we're passed.
 *
 */
static void FASTCALL
REGION_UnionNonO (
	PROSRGNDATA pReg,
	PRECT       r,
	PRECT       rEnd,
	INT         top,
	INT         bottom
	)
{
    RECT *pNextRect;

    pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;

    while (r != rEnd)
    {
		MEMCHECK(pReg, pNextRect, pReg->Buffer);
		pNextRect->left = r->left;
		pNextRect->top = top;
		pNextRect->right = r->right;
		pNextRect->bottom = bottom;
		pReg->rdh.nCount += 1;
		pNextRect++;
		r++;
    }
    return;
}

/*!
 *      Handle an overlapping band for the union operation. Picks the
 *      left-most rectangle each time and merges it into the region.
 *
 * Results: