src/hd/sm_sets.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 * Quadtree-specific set operations.
 */

#include "standard.h"

#include "sm_qtree.h"


#define QTSETIBLK       2048            /* set index allocation block size */
#define QTELEMBLK       8               /* set element allocation block */
#define QTELEMMOD(ne)   ((ne)&7)        /* (ne) % QTELEMBLK */

#define QTONTHRESH(ne)  (!QTELEMMOD((ne)+1))
#define QTNODESIZ(ne)   ((ne) + QTELEMBLK - QTELEMMOD(ne))

OBJECT  **qtsettab= NULL;               /* quadtree leaf node table */
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;

  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;
  }
  qtsettab[osi] = (OBJECT *)malloc(QTNODESIZ(*oset)*sizeof(OBJECT));
  if (qtsettab[osi] == 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 */
QUADTREE  qt;
OBJECT  id;
{
        register QUADTREE  lf;

#ifdef DEBUG
        if(id < 0)
                eputs("qtdelelem():Invalid triangle id\n");
        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "empty/bad node in qtdelelem");
        if (!inset(qtsettab[lf], id))
                error(CONSISTENCY, "id not in leaf in qtdelelem");
#else
        lf = QT_SET_INDEX(qt);
#endif
        if (qtsettab[lf][0] <= 1) {             /* blow leaf away */
                free((void *)qtsettab[lf]);
                qtsettab[lf] = (OBJECT *)qtfreesets;
                qtfreesets = lf;
                return(EMPTY);
        }
        deletelem(qtsettab[lf], id);
        if (QTONTHRESH(qtsettab[lf][0]))
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
        return(qt);
}


QUADTREE
qtaddelem(qt, id)               /* add element to leaf node */
QUADTREE  qt;
OBJECT  id;
{
        OBJECT  newset[2];
        register QUADTREE  lf;

#ifdef DEBUG
        if(id < 0)
                eputs("qtaddelem():Invalid triangle id\n");
#endif
        if (QT_IS_EMPTY(qt)) {          /* create new leaf */
                newset[0] = 1; newset[1] = id;
                return(qtnewleaf(newset));
        }                               /* else add element */
#ifdef DEBUG
        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "bad node in qtaddelem");
        if (inset(qtsettab[lf], id))
                error(CONSISTENCY, "id already in leaf in qtaddelem");
#else
        lf = QT_SET_INDEX(qt);
#endif
        if (QTONTHRESH(qtsettab[lf][0])) {
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
                if (qtsettab[lf] == NULL)
                        error(SYSTEM, "out of memory in qtaddelem");
        }
        insertelem(qtsettab[lf], id);
        return(qt);
}


#ifdef DEBUG
OBJECT *
qtqueryset(qt)                  /* return object set for leaf node */
QUADTREE  qt;
{
        register QUADTREE  lf;

        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "bad node in qtqueryset");
        return(qtsettab[lf]);
}
#endif


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)
                return;
        free((void *)qtsettab[osi]);
        qtsettab[osi] = (OBJECT *)qtfreesets;
        qtfreesets = osi;
}


qtfreeleaves()                  /* free ALL sets and leaf nodes */
{
        register int    i;

        while ((i = qtfreesets) != EMPTY) {
                qtfreesets = (int)qtsettab[i];
                qtsettab[i] = NULL;
        }
        for (i = qtnumsets; i--; )
                if (qtsettab[i] != NULL)
                        free((void *)qtsettab[i]);
        free((void *)qtsettab);
        qtsettab = NULL;
        qtnumsets = 0;
}


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[QT_MAXCSET+QT_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] > QT_MAXCSET)          /* truncate "checked" set if nec. */
       cset[0] = QT_MAXCSET;
    /* setcopy(cs, cset); */        /* copy cset back to cs */
    os = cset;
    for (i = os[0]; i-- >= 0; )
       *cs++ = *os++;
}


Revision:	3.6
Committed:	Sat Feb 22 02:07:25 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R5
Changes since 3.5:	+5 -8 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	gwlarson	3.1	#ifndef lint
2	greg	3.6	static const char RCSid[] = "$Id$";
3	gwlarson	3.1	#endif
4			/*
5			* Quadtree-specific set operations.
6			*/
7
8			#include "standard.h"
9
10			#include "sm_qtree.h"
11
12	gwlarson	3.2
13			#define QTSETIBLK 2048 /* set index allocation block size */
14	gwlarson	3.1	#define QTELEMBLK 8 /* set element allocation block */
15	gwlarson	3.3	#define QTELEMMOD(ne) ((ne)&7) /* (ne) % QTELEMBLK */
16	gwlarson	3.1
17	gwlarson	3.3	#define QTONTHRESH(ne) (!QTELEMMOD((ne)+1))
18			#define QTNODESIZ(ne) ((ne) + QTELEMBLK - QTELEMMOD(ne))
19	gwlarson	3.1
20	gwlarson	3.3	OBJECT *qtsettab= NULL; / quadtree leaf node table */
21	gwlarson	3.2	QUADTREE qtnumsets; /* number of used set indices */
22	gwlarson	3.1	static int qtfreesets = EMPTY; /* free set index list */
23
24
25			QUADTREE
26			qtnewleaf(oset) /* return new leaf node for object set */
27			OBJECT *oset;
28			{
29	gwlarson	3.4	register QUADTREE osi;
30	gwlarson	3.1
31	gwlarson	3.4	if (*oset <= 0)
32			return(EMPTY); /* should be error? */
33			if (qtfreesets != EMPTY) {
34			osi = qtfreesets;
35			qtfreesets = (int)qtsettab[osi];
36			} else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
37			qtsettab = (OBJECT *)realloc((char )qtsettab,
38			(unsigned)(osi+QTSETIBLK)sizeof(OBJECT ));
39			if (qtsettab == NULL)
40			goto memerr;
41			}
42			qtsettab[osi] = (OBJECT )malloc(QTNODESIZ(oset)*sizeof(OBJECT));
43			if (qtsettab[osi] == NULL)
44			goto memerr;
45			setcopy(qtsettab[osi], oset);
46			return(QT_INDEX(osi));
47	gwlarson	3.1	memerr:
48	gwlarson	3.4	error(SYSTEM, "out of memory in qtnewleaf");
49	gwlarson	3.1	}
50
51
52			QUADTREE
53	gwlarson	3.3	qtdelelem(qt, id) /* delete element from leaf node */
54	gwlarson	3.1	QUADTREE qt;
55			OBJECT id;
56			{
57			register QUADTREE lf;
58
59	gwlarson	3.2	#ifdef DEBUG
60			if(id < 0)
61			eputs("qtdelelem():Invalid triangle id\n");
62			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
63			error(CONSISTENCY, "empty/bad node in qtdelelem");
64			if (!inset(qtsettab[lf], id))
65			error(CONSISTENCY, "id not in leaf in qtdelelem");
66			#else
67	gwlarson	3.1	lf = QT_SET_INDEX(qt);
68	gwlarson	3.2	#endif
69	gwlarson	3.1	if (qtsettab[lf][0] <= 1) { /* blow leaf away */
70	greg	3.6	free((void *)qtsettab[lf]);
71	gwlarson	3.1	qtsettab[lf] = (OBJECT *)qtfreesets;
72			qtfreesets = lf;
73			return(EMPTY);
74	gwlarson	3.3	}
75	gwlarson	3.1	deletelem(qtsettab[lf], id);
76	gwlarson	3.3	if (QTONTHRESH(qtsettab[lf][0]))
77	gwlarson	3.1	qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
78	gwlarson	3.3	QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
79	gwlarson	3.1	return(qt);
80			}
81
82
83			QUADTREE
84	gwlarson	3.3	qtaddelem(qt, id) /* add element to leaf node */
85	gwlarson	3.1	QUADTREE qt;
86			OBJECT id;
87			{
88			OBJECT newset[2];
89			register QUADTREE lf;
90
91	gwlarson	3.2	#ifdef DEBUG
92			if(id < 0)
93			eputs("qtaddelem():Invalid triangle id\n");
94			#endif
95	gwlarson	3.1	if (QT_IS_EMPTY(qt)) { /* create new leaf */
96			newset[0] = 1; newset[1] = id;
97			return(qtnewleaf(newset));
98			} /* else add element */
99	gwlarson	3.2	#ifdef DEBUG
100			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
101			error(CONSISTENCY, "bad node in qtaddelem");
102			if (inset(qtsettab[lf], id))
103			error(CONSISTENCY, "id already in leaf in qtaddelem");
104			#else
105	gwlarson	3.1	lf = QT_SET_INDEX(qt);
106	gwlarson	3.2	#endif
107	gwlarson	3.3	if (QTONTHRESH(qtsettab[lf][0])) {
108	gwlarson	3.1	qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
109	gwlarson	3.3	QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
110	gwlarson	3.1	if (qtsettab[lf] == NULL)
111			error(SYSTEM, "out of memory in qtaddelem");
112			}
113			insertelem(qtsettab[lf], id);
114			return(qt);
115			}
116
117
118	gwlarson	3.2	#ifdef DEBUG
119			OBJECT *
120			qtqueryset(qt) /* return object set for leaf node */
121	gwlarson	3.1	QUADTREE qt;
122			{
123	gwlarson	3.2	register QUADTREE lf;
124	gwlarson	3.1
125	gwlarson	3.2	if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
126			error(CONSISTENCY, "bad node in qtqueryset");
127			return(qtsettab[lf]);
128	gwlarson	3.1	}
129	gwlarson	3.2	#endif
130	gwlarson	3.1
131
132			qtfreeleaf(qt) /* free set and leaf node */
133			QUADTREE qt;
134			{
135			register QUADTREE osi;
136
137			if (!QT_IS_LEAF(qt))
138			return;
139			osi = QT_SET_INDEX(qt);
140			if (osi >= qtnumsets)
141	gwlarson	3.2	return;
142	greg	3.6	free((void *)qtsettab[osi]);
143	gwlarson	3.1	qtsettab[osi] = (OBJECT *)qtfreesets;
144			qtfreesets = osi;
145			}
146
147
148	gwlarson	3.2
149			qtfreeleaves() /* free ALL sets and leaf nodes */
150			{
151			register int i;
152
153			while ((i = qtfreesets) != EMPTY) {
154			qtfreesets = (int)qtsettab[i];
155			qtsettab[i] = NULL;
156			}
157			for (i = qtnumsets; i--; )
158			if (qtsettab[i] != NULL)
159	greg	3.6	free((void *)qtsettab[i]);
160			free((void *)qtsettab);
161	gwlarson	3.2	qtsettab = NULL;
162			qtnumsets = 0;
163			}
164
165
166	gwlarson	3.1	check_set(os, cs) /* modify checked set and set to check */
167			register OBJECT os; / os' = os - cs */
168			register OBJECT cs; / cs' = cs + os */
169			{
170	gwlarson	3.2	OBJECT cset[QT_MAXCSET+QT_MAXSET+1];
171	gwlarson	3.1	register int i, j;
172			int k;
173			/* copy os in place, cset <- cs */
174			cset[0] = 0;
175			k = 0;
176			for (i = j = 1; i <= os[0]; i++) {
177			while (j <= cs[0] && cs[j] < os[i])
178			cset[++cset[0]] = cs[j++];
179			if (j > cs[0] \|\| os[i] != cs[j]) { /* object to check */
180			os[++k] = os[i];
181			cset[++cset[0]] = os[i];
182			}
183			}
184			if (!(os[0] = k)) /* new "to check" set size */
185			return; /* special case */
186			while (j <= cs[0]) /* get the rest of cs */
187			cset[++cset[0]] = cs[j++];
188	gwlarson	3.2	if (cset[0] > QT_MAXCSET) /* truncate "checked" set if nec. */
189			cset[0] = QT_MAXCSET;
190	gwlarson	3.1	/* setcopy(cs, cset); / / copy cset back to cs */
191			os = cset;
192			for (i = os[0]; i-- >= 0; )
193			cs++ = os++;
194			}
195	gwlarson	3.4
196
197
198
199
200
201
202
203	gwlarson	3.2