ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/sm_list.c
Revision: 3.4
Committed: Mon Dec 28 18:07:35 1998 UTC (25 years, 3 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.3: +34 -0 lines
Log Message:
New insertion routine
New Culling routine based on insertion algorithm
Adapted old insertion code: now used by picking
Point location code returns on-vertex,on-edge, or in-triangle
Added on_edge case for subdivision
Implemented unordered sets
Removed deletion from quadtree- added set compression to replace functionality

File Contents

# 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     * 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     *new_list()
24     {
25     LIST *l;
26    
27     /* check free list for available edges */
28     if( free_lists )
29     {
30     l = free_lists;
31     free_lists = LIST_NEXT(free_lists);
32     }
33     /* if no free edges- allocate the memory */
34     else
35     {
36     if( !(l = (LIST *)malloc(sizeof(LIST))))
37     error(SYSTEM,"new_list():Unable to allocate memory");
38     }
39     /* clear the memory */
40     bzero(l, sizeof(LIST));
41    
42     return(l);
43     }
44    
45    
46     /* attaches list a at the end of list b */
47     LIST
48     *append_list(a,b)
49     LIST *a,*b;
50     {
51     LIST * l;
52    
53     if(!b)
54     return(a);
55    
56     l = b;
57     while(LIST_NEXT(l) && LIST_NEXT(l) != b)
58     l = LIST_NEXT(l);
59    
60     SET_LIST_NEXT(l,a);
61    
62     return(b);
63     }
64    
65 gwlarson 3.4 /* attaches list a at the end of list b */
66     LIST
67     *add_data(l,d,end)
68     LIST *l;
69     int d;
70     LIST **end;
71    
72     {
73     LIST *list,*lptr;
74    
75     list = new_list();
76     SET_LIST_DATA(list,d);
77    
78     if(!l)
79     {
80     if(end)
81     *end = list;
82     return(list);
83     }
84     if(end)
85     lptr = *end;
86     else
87     {
88     lptr = l;
89     while(LIST_NEXT(lptr))
90     lptr = LIST_NEXT(lptr);
91     }
92     LIST_NEXT(lptr) = list;
93     if(end)
94     *end = list;
95    
96     return(l);
97     }
98    
99 gwlarson 3.1 /* Adds data to the end of a circular list. If set, "end"
100     * is a pointer to the last element in the list
101     */
102     LIST
103     *add_data_to_circular_list(l,end,d)
104     LIST *l,**end;
105     int d;
106     {
107     LIST *list;
108    
109     list = new_list();
110     SET_LIST_DATA(list,d);
111    
112     if(!l)
113     l = list;
114     else
115     {
116     if(*end)
117     SET_LIST_NEXT(*end,list);
118     else
119     l = append_list(list,l);
120     }
121    
122     *end = list;
123     SET_LIST_NEXT(list,l);
124     return(l);
125     }
126    
127     /* Pushes data element d at the top of the list- returns pointer
128     to new top of list
129     */
130     LIST
131     *push_data(l,d)
132     LIST *l;
133     int d;
134     {
135     LIST * list;
136    
137     list = new_list();
138     SET_LIST_DATA(list,d);
139     SET_LIST_NEXT(list,l);
140     return(list);
141     }
142    
143     /* frees the list */
144     LIST
145     *free_list(l)
146     LIST * l;
147     {
148     if(!l)
149     return(NULL);
150 gwlarson 3.2
151 gwlarson 3.1 free_lists = append_list(free_lists,l);
152    
153     return(NULL);
154     }
155    
156     /* Returns data element d at the top of the list- returns pointer
157     to new top of list
158     */
159     int
160     pop_list(l)
161     LIST **l;
162     {
163     LIST *p;
164 gwlarson 3.2 int d;
165 gwlarson 3.1
166     if(!l)
167     return(NULL);
168     if(!(p = *l))
169     return(NULL);
170    
171     d = LIST_DATA(p);
172    
173     *l = LIST_NEXT(p);
174    
175     LIST_NEXT(p) =NULL;
176     free_list(p);
177    
178     return(d);
179     }
180    
181     /* Search through list for data element "d", and remove from
182     * list: Returns TRUE if found, false otherwise
183     */
184     int
185     remove_from_list(d,list)
186     int d;
187     LIST **list;
188     {
189     LIST *l,*prev;
190    
191     l = *list;
192     prev = NULL;
193    
194     while(l)
195     {
196     if(LIST_DATA(l) == d)
197     {
198     if(l == *list)
199     *list = LIST_NEXT(*list);
200     else
201     SET_LIST_NEXT(prev,LIST_NEXT(l));
202    
203     SET_LIST_NEXT(l,NULL);
204     free_list(l);
205     return(TRUE);
206     }
207     prev = l;
208     l = LIST_NEXT(l);
209     }
210     return(FALSE);
211     }
212    
213    
214    
215    
216    
217    
218    
219    
220    
221