Back to index

lightning-sunbird  0.9+nobinonly
Defines | Typedefs | Functions | Variables
pixregion.c File Reference
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include "pixregionint.h"
#include "slim_internal.h"

Go to the source code of this file.

Defines

#define INLINE
#define assert(expr)
#define good(reg)   assert(pixman_region16_valid(reg))
#define MIN(a, b)   ((a) < (b) ? (a) : (b))
#define MAX(a, b)   ((a) > (b) ? (a) : (b))
#define EXTENTCHECK(r1, r2)
#define INBOX(r, x, y)
#define SUBSUMES(r1, r2)
#define allocData(n)   malloc(PIXREGION_SZOF(n))
#define freeData(reg)   if ((reg)->data && (reg)->data->size) free((reg)->data)
#define RECTALLOC_BAIL(pReg, n, bail)
#define RECTALLOC(pReg, n)
#define ADDRECT(pNextRect, nx1, ny1, nx2, ny2)
#define NEWRECT(pReg, pNextRect, nx1, ny1, nx2, ny2)
#define DOWNSIZE(reg, numRects)
#define Coalesce(newReg, prevBand, curBand)
#define FindBand(r, rBandEnd, rEnd, ry1)
#define AppendRegions(newReg, r, rEnd)
#define MERGERECT(r)
#define ExchangeRects(a, b)
#define ExchangeSpans(a, b)
#define NextBand()

Typedefs

typedef pixman_region_status_t(* OverlapProcPtr )(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)

Functions

static pixman_region_status_t pixman_break (pixman_region16_t *pReg)
static void pixman_init (pixman_region16_t *region, pixman_box16_t *rect)
static void pixman_uninit (pixman_region16_t *region)
 slim_hidden_proto (pixman_region_create_simple)
pixman_region16_t * pixman_region_create_simple (pixman_box16_t *extents)
 slim_hidden_def (pixman_region_create_simple)
void pixman_region_destroy (pixman_region16_t *region)
int pixman_region_num_rects (pixman_region16_t *region)
pixman_box16_tpixman_region_rects (pixman_region16_t *region)
static pixman_region_status_t pixman_rect_alloc (pixman_region16_t *region, int n)
pixman_region_status_t pixman_region_copy (pixman_region16_t *dst, pixman_region16_t *src)
 slim_hidden_def (pixman_region_copy)
static INLINE int pixman_coalesce (pixman_region16_t *region, int prevStart, int curStart)
static INLINE
pixman_region_status_t 
pixman_region_appendNonO (pixman_region16_t *region, pixman_box16_t *r, pixman_box16_t *rEnd, int y1, int y2)
static pixman_region_status_t pixman_op (pixman_region16_t *newReg, pixman_region16_t *reg1, pixman_region16_t *reg2, OverlapProcPtr overlapFunc, int appendNon1, int appendNon2, int *pOverlap)
static void pixman_set_extents (pixman_region16_t *region)
static pixman_region_status_t pixman_region_intersectO (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_region_status_t pixman_region_intersect (pixman_region16_t *newReg, pixman_region16_t *reg1, pixman_region16_t *reg2)
static pixman_region_status_t pixman_region_unionO (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_region_status_t pixman_region_union_rect (pixman_region16_t *dest, pixman_region16_t *source, int x, int y, unsigned int width, unsigned int height)
pixman_region_status_t pixman_region_union (pixman_region16_t *newReg, pixman_region16_t *reg1, pixman_region16_t *reg2)
 slim_hidden_def (pixman_region_union)
pixman_region_status_t pixman_region_append (pixman_region16_t *dstrgn, pixman_region16_t *rgn)
static void QuickSortRects (pixman_box16_t rects[], int numRects)
pixman_region_status_t pixman_region_validate (pixman_region16_t *badreg, int *pOverlap)
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_region_status_t pixman_region_subtract (pixman_region16_t *regD, pixman_region16_t *regM, pixman_region16_t *regS)
pixman_region_status_t pixman_region_inverse (pixman_region16_t *newReg, pixman_region16_t *reg1, pixman_box16_t *invRect)
int pixman_region_contains_rectangle (pixman_region16_t *region, pixman_box16_t *prect)
void pixman_region_translate (pixman_region16_t *region, int x, int y)
void pixman_region_reset (pixman_region16_t *region, pixman_box16_t *box)
int pixman_region_contains_point (pixman_region16_t *region, int x, int y, pixman_box16_t *box)
int pixman_region_not_empty (pixman_region16_t *region)
void pixman_region_empty (pixman_region16_t *region)
pixman_box16_tpixman_region_extents (pixman_region16_t *region)
static void QuickSortSpans (pixman_region16_point_t spans[], int widths[], int numSpans)

Variables

static pixman_box16_t pixman_region_emptyBox = {0, 0, 0, 0}
static pixman_region16_data_t pixman_region_emptyData = {0, 0}
static pixman_region16_data_t pixman_brokendata = {0, 0}
static pixman_region16_t pixman_brokenregion = { { 0, 0, 0, 0 }, &pixman_brokendata }

Define Documentation

#define ADDRECT (   pNextRect,
  nx1,
  ny1,
  nx2,
  ny2 
)
Value:
{                                         \
    pNextRect->x1 = nx1;                  \
    pNextRect->y1 = ny1;                  \
    pNextRect->x2 = nx2;                  \
    pNextRect->y2 = ny2;                  \
    pNextRect++;                          \
}
#define AppendRegions (   newReg,
  r,
  rEnd 
)
Value:
{                                                              \
    int newRects;                                              \
    if ((newRects = rEnd - r)) {                               \
       RECTALLOC(newReg, newRects);                                   \
       memmove((char *)PIXREGION_TOP(newReg),(char *)r,                      \
              newRects * sizeof(pixman_box16_t));                            \
       newReg->data->numRects += newRects;                            \
    }                                                          \
}

Definition at line 607 of file pixregion.c.

#define assert (   expr)

Definition at line 70 of file pixregion.c.

#define Coalesce (   newReg,
  prevBand,
  curBand 
)
Value:
if (curBand - prevBand == newReg->data->numRects - curBand) {  \
       prevBand = pixman_coalesce(newReg, prevBand, curBand);         \
    } else {                                                   \
       prevBand = curBand;                                     \
    }

Definition at line 545 of file pixregion.c.

#define DOWNSIZE (   reg,
  numRects 
)
Value:
if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
{                                                               \
    pixman_region16_data_t * NewData;                                                \
    NewData = (pixman_region16_data_t *)realloc((reg)->data, PIXREGION_SZOF(numRects));     \
    if (NewData)                                                \
    {                                                           \
       NewData->size = (numRects);                              \
       (reg)->data = NewData;                                          \
    }                                                           \
}
#define ExchangeRects (   a,
  b 
)
Value:
{                        \
    pixman_box16_t     t;       \
    t = rects[a];        \
    rects[a] = rects[b];    \
    rects[b] = t;        \
}

Definition at line 1355 of file pixregion.c.

#define ExchangeSpans (   a,
  b 
)
Value:
{                                                    \
    pixman_region16_point_t tpt;                                   \
    int    tw;                                              \
                                                     \
    tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt;    \
    tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
}

Definition at line 2285 of file pixregion.c.

#define EXTENTCHECK (   r1,
  r2 
)
Value:
(!( ((r1)->x2 <= (r2)->x1)  || \
          ((r1)->x1 >= (r2)->x2)  || \
          ((r1)->y2 <= (r2)->y1)  || \
          ((r1)->y1 >= (r2)->y2) ) )
#define FindBand (   r,
  rBandEnd,
  rEnd,
  ry1 
)
Value:
{                                                    \
    ry1 = r->y1;                                     \
    rBandEnd = r+1;                                  \
    while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) {   \
       rBandEnd++;                                   \
    }                                                \
}

Definition at line 598 of file pixregion.c.

#define freeData (   reg)    if ((reg)->data && (reg)->data->size) free((reg)->data)
#define good (   reg)    assert(pixman_region16_valid(reg))

Definition at line 73 of file pixregion.c.

#define INBOX (   r,
  x,
  y 
)
Value:
( ((r)->x2 >  x) && \
        ((r)->x1 <= x) && \
        ((r)->y2 >  y) && \
        ((r)->y1 <= y) )

Definition at line 61 of file pixregion.c.

#define MAX (   a,
  b 
)    ((a) > (b) ? (a) : (b))

Definition at line 76 of file pixregion.c.

#define MERGERECT (   r)
Value:
{                                                       \
    if (r->x1 <= x2) {                                         \
       /* Merge with current rectangle */               \
       if (r->x1 < x2) *pOverlap = PIXMAN_REGION_STATUS_SUCCESS;                           \
       if (x2 < r->x2) x2 = r->x2;                      \
    } else {                                            \
       /* Add current rectangle, start new one */              \
       NEWRECT(region, pNextRect, x1, y1, x2, y2);             \
       x1 = r->x1;                                      \
       x2 = r->x2;                                      \
    }                                                   \
    r++;                                                \
}

Definition at line 1059 of file pixregion.c.

#define MIN (   a,
  b 
)    ((a) < (b) ? (a) : (b))

Definition at line 75 of file pixregion.c.

#define NEWRECT (   pReg,
  pNextRect,
  nx1,
  ny1,
  nx2,
  ny2 
)
Value:
{                                                              \
    if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
    {                                                          \
       if (!pixman_rect_alloc(pReg, 1))                               \
           return PIXMAN_REGION_STATUS_FAILURE;                                     \
       pNextRect = PIXREGION_TOP(pReg);                               \
    }                                                          \
    ADDRECT(pNextRect,nx1,ny1,nx2,ny2);                               \
    pReg->data->numRects++;                                    \
    assert(pReg->data->numRects<=pReg->data->size);                   \
}
Value:
{                                                           \
    clipy1 = pboxBandStart->y1;                                    \
    clipy2 = pboxBandStart->y2;                                    \
    pboxBandEnd = pboxBandStart + 1;                               \
    while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) {  \
       pboxBandEnd++;                                              \
    }                                                       \
    for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
}

Definition at line 2385 of file pixregion.c.

#define RECTALLOC (   pReg,
  n 
)
Value:
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
    if (!pixman_rect_alloc(pReg, n)) { return PIXMAN_REGION_STATUS_FAILURE; }
#define RECTALLOC_BAIL (   pReg,
  n,
  bail 
)
Value:
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
    if (!pixman_rect_alloc(pReg, n)) { goto bail; }
#define SUBSUMES (   r1,
  r2 
)
Value:
( ((r1)->x1 <= (r2)->x1) && \
        ((r1)->x2 >= (r2)->x2) && \
        ((r1)->y1 <= (r2)->y1) && \
        ((r1)->y2 >= (r2)->y2) )

Typedef Documentation

typedef pixman_region_status_t(* OverlapProcPtr)(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)

Definition at line 647 of file pixregion.c.


Function Documentation

static pixman_region_status_t pixman_break ( pixman_region16_t *  pReg) [static]

Definition at line 386 of file pixregion.c.

{
    freeData (region);
    region->extents = pixman_region_emptyBox;
    region->data = &pixman_brokendata;
    return PIXMAN_REGION_STATUS_FAILURE;
}

Here is the caller graph for this function:

static INLINE int pixman_coalesce ( pixman_region16_t *  region,
int  prevStart,
int  curStart 
) [static]

Definition at line 486 of file pixregion.c.

{
    pixman_box16_t * pPrevBox;     /* Current box in previous band         */
    pixman_box16_t * pCurBox;      /* Current box in current band       */
    int       numRects;     /* Number rectangles in both bands   */
    int       y2;           /* Bottom of current band        */
    /*
     * Figure out how many rectangles are in the band.
     */
    numRects = curStart - prevStart;
    assert(numRects == region->data->numRects - curStart);

    if (!numRects) return curStart;

    /*
     * The bands may only be coalesced if the bottom of the previous
     * matches the top scanline of the current.
     */
    pPrevBox = PIXREGION_BOX(region, prevStart);
    pCurBox = PIXREGION_BOX(region, curStart);
    if (pPrevBox->y2 != pCurBox->y1) return curStart;

    /*
     * 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.
     */
    y2 = pCurBox->y2;

    do {
       if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
           return (curStart);
       }
       pPrevBox++;
       pCurBox++;
       numRects--;
    } while (numRects);

    /*
     * The bands may be merged, so set the bottom y of each box
     * in the previous band to the bottom y of the current band.
     */
    numRects = curStart - prevStart;
    region->data->numRects -= numRects;
    do {
       pPrevBox--;
       pPrevBox->y2 = y2;
       numRects--;
    } while (numRects);
    return prevStart;
}
static void pixman_init ( pixman_region16_t *  region,
pixman_box16_t rect 
) [static]

Definition at line 343 of file pixregion.c.

{
    if (extents)
    {
       region->extents = *extents;
       region->data = NULL;
    }
    else
    {
       region->extents = pixman_region_emptyBox;
       region->data = &pixman_region_emptyData;
    }
}

Here is the caller graph for this function:

static pixman_region_status_t pixman_op ( pixman_region16_t *  newReg,
pixman_region16_t *  reg1,
pixman_region16_t *  reg2,
OverlapProcPtr  overlapFunc,
int  appendNon1,
int  appendNon2,
int pOverlap 
) [static]

Definition at line 658 of file pixregion.c.

{
    pixman_box16_t * r1;                      /* Pointer into first region     */
    pixman_box16_t * r2;                      /* Pointer into 2d region           */
    pixman_box16_t *     r1End;               /* End of 1st region         */
    pixman_box16_t *     r2End;               /* End of 2d region                 */
    short         ybot;                /* Bottom of intersection           */
    short         ytop;                /* Top of intersection       */
    pixman_region16_data_t *           oldData;             /* Old data for newReg       */
    int                  prevBand;            /* Index of start of
                                        * previous band in newReg       */
    int                  curBand;             /* Index of start of current
                                        * band in newReg                   */
    pixman_box16_t * r1BandEnd;               /* End of current band in r1     */
    pixman_box16_t * r2BandEnd;               /* End of current band in r2     */
    short         top;                 /* Top of non-overlapping band   */
    short         bot;                 /* Bottom of non-overlapping band*/
    int    r1y1;                /* Temps for r1->y1 and r2->y1   */
    int    r2y1;
    int                  newSize;
    int                  numRects;

    /*
     * Break any region computed from a broken region
     */
    if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2))
       return pixman_break (newReg);
    
    /*
     * Initialization:
     * set r1, r2, r1End and r2End appropriately, save the rectangles
     * 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 = PIXREGION_RECTS(reg1);
    newSize = PIXREGION_NUM_RECTS(reg1);
    r1End = r1 + newSize;
    numRects = PIXREGION_NUM_RECTS(reg2);
    r2 = PIXREGION_RECTS(reg2);
    r2End = r2 + numRects;
    assert(r1 != r1End);
    assert(r2 != r2End);

    oldData = (pixman_region16_data_t *)NULL;
    if (((newReg == reg1) && (newSize > 1)) ||
       ((newReg == reg2) && (numRects > 1)))
    {
       oldData = newReg->data;
       newReg->data = &pixman_region_emptyData;
    }
    /* guess at new size */
    if (numRects > newSize)
       newSize = numRects;
    newSize <<= 1;
    if (!newReg->data)
       newReg->data = &pixman_region_emptyData;
    else if (newReg->data->size)
       newReg->data->numRects = 0;
    if (newSize > newReg->data->size)
       if (!pixman_rect_alloc(newReg, newSize))
           return PIXMAN_REGION_STATUS_FAILURE;

    /*
     * Initialize ybot.
     * 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.
     */

    ybot = MIN(r1->y1, r2->y1);
    
    /*
     * prevBand serves to mark the start of the previous band so rectangles
     * can be coalesced into larger rectangles. qv. pixman_coalesce, 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 {
       /*
        * 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.
        */
       assert(r1 != r1End);
       assert(r2 != r2End);
    
       FindBand(r1, r1BandEnd, r1End, r1y1);
       FindBand(r2, r2BandEnd, r2End, r2y1);

       /*
        * 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 (r1y1 < r2y1) {
           if (appendNon1) {
              top = MAX(r1y1, ybot);
              bot = MIN(r1->y2, r2y1);
              if (top != bot)      {
                  curBand = newReg->data->numRects;
                  pixman_region_appendNonO(newReg, r1, r1BandEnd, top, bot);
                  Coalesce(newReg, prevBand, curBand);
              }
           }
           ytop = r2y1;
       } else if (r2y1 < r1y1) {
           if (appendNon2) {
              top = MAX(r2y1, ybot);
              bot = MIN(r2->y2, r1y1);
              if (top != bot) {
                  curBand = newReg->data->numRects;
                  pixman_region_appendNonO(newReg, r2, r2BandEnd, top, bot);
                  Coalesce(newReg, prevBand, curBand);
              }
           }
           ytop = r1y1;
       } else {
           ytop = r1y1;
       }

       /*
        * Now see if we've hit an intersecting band. The two bands only
        * intersect if ybot > ytop
        */
       ybot = MIN(r1->y2, r2->y2);
       if (ybot > ytop) {
           curBand = newReg->data->numRects;
           (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
                         pOverlap);
           Coalesce(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 (if any) still has rectangles left.
     *
     * We only need to worry about banding and coalescing for the very first
     * band left.  After that, we can just group all remaining boxes,
     * regardless of how many bands, into one final append to the list.
     */

    if ((r1 != r1End) && appendNon1) {
       /* Do first nonOverlap1Func call, which may be able to coalesce */
       FindBand(r1, r1BandEnd, r1End, r1y1);
       curBand = newReg->data->numRects;
       pixman_region_appendNonO(newReg, r1, r1BandEnd, MAX(r1y1, ybot), r1->y2);
       Coalesce(newReg, prevBand, curBand);
       /* Just append the rest of the boxes  */
       AppendRegions(newReg, r1BandEnd, r1End);

    } else if ((r2 != r2End) && appendNon2) {
       /* Do first nonOverlap2Func call, which may be able to coalesce */
       FindBand(r2, r2BandEnd, r2End, r2y1);
       curBand = newReg->data->numRects;
       pixman_region_appendNonO(newReg, r2, r2BandEnd, MAX(r2y1, ybot), r2->y2);
       Coalesce(newReg, prevBand, curBand);
       /* Append rest of boxes */
       AppendRegions(newReg, r2BandEnd, r2End);
    }

    if (oldData)
       free(oldData);

    if (!(numRects = newReg->data->numRects))
    {
       freeData(newReg);
       newReg->data = &pixman_region_emptyData;
    }
    else if (numRects == 1)
    {
       newReg->extents = *PIXREGION_BOXPTR(newReg);
       freeData(newReg);
       newReg->data = (pixman_region16_data_t *)NULL;
    }
    else
    {
       DOWNSIZE(newReg, numRects);
    }

    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static pixman_region_status_t pixman_rect_alloc ( pixman_region16_t *  region,
int  n 
) [static]

Definition at line 395 of file pixregion.c.

{
    pixman_region16_data_t *data;
    
    if (!region->data)
    {
       n++;
       region->data = allocData(n);
       if (!region->data)
           return pixman_break (region);
       region->data->numRects = 1;
       *PIXREGION_BOXPTR(region) = region->extents;
    }
    else if (!region->data->size)
    {
       region->data = allocData(n);
       if (!region->data)
           return pixman_break (region);
       region->data->numRects = 0;
    }
    else
    {
       if (n == 1)
       {
           n = region->data->numRects;
           if (n > 500) /* XXX pick numbers out of a hat */
              n = 250;
       }
       n += region->data->numRects;
       data = (pixman_region16_data_t *)realloc(region->data, PIXREGION_SZOF(n));
       if (!data)
           return pixman_break (region);
       region->data = data;
    }
    region->data->size = n;
    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:

pixman_region_status_t pixman_region_append ( pixman_region16_t *  dstrgn,
pixman_region16_t *  rgn 
)

Definition at line 1269 of file pixregion.c.

{
    int numRects, dnumRects, size;
    pixman_box16_t *new, *old;
    int prepend;

    if (PIXREGION_NAR(rgn))
       return pixman_break (dstrgn);
    
    if (!rgn->data && (dstrgn->data == &pixman_region_emptyData))
    {
       dstrgn->extents = rgn->extents;
       dstrgn->data = (pixman_region16_data_t *)NULL;
       return PIXMAN_REGION_STATUS_SUCCESS;
    }

    numRects = PIXREGION_NUM_RECTS(rgn);
    if (!numRects)
       return PIXMAN_REGION_STATUS_SUCCESS;
    prepend = PIXMAN_REGION_STATUS_FAILURE;
    size = numRects;
    dnumRects = PIXREGION_NUM_RECTS(dstrgn);
    if (!dnumRects && (size < 200))
       size = 200; /* XXX pick numbers out of a hat */
    RECTALLOC(dstrgn, size);
    old = PIXREGION_RECTS(rgn);
    if (!dnumRects)
       dstrgn->extents = rgn->extents;
    else if (dstrgn->extents.x2 > dstrgn->extents.x1)
    {
       pixman_box16_t *first, *last;

       first = old;
       last = PIXREGION_BOXPTR(dstrgn) + (dnumRects - 1);
       if ((first->y1 > last->y2) ||
           ((first->y1 == last->y1) && (first->y2 == last->y2) &&
            (first->x1 > last->x2)))
       {
           if (rgn->extents.x1 < dstrgn->extents.x1)
              dstrgn->extents.x1 = rgn->extents.x1;
           if (rgn->extents.x2 > dstrgn->extents.x2)
              dstrgn->extents.x2 = rgn->extents.x2;
           dstrgn->extents.y2 = rgn->extents.y2;
       }
       else
       {
           first = PIXREGION_BOXPTR(dstrgn);
           last = old + (numRects - 1);
           if ((first->y1 > last->y2) ||
              ((first->y1 == last->y1) && (first->y2 == last->y2) &&
               (first->x1 > last->x2)))
           {
              prepend = PIXMAN_REGION_STATUS_SUCCESS;
              if (rgn->extents.x1 < dstrgn->extents.x1)
                  dstrgn->extents.x1 = rgn->extents.x1;
              if (rgn->extents.x2 > dstrgn->extents.x2)
                  dstrgn->extents.x2 = rgn->extents.x2;
              dstrgn->extents.y1 = rgn->extents.y1;
           }
           else
              dstrgn->extents.x2 = dstrgn->extents.x1;
       }
    }
    if (prepend)
    {
       new = PIXREGION_BOX(dstrgn, numRects);
       if (dnumRects == 1)
           *new = *PIXREGION_BOXPTR(dstrgn);
       else
           memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn), 
                dnumRects * sizeof(pixman_box16_t));
       new = PIXREGION_BOXPTR(dstrgn);
    }
    else
       new = PIXREGION_BOXPTR(dstrgn) + dnumRects;
    if (numRects == 1)
       *new = *old;
    else
       memmove((char *)new, (char *)old, numRects * sizeof(pixman_box16_t));
    dstrgn->data->numRects += numRects;
    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the call graph for this function:

static INLINE pixman_region_status_t pixman_region_appendNonO ( pixman_region16_t *  region,
pixman_box16_t r,
pixman_box16_t rEnd,
int  y1,
int  y2 
) [static]

Definition at line 570 of file pixregion.c.

{
    pixman_box16_t * pNextRect;
    int       newRects;

    newRects = rEnd - r;

    assert(y1 < y2);
    assert(newRects != 0);

    /* Make sure we have enough space for all rectangles to be added */
    RECTALLOC(region, newRects);
    pNextRect = PIXREGION_TOP(region);
    region->data->numRects += newRects;
    do {
       assert(r->x1 < r->x2);
       ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
       r++;
    } while (r != rEnd);

    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the caller graph for this function:

int pixman_region_contains_point ( pixman_region16_t *  region,
int  x,
int  y,
pixman_box16_t box 
)

Definition at line 2216 of file pixregion.c.

{
    pixman_box16_t *pbox, *pboxEnd;
    int numRects;

    good(region);
    numRects = PIXREGION_NUM_RECTS(region);
    if (!numRects || !INBOX(&region->extents, x, y))
        return(PIXMAN_REGION_STATUS_FAILURE);
    if (numRects == 1)
    {
       *box = region->extents;
       return(PIXMAN_REGION_STATUS_SUCCESS);
    }
    for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
        pbox != pboxEnd;
        pbox++)
    {
        if (y >= pbox->y2)
          continue;         /* not there yet */
       if ((y < pbox->y1) || (x < pbox->x1))
          break;            /* missed it */
       if (x >= pbox->x2)
          continue;         /* not there yet */
       *box = *pbox;
       return(PIXMAN_REGION_STATUS_SUCCESS);
    }
    return(PIXMAN_REGION_STATUS_FAILURE);
}
int pixman_region_contains_rectangle ( pixman_region16_t *  region,
pixman_box16_t prect 
)

Definition at line 1998 of file pixregion.c.

{
    int       x;
    int       y;
    pixman_box16_t *     pbox;
    pixman_box16_t *     pboxEnd;
    int                     partIn, partOut;
    int                     numRects;

    good(region);
    numRects = PIXREGION_NUM_RECTS(region);
    /* useful optimization */
    if (!numRects || !EXTENTCHECK(&region->extents, prect))
        return(rgnOUT);

    if (numRects == 1)
    {
       /* We know that it must be rgnIN or rgnPART */
       if (SUBSUMES(&region->extents, prect))
           return(rgnIN);
       else
           return(rgnPART);
    }

    partOut = PIXMAN_REGION_STATUS_FAILURE;
    partIn = PIXMAN_REGION_STATUS_FAILURE;

    /* (x,y) starts at upper left of rect, moving to the right and down */
    x = prect->x1;
    y = prect->y1;

    /* can stop when both partOut and partIn are PIXMAN_REGION_STATUS_SUCCESS, or we reach prect->y2 */
    for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
         pbox != pboxEnd;
         pbox++)
    {

        if (pbox->y2 <= y)
           continue;    /* getting up to speed or skipping remainder of band */

        if (pbox->y1 > y)
        {
           partOut = PIXMAN_REGION_STATUS_SUCCESS;      /* missed part of rectangle above */
           if (partIn || (pbox->y1 >= prect->y2))
              break;
           y = pbox->y1;        /* x guaranteed to be == prect->x1 */
        }

        if (pbox->x2 <= x)
           continue;            /* not far enough over yet */

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

        if (pbox->x1 < prect->x2)
        {
            partIn = PIXMAN_REGION_STATUS_SUCCESS;      /* definitely overlap */
            if (partOut)
               break;
        }

        if (pbox->x2 >= prect->x2)
        {
           y = pbox->y2;        /* finished with this band */
           if (y >= prect->y2)
              break;
           x = prect->x1;       /* 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...
            */
           partOut = PIXMAN_REGION_STATUS_SUCCESS;
           break;
       }
    }

    return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
}
pixman_region_status_t pixman_region_copy ( pixman_region16_t *  dst,
pixman_region16_t *  src 
)

Definition at line 434 of file pixregion.c.

{
    good(dst);
    good(src);
    if (dst == src)
       return PIXMAN_REGION_STATUS_SUCCESS;
    dst->extents = src->extents;
    if (!src->data || !src->data->size)
    {
       freeData(dst);
       dst->data = src->data;
       return PIXMAN_REGION_STATUS_SUCCESS;
    }
    if (!dst->data || (dst->data->size < src->data->numRects))
    {
       freeData(dst);
       dst->data = allocData(src->data->numRects);
       if (!dst->data)
           return pixman_break (dst);
       dst->data->size = src->data->numRects;
    }
    dst->data->numRects = src->data->numRects;
    memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src), 
         dst->data->numRects * sizeof(pixman_box16_t));
    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the call graph for this function:

pixman_region16_t* pixman_region_create_simple ( pixman_box16_t extents)

Definition at line 323 of file pixregion.c.

{
    pixman_region16_t *region;
   
    region = malloc (sizeof (pixman_region16_t));
    if (region == NULL)
       return &pixman_brokenregion;

    pixman_init (region, extents);

    return region;
}

Here is the call graph for this function:

void pixman_region_destroy ( pixman_region16_t *  region)

Definition at line 365 of file pixregion.c.

{
    pixman_uninit (region);

    if (region != &pixman_brokenregion)
       free (region);
}

Here is the call graph for this function:

void pixman_region_empty ( pixman_region16_t *  region)

Definition at line 2267 of file pixregion.c.

{
    good(region);
    freeData(region);
    region->extents.x2 = region->extents.x1;
    region->extents.y2 = region->extents.y1;
    region->data = &pixman_region_emptyData;
}
pixman_box16_t* pixman_region_extents ( pixman_region16_t *  region)

Definition at line 2278 of file pixregion.c.

{
    good(region);
    return(&region->extents);
}
pixman_region_status_t pixman_region_intersect ( pixman_region16_t *  newReg,
pixman_region16_t *  reg1,
pixman_region16_t *  reg2 
)

Definition at line 999 of file pixregion.c.

{
    good(reg1);
    good(reg2);
    good(newReg);
   /* check for trivial reject */
    if (PIXREGION_NIL(reg1)  || PIXREGION_NIL(reg2) ||
       !EXTENTCHECK(&reg1->extents, &reg2->extents))
    {
       /* Covers about 20% of all cases */
       freeData(newReg);
       newReg->extents.x2 = newReg->extents.x1;
       newReg->extents.y2 = newReg->extents.y1;
       if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
       {
           newReg->data = &pixman_brokendata;
           return PIXMAN_REGION_STATUS_FAILURE;
       }
       else
           newReg->data = &pixman_region_emptyData;
    }
    else if (!reg1->data && !reg2->data)
    {
       /* Covers about 80% of cases that aren't trivially rejected */
       newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
       newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
       newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
       newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
       freeData(newReg);
       newReg->data = (pixman_region16_data_t *)NULL;
    }
    else if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
    {
       return pixman_region_copy(newReg, reg1);
    }
    else if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
    {
       return pixman_region_copy(newReg, reg2);
    }
    else if (reg1 == reg2)
    {
       return pixman_region_copy(newReg, reg1);
    }
    else
    {
       /* General purpose intersection */
       int overlap; /* result ignored */
       if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, PIXMAN_REGION_STATUS_FAILURE, PIXMAN_REGION_STATUS_FAILURE,
                     &overlap))
           return PIXMAN_REGION_STATUS_FAILURE;
       pixman_set_extents(newReg);
    }

    good(newReg);
    return(PIXMAN_REGION_STATUS_SUCCESS);
}

Here is the call graph for this function:

static pixman_region_status_t pixman_region_intersectO ( 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 
) [static]

Definition at line 951 of file pixregion.c.

{
    int       x1;
    int       x2;
    pixman_box16_t * pNextRect;

    pNextRect = PIXREGION_TOP(region);

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

    do {
       x1 = MAX(r1->x1, r2->x1);
       x2 = MIN(r1->x2, r2->x2);

       /*
        * If there's any overlap between the two rectangles, add that
        * overlap to the new region.
        */
       if (x1 < x2)
           NEWRECT(region, pNextRect, x1, y1, x2, y2);

       /*
        * Advance the pointer(s) with the leftmost right side, since the next
        * rectangle on that list may still overlap the other region's
        * current rectangle.
        */
       if (r1->x2 == x2) {
           r1++;
       }
       if (r2->x2 == x2) {
           r2++;
       }
    } while ((r1 != r1End) && (r2 != r2End));

    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the caller graph for this function:

pixman_region_status_t pixman_region_inverse ( pixman_region16_t *  newReg,
pixman_region16_t *  reg1,
pixman_box16_t invRect 
)

Definition at line 1938 of file pixregion.c.

{
    pixman_region16_t         invReg;     /* Quick and dirty region made from the
                             * bounding box */
    int         overlap;    /* result ignored */

    good(reg1);
    good(newReg);
   /* check for trivial rejects */
    if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, &reg1->extents))
    {
       if (PIXREGION_NAR(reg1))
           return pixman_break (newReg);
       newReg->extents = *invRect;
       freeData(newReg);
       newReg->data = (pixman_region16_data_t *)NULL;
        return PIXMAN_REGION_STATUS_SUCCESS;
    }

    /* Add those rectangles in region 1 that aren't in region 2,
       do yucky substraction for overlaps, and
       just throw away rectangles in region 2 that aren't in region 1 */
    invReg.extents = *invRect;
    invReg.data = (pixman_region16_data_t *)NULL;
    if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_FAILURE, &overlap))
       return PIXMAN_REGION_STATUS_FAILURE;

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

Here is the call graph for this function:

int pixman_region_not_empty ( pixman_region16_t *  region)

Definition at line 2250 of file pixregion.c.

{
    good(region);
    return(!PIXREGION_NIL(region));
}
int pixman_region_num_rects ( pixman_region16_t *  region)

Definition at line 374 of file pixregion.c.

{
    return PIXREGION_NUM_RECTS (region);
}
pixman_box16_t* pixman_region_rects ( pixman_region16_t *  region)

Definition at line 380 of file pixregion.c.

{
    return PIXREGION_RECTS (region);
}
void pixman_region_reset ( pixman_region16_t *  region,
pixman_box16_t box 
)

Definition at line 2205 of file pixregion.c.

{
    good(region);
    assert(box->x1<=box->x2);
    assert(box->y1<=box->y2);
    region->extents = *box;
    freeData(region);
    region->data = (pixman_region16_data_t *)NULL;
}
pixman_region_status_t pixman_region_subtract ( pixman_region16_t *  regD,
pixman_region16_t *  regM,
pixman_region16_t *  regS 
)

Definition at line 1873 of file pixregion.c.

{
    int overlap; /* result ignored */

    good(regM);
    good(regS);
    good(regD);
   /* check for trivial rejects */
    if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
       !EXTENTCHECK(&regM->extents, &regS->extents))
    {
       if (PIXREGION_NAR (regS))
           return pixman_break (regD);
       return pixman_region_copy(regD, regM);
    }
    else if (regM == regS)
    {
       freeData(regD);
       regD->extents.x2 = regD->extents.x1;
       regD->extents.y2 = regD->extents.y1;
       regD->data = &pixman_region_emptyData;
       return PIXMAN_REGION_STATUS_SUCCESS;
    }
 
    /* Add those rectangles in region 1 that aren't in region 2,
       do yucky substraction for overlaps, and
       just throw away rectangles in region 2 that aren't in region 1 */
    if (!pixman_op(regD, regM, regS, pixman_region_subtractO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_FAILURE, &overlap))
       return PIXMAN_REGION_STATUS_FAILURE;

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

Here is the call graph for this function:

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 
) [static]

Definition at line 1749 of file pixregion.c.

{
    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
               * minuend
               */
              r2++;
           }
       }
       else if (r2->x1 < r1->x2)
       {
           /*
            * Left part of subtrahend covers part of minuend: add uncovered
            * part of minuend to region and skip to next subtrahend.
            */
           assert(x1<r2->x1);
           NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);

           x1 = r2->x2;
           if (x1 >= r1->x2)
           {
              /*
               * Minuend used up: advance to new...
               */
              r1++;
              if (r1 != r1End)
                  x1 = r1->x1;
           }
           else
           {
              /*
               * Subtrahend used up
               */
              r2++;
           }
       }
       else
       {
           /*
            * Minuend used up: add any remaining piece before advancing.
            */
           if (r1->x2 > x1)
              NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
           r1++;
           if (r1 != r1End)
              x1 = r1->x1;
       }
    } while ((r1 != r1End) && (r2 != r2End));


    /*
     * Add remaining minuend rectangles to region.
     */
    while (r1 != r1End)
    {
       assert(x1<r1->x2);
       NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
       r1++;
       if (r1 != r1End)
           x1 = r1->x1;
    }
    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the caller graph for this function:

void pixman_region_translate ( pixman_region16_t *  region,
int  x,
int  y 
)

Definition at line 2094 of file pixregion.c.

{
    int x1, x2, y1, y2;
    int nbox;
    pixman_box16_t * pbox;

    good(region);
    region->extents.x1 = x1 = region->extents.x1 + x;
    region->extents.y1 = y1 = region->extents.y1 + y;
    region->extents.x2 = x2 = region->extents.x2 + x;
    region->extents.y2 = y2 = region->extents.y2 + y;
    if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
    {
       if (region->data && (nbox = region->data->numRects))
       {
           for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
           {
              pbox->x1 += x;
              pbox->y1 += y;
              pbox->x2 += x;
              pbox->y2 += y;
           }
       }
       return;
    }
    if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
    {
       region->extents.x2 = region->extents.x1;
       region->extents.y2 = region->extents.y1;
       freeData(region);
       region->data = &pixman_region_emptyData;
       return;
    }
    if (x1 < SHRT_MIN)
       region->extents.x1 = SHRT_MIN;
    else if (x2 > SHRT_MAX)
       region->extents.x2 = SHRT_MAX;
    if (y1 < SHRT_MIN)
       region->extents.y1 = SHRT_MIN;
    else if (y2 > SHRT_MAX)
       region->extents.y2 = SHRT_MAX;
    if (region->data && (nbox = region->data->numRects))
    {
       pixman_box16_t * pboxout;

       for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
       {
           pboxout->x1 = x1 = pbox->x1 + x;
           pboxout->y1 = y1 = pbox->y1 + y;
           pboxout->x2 = x2 = pbox->x2 + x;
           pboxout->y2 = y2 = pbox->y2 + y;
           if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
               (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
           {
              region->data->numRects--;
              continue;
           }
           if (x1 < SHRT_MIN)
              pboxout->x1 = SHRT_MIN;
           else if (x2 > SHRT_MAX)
              pboxout->x2 = SHRT_MAX;
           if (y1 < SHRT_MIN)
              pboxout->y1 = SHRT_MIN;
           else if (y2 > SHRT_MAX)
              pboxout->y2 = SHRT_MAX;
           pboxout++;
       }
       if (pboxout != pbox)
       {
           if (region->data->numRects == 1)
           {
              region->extents = *PIXREGION_BOXPTR(region);
              freeData(region);
              region->data = (pixman_region16_data_t *)NULL;
           }
           else
              pixman_set_extents(region);
       }
    }
}

Here is the call graph for this function:

pixman_region_status_t pixman_region_union ( pixman_region16_t *  newReg,
pixman_region16_t *  reg1,
pixman_region16_t *  reg2 
)

Definition at line 1172 of file pixregion.c.

{
    int overlap; /* result ignored */

    /* Return PIXMAN_REGION_STATUS_SUCCESS if some overlap between reg1, reg2 */
    good(reg1);
    good(reg2);
    good(newReg);
    /*  checks all the simple cases */

    /*
     * Region 1 and 2 are the same
     */
    if (reg1 == reg2)
    {
       return pixman_region_copy(newReg, reg1);
    }

    /*
     * Region 1 is empty
     */
    if (PIXREGION_NIL(reg1))
    {
       if (PIXREGION_NAR(reg1))
           return pixman_break (newReg);
        if (newReg != reg2)
           return pixman_region_copy(newReg, reg2);
        return PIXMAN_REGION_STATUS_SUCCESS;
    }

    /*
     * Region 2 is empty
     */
    if (PIXREGION_NIL(reg2))
    {
       if (PIXREGION_NAR(reg2))
           return pixman_break (newReg);
        if (newReg != reg1)
           return pixman_region_copy(newReg, reg1);
        return PIXMAN_REGION_STATUS_SUCCESS;
    }

    /*
     * Region 1 completely subsumes region 2
     */
    if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
    {
        if (newReg != reg1)
           return pixman_region_copy(newReg, reg1);
        return PIXMAN_REGION_STATUS_SUCCESS;
    }

    /*
     * Region 2 completely subsumes region 1
     */
    if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
    {
        if (newReg != reg2)
           return pixman_region_copy(newReg, reg2);
        return PIXMAN_REGION_STATUS_SUCCESS;
    }

    if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, PIXMAN_REGION_STATUS_SUCCESS, PIXMAN_REGION_STATUS_SUCCESS, &overlap))
       return PIXMAN_REGION_STATUS_FAILURE;

    newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
    newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
    newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
    newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
    good(newReg);
    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the call graph for this function:

pixman_region_status_t pixman_region_union_rect ( pixman_region16_t *  dest,
pixman_region16_t *  source,
int  x,
int  y,
unsigned int  width,
unsigned int  height 
)

Definition at line 1155 of file pixregion.c.

{
    pixman_region16_t region;

    if (!width || !height)
       return pixman_region_copy (dest, source);
    region.data = NULL;
    region.extents.x1 = x;
    region.extents.y1 = y;
    region.extents.x2 = x + width;
    region.extents.y2 = y + height;

    return pixman_region_union (dest, source, &region);
}
static pixman_region_status_t pixman_region_unionO ( 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 
) [static]

Definition at line 1094 of file pixregion.c.

{
    pixman_box16_t *     pNextRect;
    int        x1;     /* left and right side of current union */
    int        x2;

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

    pNextRect = PIXREGION_TOP(region);

    /* Start off current rectangle */
    if (r1->x1 < r2->x1)
    {
       x1 = r1->x1;
       x2 = r1->x2;
       r1++;
    }
    else
    {
       x1 = r2->x1;
       x2 = r2->x2;
       r2++;
    }
    while (r1 != r1End && r2 != r2End)
    {
       if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
    }

    /* Finish off whoever (if any) is left */
    if (r1 != r1End)
    {
       do
       {
           MERGERECT(r1);
       } while (r1 != r1End);
    }
    else if (r2 != r2End)
    {
       do
       {
           MERGERECT(r2);
       } while (r2 != r2End);
    }
    
    /* Add current rectangle */
    NEWRECT(region, pNextRect, x1, y1, x2, y2);

    return PIXMAN_REGION_STATUS_SUCCESS;
}

Here is the caller graph for this function:

pixman_region_status_t pixman_region_validate ( pixman_region16_t *  badreg,
int pOverlap 
)

Definition at line 1455 of file pixregion.c.

{
    /* 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                    */
    int              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);
}

Here is the call graph for this function:

static void pixman_set_extents ( pixman_region16_t *  region) [static]

Definition at line 893 of file pixregion.c.

{
    pixman_box16_t *box, *boxEnd;

    if (!region->data)
       return;
    if (!region->data->size)
    {
       region->extents.x2 = region->extents.x1;
       region->extents.y2 = region->extents.y1;
       return;
    }

    box = PIXREGION_BOXPTR(region);
    boxEnd = PIXREGION_END(region);

    /*
     * Since box is the first rectangle in the region, it must have the
     * smallest y1 and since boxEnd is the last rectangle in the region,
     * it must have the largest y2, because of banding. Initialize x1 and
     * x2 from  box and boxEnd, resp., as good things to initialize them
     * to...
     */
    region->extents.x1 = box->x1;
    region->extents.y1 = box->y1;
    region->extents.x2 = boxEnd->x2;
    region->extents.y2 = boxEnd->y2;

    assert(region->extents.y1 < region->extents.y2);
    while (box <= boxEnd) {
       if (box->x1 < region->extents.x1)
           region->extents.x1 = box->x1;
       if (box->x2 > region->extents.x2)
           region->extents.x2 = box->x2;
       box++;
    };

    assert(region->extents.x1 < region->extents.x2);
}

Here is the caller graph for this function:

static void pixman_uninit ( pixman_region16_t *  region) [static]

Definition at line 358 of file pixregion.c.

{
    good (region);
    freeData (region);
}

Here is the caller graph for this function:

static void QuickSortRects ( pixman_box16_t  rects[],
int  numRects 
) [static]

Definition at line 1364 of file pixregion.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

static void QuickSortSpans ( pixman_region16_point_t  spans[],
int  widths[],
int  numSpans 
) [static]

Definition at line 2299 of file pixregion.c.

{
    int           y;
    int           i, j, m;
    pixman_region16_point_t *r;

    /* Always called with numSpans > 1 */
    /* Sorts only by y, doesn't bother to sort by x */

    do
    {
       if (numSpans < 9)
       {
           /* Do insertion sort */
           int yprev;

           yprev = spans[0].y;
           i = 1;
           do
           { /* while i != numSpans */
              y = spans[i].y;
              if (yprev > y)
              {
                  /* spans[i] is out of order.  Move into proper location. */
                  pixman_region16_point_t tpt;
                  int           tw, k;

                  for (j = 0; y >= spans[j].y; j++) {}
                  tpt = spans[i];
                  tw  = widths[i];
                  for (k = i; k != j; k--)
                  {
                     spans[k] = spans[k-1];
                     widths[k] = widths[k-1];
                  }
                  spans[j] = tpt;
                  widths[j] = tw;
                  y = spans[i].y;
              } /* if out of order */
              yprev = y;
              i++;
           } while (i != numSpans);
           return;
       }

       /* Choose partition element, stick in location 0 */
       m = numSpans / 2;
       if (spans[m].y > spans[0].y)              ExchangeSpans(m, 0);
       if (spans[m].y > spans[numSpans-1].y)   ExchangeSpans(m, numSpans-1);
       if (spans[m].y > spans[0].y)              ExchangeSpans(m, 0);
       y = spans[0].y;

        /* Partition array */
        i = 0;
        j = numSpans;
        do
       {
           r = &(spans[i]);
           do
           {
              r++;
              i++;
            } while (i != numSpans && r->y < y);
           r = &(spans[j]);
           do
           {
              r--;
              j--;
            } while (y < r->y);
            if (i < j)
              ExchangeSpans(i, j);
        } while (i < j);

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

       /* Recurse */
        if (numSpans-j-1 > 1)
           QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
        numSpans = j;
    } while (numSpans > 1);
}

Definition at line 93 of file pixregion.c.

                                     { goto bail; }

#define RECTALLOC(pReg,n) \
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
    if (!pixman_rect_alloc(pReg, n)) { return PIXMAN_REGION_STATUS_FAILURE; }

#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2)       \
{                                         \
    pNextRect->x1 = nx1;                  \
    pNextRect->y1 = ny1;                  \
    pNextRect->x2 = nx2;                  \
    pNextRect->y2 = ny2;                  \
    pNextRect++;                          \
}

#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2)                \
{                                                              \
    if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
    {                                                          \
       if (!pixman_rect_alloc(pReg, 1))                               \
           return PIXMAN_REGION_STATUS_FAILURE;                                     \
       pNextRect = PIXREGION_TOP(pReg);                               \
    }                                                          \
    ADDRECT(pNextRect,nx1,ny1,nx2,ny2);                               \
    pReg->data->numRects++;                                    \
    assert(pReg->data->numRects<=pReg->data->size);                   \
}


#define DOWNSIZE(reg,numRects)                                         \
if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
{                                                               \
    pixman_region16_data_t * NewData;                                                \
    NewData = (pixman_region16_data_t *)realloc((reg)->data, PIXREGION_SZOF(numRects));     \
    if (NewData)                                                \
    {                                                           \
       NewData->size = (numRects);                              \
       (reg)->data = NewData;                                          \
    }                                                           \
}


#ifdef DEBUG
int
pixman_region16_print(rgn)
    pixman_region16_t * rgn;
{
    int num, size;
    int i;
    pixman_box16_t * rects;

    num = PIXREGION_NUM_RECTS(rgn);
    size = PIXREGION_SIZE(rgn);
    rects = PIXREGION_RECTS(rgn);
    ErrorF("num: %d size: %d\n", num, size);
    ErrorF("extents: %d %d %d %d\n",
          rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
    for (i = 0; i < num; i++)
      ErrorF("%d %d %d %d \n",
            rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
    ErrorF("\n");
    return(num);
}


pixman_region_status_t
pixman_region16_tsEqual(reg1, reg2)
    pixman_region16_t * reg1;
    pixman_region16_t * reg2;
{
    int i;
    pixman_box16_t * rects1, rects2;

    if (reg1->extents.x1 != reg2->extents.x1) return PIXMAN_REGION_STATUS_FAILURE;
    if (reg1->extents.x2 != reg2->extents.x2) return PIXMAN_REGION_STATUS_FAILURE;
    if (reg1->extents.y1 != reg2->extents.y1) return PIXMAN_REGION_STATUS_FAILURE;
    if (reg1->extents.y2 != reg2->extents.y2) return PIXMAN_REGION_STATUS_FAILURE;
    if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return PIXMAN_REGION_STATUS_FAILURE;
    
    rects1 = PIXREGION_RECTS(reg1);
    rects2 = PIXREGION_RECTS(reg2);
    for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
       if (rects1[i].x1 != rects2[i].x1) return PIXMAN_REGION_STATUS_FAILURE;
       if (rects1[i].x2 != rects2[i].x2) return PIXMAN_REGION_STATUS_FAILURE;
       if (rects1[i].y1 != rects2[i].y1) return PIXMAN_REGION_STATUS_FAILURE;
       if (rects1[i].y2 != rects2[i].y2) return PIXMAN_REGION_STATUS_FAILURE;
    }
    return PIXMAN_REGION_STATUS_SUCCESS;
}

pixman_region_status_t
pixman_region16_valid(reg)
    pixman_region16_t * reg;
{
    int i, numRects;

    if ((reg->extents.x1 > reg->extents.x2) ||
       (reg->extents.y1 > reg->extents.y2))
       return PIXMAN_REGION_STATUS_FAILURE;
    numRects = PIXREGION_NUM_RECTS(reg);
    if (!numRects)
       return ((reg->extents.x1 == reg->extents.x2) &&
              (reg->extents.y1 == reg->extents.y2) &&
              (reg->data->size || (reg->data == &pixman_region_emptyData)));
    else if (numRects == 1)
       return (!reg->data);
    else
    {
       pixman_box16_t * pboxP, pboxN;
       pixman_box16_t box;

       pboxP = PIXREGION_RECTS(reg);
       box = *pboxP;
       box.y2 = pboxP[numRects-1].y2;
       pboxN = pboxP + 1;
       for (i = numRects; --i > 0; pboxP++, pboxN++)
       {
           if ((pboxN->x1 >= pboxN->x2) ||
              (pboxN->y1 >= pboxN->y2))
              return PIXMAN_REGION_STATUS_FAILURE;
           if (pboxN->x1 < box.x1)
               box.x1 = pboxN->x1;
           if (pboxN->x2 > box.x2)
              box.x2 = pboxN->x2;
           if ((pboxN->y1 < pboxP->y1) ||
              ((pboxN->y1 == pboxP->y1) &&
               ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
              return PIXMAN_REGION_STATUS_FAILURE;
       }
       return ((box.x1 == reg->extents.x1) &&
              (box.x2 == reg->extents.x2) &&
              (box.y1 == reg->extents.y1) &&
              (box.y2 == reg->extents.y2));
    }
}

#endif /* DEBUG */


/*     Create a new empty region   */
pixman_region16_t *
pixman_region_create (void)
{
    return pixman_region_create_simple (NULL);
}

Here is the call graph for this function:


Variable Documentation

Definition at line 81 of file pixregion.c.

pixman_region16_t pixman_brokenregion = { { 0, 0, 0, 0 }, &pixman_brokendata } [static]

Definition at line 82 of file pixregion.c.

pixman_box16_t pixman_region_emptyBox = {0, 0, 0, 0} [static]

Definition at line 78 of file pixregion.c.

Definition at line 79 of file pixregion.c.