src/hd/sm_usets.c

#ifndef lint
static const char       RCSid[] = "$Id: sm_usets.c,v 3.5 2003/06/30 14:59:12 schorsch Exp $";
#endif
/*
 * Quadtree-specific set operations with unsorted sets.
 */

#include <string.h>

#include "standard.h"
#include "sm_flag.h"
#include "object.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 */
int32 *qtsetflag = NULL;
static int qtallocsets =0;

qtclearsetflags()
{

  if(!qtsetflag)
    return;

    memset((char *)qtsetflag, '\0', 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((void *)qtsettab,
                                (unsigned)(osi+QTSETIBLK)*sizeof(OBJECT *));
                if (qtsettab == NULL)
                        goto memerr;
                qtsetflag = (int32 *)realloc((void *)qtsetflag,
                                   FLAG_BYTES(osi+ QTSETIBLK));
                if (qtsetflag == NULL)
                        goto memerr;
                if(qtallocsets)
                  memset((char *)((char *)(qtsetflag)+FLAG_BYTES(qtallocsets)), '\0',
                      FLAG_BYTES(osi+QTSETIBLK)-FLAG_BYTES(qtallocsets));
                else
                  memset((char *)(qtsetflag), '\0', 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");
}


deletuelem(os, obj)             /* delete obj from unsorted os, no questions */
register OBJECT  *os;
OBJECT  obj;
{
        register int  i,j;
        OBJECT *optr;
        /* Take 2nd to last and put in position of obj: move last down:
           want to preserve last added
         */
        i = (*os)--;
#ifdef DEBUG
        if( i <= 0)
          error(CONSISTENCY,"deleteuelem():empty set\n");
#endif
        if(i < 3)
        {
          if((i == 2) && (*(++os) == obj))
            *os = *(os+1);
          return;
        }
        optr = os + i;
        os++;
        while (i-- > 1 && *os != obj)
           os++;
#ifdef DEBUG
        if( *os != obj)
          error(CONSISTENCY,"deleteuelem():id not found\n");
#endif
        *os = *(optr-1);
        *(optr-1) = *optr;
}

QUADTREE
qtdeletuelem(qt, id)            /* delete element from unsorted leaf node */
QUADTREE  qt;
OBJECT  id;
{
        register QUADTREE  lf;
#ifdef DEBUG
        if(id < 0)
                eputs("qtdeletuelem():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 (qtsettab[lf][0] <= 1) {             /* blow leaf away */
                free((void *)qtsettab[lf]);
                qtsettab[lf] = (OBJECT *)qtfreesets;
                qtfreesets = lf;
                return(EMPTY);
        }
        deletuelem(qtsettab[lf], id);
        if (QTONTHRESH(qtsettab[lf][0]))
                qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
                                QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
        return(qt);
}

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((void *)qtsettab[lf]);
                qtsettab[lf] = (OBJECT *)qtfreesets;
                qtfreesets = lf;
                return(EMPTY);
        }
        deletelem(qtsettab[lf], id);
        if (QTONTHRESH(qtsettab[lf][0]))
                qtsettab[lf] = (OBJECT *)realloc((void *)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((void *)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((void *)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("qtadduelem():Invalid sample 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((void *)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((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;
        if(qtsetflag)
        {
          free((void *)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.6
Committed:	Fri Nov 5 03:31:37 2004 UTC (20 years ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 3.5:	+1 -1 lines
State:	*FILE REMOVED*
Log Message:	Removed unused programs and files from distribution (sources to CVS attic)
#	User	Rev	Content
1	gwlarson	3.1	#ifndef lint
2	greg	3.6	static const char RCSid[] = "$Id: sm_usets.c,v 3.5 2003/06/30 14:59:12 schorsch Exp $";
3	gwlarson	3.1	#endif
4			/*
5			* Quadtree-specific set operations with unsorted sets.
6			*/
7
8	schorsch	3.5	#include <string.h>
9
10	gwlarson	3.1	#include "standard.h"
11			#include "sm_flag.h"
12	greg	3.2	#include "object.h"
13	gwlarson	3.1	#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	greg	3.4	int32 *qtsetflag = NULL;
27	gwlarson	3.1	static int qtallocsets =0;
28
29			qtclearsetflags()
30			{
31
32			if(!qtsetflag)
33			return;
34
35	schorsch	3.5	memset((char *)qtsetflag, '\0', FLAG_BYTES(qtallocsets));
36	gwlarson	3.1	}
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	greg	3.3	qtsettab = (OBJECT *)realloc((void )qtsettab,
52	gwlarson	3.1	(unsigned)(osi+QTSETIBLK)sizeof(OBJECT ));
53			if (qtsettab == NULL)
54			goto memerr;
55	greg	3.4	qtsetflag = (int32 )realloc((void )qtsetflag,
56	gwlarson	3.1	FLAG_BYTES(osi+ QTSETIBLK));
57			if (qtsetflag == NULL)
58			goto memerr;
59			if(qtallocsets)
60	schorsch	3.5	memset((char )((char )(qtsetflag)+FLAG_BYTES(qtallocsets)), '\0',
61	gwlarson	3.1	FLAG_BYTES(osi+QTSETIBLK)-FLAG_BYTES(qtallocsets));
62			else
63	schorsch	3.5	memset((char *)(qtsetflag), '\0', FLAG_BYTES(osi +QTSETIBLK));
64	gwlarson	3.1
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	greg	3.2	deletuelem(os, obj) /* delete obj from unsorted os, no questions */
78			register OBJECT *os;
79			OBJECT obj;
80			{
81			register int i,j;
82			OBJECT *optr;
83			/* Take 2nd to last and put in position of obj: move last down:
84			want to preserve last added
85			*/
86			i = (*os)--;
87			#ifdef DEBUG
88			if( i <= 0)
89			error(CONSISTENCY,"deleteuelem():empty set\n");
90			#endif
91			if(i < 3)
92			{
93			if((i == 2) && (*(++os) == obj))
94			os = (os+1);
95			return;
96			}
97			optr = os + i;
98			os++;
99			while (i-- > 1 && *os != obj)
100			os++;
101			#ifdef DEBUG
102			if( *os != obj)
103			error(CONSISTENCY,"deleteuelem():id not found\n");
104			#endif
105			os = (optr-1);
106			(optr-1) = optr;
107			}
108
109			QUADTREE
110			qtdeletuelem(qt, id) /* delete element from unsorted leaf node */
111			QUADTREE qt;
112			OBJECT id;
113			{
114			register QUADTREE lf;
115			#ifdef DEBUG
116			if(id < 0)
117			eputs("qtdeletuelem():Invalid triangle id\n");
118			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
119			error(CONSISTENCY, "empty/bad node in qtdelelem");
120			#else
121			lf = QT_SET_INDEX(qt);
122			#endif
123			if (qtsettab[lf][0] <= 1) { /* blow leaf away */
124			free((void *)qtsettab[lf]);
125			qtsettab[lf] = (OBJECT *)qtfreesets;
126			qtfreesets = lf;
127			return(EMPTY);
128			}
129			deletuelem(qtsettab[lf], id);
130			if (QTONTHRESH(qtsettab[lf][0]))
131	greg	3.3	qtsettab[lf] = (OBJECT )realloc((void )qtsettab[lf],
132	greg	3.2	QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
133			return(qt);
134			}
135	gwlarson	3.1
136			QUADTREE
137			qtdelelem(qt, id) /* delete element from leaf node */
138			QUADTREE qt;
139			OBJECT id;
140			{
141			register QUADTREE lf;
142			#ifdef DEBUG
143			if(id < 0)
144			eputs("qtdelelem():Invalid triangle id\n");
145			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
146			error(CONSISTENCY, "empty/bad node in qtdelelem");
147			#else
148			lf = QT_SET_INDEX(qt);
149			#endif
150
151			if (!inset(qtsettab[lf], id))
152			{
153			#ifdef DEBUG
154			eputs("id not in leaf in qtdelelem\n");
155			#endif
156			return(qt);
157			}
158			if (qtsettab[lf][0] <= 1) { /* blow leaf away */
159	greg	3.2	free((void *)qtsettab[lf]);
160	gwlarson	3.1	qtsettab[lf] = (OBJECT *)qtfreesets;
161			qtfreesets = lf;
162			return(EMPTY);
163			}
164			deletelem(qtsettab[lf], id);
165			if (QTONTHRESH(qtsettab[lf][0]))
166	greg	3.3	qtsettab[lf] = (OBJECT )realloc((void )qtsettab[lf],
167	gwlarson	3.1	QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
168			return(qt);
169			}
170
171
172			QUADTREE
173			qtaddelem(qt, id) /* add element to leaf node */
174			QUADTREE qt;
175			OBJECT id;
176			{
177			OBJECT newset[2];
178			register QUADTREE lf;
179
180			#ifdef DEBUG
181			if(id < 0)
182			eputs("qtaddelem():Invalid triangle id\n");
183			#endif
184			if (QT_IS_EMPTY(qt)) { /* create new leaf */
185			newset[0] = 1; newset[1] = id;
186			return(qtnewleaf(newset));
187			} /* else add element */
188			#ifdef DEBUG
189			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
190			error(CONSISTENCY, "bad node in qtaddelem");
191			#else
192			lf = QT_SET_INDEX(qt);
193			#endif
194
195			if (inset(qtsettab[lf], id))
196			{
197			#ifdef DEBUG
198			eputs("id already in leaf in qtaddelem\n");
199			#endif
200			return(qt);
201			}
202			if (QTONTHRESH(qtsettab[lf][0])) {
203	greg	3.3	qtsettab[lf] = (OBJECT )realloc((void )qtsettab[lf],
204	gwlarson	3.1	QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
205			if (qtsettab[lf] == NULL)
206			error(SYSTEM, "out of memory in qtaddelem");
207			}
208			insertelem(qtsettab[lf], id);
209			return(qt);
210			}
211
212			#define insertuelem(os,id) ((os)[++((os)[0])] = (id))
213
214			int
215			qtcompressuelem(qt,compress_set)
216			QUADTREE qt;
217			int (*compress_set)();
218			{
219			register QUADTREE lf;
220			int i,j,osize;
221			OBJECT *os;
222
223			if(QT_IS_EMPTY(qt))
224			return(qt);
225			#ifdef DEBUG
226			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
227			error(CONSISTENCY, "bad node in qtaddelem");
228			#else
229			lf = QT_SET_INDEX(qt);
230			#endif
231			os = qtsettab[lf];
232			osize = os[0];
233			if((i=compress_set(os)) < osize)
234			{
235	greg	3.3	qtsettab[lf] = (OBJECT )realloc((void )qtsettab[lf],
236	gwlarson	3.1	QTNODESIZ(i+1)*sizeof(OBJECT));
237			if (qtsettab[lf] == NULL)
238			error(SYSTEM, "out of memory in qtaddelem");
239			}
240			return(qt);
241			}
242
243
244			QUADTREE
245			qtadduelem(qt, id) /* add element to unsorted leaf node */
246			QUADTREE qt;
247			OBJECT id;
248			{
249			OBJECT newset[2];
250			register QUADTREE lf;
251
252			#ifdef DEBUG
253			if(id < 0)
254	greg	3.2	eputs("qtadduelem():Invalid sample id\n");
255	gwlarson	3.1	#endif
256			if (QT_IS_EMPTY(qt)) { /* create new leaf */
257			newset[0] = 1; newset[1] = id;
258			return(qtnewleaf(newset));
259			} /* else add element */
260			#ifdef DEBUG
261			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
262			error(CONSISTENCY, "bad node in qtaddelem");
263			#else
264			lf = QT_SET_INDEX(qt);
265			#endif
266			if (QTONTHRESH(qtsettab[lf][0])) {
267	greg	3.3	qtsettab[lf] = (OBJECT )realloc((void )qtsettab[lf],
268	gwlarson	3.1	QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
269			if (qtsettab[lf] == NULL)
270			error(SYSTEM, "out of memory in qtaddelem");
271			}
272			insertuelem(qtsettab[lf], id);
273			return(qt);
274			}
275
276
277			#ifdef DEBUG
278			OBJECT *
279			qtqueryset(qt) /* return object set for leaf node */
280			QUADTREE qt;
281			{
282			register QUADTREE lf;
283
284			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
285			error(CONSISTENCY, "bad node in qtqueryset");
286			return(qtsettab[lf]);
287			}
288			#endif
289
290			int
291			qtinuset(qt,id)
292			QUADTREE qt;
293			OBJECT id;
294			{
295			OBJECT *os;
296			int i;
297
298			os = qtqueryset(qt);
299			for(i=os[0],os++; i > 0; i--,os++)
300			if(*os==id)
301			return(1);
302
303			return(0);
304			}
305
306
307			qtfreeleaf(qt) /* free set and leaf node */
308			QUADTREE qt;
309			{
310			register QUADTREE osi;
311
312			if (!QT_IS_LEAF(qt))
313			return;
314			osi = QT_SET_INDEX(qt);
315			if (osi >= qtnumsets)
316			return;
317	greg	3.2	free((void *)qtsettab[osi]);
318	gwlarson	3.1	qtsettab[osi] = (OBJECT *)qtfreesets;
319			qtfreesets = osi;
320			}
321
322
323
324			qtfreeleaves() /* free ALL sets and leaf nodes */
325			{
326			register int i;
327
328			while ((i = qtfreesets) != EMPTY) {
329			qtfreesets = (int)qtsettab[i];
330			qtsettab[i] = NULL;
331			}
332			for (i = qtnumsets; i--; )
333			if (qtsettab[i] != NULL)
334	greg	3.2	free((void *)qtsettab[i]);
335			free((void *)qtsettab);
336	gwlarson	3.1	qtsettab = NULL;
337			if(qtsetflag)
338			{
339	greg	3.2	free((void *)qtsetflag);
340	gwlarson	3.1	qtsetflag=0;
341			}
342			qtnumsets = 0;
343			}
344
345
346			/* no bounds on os csptr. This routine is conservative: the result returned
347			in os is the set intersection, and therefore is bounded by the size of os.
348			cs is bound to be <= QT_MAXCSET
349			*/
350			check_set_large(os, cs) /* modify checked set and set to check */
351			register OBJECT os; / os' = os - cs */
352			register OBJECT cs; / cs' = cs + os */
353			{
354			OBJECT cset[QT_MAXCSET+1];
355			register int i, j;
356			int k;
357			/* copy os in place, cset <- cs */
358
359			cset[0] = 0;
360			k = 0;
361			for (i = j = 1; i <= os[0]; i++) {
362			while (j <= cs[0] && cs[j] < os[i])
363			if(cset[0] < QT_MAXCSET)
364			cset[++cset[0]] = cs[j++];
365			else
366			j++;
367			if (j > cs[0] \|\| os[i] != cs[j]) { /* object to check */
368			os[++k] = os[i];
369			if(cset[0] < QT_MAXCSET)
370			cset[++cset[0]] = os[i];
371			}
372			}
373			if (!(os[0] = k)) /* new "to check" set size */
374			return; /* special case */
375
376			while (j <= cs[0]) /* get the rest of cs */
377			if(cset[0] == QT_MAXCSET)
378			break;
379			else
380			cset[++cset[0]] = cs[j++];
381
382			os = cset; /* copy cset back to cs */
383			for (i = os[0]; i-- >= 0; )
384			cs++ = os++;
385
386			}
387
388
389
390