src/hd/sm_sets.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 * Quadtree-specific set operations.
 */

#include "standard.h"

#include "sm_qtree.h"
#include "object.h"

#define QTSETIBLK       1024            /* set index allocation block size */
#define QTELEMBLK       8               /* set element allocation block */

#define QTNODESIZ(ne)   ((ne) + QTELEMBLK - ((ne) % QTELEMBLK))

static OBJECT   **qtsettab;             /* quadtree leaf node table */
static QUADTREE  qtnumsets;             /* number of used set indices */
static int  qtfreesets = EMPTY;         /* free set index list */


QUADTREE
qtnewleaf(oset)                 /* return new leaf node for object set */
OBJECT  *oset;
{
        register QUADTREE  osi;
        int     nalc;

        if (*oset <= 0)
                return(EMPTY);          /* should be error? */
        if (qtfreesets != EMPTY) {
                osi = qtfreesets;
                qtfreesets = (int)qtsettab[osi];
        } else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
                qtsettab = (OBJECT **)realloc((char *)qtsettab,
                                (unsigned)(osi+QTSETIBLK)*sizeof(OBJECT *));
                if (qtsettab == NULL)
                        goto memerr;
        }
        nalc = QTNODESIZ(*oset);
        if ((qtsettab[osi] = (OBJECT *)malloc(nalc*sizeof(OBJECT))) == NULL)
                goto memerr;
        setcopy(qtsettab[osi], oset);
        return(QT_INDEX(osi));
memerr:
        error(SYSTEM, "out of memory in qtnewleaf");
}


QUADTREE
qtdelelem(qt, id)               /* delete element from leaf node, no quest. */
QUADTREE  qt;
OBJECT  id;
{
        register QUADTREE  lf;
        int  oalc, nalc;

        if (QT_IS_EMPTY(qt))
                return(EMPTY);
        if (!QT_IS_LEAF(qt))
                goto noderr;
        lf = QT_SET_INDEX(qt);
        if (lf >= qtnumsets)
                goto noderr;
        if (qtsettab[lf][0] <= 1) {             /* blow leaf away */
                free((char *)qtsettab[lf]);
                qtsettab[lf] = (OBJECT *)qtfreesets;
                qtfreesets = lf;
                return(EMPTY);
        }                                       /* else delete element */
        oalc = QTNODESIZ(qtsettab[lf][0]);
        nalc = QTNODESIZ(qtsettab[lf][0] - 1);
        deletelem(qtsettab[lf], id);
        if (nalc != oalc)
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                nalc*sizeof(OBJECT));
        return(qt);
noderr:
        error(CONSISTENCY, "bad node in qtdelelem");
}


QUADTREE
qtaddelem(qt, id)               /* add element to leaf node, no quest. */
QUADTREE  qt;
OBJECT  id;
{
        OBJECT  newset[2];
        register QUADTREE  lf;
        int  oalc, nalc;

        if (QT_IS_EMPTY(qt)) {          /* create new leaf */
                newset[0] = 1; newset[1] = id;
                return(qtnewleaf(newset));
        }                               /* else add element */
        if (!QT_IS_LEAF(qt))
                goto noderr;
        lf = QT_SET_INDEX(qt);
        if (lf >= qtnumsets)
                goto noderr;
        oalc = QTNODESIZ(qtsettab[lf][0]);
        nalc = QTNODESIZ(qtsettab[lf][0] + 1);
        if (nalc != oalc) {
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                nalc*sizeof(OBJECT));
                if (qtsettab[lf] == NULL)
                        error(SYSTEM, "out of memory in qtaddelem");
        }
        insertelem(qtsettab[lf], id);
        return(qt);
noderr:
        error(CONSISTENCY, "bad node in qtaddelem");
}


qtgetset(oset, qt)              /* get object set for leaf node */
register OBJECT  *oset;
QUADTREE  qt;
{
        QUADTREE  lf;
        register OBJECT  *os;
        register int  i;

        if (!QT_IS_LEAF(qt))
                goto noderr;
        lf = QT_SET_INDEX(qt);
        if (lf >= qtnumsets)
                goto noderr;
        for (i = *(os = qtsettab[lf]); i-- >= 0; )
                *oset++ = *os++;
        return;
noderr:
        error(CONSISTENCY, "bad node in qtgetset");
}


qtfreeleaf(qt)                  /* free set and leaf node */
QUADTREE  qt;
{
        register QUADTREE       osi;

        if (!QT_IS_LEAF(qt))
                return;
        osi = QT_SET_INDEX(qt);
        if (osi >= qtnumsets)
                error(CONSISTENCY, "bad node in qtfreeleaf");
        free((char *)qtsettab[osi]);
        qtsettab[osi] = (OBJECT *)qtfreesets;
        qtfreesets = osi;
}


check_set(os, cs)                /* modify checked set and set to check */
register OBJECT  *os;                   /* os' = os - cs */
register OBJECT  *cs;                   /* cs' = cs + os */
{
    OBJECT  cset[MAXCSET+MAXSET+1];
    register int  i, j;
    int  k;
                                        /* copy os in place, cset <- cs */
    cset[0] = 0;
    k = 0;
    for (i = j = 1; i <= os[0]; i++) {
        while (j <= cs[0] && cs[j] < os[i])
           cset[++cset[0]] = cs[j++];
        if (j > cs[0] || os[i] != cs[j]) {      /* object to check */
            os[++k] = os[i];
            cset[++cset[0]] = os[i];
        }
    }
    if (!(os[0] = k))               /* new "to check" set size */
       return;                 /* special case */
    while (j <= cs[0])              /* get the rest of cs */
       cset[++cset[0]] = cs[j++];
    if (cset[0] > MAXCSET)          /* truncate "checked" set if nec. */
       cset[0] = MAXCSET;
    /* setcopy(cs, cset); */        /* copy cset back to cs */
    os = cset;
    for (i = os[0]; i-- >= 0; )
       *cs++ = *os++;
}
Revision:	3.1
Committed:	Wed Aug 19 17:45:23 1998 UTC (25 years, 8 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Log Message:	Initial revision
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ SGI";
5			#endif
6
7			/*
8			* Quadtree-specific set operations.
9			*/
10
11			#include "standard.h"
12
13			#include "sm_qtree.h"
14			#include "object.h"
15
16			#define QTSETIBLK 1024 /* set index allocation block size */
17			#define QTELEMBLK 8 /* set element allocation block */
18
19			#define QTNODESIZ(ne) ((ne) + QTELEMBLK - ((ne) % QTELEMBLK))
20
21			static OBJECT *qtsettab; / quadtree leaf node table */
22			static QUADTREE qtnumsets; /* number of used set indices */
23			static int qtfreesets = EMPTY; /* free set index list */
24
25
26			QUADTREE
27			qtnewleaf(oset) /* return new leaf node for object set */
28			OBJECT *oset;
29			{
30			register QUADTREE osi;
31			int nalc;
32
33			if (*oset <= 0)
34			return(EMPTY); /* should be error? */
35			if (qtfreesets != EMPTY) {
36			osi = qtfreesets;
37			qtfreesets = (int)qtsettab[osi];
38			} else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
39			qtsettab = (OBJECT *)realloc((char )qtsettab,
40			(unsigned)(osi+QTSETIBLK)sizeof(OBJECT ));
41			if (qtsettab == NULL)
42			goto memerr;
43			}
44			nalc = QTNODESIZ(*oset);
45			if ((qtsettab[osi] = (OBJECT )malloc(nalcsizeof(OBJECT))) == NULL)
46			goto memerr;
47			setcopy(qtsettab[osi], oset);
48			return(QT_INDEX(osi));
49			memerr:
50			error(SYSTEM, "out of memory in qtnewleaf");
51			}
52
53
54			QUADTREE
55			qtdelelem(qt, id) /* delete element from leaf node, no quest. */
56			QUADTREE qt;
57			OBJECT id;
58			{
59			register QUADTREE lf;
60			int oalc, nalc;
61
62			if (QT_IS_EMPTY(qt))
63			return(EMPTY);
64			if (!QT_IS_LEAF(qt))
65			goto noderr;
66			lf = QT_SET_INDEX(qt);
67			if (lf >= qtnumsets)
68			goto noderr;
69			if (qtsettab[lf][0] <= 1) { /* blow leaf away */
70			free((char *)qtsettab[lf]);
71			qtsettab[lf] = (OBJECT *)qtfreesets;
72			qtfreesets = lf;
73			return(EMPTY);
74			} /* else delete element */
75			oalc = QTNODESIZ(qtsettab[lf][0]);
76			nalc = QTNODESIZ(qtsettab[lf][0] - 1);
77			deletelem(qtsettab[lf], id);
78			if (nalc != oalc)
79			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
80			nalc*sizeof(OBJECT));
81			return(qt);
82			noderr:
83			error(CONSISTENCY, "bad node in qtdelelem");
84			}
85
86
87			QUADTREE
88			qtaddelem(qt, id) /* add element to leaf node, no quest. */
89			QUADTREE qt;
90			OBJECT id;
91			{
92			OBJECT newset[2];
93			register QUADTREE lf;
94			int oalc, nalc;
95
96			if (QT_IS_EMPTY(qt)) { /* create new leaf */
97			newset[0] = 1; newset[1] = id;
98			return(qtnewleaf(newset));
99			} /* else add element */
100			if (!QT_IS_LEAF(qt))
101			goto noderr;
102			lf = QT_SET_INDEX(qt);
103			if (lf >= qtnumsets)
104			goto noderr;
105			oalc = QTNODESIZ(qtsettab[lf][0]);
106			nalc = QTNODESIZ(qtsettab[lf][0] + 1);
107			if (nalc != oalc) {
108			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
109			nalc*sizeof(OBJECT));
110			if (qtsettab[lf] == NULL)
111			error(SYSTEM, "out of memory in qtaddelem");
112			}
113			insertelem(qtsettab[lf], id);
114			return(qt);
115			noderr:
116			error(CONSISTENCY, "bad node in qtaddelem");
117			}
118
119
120			qtgetset(oset, qt) /* get object set for leaf node */
121			register OBJECT *oset;
122			QUADTREE qt;
123			{
124			QUADTREE lf;
125			register OBJECT *os;
126			register int i;
127
128			if (!QT_IS_LEAF(qt))
129			goto noderr;
130			lf = QT_SET_INDEX(qt);
131			if (lf >= qtnumsets)
132			goto noderr;
133			for (i = *(os = qtsettab[lf]); i-- >= 0; )
134			oset++ = os++;
135			return;
136			noderr:
137			error(CONSISTENCY, "bad node in qtgetset");
138			}
139
140
141			qtfreeleaf(qt) /* free set and leaf node */
142			QUADTREE qt;
143			{
144			register QUADTREE osi;
145
146			if (!QT_IS_LEAF(qt))
147			return;
148			osi = QT_SET_INDEX(qt);
149			if (osi >= qtnumsets)
150			error(CONSISTENCY, "bad node in qtfreeleaf");
151			free((char *)qtsettab[osi]);
152			qtsettab[osi] = (OBJECT *)qtfreesets;
153			qtfreesets = osi;
154			}
155
156
157			check_set(os, cs) /* modify checked set and set to check */
158			register OBJECT os; / os' = os - cs */
159			register OBJECT cs; / cs' = cs + os */
160			{
161			OBJECT cset[MAXCSET+MAXSET+1];
162			register int i, j;
163			int k;
164			/* copy os in place, cset <- cs */
165			cset[0] = 0;
166			k = 0;
167			for (i = j = 1; i <= os[0]; i++) {
168			while (j <= cs[0] && cs[j] < os[i])
169			cset[++cset[0]] = cs[j++];
170			if (j > cs[0] \|\| os[i] != cs[j]) { /* object to check */
171			os[++k] = os[i];
172			cset[++cset[0]] = os[i];
173			}
174			}
175			if (!(os[0] = k)) /* new "to check" set size */
176			return; /* special case */
177			while (j <= cs[0]) /* get the rest of cs */
178			cset[++cset[0]] = cs[j++];
179			if (cset[0] > MAXCSET) /* truncate "checked" set if nec. */
180			cset[0] = MAXCSET;
181			/* setcopy(cs, cset); / / copy cset back to cs */
182			os = cset;
183			for (i = os[0]; i-- >= 0; )
184			cs++ = os++;
185			}