ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_list.c
Revision: 3.7
Committed: Thu Jun 10 15:22:23 1999 UTC (24 years, 9 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.6: +6 -4 lines
Log Message:
Implemented sample quadtree in place of triangle quadtree
Made geometric predicates more robust
Added #define LORES which utilizes a single precision floating point
  sample array, the default is a double sample array
Added topology DEBUG commands (for DEBUG > 1)
Made code optimizations

File Contents

# Content
1 /* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3 #ifndef lint
4 static char SCCSid[] = "$SunId$ SGI";
5 #endif
6
7 /*
8 * sm_list.c
9 * Routines for handling linked generic linked lists, stack, and
10 * circular lists. Data element is an int (can be cast to hold
11 * pointer to more general data element)
12 */
13
14 #include "standard.h"
15 #include "sm_list.h"
16
17 /* List of available edges */
18 static LIST *free_lists = NULL;
19 #ifdef DEBUG
20 extern int Malloc_cnt;
21 #endif
22 LIST
23 /* NOTE: Memory is not initialized */
24 *new_list()
25 {
26 LIST *l;
27
28 /* check free list for available edges */
29 if( free_lists )
30 {
31 l = free_lists;
32 free_lists = LIST_NEXT(free_lists);
33 }
34 /* if no free edges- allocate the memory */
35 else
36 {
37 if( !(l = (LIST *)malloc(sizeof(LIST))))
38 error(SYSTEM,"new_list():Unable to allocate memory");
39 }
40 return(l);
41 }
42
43
44 /* attaches list a at the end of list b */
45 LIST
46 *append_list(a,b)
47 LIST *a,*b;
48 {
49 LIST * l;
50
51 if(!b)
52 return(a);
53
54 l = b;
55 while(LIST_NEXT(l) && LIST_NEXT(l) != b)
56 l = LIST_NEXT(l);
57
58 SET_LIST_NEXT(l,a);
59
60 return(b);
61 }
62
63 /* attaches list a at the end of list b */
64 LIST
65 *add_data(l,d,end)
66 LIST *l;
67 int d;
68 LIST **end;
69
70 {
71 LIST *list,*lptr;
72
73 list = new_list();
74 SET_LIST_DATA(list,d);
75 SET_LIST_NEXT(list,NULL);
76 if(!l)
77 {
78 if(end)
79 *end = list;
80 return(list);
81 }
82 if(end)
83 lptr = *end;
84 else
85 {
86 lptr = l;
87 while(LIST_NEXT(lptr))
88 lptr = LIST_NEXT(lptr);
89 }
90 LIST_NEXT(lptr) = list;
91 if(end)
92 *end = list;
93
94 return(l);
95 }
96
97 /* Adds data to the end of a circular list. If set, "end"
98 * is a pointer to the last element in the list
99 */
100 LIST
101 *add_data_to_circular_list(l,end,d)
102 LIST *l,**end;
103 int d;
104 {
105 LIST *list;
106
107 list = new_list();
108 SET_LIST_DATA(list,d);
109
110 if(!l)
111 l = list;
112 else
113 {
114 if(*end)
115 SET_LIST_NEXT(*end,list);
116 else
117 l = append_list(list,l);
118 }
119
120 *end = list;
121 SET_LIST_NEXT(list,l);
122 return(l);
123 }
124
125
126
127 /* frees the list */
128 LIST
129 *free_list(l)
130 LIST * l;
131 {
132 if(!l)
133 return(NULL);
134
135 free_lists = append_list(free_lists,l);
136
137 return(NULL);
138 }
139
140 /* Pushes data element d at the top of the list- returns pointer
141 to new top of list
142 */
143 LIST
144 *push_data(l,d)
145 LIST *l;
146 int d;
147 {
148 LIST *list;
149
150 list = new_list();
151 SET_LIST_DATA(list,d);
152 SET_LIST_NEXT(list,l);
153 return(list);
154 }
155 /* Returns data element d at the top of the list- returns pointer
156 to new top of list
157 */
158 int
159 pop_list(l)
160 LIST **l;
161 {
162 LIST *p;
163 int d;
164
165 if(!l)
166 return(NULL);
167 if(!(p = *l))
168 return(NULL);
169
170 d = LIST_DATA(p);
171
172 *l = LIST_NEXT(p);
173
174 LIST_NEXT(p) =NULL;
175 free_list(p);
176
177 return(d);
178 }
179
180 /* Search through list for data element "d", and remove from
181 * list: Returns TRUE if found, false otherwise
182 */
183 int
184 remove_from_list(d,list)
185 int d;
186 LIST **list;
187 {
188 LIST *l,*prev;
189
190 l = *list;
191 prev = NULL;
192
193 while(l)
194 {
195 if(LIST_DATA(l) == d)
196 {
197 if(l == *list)
198 *list = LIST_NEXT(*list);
199 else
200 SET_LIST_NEXT(prev,LIST_NEXT(l));
201
202 SET_LIST_NEXT(l,NULL);
203 free_list(l);
204 return(TRUE);
205 }
206 prev = l;
207 l = LIST_NEXT(l);
208 }
209 return(FALSE);
210 }
211
212
213
214
215
216
217
218
219
220
221
222
223
224