ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_sets.c
(Generate patch)

Comparing ray/src/hd/sm_sets.c (file contents):
Revision 3.1 by gwlarson, Wed Aug 19 17:45:23 1998 UTC vs.
Revision 3.3 by gwlarson, Wed Sep 16 18:16:29 1998 UTC

# Line 11 | Line 11 | static char SCCSid[] = "$SunId$ SGI";
11   #include "standard.h"
12  
13   #include "sm_qtree.h"
14 – #include "object.h"
14  
15 < #define QTSETIBLK       1024            /* set index allocation block size */
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 QTNODESIZ(ne)   ((ne) + QTELEMBLK - ((ne) % QTELEMBLK))
20 > #define QTONTHRESH(ne)  (!QTELEMMOD((ne)+1))
21 > #define QTNODESIZ(ne)   ((ne) + QTELEMBLK - QTELEMMOD(ne))
22  
23 < static OBJECT   **qtsettab;             /* quadtree leaf node table */
24 < static QUADTREE  qtnumsets;             /* number of used set indices */
23 > OBJECT  **qtsettab= NULL;               /* quadtree leaf node table */
24 > QUADTREE  qtnumsets;                    /* number of used set indices */
25   static int  qtfreesets = EMPTY;         /* free set index list */
26  
27  
# Line 28 | Line 30 | qtnewleaf(oset)                        /* return new leaf node for object s
30   OBJECT  *oset;
31   {
32          register QUADTREE  osi;
31 –        int     nalc;
33  
34          if (*oset <= 0)
35                  return(EMPTY);          /* should be error? */
# Line 41 | Line 42 | OBJECT  *oset;
42                  if (qtsettab == NULL)
43                          goto memerr;
44          }
45 <        nalc = QTNODESIZ(*oset);
46 <        if ((qtsettab[osi] = (OBJECT *)malloc(nalc*sizeof(OBJECT))) == NULL)
45 >        qtsettab[osi] = (OBJECT *)malloc(QTNODESIZ(*oset)*sizeof(OBJECT));
46 >        if (qtsettab[osi] == NULL)
47                  goto memerr;
48          setcopy(qtsettab[osi], oset);
49          return(QT_INDEX(osi));
# Line 52 | Line 53 | memerr:
53  
54  
55   QUADTREE
56 < qtdelelem(qt, id)               /* delete element from leaf node, no quest. */
56 > qtdelelem(qt, id)               /* delete element from leaf node */
57   QUADTREE  qt;
58   OBJECT  id;
59   {
60          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;
62 > #ifdef DEBUG
63 >        if(id < 0)
64 >                eputs("qtdelelem():Invalid triangle id\n");
65 >        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
66 >                error(CONSISTENCY, "empty/bad node in qtdelelem");
67 >        if (!inset(qtsettab[lf], id))
68 >                error(CONSISTENCY, "id not in leaf in qtdelelem");
69 > #else
70          lf = QT_SET_INDEX(qt);
71 <        if (lf >= qtnumsets)
68 <                goto noderr;
71 > #endif
72          if (qtsettab[lf][0] <= 1) {             /* blow leaf away */
73                  free((char *)qtsettab[lf]);
74                  qtsettab[lf] = (OBJECT *)qtfreesets;
75                  qtfreesets = lf;
76                  return(EMPTY);
77 <        }                                       /* else delete element */
75 <        oalc = QTNODESIZ(qtsettab[lf][0]);
76 <        nalc = QTNODESIZ(qtsettab[lf][0] - 1);
77 >        }
78          deletelem(qtsettab[lf], id);
79 <        if (nalc != oalc)
79 >        if (QTONTHRESH(qtsettab[lf][0]))
80                  qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
81 <                                nalc*sizeof(OBJECT));
81 >                                QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
82          return(qt);
82 – noderr:
83 –        error(CONSISTENCY, "bad node in qtdelelem");
83   }
84  
85  
86   QUADTREE
87 < qtaddelem(qt, id)               /* add element to leaf node, no quest. */
87 > qtaddelem(qt, id)               /* add element to leaf node */
88   QUADTREE  qt;
89   OBJECT  id;
90   {
91          OBJECT  newset[2];
92          register QUADTREE  lf;
94 –        int  oalc, nalc;
93  
94 + #ifdef DEBUG
95 +        if(id < 0)
96 +                eputs("qtaddelem():Invalid triangle id\n");
97 + #endif
98          if (QT_IS_EMPTY(qt)) {          /* create new leaf */
99                  newset[0] = 1; newset[1] = id;
100                  return(qtnewleaf(newset));
101          }                               /* else add element */
102 <        if (!QT_IS_LEAF(qt))
103 <                goto noderr;
102 > #ifdef DEBUG
103 >        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
104 >                error(CONSISTENCY, "bad node in qtaddelem");
105 >        if (inset(qtsettab[lf], id))
106 >                error(CONSISTENCY, "id already in leaf in qtaddelem");
107 > #else
108          lf = QT_SET_INDEX(qt);
109 <        if (lf >= qtnumsets)
110 <                goto noderr;
105 <        oalc = QTNODESIZ(qtsettab[lf][0]);
106 <        nalc = QTNODESIZ(qtsettab[lf][0] + 1);
107 <        if (nalc != oalc) {
109 > #endif
110 >        if (QTONTHRESH(qtsettab[lf][0])) {
111                  qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
112 <                                nalc*sizeof(OBJECT));
112 >                                QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
113                  if (qtsettab[lf] == NULL)
114                          error(SYSTEM, "out of memory in qtaddelem");
115          }
116          insertelem(qtsettab[lf], id);
117          return(qt);
115 – noderr:
116 –        error(CONSISTENCY, "bad node in qtaddelem");
118   }
119  
120  
121 < qtgetset(oset, qt)              /* get object set for leaf node */
122 < register OBJECT  *oset;
121 > #ifdef DEBUG
122 > OBJECT *
123 > qtqueryset(qt)                  /* return object set for leaf node */
124   QUADTREE  qt;
125   {
126 <        QUADTREE  lf;
125 <        register OBJECT  *os;
126 <        register int  i;
126 >        register QUADTREE  lf;
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");
128 >        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
129 >                error(CONSISTENCY, "bad node in qtqueryset");
130 >        return(qtsettab[lf]);
131   }
132 + #endif
133  
134  
135   qtfreeleaf(qt)                  /* free set and leaf node */
# Line 147 | Line 141 | QUADTREE  qt;
141                  return;
142          osi = QT_SET_INDEX(qt);
143          if (osi >= qtnumsets)
144 <                error(CONSISTENCY, "bad node in qtfreeleaf");
144 >                return;
145          free((char *)qtsettab[osi]);
146          qtsettab[osi] = (OBJECT *)qtfreesets;
147          qtfreesets = osi;
148   }
149  
150  
151 +
152 + qtfreeleaves()                  /* free ALL sets and leaf nodes */
153 + {
154 +        register int    i;
155 +
156 +        while ((i = qtfreesets) != EMPTY) {
157 +                qtfreesets = (int)qtsettab[i];
158 +                qtsettab[i] = NULL;
159 +        }
160 +        for (i = qtnumsets; i--; )
161 +                if (qtsettab[i] != NULL)
162 +                        free((char *)qtsettab[i]);
163 +        free((char *)qtsettab);
164 +        qtsettab = NULL;
165 +        qtnumsets = 0;
166 + }
167 +
168 +
169   check_set(os, cs)                /* modify checked set and set to check */
170   register OBJECT  *os;                   /* os' = os - cs */
171   register OBJECT  *cs;                   /* cs' = cs + os */
172   {
173 <    OBJECT  cset[MAXCSET+MAXSET+1];
173 >    OBJECT  cset[QT_MAXCSET+QT_MAXSET+1];
174      register int  i, j;
175      int  k;
176                                          /* copy os in place, cset <- cs */
# Line 176 | Line 188 | register OBJECT  *cs;                   /* cs' = cs +
188         return;                 /* special case */
189      while (j <= cs[0])              /* get the rest of cs */
190         cset[++cset[0]] = cs[j++];
191 <    if (cset[0] > MAXCSET)          /* truncate "checked" set if nec. */
192 <       cset[0] = MAXCSET;
191 >    if (cset[0] > QT_MAXCSET)          /* truncate "checked" set if nec. */
192 >       cset[0] = QT_MAXCSET;
193      /* setcopy(cs, cset); */        /* copy cset back to cs */
194      os = cset;
195      for (i = os[0]; i-- >= 0; )
196         *cs++ = *os++;
197   }
198 +

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines