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.6 by greg, Sat Feb 22 02:07:25 2003 UTC

# Line 1 | Line 1
1 – /* Copyright (c) 1998 Silicon Graphics, Inc. */
2 –
1   #ifndef lint
2 < static char SCCSid[] = "$SunId$ SGI";
2 > static const char       RCSid[] = "$Id$";
3   #endif
6 –
4   /*
5   * Quadtree-specific set operations.
6   */
# Line 11 | Line 8 | static char SCCSid[] = "$SunId$ SGI";
8   #include "standard.h"
9  
10   #include "sm_qtree.h"
14 – #include "object.h"
11  
12 < #define QTSETIBLK       1024            /* set index allocation block size */
12 >
13 > #define QTSETIBLK       2048            /* set index allocation block size */
14   #define QTELEMBLK       8               /* set element allocation block */
15 + #define QTELEMMOD(ne)   ((ne)&7)        /* (ne) % QTELEMBLK */
16  
17 < #define QTNODESIZ(ne)   ((ne) + QTELEMBLK - ((ne) % QTELEMBLK))
17 > #define QTONTHRESH(ne)  (!QTELEMMOD((ne)+1))
18 > #define QTNODESIZ(ne)   ((ne) + QTELEMBLK - QTELEMMOD(ne))
19  
20 < static OBJECT   **qtsettab;             /* quadtree leaf node table */
21 < static QUADTREE  qtnumsets;             /* number of used set indices */
20 > OBJECT  **qtsettab= NULL;               /* quadtree leaf node table */
21 > QUADTREE  qtnumsets;                    /* number of used set indices */
22   static int  qtfreesets = EMPTY;         /* free set index list */
23  
24  
# Line 27 | Line 26 | QUADTREE
26   qtnewleaf(oset)                 /* return new leaf node for object set */
27   OBJECT  *oset;
28   {
29 <        register QUADTREE  osi;
31 <        int     nalc;
29 >  register QUADTREE  osi;
30  
31 <        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 <        nalc = QTNODESIZ(*oset);
43 <        if ((qtsettab[osi] = (OBJECT *)malloc(nalc*sizeof(OBJECT))) == NULL)
44 <                goto memerr;
45 <        setcopy(qtsettab[osi], oset);
46 <        return(QT_INDEX(osi));
31 >  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   memerr:
48 <        error(SYSTEM, "out of memory in qtnewleaf");
48 >  error(SYSTEM, "out of memory in qtnewleaf");
49   }
50  
51  
52   QUADTREE
53 < qtdelelem(qt, id)               /* delete element from leaf node, no quest. */
53 > qtdelelem(qt, id)               /* delete element from leaf node */
54   QUADTREE  qt;
55   OBJECT  id;
56   {
57          register QUADTREE  lf;
60 –        int  oalc, nalc;
58  
59 <        if (QT_IS_EMPTY(qt))
60 <                return(EMPTY);
61 <        if (!QT_IS_LEAF(qt))
62 <                goto noderr;
59 > #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          lf = QT_SET_INDEX(qt);
68 <        if (lf >= qtnumsets)
68 <                goto noderr;
68 > #endif
69          if (qtsettab[lf][0] <= 1) {             /* blow leaf away */
70 <                free((char *)qtsettab[lf]);
70 >                free((void *)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);
74 >        }
75          deletelem(qtsettab[lf], id);
76 <        if (nalc != oalc)
76 >        if (QTONTHRESH(qtsettab[lf][0]))
77                  qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
78 <                                nalc*sizeof(OBJECT));
78 >                                QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
79          return(qt);
82 – noderr:
83 –        error(CONSISTENCY, "bad node in qtdelelem");
80   }
81  
82  
83   QUADTREE
84 < qtaddelem(qt, id)               /* add element to leaf node, no quest. */
84 > qtaddelem(qt, id)               /* add element to leaf node */
85   QUADTREE  qt;
86   OBJECT  id;
87   {
88          OBJECT  newset[2];
89          register QUADTREE  lf;
94 –        int  oalc, nalc;
90  
91 + #ifdef DEBUG
92 +        if(id < 0)
93 +                eputs("qtaddelem():Invalid triangle id\n");
94 + #endif
95          if (QT_IS_EMPTY(qt)) {          /* create new leaf */
96                  newset[0] = 1; newset[1] = id;
97                  return(qtnewleaf(newset));
98          }                               /* else add element */
99 <        if (!QT_IS_LEAF(qt))
100 <                goto noderr;
99 > #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          lf = QT_SET_INDEX(qt);
106 <        if (lf >= qtnumsets)
107 <                goto noderr;
105 <        oalc = QTNODESIZ(qtsettab[lf][0]);
106 <        nalc = QTNODESIZ(qtsettab[lf][0] + 1);
107 <        if (nalc != oalc) {
106 > #endif
107 >        if (QTONTHRESH(qtsettab[lf][0])) {
108                  qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
109 <                                nalc*sizeof(OBJECT));
109 >                                QTNODESIZ(qtsettab[lf][0]+1)*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");
115   }
116  
117  
118 < qtgetset(oset, qt)              /* get object set for leaf node */
119 < register OBJECT  *oset;
118 > #ifdef DEBUG
119 > OBJECT *
120 > qtqueryset(qt)                  /* return object set for leaf node */
121   QUADTREE  qt;
122   {
123 <        QUADTREE  lf;
125 <        register OBJECT  *os;
126 <        register int  i;
123 >        register QUADTREE  lf;
124  
125 <        if (!QT_IS_LEAF(qt))
126 <                goto noderr;
127 <        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");
125 >        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
126 >                error(CONSISTENCY, "bad node in qtqueryset");
127 >        return(qtsettab[lf]);
128   }
129 + #endif
130  
131  
132   qtfreeleaf(qt)                  /* free set and leaf node */
# Line 147 | Line 138 | QUADTREE  qt;
138                  return;
139          osi = QT_SET_INDEX(qt);
140          if (osi >= qtnumsets)
141 <                error(CONSISTENCY, "bad node in qtfreeleaf");
142 <        free((char *)qtsettab[osi]);
141 >                return;
142 >        free((void *)qtsettab[osi]);
143          qtsettab[osi] = (OBJECT *)qtfreesets;
144          qtfreesets = osi;
145   }
146  
147  
148 +
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 +                        free((void *)qtsettab[i]);
160 +        free((void *)qtsettab);
161 +        qtsettab = NULL;
162 +        qtnumsets = 0;
163 + }
164 +
165 +
166   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 <    OBJECT  cset[MAXCSET+MAXSET+1];
170 >    OBJECT  cset[QT_MAXCSET+QT_MAXSET+1];
171      register int  i, j;
172      int  k;
173                                          /* copy os in place, cset <- cs */
# Line 176 | Line 185 | register OBJECT  *cs;                   /* cs' = cs +
185         return;                 /* special case */
186      while (j <= cs[0])              /* get the rest of cs */
187         cset[++cset[0]] = cs[j++];
188 <    if (cset[0] > MAXCSET)          /* truncate "checked" set if nec. */
189 <       cset[0] = MAXCSET;
188 >    if (cset[0] > QT_MAXCSET)          /* truncate "checked" set if nec. */
189 >       cset[0] = QT_MAXCSET;
190      /* setcopy(cs, cset); */        /* copy cset back to cs */
191      os = cset;
192      for (i = os[0]; i-- >= 0; )
193         *cs++ = *os++;
194   }
195 +
196 +
197 +
198 +
199 +
200 +
201 +
202 +
203 +

Diff Legend

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