1 /* pdnmesh - a 2D finite element solver
2 Copyright (C) 2001-2005 Sarod Yatawatta <sarod@users.sf.net>
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2 of the License, or
6 (at your option) any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 $Id: dag.c,v 1.16 2005/04/19 00:36:36 sarod Exp $
17 */
18
19 #ifdef HAVE_CONFIG_H
20 #include <config.h>
21 #endif
22
23
24 /* Directed Acyclic Graph */
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include "types.h"
29
30 /* sentinel for queue intialization */
31 static DAG_node_queue Dsentinel={NULL,NULL,NULL};
32 /* initialize DAG */
33 int
DAG_init(DAG_tree * t,int (* comp_INC)(const void * rec1,const void * rec2,const void * MM),void (* print_record)(const void * rec))34 DAG_init(DAG_tree *t, int (*comp_INC)(const void *rec1,const void *rec2, const void *MM/* Mesh */),
35 void (*print_record)(const void *rec))
36 {
37 t->root=0;
38 t->comp_INC=comp_INC;
39 t->print_record=print_record;
40 /* intialize the queue */
41 t->sentinel=&Dsentinel;
42 t->qhead=t->sentinel;
43 t->qtail=t->sentinel;
44 t->sentinel->next=t->sentinel->prev=0;
45 return(DAG_STATUS_OK);
46 }
47
48 /* we return the dag node with piggyback data record */
49 /* because we need it for cross referencing */
50 void *
DAG_insert(DAG_tree * t,DAG_node * parent,void * rec)51 DAG_insert(DAG_tree *t, DAG_node *parent, void *rec)
52 {
53 DAG_node_list *temp_list_node, *head,*tail;
54 DAG_node_queue *temp_q;
55 DAG_node *child;
56
57
58 if ((child=(DAG_node *)malloc(sizeof(DAG_node)))==0) {
59 fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
60 exit(1);
61 }
62 child->rec=rec;
63 /* we do not actually keep the data here */
64 /* because it will be kept in the balanced tree */
65 child->list=0;
66
67 /* insert new node to queue because by default it will be a leaf */
68 if ((temp_q=(DAG_node_queue *)malloc(sizeof(DAG_node_queue)))==0) {
69 fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
70 exit(1);
71 }
72 /* insert it above the sentinel */
73 temp_q->next=t->sentinel->next;
74 if ( t->sentinel->next ) {
75 t->sentinel->next->prev=temp_q;
76 }
77 t->sentinel->next=temp_q;
78 temp_q->prev=t->sentinel;
79 temp_q->child=child;
80 /* this is the empty queue case */
81 if ( t->qhead == t->sentinel ) {
82 t->qhead=temp_q;
83 }
84
85 /* first handle empty DAG */
86 if (t->root==0) {
87 t->root=child;
88 return((void*)child);
89 }
90
91 /* non - empty tree */
92 /* first create the list node and the dag node pointing it */
93 if ((temp_list_node=(DAG_node_list *)malloc(sizeof(DAG_node_list)))==0) {
94 fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
95 exit(1);
96 }
97 temp_list_node->next=0;
98 temp_list_node->child=child;
99
100 if (parent->list==0) {
101 parent->list=temp_list_node;
102 return((void*)temp_list_node->child);
103 }
104 /* else implied */
105 head=parent->list;
106 /* traverse parent list of children*/
107 while (head){
108 tail=head;
109 head=head->next;
110 }
111 tail->next=temp_list_node;
112 return((void*)temp_list_node->child);
113 }
114
115 /* add a cross link between two nodes */
116 void *
DAG_link(DAG_tree * t,DAG_node * parent,DAG_node * child)117 DAG_link(DAG_tree *t, DAG_node *parent, DAG_node *child)
118 {
119 DAG_node_list *temp_list_node, *head,*tail;
120 /* first create the list node and the dag node pointing it */
121 if ((temp_list_node=(DAG_node_list *)malloc(sizeof(DAG_node_list)))==0) {
122 fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
123 exit(1);
124 }
125 temp_list_node->next=0;
126 temp_list_node->child=child;
127 if (!parent) {
128 fprintf(stderr,"%s: %d: error",__FILE__,__LINE__);
129 return(0);
130 }
131 if (parent->list==0) {
132 parent->list=temp_list_node;
133 return((void*)temp_list_node->child);
134 }
135 /* else implied */
136 head=parent->list;
137 /* traverse parent list of children*/
138 while (head){
139 tail=head;
140 head=head->next;
141 }
142 tail->next=temp_list_node;
143 return((void*)temp_list_node->child);
144 }
145
146
147 /* returns node pointer where data is found */
148 /* assertion - nodes at same level cover disjoint regions */
149 /* nodes at higher level cover same region as nodes at lower level */
150 void *
DAG_find(DAG_tree * t,void * datarec,const void * MM)151 DAG_find(DAG_tree *t, void *datarec, const void *MM/* Mesh */)
152 {
153 /* note- datarec need not be the type rec */
154 DAG_node *parent;
155 DAG_node_list *head;
156 /* empty tree */
157 if (!t || t->root==0) {
158 return(0);
159 }
160
161 /* next a special check for root data */
162 if (!t->comp_INC((void *)t->root->rec,(void *)datarec,MM))
163 return(0);
164 /* if root record is not including data, no need to check any further */
165
166 /* loop till we reach the leaves of DAG */
167 parent=t->root;
168 do {
169 head=parent->list;
170 while (head && (!t->comp_INC((void*)head->child->rec,(void *)datarec,MM))) {
171 head=head->next;
172 }
173 /* if we are here, either head==0, or Inclusion function works */
174 if (head==0) {
175 return((void*)parent);
176 } else {
177 parent=head->child;
178 }
179 } while (parent);
180
181 /* we will not get here, hopefully */
182 return(0);
183
184 }
185
186 /* local visit */
187 static void
visit_node(DAG_tree * t,DAG_node * parent)188 visit_node(DAG_tree *t,DAG_node *parent)
189 {
190 DAG_node_list *head;
191 t->print_record(parent->rec);
192 /* traverse child list */
193 head=parent->list;
194 /* traverse parent list of children*/
195 while (head){
196 visit_node(t,head->child);
197 head=head->next;
198 }
199 }
200 /* traverse and print */
201 void
DAG_traverse(DAG_tree * t)202 DAG_traverse(DAG_tree *t)
203 {
204 /* empty tree */
205 if (t && t->root) {
206 visit_node(t,t->root);
207 }
208 }
209
210 /* traverse the leaf list and prune it */
211 /* that is, remove nodes that are not leaves */
212 /* returns the next leaf node data pointer */
213 void *
DAG_traverse_prune_list(DAG_tree * t)214 DAG_traverse_prune_list(DAG_tree *t)
215 {
216 DAG_node_queue *temp;
217 /* empty - impossible */
218 if (!t || !t->sentinel)
219 return(0);
220 /* tail==(sentinel)==head - empty */
221 if ( (t->qhead==t->sentinel) && (t->qtail==t->sentinel ) ){
222 return(0);
223 }
224 /* we have reached the end of our traversal */
225 /* (tail)-(*)-(*)-(*).....(*)-(sentinel)==head */
226 /* change this to */
227 /* (tail)==(sentinel)-(*)-(*)-(*).....(*)-(head) */
228 if (t->qhead == t->sentinel ) {
229 /* move sentinel to tail */
230 temp=t->sentinel;
231 t->qhead=t->qhead->prev;
232 t->qhead->next=0;
233 temp->next=t->qtail;
234 t->qtail->prev=temp;
235 t->qtail=temp;
236 t->qtail->prev=0;
237 return(0);
238 }
239
240 /* normal case */
241 /* (tail)-(*)-(*)-(*).....(*)-(sentinel)-(*)-(*)-(*).....(*)-(head)*/
242 while (t->qhead != t->sentinel ) {
243 /* get the next node from queue */
244 temp=t->qhead;
245 t->qhead=temp->prev;
246 if ( t->qhead ) {
247 t->qhead->next=0;
248 }
249 /* check if this is a leaf */
250 if ( !temp->child->list ) {
251 /* insert this back at the tail
252 * and return its record value */
253 temp->next=t->qtail;
254 temp->prev=0;
255 if ( t->qtail ) {
256 t->qtail->prev =temp;
257 }
258 t->qtail=temp;
259 return(temp->child->rec);
260 } else {
261 /* this is not a leaf, so remove it from the queue */
262 #ifdef DEBUG
263 printf("DAG pruning\n");
264 #endif
265 free(temp);
266 /* get another node from queue */
267 }
268 }
269
270 /* if we reach here, queue does not have a leaf */
271 return(0);
272
273 }
274
275 /* reset queue for a new traversal */
276 void
DAG_traverse_list_reset(DAG_tree * t)277 DAG_traverse_list_reset(DAG_tree *t)
278 {
279 /* empty - impossible */
280 if ( t->sentinel ) {
281
282 /* move the sentinel down to the tail of the queue */
283 if ((t->qhead !=t->sentinel)&&(t->qtail !=t->sentinel)) {
284 /* sentinel in the middle */
285 t->sentinel->prev->next=t->sentinel->next;
286 t->sentinel->next->prev=t->sentinel->prev;
287 /* move down */
288 t->qtail->prev=t->sentinel;
289 t->sentinel->prev=0;
290 t->sentinel->next=t->qtail;
291 t->qtail=t->sentinel;
292 } else if ((t->qhead ==t->sentinel) &&(t->qtail !=t->sentinel) ) {
293 /* sentinel at head, bring to bottom */
294 t->sentinel->prev->next=0;
295 t->qhead=t->sentinel->prev;
296 /* move down */
297 t->qtail->prev=t->sentinel;
298 t->sentinel->prev=0;
299 t->sentinel->next=t->qtail;
300 t->qtail=t->sentinel;
301 }
302
303 }
304 }
305
306
307 /* local free */
308 static void
free_node(DAG_tree * t,DAG_node * parent)309 free_node(DAG_tree *t,DAG_node *parent)
310 {
311 DAG_node_list *head;
312 /* BIG NOTE: we do not free the record here
313 * it has to be freed using the RBT */
314 /* t->print_record(parent->rec); */
315 if ( parent ) {
316 /* traverse child list */
317 head=parent->list;
318 /* free parent list of children*/
319 while (head){
320 free_node(t,head->child);
321 head=head->next;
322 }
323 /* free itself */
324 free(parent);
325 }
326 }
327
328 /* BIG NOTE: we do not free the record here
329 * it has to be freed using the RBT */
330 /* free DAG */
331 void
DAG_free(DAG_tree * t)332 DAG_free(DAG_tree *t)
333 {
334 DAG_node_queue *temp;
335 /* free tree */
336 if (!t->root) {
337 free_node(t,t->root);
338 }
339
340 /* free queue */
341 if ( (t->qhead!=t->qtail) ){
342 /* normal case */
343 /* (tail)-(*)-(*)-(*).....(*)-(sentinel)-(*)-(*)-(*).....(*)-(head)*/
344 temp=t->qhead;
345 t->qhead=temp->prev;
346 while (temp ) {
347 if (temp!=t->sentinel) {free(temp);}
348 temp=t->qhead;
349 if ( temp )
350 t->qhead=temp->prev;
351 }
352 }
353 }
354
355
356
357 /* reset queue for a new reverse-traversal */
358 void
DAG_reverse_traverse_list_reset(DAG_tree * t)359 DAG_reverse_traverse_list_reset(DAG_tree *t)
360 {
361 /* empty - impossible */
362 if ( t->sentinel ) {
363
364 /* move the sentinel up to the head of the queue */
365 if ((t->qhead !=t->sentinel)&&(t->qtail !=t->sentinel)) {
366 /* sentinel in the middle */
367 t->sentinel->prev->next=t->sentinel->next;
368 t->sentinel->next->prev=t->sentinel->prev;
369 /* move up */
370 t->qhead->next=t->sentinel;
371 t->sentinel->next=0;
372 t->sentinel->prev=t->qhead;
373 t->qhead=t->sentinel;
374 } else if ((t->qtail==t->sentinel) &&(t->qhead !=t->sentinel) ) {
375 /* sentinel at tail, bring to top*/
376 t->sentinel->next->prev=0;
377 t->qtail=t->sentinel->next;
378 /* move up */
379 t->qhead->next=t->sentinel;
380 t->sentinel->next=0;
381 t->sentinel->prev=t->qhead;
382 t->qhead=t->sentinel;
383 }
384
385 }
386 }
387
388
389 /* reverse-traverse the leaf list and prune it */
390 /* that is, remove nodes that are not leaves */
391 /* returns the next leaf node data pointer */
392 /* note: reverse traverse is needed when we do not want to consider
393 * triangles created while traversing the list.
394 * these new triangles will be considered in the next traversal of
395 * the list. this is the difference between
396 * reverse and normal traversals. the reason being, new triangles
397 * are always inserted before the sentinel. so (head)-*-*-(sentinel)
398 * part gets new triangles, not the (sentinel)-*-(tail) part
399 */
400 void *
DAG_reverse_traverse_prune_list(DAG_tree * t)401 DAG_reverse_traverse_prune_list(DAG_tree *t)
402 {
403 DAG_node_queue *temp;
404 /* empty - impossible */
405 if ( !t->sentinel )
406 return(0);
407 /* tail==(sentinel)==head - empty */
408 if ( (t->qhead==t->sentinel) && (t->qtail==t->sentinel ) ){
409 return(0);
410 }
411 /* we have reached the end of our traversal */
412 /* (head)-(*)-(*)-(*).....(*)-(sentinel)==tail*/
413 /* change this to */
414 /* (head)==(sentinel)-(*)-(*)-(*).....(*)-(tail) */
415 if (t->qtail== t->sentinel ) {
416 /* move sentinel to head */
417 temp=t->sentinel;
418 t->qtail=t->qtail->next;
419 t->qtail->prev=0;
420 temp->prev=t->qhead;
421 t->qhead->next=temp;
422 t->qhead=temp;
423 t->qhead->next=0;
424 return(0);
425 }
426
427 /* normal case */
428 /* (head)-(*)-(*)-(*).....(*)-(sentinel)-(*)-(*)-(*).....(*)-(tail)*/
429 while (t->qtail != t->sentinel ) {
430 /* get the next node from queue (tail) */
431 temp=t->qtail;
432 t->qtail=temp->next;
433 if ( t->qtail) {
434 t->qtail->prev=0;
435 }
436 /* check if this is a leaf */
437 if ( !temp->child->list ) {
438 /* insert this back at the head
439 * and return its record value */
440 temp->prev=t->qhead;
441 temp->next=0;
442 if ( t->qhead) {
443 t->qhead->next=temp;
444 }
445 t->qhead=temp;
446 return(temp->child->rec);
447 } else {
448 /* this is not a leaf, so remove it from the queue */
449 #ifdef DEBUG
450 printf("DAG pruning\n");
451 #endif
452 free(temp);
453 /* get another node from queue */
454 }
455 }
456
457 /* if we reach here, queue does not have a leaf */
458 return(0);
459
460 }
461