src/hd/sm_usets.c

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

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

/*
 * Quadtree-specific set operations with unsorted sets.
 */

#include "standard.h"
#include "sm_flag.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=0;                  /* number of used set indices */
static int  qtfreesets = EMPTY;         /* free set index list */
int4 *qtsetflag = NULL;
static int qtallocsets =0;

qtclearsetflags()
{

  if(!qtsetflag)
    return;

    bzero((char *)qtsetflag,FLAG_BYTES(qtallocsets));
}


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;
                qtsetflag = (int4 *)realloc((char *)qtsetflag,
                                   FLAG_BYTES(osi+ QTSETIBLK));
                if (qtsetflag == NULL)
                        goto memerr;
                if(qtallocsets)
                  bzero((char *)((char *)(qtsetflag)+FLAG_BYTES(qtallocsets)),
                      FLAG_BYTES(osi+QTSETIBLK)-FLAG_BYTES(qtallocsets));
                else
                  bzero((char *)(qtsetflag),FLAG_BYTES(osi +QTSETIBLK));

                qtallocsets = osi + QTSETIBLK; 
        }
        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\n");
}


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");
#else
        lf = QT_SET_INDEX(qt);
#endif

        if (!inset(qtsettab[lf], id))
        {
#ifdef DEBUG
          eputs("id not in leaf in qtdelelem\n");
#endif
          return(qt);
        }
        if (qtsettab[lf][0] <= 1) {             /* blow leaf away */
                free((char *)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");
#else
        lf = QT_SET_INDEX(qt);
#endif
        
        if (inset(qtsettab[lf], id))
        {
#ifdef DEBUG
          eputs("id already in leaf in qtaddelem\n");
#endif
          return(qt);
        }
        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);
}

#define insertuelem(os,id) ((os)[++((os)[0])] = (id))

int
qtcompressuelem(qt,compress_set)
  QUADTREE qt;
  int (*compress_set)();
{
    register QUADTREE  lf;
    int i,j,osize;
    OBJECT *os;

    if(QT_IS_EMPTY(qt)) 
      return(qt);
#ifdef DEBUG
        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "bad node in qtaddelem");
#else
        lf = QT_SET_INDEX(qt);
#endif
        os = qtsettab[lf];
        osize = os[0];
        if((i=compress_set(os)) < osize)
        {
          qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                           QTNODESIZ(i+1)*sizeof(OBJECT));
          if (qtsettab[lf] == NULL)
            error(SYSTEM, "out of memory in qtaddelem");
        }
        return(qt);
}


QUADTREE
qtadduelem(qt, id)              /* add element to unsorted 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");
#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");
        }
        insertuelem(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

int
qtinuset(qt,id)
QUADTREE qt;
OBJECT id;
{
  OBJECT *os;
  int i;

  os = qtqueryset(qt);
  for(i=os[0],os++; i > 0; i--,os++)
    if(*os==id)
      return(1);

  return(0);
}


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((char *)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((char *)qtsettab[i]);
        free((char *)qtsettab);
        qtsettab = NULL;
        if(qtsetflag)
        {
          free((char *)qtsetflag);
          qtsetflag=0;
        }
        qtnumsets = 0;
}


/* no bounds on os csptr. This routine is conservative: the result returned
in os is the set intersection, and therefore is bounded by the size of os.
cs is bound to be <= QT_MAXCSET
*/ 
check_set_large(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+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])
          if(cset[0] < QT_MAXCSET)
            cset[++cset[0]] = cs[j++];
          else
            j++;
        if (j > cs[0] || os[i] != cs[j]) {      /* object to check */
            os[++k] = os[i];
            if(cset[0] < QT_MAXCSET)
              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 */
      if(cset[0] == QT_MAXCSET)
        break;
      else
        cset[++cset[0]] = cs[j++];
    
    os = cset;                 /* copy cset back to cs */
    for (i = os[0]; i-- >= 0; )
       *cs++ = *os++;  

}


Revision:	3.1
Committed:	Mon Dec 28 17:53:06 1998 UTC (25 years, 4 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 with unsorted sets.
9			*/
10
11			#include "standard.h"
12			#include "sm_flag.h"
13			#include "sm_qtree.h"
14
15
16			#define QTSETIBLK 2048 /* set index allocation block size */
17			#define QTELEMBLK 8 /* set element allocation block */
18			#define QTELEMMOD(ne) ((ne)&7) /* (ne) % QTELEMBLK */
19
20			#define QTONTHRESH(ne) (!QTELEMMOD((ne)+1))
21			#define QTNODESIZ(ne) ((ne) + QTELEMBLK - QTELEMMOD(ne))
22
23			OBJECT *qtsettab= NULL; / quadtree leaf node table */
24			QUADTREE qtnumsets=0; /* number of used set indices */
25			static int qtfreesets = EMPTY; /* free set index list */
26			int4 *qtsetflag = NULL;
27			static int qtallocsets =0;
28
29			qtclearsetflags()
30			{
31
32			if(!qtsetflag)
33			return;
34
35			bzero((char *)qtsetflag,FLAG_BYTES(qtallocsets));
36			}
37
38
39			QUADTREE
40			qtnewleaf(oset) /* return new leaf node for object set */
41			OBJECT *oset;
42			{
43			register QUADTREE osi;
44
45			if (*oset <= 0)
46			return(EMPTY); /* should be error? */
47			if (qtfreesets != EMPTY) {
48			osi = qtfreesets;
49			qtfreesets = (int)qtsettab[osi];
50			} else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
51			qtsettab = (OBJECT *)realloc((char )qtsettab,
52			(unsigned)(osi+QTSETIBLK)sizeof(OBJECT ));
53			if (qtsettab == NULL)
54			goto memerr;
55			qtsetflag = (int4 )realloc((char )qtsetflag,
56			FLAG_BYTES(osi+ QTSETIBLK));
57			if (qtsetflag == NULL)
58			goto memerr;
59			if(qtallocsets)
60			bzero((char )((char )(qtsetflag)+FLAG_BYTES(qtallocsets)),
61			FLAG_BYTES(osi+QTSETIBLK)-FLAG_BYTES(qtallocsets));
62			else
63			bzero((char *)(qtsetflag),FLAG_BYTES(osi +QTSETIBLK));
64
65			qtallocsets = osi + QTSETIBLK;
66			}
67			qtsettab[osi] = (OBJECT )malloc(QTNODESIZ(oset)*sizeof(OBJECT));
68			if (qtsettab[osi] == NULL)
69			goto memerr;
70			setcopy(qtsettab[osi], oset);
71			return(QT_INDEX(osi));
72			memerr:
73			error(SYSTEM, "out of memory in qtnewleaf\n");
74			}
75
76
77
78			QUADTREE
79			qtdelelem(qt, id) /* delete element from leaf node */
80			QUADTREE qt;
81			OBJECT id;
82			{
83			register QUADTREE lf;
84			#ifdef DEBUG
85			if(id < 0)
86			eputs("qtdelelem():Invalid triangle id\n");
87			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
88			error(CONSISTENCY, "empty/bad node in qtdelelem");
89			#else
90			lf = QT_SET_INDEX(qt);
91			#endif
92
93			if (!inset(qtsettab[lf], id))
94			{
95			#ifdef DEBUG
96			eputs("id not in leaf in qtdelelem\n");
97			#endif
98			return(qt);
99			}
100			if (qtsettab[lf][0] <= 1) { /* blow leaf away */
101			free((char *)qtsettab[lf]);
102			qtsettab[lf] = (OBJECT *)qtfreesets;
103			qtfreesets = lf;
104			return(EMPTY);
105			}
106			deletelem(qtsettab[lf], id);
107			if (QTONTHRESH(qtsettab[lf][0]))
108			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
109			QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
110			return(qt);
111			}
112
113
114			QUADTREE
115			qtaddelem(qt, id) /* add element to leaf node */
116			QUADTREE qt;
117			OBJECT id;
118			{
119			OBJECT newset[2];
120			register QUADTREE lf;
121
122			#ifdef DEBUG
123			if(id < 0)
124			eputs("qtaddelem():Invalid triangle id\n");
125			#endif
126			if (QT_IS_EMPTY(qt)) { /* create new leaf */
127			newset[0] = 1; newset[1] = id;
128			return(qtnewleaf(newset));
129			} /* else add element */
130			#ifdef DEBUG
131			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
132			error(CONSISTENCY, "bad node in qtaddelem");
133			#else
134			lf = QT_SET_INDEX(qt);
135			#endif
136
137			if (inset(qtsettab[lf], id))
138			{
139			#ifdef DEBUG
140			eputs("id already in leaf in qtaddelem\n");
141			#endif
142			return(qt);
143			}
144			if (QTONTHRESH(qtsettab[lf][0])) {
145			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
146			QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
147			if (qtsettab[lf] == NULL)
148			error(SYSTEM, "out of memory in qtaddelem");
149			}
150			insertelem(qtsettab[lf], id);
151			return(qt);
152			}
153
154			#define insertuelem(os,id) ((os)[++((os)[0])] = (id))
155
156			int
157			qtcompressuelem(qt,compress_set)
158			QUADTREE qt;
159			int (*compress_set)();
160			{
161			register QUADTREE lf;
162			int i,j,osize;
163			OBJECT *os;
164
165			if(QT_IS_EMPTY(qt))
166			return(qt);
167			#ifdef DEBUG
168			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
169			error(CONSISTENCY, "bad node in qtaddelem");
170			#else
171			lf = QT_SET_INDEX(qt);
172			#endif
173			os = qtsettab[lf];
174			osize = os[0];
175			if((i=compress_set(os)) < osize)
176			{
177			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
178			QTNODESIZ(i+1)*sizeof(OBJECT));
179			if (qtsettab[lf] == NULL)
180			error(SYSTEM, "out of memory in qtaddelem");
181			}
182			return(qt);
183			}
184
185
186			QUADTREE
187			qtadduelem(qt, id) /* add element to unsorted leaf node */
188			QUADTREE qt;
189			OBJECT id;
190			{
191			OBJECT newset[2];
192			register QUADTREE lf;
193
194			#ifdef DEBUG
195			if(id < 0)
196			eputs("qtaddelem():Invalid triangle id\n");
197			#endif
198			if (QT_IS_EMPTY(qt)) { /* create new leaf */
199			newset[0] = 1; newset[1] = id;
200			return(qtnewleaf(newset));
201			} /* else add element */
202			#ifdef DEBUG
203			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
204			error(CONSISTENCY, "bad node in qtaddelem");
205			#else
206			lf = QT_SET_INDEX(qt);
207			#endif
208			if (QTONTHRESH(qtsettab[lf][0])) {
209			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
210			QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
211			if (qtsettab[lf] == NULL)
212			error(SYSTEM, "out of memory in qtaddelem");
213			}
214			insertuelem(qtsettab[lf], id);
215			return(qt);
216			}
217
218
219			#ifdef DEBUG
220			OBJECT *
221			qtqueryset(qt) /* return object set for leaf node */
222			QUADTREE qt;
223			{
224			register QUADTREE lf;
225
226			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
227			error(CONSISTENCY, "bad node in qtqueryset");
228			return(qtsettab[lf]);
229			}
230			#endif
231
232			int
233			qtinuset(qt,id)
234			QUADTREE qt;
235			OBJECT id;
236			{
237			OBJECT *os;
238			int i;
239
240			os = qtqueryset(qt);
241			for(i=os[0],os++; i > 0; i--,os++)
242			if(*os==id)
243			return(1);
244
245			return(0);
246			}
247
248
249			qtfreeleaf(qt) /* free set and leaf node */
250			QUADTREE qt;
251			{
252			register QUADTREE osi;
253
254			if (!QT_IS_LEAF(qt))
255			return;
256			osi = QT_SET_INDEX(qt);
257			if (osi >= qtnumsets)
258			return;
259			free((char *)qtsettab[osi]);
260			qtsettab[osi] = (OBJECT *)qtfreesets;
261			qtfreesets = osi;
262			}
263
264
265
266			qtfreeleaves() /* free ALL sets and leaf nodes */
267			{
268			register int i;
269
270			while ((i = qtfreesets) != EMPTY) {
271			qtfreesets = (int)qtsettab[i];
272			qtsettab[i] = NULL;
273			}
274			for (i = qtnumsets; i--; )
275			if (qtsettab[i] != NULL)
276			free((char *)qtsettab[i]);
277			free((char *)qtsettab);
278			qtsettab = NULL;
279			if(qtsetflag)
280			{
281			free((char *)qtsetflag);
282			qtsetflag=0;
283			}
284			qtnumsets = 0;
285			}
286
287
288			/* no bounds on os csptr. This routine is conservative: the result returned
289			in os is the set intersection, and therefore is bounded by the size of os.
290			cs is bound to be <= QT_MAXCSET
291			*/
292			check_set_large(os, cs) /* modify checked set and set to check */
293			register OBJECT os; / os' = os - cs */
294			register OBJECT cs; / cs' = cs + os */
295			{
296			OBJECT cset[QT_MAXCSET+1];
297			register int i, j;
298			int k;
299			/* copy os in place, cset <- cs */
300
301			cset[0] = 0;
302			k = 0;
303			for (i = j = 1; i <= os[0]; i++) {
304			while (j <= cs[0] && cs[j] < os[i])
305			if(cset[0] < QT_MAXCSET)
306			cset[++cset[0]] = cs[j++];
307			else
308			j++;
309			if (j > cs[0] \|\| os[i] != cs[j]) { /* object to check */
310			os[++k] = os[i];
311			if(cset[0] < QT_MAXCSET)
312			cset[++cset[0]] = os[i];
313			}
314			}
315			if (!(os[0] = k)) /* new "to check" set size */
316			return; /* special case */
317
318			while (j <= cs[0]) /* get the rest of cs */
319			if(cset[0] == QT_MAXCSET)
320			break;
321			else
322			cset[++cset[0]] = cs[j++];
323
324			os = cset; /* copy cset back to cs */
325			for (i = os[0]; i-- >= 0; )
326			cs++ = os++;
327
328			}
329
330
331
332