rlist.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

#include "vnc.h"
#include "vncs.h"

static int tot;
static void rprint(Rlist*);

static void
growrlist(Rlist *rlist, int n)
{
	int old;

	if(rlist->nrect+n <= rlist->maxrect)
		return;

	old = rlist->maxrect;
	while(rlist->nrect+n > rlist->maxrect){
		if(rlist->maxrect == 0)
			rlist->maxrect = 16;
		else
			rlist->maxrect *= 2;
	}

	tot += rlist->maxrect - old;
	if(tot > 10000)
		sysfatal("too many rectangles");

	rlist->rect = realloc(rlist->rect, rlist->maxrect*sizeof(rlist->rect[0]));
	if(rlist->rect == nil)
		sysfatal("realloc failed in growrlist");
}

static void
rappend(Rlist *rl, Rectangle r)
{
	growrlist(rl, 1);
	rl->rect[rl->nrect++] = r;
}

/* remove rectangle i from the list */
static int
rtrim(Rlist *r, int i)
{
	if(i < 0 || i >= r->nrect)
		return 0;
	if(i == r->nrect-1){
		r->nrect--;
		return 1;
	}
	r->rect[i] = r->rect[--r->nrect];
	return 1;
}

static int
rectadjacent(Rectangle r, Rectangle s)
{
	return r.min.x<=s.max.x && s.min.x<=r.max.x &&
	       r.min.y<=s.max.y && s.min.y<=r.max.y;
}

/*
 * If s shares three edges with r, compute the
 * rectangle r - s and return 1.
 * Else return 0.
 */
static int
rectubr(Rectangle *r, Rectangle s)
{
	if(r->min.y==s.min.y && r->max.y==s.max.y){
		if(r->min.x == s.min.x){
			r->min.x = s.max.x;
			assert(r->max.x > r->min.x);
			return 1;
		}
		if(r->max.x == s.max.x){
			r->max.x = s.min.x;
			assert(r->max.x > r->min.x);
			return 1;
		}
	}
	if(r->min.x==s.min.x && r->max.x==s.max.x){
		if(r->min.y == s.min.y){
			r->min.y = s.max.y;
			assert(r->max.y > r->min.y);
			return 1;
		}
		if(r->max.y == s.max.y){
			r->max.y = s.min.y;
			assert(r->max.y > r->min.y);
			return 1;
		}
	}
	return 0;
}

/*
 * If s is a corner of r, remove s from r, yielding
 * two rectangles r and rr.  R holds the part with
 * smaller coordinates.
 */
static int
rectcornersubr(Rectangle *r, Rectangle s, Rectangle *rr)
{
#	define UPRIGHT(r) Pt((r).max.x, (r).min.y)
#	define LOWLEFT(r) Pt((r).min.x, (r).max.y)

	*rr = *r;

	if(s.min.x == r->min.x){  
		if(s.min.y == r->min.y){  // upper left
			*rr = Rpt(UPRIGHT(s), r->max);
			*r = Rpt(LOWLEFT(s), LOWLEFT(*rr));
			return 1;
		}
		if(s.max.y == r->max.y){ // lower left
			*rr = Rpt(Pt(s.max.x, r->min.y), r->max);
			*r = Rpt(r->min, UPRIGHT(s));
			return 1;
		}
	}
	if(s.max.x == r->max.x){
		if(s.max.y == r->max.y){ // lower right
			*rr = Rpt(Pt(s.min.x, r->min.y), UPRIGHT(s));
			*r = Rpt(r->min, LOWLEFT(s));
			return 1;
		}
		if(s.min.y == r->min.y){ // upper right
			*rr = Rpt(LOWLEFT(s), r->max);
			*r = Rpt(r->min, LOWLEFT(*rr));
			return 1;
		}
	}
	return 0;
}

/*
 * If s is a band cutting r into two pieces, set r to one piece
 * and rr to the other.
 */
static int
recttridesubr(Rectangle *nr, Rectangle s, Rectangle *rr)
{
	*rr = *nr;
	if((nr->min.x == s.min.x && nr->max.x == s.max.x) &&
	    (nr->min.y < s.min.y && s.max.y < nr->max.y)){
		nr->max.y = s.min.y;
		rr->min.y = s.max.y;
		return 1;
	}

	if((nr->min.y == s.min.y && nr->max.y == s.max.y) &&
	    (nr->min.x < s.min.x && s.max.x < nr->max.x)){
		nr->max.x = s.min.x;
		rr->min.x = s.max.x;
		return 1;
	}
	return 0;
}

void
addtorlist(Rlist *rlist, Rectangle r)
{
	int i, j;
	Rectangle ir, cr, rr;
	Rlist tmp;

	if(r.min.x >= r.max.x || r.min.y >= r.max.y)
		return;

	memset(&tmp, 0, sizeof tmp);
	rappend(&tmp, r);
	
	if(verbose > 5)
		fprint(2, "region union add %R:\n", r);

	combinerect(&rlist->bbox, r); // must do this first
	for(j = 0; j < tmp.nrect; j++){
		r = tmp.rect[j];

		for(i=0; i < rlist->nrect; i++){
			ir = rlist->rect[i];

			if(verbose > 5)
				fprint(2, "checking %R against %R\n", r, ir);
			if(!rectadjacent(ir, r))
				continue;

			/* r is covered by ir? */
			if(rectinrect(r, ir))
				break;

			/* r covers ir? */
 			if(rectinrect(ir, r)){
				rtrim(rlist, i);
				i--;
				continue;
			}

			/* aligned and overlapping? */
			if((ir.min.y == r.min.y && ir.max.y == r.max.y) ||
		    	(ir.min.x == r.min.x && ir.max.x == r.max.x)){
				combinerect(&r, ir);
				rtrim(rlist, i);
				i--;
				continue;
			}

			/* not aligned */ 
			if(verbose > 5)
				fprint(2, "break up rect %R and %R\n", ir, r);
			/* 2->2 breakup */
			cr = ir;
			if (!rectclip(&cr, r))	/* share only one point */
				continue;

			if(rectubr(&r, cr))
				continue;

			if(rectubr(&rlist->rect[i], cr))
				continue;

			/* 2 -> 3 breakup */
			/* stride across */
			if(recttridesubr(&r, cr, &rr)){
				rappend(&tmp, rr);
				continue;
			}

			/* corner overlap */
			if(rectcornersubr(&r, cr, &rr)){
				rappend(&tmp, rr);
				continue;
			}
			abort();
		}
		if(i == rlist->nrect)
			rappend(rlist, r);
	}
	freerlist(&tmp);
	if(verbose > 5)
		rprint(rlist);
}

void
freerlist(Rlist *r)
{
	free(r->rect);
	tot -= r->maxrect;
	r->nrect = 0;
	r->maxrect = 0;
	r->rect = nil;
}

static void
rprint(Rlist *r)
{
	int i;

	fprint(2, "rlist %p:", r);
	for(i=0; i<r->nrect; i++)
		fprint(2, " %R", r->rect[i]);
	fprint(2, "\n");
}


#ifdef REGION_DEBUG

int verbose = 10;

void main(int argc, char * argv[])
{
	Rectangle r1 = Rect(0, 0, 300, 200);
	Rectangle r2 = Rect(100, 100, 400, 300);
	Rectangle r3 = Rect(200, 100, 500, 300);
	Region reg;

	initdraw(0, 0, "vncviewer");
	region_init(&reg);
	region_union(&reg, r1, r1);
	region_union(&reg, r2, r2);
	region_union(&reg, r3, r3);
}

#endif