rectlist.c

操作系统SunOS 4.1.3版本的源码

#ifndef lint
#ifdef sccs
static	char sccsid[] = "@(#)rectlist.c 1.1 92/07/30 Copyr 1984 Sun Micro";
#endif
#endif

/*
 * Copyright (c) 1984 by Sun Microsystems, Inc.
 */

/*
 * 	Overview:	Implements the interface to the data structure called 
 *			a rectlist which is a list of rectangles.
 */

#include <sunwindow/rect.h>
#include <sunwindow/rectlist.h>

#ifndef KERNEL
#include <stdio.h>

#define	RNTABLEINC	30

#else
#include <sys/param.h>

extern	caddr_t kmem_zalloc();
#define	RNTABLEINC	NBPG/(sizeof(struct rectnode))
#endif

int	rnTableIndex;
int	rnTableOverflowed;
struct	rectnode *rnTable;	/* Array of alloced but not used nodes */
struct	rectnode *rnFree;	/* List of free nodes */

/*
 * rectlist constants
 */
extern        struct rectlist rl_null;

#define	rnptr_null	(struct	rectnode *)0

struct	rectnode *_rl_getrectnode(), **_rl_removerectnode();
bool	rl_boundintersectsrect();

#ifndef KERNEL
/*
 * rectlist geometry functions
 */
bool
rl_includespoint(rl, x, y)
	register struct	rectlist *rl;
	coord	x, y;
{
	register struct	rectnode *rn;

	rl_coordoffset(rl, &x, &y);
	if (rect_includespoint(&rl->rl_bound, x, y)) 
		for (rn = rl->rl_head; rn; rn = rn->rn_next) {
			if (rect_includespoint(&rn->rn_rect, x, y))
				return (TRUE);
		}
	return (FALSE);
}
#endif !KERNEL

rl_intersection(rl1, rl2, rl)
	register struct	rectlist *rl1, *rl2, *rl;
{
	struct	rect r;
	register struct	rectnode *rn;
	struct	rectlist rltemp;
	struct	rectlist rlresult;
	rltemp = rl_null;
	rlresult = rl_null;
	
	rl_rectoffset(rl1, &rl1->rl_bound, &r);
	if (rl_boundintersectsrect(&r, rl2))
		/*
		 * For each Rect in rl1 intersect with each Rect in rl2
		 */
		for (rn = rl1->rl_head; rn; rn = rn->rn_next) {
			rl_rectoffset(rl1, &rn->rn_rect, &r);
			(void)rl_rectintersection(&r, rl2, &rltemp);
			_rl_append(&rlresult, &rltemp);
			rltemp = rl_null; /* because appRLs consumed rltemp */
		}
	(void)rl_free(rl);
	*rl = rlresult;
}

#ifndef KERNEL
rl_sort(rl1, rl, sortorder)
	register struct	rectlist *rl1, *rl;
	int	sortorder;
{
	struct	rectlist rltemp;	/* Extract 'most' rect one at a time */
	struct	rectlist rlresult; /* Put 'most' rect here as pull off rltemp */
	struct	rectnode *rnTemp;	/* Source index */
	struct	rectnode *rnResult;	/* Result index */
	struct	rectnode *rnMost;	/* Temp result index */
	struct	rect rMost, rtemp;
	rltemp = rl_null;
	rlresult = rl_null;
	
	(void)rl_copy(rl1, &rlresult);	/* Result same as input */
	if (rl1 == rl)
		rltemp = *rl;		/* Cause will overwrite anyway */
	else
		(void)rl_copy(rl1, &rltemp);	/* Don't damage input */
	for (rnResult = rlresult.rl_head; rnResult;
	    rnResult = rnResult->rn_next) {
		rnMost = NULL;
		rMost = rect_null;
		for (rnTemp = rltemp.rl_head; rnTemp; rnTemp = rnTemp->rn_next) {
			if (rect_equal(&rnTemp->rn_rect, &rect_null))
				continue; /* Already extracted this item */
			if (rnMost == NULL) { /* Something to compare with */
				rnMost = rnTemp;
				rMost = rnMost->rn_rect;
				continue;
			}
			rtemp = rnTemp->rn_rect;
			if (rect_order(&rtemp, &rMost, sortorder)==TRUE) {
				rnMost = rnTemp;
				rMost = rtemp;
			}
		}
		if (rnMost == NULL)
			break; /* sorted all items */
		rnResult->rn_rect = rMost;
		rnMost->rn_rect = rect_null; /* Don't compare this item again */
	}
	(void)rl_free(rl);
	*rl = rlresult;
}
#endif !KERNEL

rl_union(rl1, rl2, rl)
	register struct	rectlist *rl1, *rl2, *rl;
{
	if (rl1 == rl)
		_rl_union(rl, rl2);
	else if (rl2 == rl)
		_rl_union(rl, rl1);
	else {
		(void)rl_copy(rl1, rl);
		_rl_union(rl, rl2);
	}
}

rl_difference(rl1, rl2, rl)
	register struct	rectlist *rl1, *rl2, *rl;
{
	struct	rect r;
	register struct	rectnode *rn;

	(void)rl_copy(rl1, rl);
	rl_rectoffset(rl, &rl->rl_bound, &r);
	if (rl_boundintersectsrect(&r, rl2)) {
		/*
		 * For each Rect in rl2 remove from rl
		 */
		for (rn = rl2->rl_head; rn; rn = rn->rn_next) {
			rl_rectoffset(rl2, &rn->rn_rect, &r);
			_rl_removerect(&r, rl);
		}
		_rl_makebound(rl);
	}
}

bool
rl_empty(rl)
	register struct	rectlist *rl;
{
	register struct	rectnode *rn;

	if (rect_isnull(&(rl->rl_bound)))
		return (TRUE);
	for (rn = rl->rl_head; rn; rn = rn->rn_next) {
		if (!rect_isnull(&(rn->rn_rect)))
			return (FALSE);
	}
	return (TRUE);
}

bool
rl_equal(rl1, rl2)
	register struct	rectlist *rl1, *rl2;
{	register struct	rectnode *rn1, *rn2;

	if (!rect_equal(&rl1->rl_bound, &rl2->rl_bound) ||
	    rl1->rl_x!=rl2->rl_x || rl1->rl_y!=rl2->rl_y)
		return (FALSE);
	rn2 = rl2->rl_head;
	for (rn1 = rl1->rl_head; ; rn1 = rn1->rn_next) {
		if (rn1==NULL && rn2==NULL)
			return (TRUE);
		if (rn1==NULL || rn2==NULL)
			return (FALSE);
		if (!rect_equal(&rn1->rn_rect, &rn2->rn_rect))
			return (FALSE);
		rn2 = rn2->rn_next;
	}
}

#ifndef KERNEL
/*
 * rectlist with Rect geometry functions
 */
bool
rl_equalrect(r, rl)
	register struct	rect *r;
	register struct	rectlist *rl;
{
	struct	rect rtemp;

	rl_rectoffset(rl, &rl->rl_bound, &rtemp);
	if (rect_equal(r, &rtemp) && rl->rl_head == rl->rl_tail)
		return (TRUE);
	else
		return (FALSE);
}
#endif !KERNEL

bool
rl_boundintersectsrect(r, rl)
	register struct	rect *r;
	register struct	rectlist *rl;
{
	struct	rect rtemp;

	rl_rectoffset(rl, &rl->rl_bound, &rtemp);
	return (rect_intersectsrect(&rtemp, r));
}

bool
rl_rectintersects(r, rl) 
	register struct	rect *r; 
	register struct	rectlist *rl;
{
	struct	rectnode *rn;
	struct	rect r1;

	if (rl_boundintersectsrect(r, rl)) 
		/* For each Rect in rl intersect with r */
		for (rn = rl->rl_head; rn; rn = rn->rn_next) {
			rl_rectoffset(rl, &rn->rn_rect, &r1);
			if (rect_intersectsrect(r, &r1))
				return (TRUE);
		}
	return (FALSE);
}

rl_rectintersection(r, rl1, rl) 
	register struct	rect *r; 
	register struct	rectlist *rl1, *rl;
{
	struct	rectnode *rn;
	struct	rect r1, rtemp;
	struct	rectlist rlresult;
	rlresult = rl_null;

	if (rl_boundintersectsrect(r, rl1)) 
		/* For each Rect in rl1 intersect with r */
		for (rn = rl1->rl_head; rn; rn = rn->rn_next) {
			rl_rectoffset(rl1, &rn->rn_rect, &r1);
			(void)rect_intersection(r, &r1, &rtemp);
			_rl_appendrect(&rtemp, &rlresult);
		}
	(void)rl_free(rl);
	*rl = rlresult;
}

rl_rectunion(r, rl1, rl)
	register struct	rect *r; 
	register struct	rectlist *rl1, *rl;
{
	struct	rectlist rlresult;
	struct	rect rtemp;
	register struct	rectnode *rn;
	rlresult = rl_null;

	_rl_appendrect(r, &rlresult);
	if (rl_boundintersectsrect(r, rl1)) 
		for (rn = rl1->rl_head; rn; rn = rn->rn_next) {
			rl_rectoffset(rl1, &rn->rn_rect, &rtemp);
			_rl_removerect(&rtemp, &rlresult);
		}
	(void)rl_copy(rl1, rl);
	_rl_append(rl, &rlresult);
}

rl_rectdifference(r, rl1, rl)
	register struct	rect *r;
	register struct	rectlist *rl1, *rl;
{
	struct	rect rtemp;
	struct	rectlist rltemp;
	register struct	rectnode *rn;

	if (rect_isnull(r))
		(void)rl_copy(rl1, rl);
	else if (_rl_equal(rl1, &rl_null))
		(void)rl_free(rl);
	else {
		if (rl1 == rl)
			_rl_removerect(r, rl);
		else {
			(void)rl_free(rl);
			for (rn = rl1->rl_head; rn; rn = rn->rn_next) {
				rl_rectoffset(rl1,&rn->rn_rect, &rtemp);
				rltemp = rl_null;
				_rl_difrects(&rtemp, r, &rltemp);
				_rl_append(rl, &rltemp);
			}
		}
		_rl_makebound(rl);
	}
}

/*
 * rectlist initialization functions
 */

rl_initwithrect(r, rl)
	register struct	rect *r;
	struct	rectlist *rl;
{

	*rl = rl_null;
	_rl_appendrect(r, rl);
}

/*
 * rectlist List Memory Management functions
 */
rl_copy(rl1, rl)
	register struct	rectlist *rl1, *rl;
{
	register struct	rectnode *rn;
	
	if (rl1 != rl) {
		(void)rl_free(rl);
		*rl= *rl1;
		rl->rl_head = 0;
		rl->rl_tail = 0;
		for (rn = rl1->rl_head; rn; rn = rn->rn_next)
			_rl_appendrect(&rn->rn_rect, rl);
	}
}

rl_free(rl)
	register struct	rectlist *rl;
{
	register struct	rectnode *rn, *rn_next, *rn_last = (struct rectnode *)0;
	
	for (rn = rl->rl_head; rn; rn = rn_next) {
		rn_next = rn->rn_next;
		_rl_freerectnode(rn);
		rn_last = rn;
	}
	if (rn_last != rl->rl_tail) {
#ifdef	KERNEL