1 /* SCCS-info %W% %E% */
2
3 /*--------------------------------------------------------------------*/
4 /* */
5 /* VCG : Visualization of Compiler Graphs */
6 /* -------------------------------------- */
7 /* */
8 /* file: animation3.c */
9 /* version: 1.00.00 */
10 /* creation: 12.11.93 */
11 /* author: G. Sander (Version 1.00.00-...) */
12 /* Universitaet des Saarlandes, 66041 Saarbruecken */
13 /* ESPRIT Project #5399 Compare */
14 /* description: Animation demo 3 for VCG */
15 /* status: in work */
16 /* */
17 /*--------------------------------------------------------------------*/
18
19 /* $Id: animation3.c,v 1.2 1995/02/08 18:43:55 sander Exp $ */
20
21 /*
22 * Copyright (C) 1993-2005 Saarland University
23 *
24 * This program and documentation is free software; you can redistribute
25 * it under the terms of the GNU General Public License as published by
26 * the Free Software Foundation; either version 2 of the License, or
27 * (at your option) any later version.
28 *
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * You should have received a copy of the GNU General Public License
35 * along with this program; if not, write to the Free Software
36 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
37 *
38 * The software is available per anonymous ftp at ftp.cs.uni-sb.de.
39 * Contact sander@cs.uni-sb.de for additional information.
40 */
41
42
43 /* $Log: animation3.c,v $
44 * Revision 1.2 1995/02/08 18:43:55 sander
45 * time renamed into timep for compatibility.
46 *
47 * Revision 1.1 1995/02/08 11:21:41 sander
48 * Initial revision
49 *
50 */
51
52
53 /*--------------------------------------------------------------------*
54 * This is a small example how to program a animation. The protocol
55 * used here is the following:
56 *
57 * The client (this program) sends signals to the server (VCG) when
58 * the server should display the graph.
59 * The server touches the file, if it is ready with displaying,
60 * thus the client waits for a change of the time stamp of the
61 * file.
62 *
63 * In this example, we insert numbers into a red-black-tree. The
64 * steps to rebalance the tree are visualized.
65 *--------------------------------------------------------------------*/
66
67 #include <stdio.h>
68 #include <stdlib.h>
69 #include <string.h>
70 #include <signal.h>
71 #include <sys/types.h>
72 #include <sys/stat.h>
73 #include "../src/globals.h"
74
75
76 /* Prototypes
77 * ----------
78 */
79
80 int main _PP((int argc, char *argv[]));
81 void call_vcg _PP((void));
82 void signal_vcg _PP((int k));
83 void wait_for_vcg _PP((void));
84 void get_time _PP((char *fn));
85
86 void insert _PP((int x));
87 void print_tree _PP((void));
88 void free_spec _PP((void));
89
90
91 /* This must be an absolute path to the vcg-tool !
92 * No ~, .. or similar trash allowed.
93 */
94
95 #ifndef VCGCALL
96 #define VCGCALL "/RW/users/sander/pub/bin/xvcg"
97 #endif
98
99 #ifndef VCGTOOL
100 #define VCGTOOL "vcg"
101 #endif
102
103
104 /* Global Variables
105 * ----------------
106 */
107
108 FILE *f = NULL;
109 char filename[] = "rbtree.vcg";
110
111 /*--------------------------------------------------------------------*/
112
113 /* Main Routine
114 * ------------
115 * The main program consists of a small sequence of pictures.
116 * Each picture is generated by create_graph and reloaded into
117 * the vcg by signal_vcg. The calls of get_time and wait_for_vcg
118 * are used for time synchronisation.
119 */
120
121
122 /* These are the numbers to be inserted into the rb-tree */
123
124 int ins[15] = {
125 2, 8, 15, 17, 1,
126 18, 4, 20, 13, 11,
127 6, 10, 12, 14, 9
128 };
129
130
131 char timep[20] = "1";
132
133 #ifdef ANSI_C
main(int argc,char * argv[])134 int main(int argc, char *argv[])
135 #else
136 int main(argc, argv)
137 int argc;
138 char *argv[];
139 #endif
140 {
141 int i;
142
143 if (argc==2) {
144 strcpy(timep,argv[1]);
145 }
146
147 free_spec();
148 insert(3);
149 insert(5);
150 insert(7);
151 print_tree();
152 get_time(filename);
153 call_vcg();
154 wait_for_vcg();
155 sleep(5); /* time to open the window */
156
157 for (i=0; i<15; i++) {
158 insert(ins[i]);
159 print_tree();
160 get_time(filename);
161 signal_vcg(- SIGUSR1);
162 wait_for_vcg();
163 }
164
165 free_spec();
166 print_tree();
167 get_time(filename);
168 signal_vcg(- SIGUSR1);
169 wait_for_vcg();
170
171 signal_vcg(- SIGUSR2); /* close vcg (does not work with X11) */
172 sleep(3);
173 signal_vcg(- SIGQUIT); /* exit vcg */
174 }
175
176
177 /*--------------------------------------------------------------------*/
178 /* Communication with vcg */
179 /*--------------------------------------------------------------------*/
180
181 /* Call the vcg-tool
182 * -----------------
183 * Calling means fork a child process that is the vcg-tool.
184 */
185
186 int pid; /* Process Id of the vcg process */
187
188 #ifdef ANSI_C
call_vcg(void)189 void call_vcg(void)
190 #else
191 void call_vcg()
192 #endif
193 {
194 FILE *f;
195
196 pid = fork();
197 switch (pid) {
198 case -1: /* this is an error */
199 FPRINTF(stderr,"Cannot fork process vcg\n");
200 exit(-1);
201 /* NEVER REACHED */
202
203 case 0: /* this is the child process: call vcg */
204
205 { char toolname[1024];
206
207 strcpy(toolname,"../src/");
208 strcat(toolname,VCGTOOL);
209 if ((f = fopen(toolname,"r")) != NULL) {
210 fclose(f);
211 }
212 else if ((f = fopen(VCGCALL,"r")) != NULL) {
213 fclose(f);
214 strcpy(toolname,VCGCALL);
215 }
216 else strcpy(toolname,VCGTOOL);
217
218
219 PRINTF("Call %s timing: %s\n",toolname, timep);
220 execl(toolname,toolname,
221 "-silent",
222 "-a",timep,
223 #ifdef X11
224 "-geometry","200x200-30+30",
225 #endif
226 filename,0L);
227 }
228 /* NEVER REACHED */
229
230 default: /* this is the father process: */
231 /* pid is now the ID of the child process */
232 ;
233 }
234 }
235
236
237 /* Send a signal to the vcg-tool
238 * -----------------------------
239 */
240
241 char cmdline[1024]; /* Buffer for the kill-command */
242
243 #ifdef ANSI_C
signal_vcg(int k)244 void signal_vcg(int k)
245 #else
246 void signal_vcg(k)
247 int k;
248 #endif
249 {
250 SPRINTF(cmdline,"kill %d %d \n",k,pid);
251 system(cmdline);
252 }
253
254
255 /* Wait until a new time stamp
256 * ---------------------------
257 * The file containing the graph specification is touched after
258 * loading it. Thus we wait for a new time stamp of the file,
259 * that indicates that the loading is finished.
260 */
261
262 time_t file_touch_time1, file_touch_time2; /* time stamps */
263
264 #ifdef ANSI_C
wait_for_vcg(void)265 void wait_for_vcg(void)
266 #else
267 void wait_for_vcg()
268 #endif
269 {
270 int i;
271
272 i = 0;
273 /* Wait maximal 60 seconds */
274 while (i<60) {
275 file_touch_time2 = file_touch_time1;
276 get_time(filename);
277 sleep(1); /* 1 seconds */
278 if (file_touch_time1!=file_touch_time2) {
279 return;
280 }
281 i++;
282 }
283 FPRINTF(stderr,"Timeout\n");
284 exit(-1);
285 }
286
287
288 /* get the touch-time of a file named fn
289 * -------------------------------------
290 */
291
292 #ifdef ANSI_C
get_time(char * fn)293 void get_time(char *fn)
294 #else
295 void get_time(fn)
296 char *fn;
297 #endif
298 {
299 struct stat file_stat;
300
301 if (!stat(fn,&file_stat))
302 file_touch_time1 = file_stat.st_mtime;
303 else {
304 FPRINTF(stderr,"Cannot get time of %s\n", filename);
305 exit(-1);
306 }
307 }
308
309
310
311 /*--------------------------------------------------------------------*/
312 /* RED BLACK TREES */
313 /*--------------------------------------------------------------------*/
314
315 /* Colors for the red-black tree's */
316
317 #define RED 0
318 #define BLACK 1
319
320 /* Children */
321
322 #define LEFT 0
323 #define RIGHT 1
324
325 /* Type */
326
327 typedef struct rb_node {
328 int num;
329 int col;
330 int sons;
331 struct rb_node *son[2];
332 } *NODE;
333
334 /* Root of the tree */
335
336 NODE root = 0;
337
338 /* Prototypes for red-black-tree functions */
339 /*-----------------------------------------*/
340
341 NODE alloc_node _PP((int n));
342 void init_stack _PP((void));
343 int stack_empty _PP((void));
344 void push_stack _PP((NODE n, int d));
345 void pop_stack _PP((void));
346 NODE top_node _PP((void));
347 int top_dir _PP((void));
348 NODE search _PP((int x));
349 void rotation _PP((NODE p, NODE q, int dir));
350 void double_rotation _PP((NODE p, NODE q, NODE r, int dir1, int dir2));
351 void print_node _PP((FILE *f,NODE n,int i));
352
353
354 /* Create a rb_node
355 * ----------------
356 */
357
358 #ifdef ANSI_C
alloc_node(int n)359 NODE alloc_node(int n)
360 #else
361 NODE alloc_node(n)
362 int n;
363 #endif
364 {
365 NODE h;
366
367 h = (NODE)malloc(sizeof(struct rb_node));
368 if (!h) {
369 PRINTF("Fatal error: no memory\n");
370 exit(-1);
371 }
372 h->num = n;
373 h->col = BLACK;
374 h->sons = 0;
375 h->son[0] = 0;
376 h->son[1] = 0;
377 return(h);
378 }
379
380
381 /* The stack for the access
382 * ------------------------
383 */
384
385 NODE node_stack[100];
386 int dir_stack[100];
387 int top;
388
389
390 #ifdef ANSI_C
init_stack(void)391 void init_stack(void)
392 #else
393 void init_stack()
394 #endif
395 {
396 top = 0;
397 }
398
399
400 #ifdef ANSI_C
stack_empty(void)401 int stack_empty(void)
402 #else
403 int stack_empty()
404 #endif
405 {
406 return(top==0);
407 }
408
409
410 #ifdef ANSI_C
push_stack(NODE n,int d)411 void push_stack(NODE n, int d)
412 #else
413 void push_stack(n, d)
414 NODE n;
415 int d;
416 #endif
417 {
418 node_stack[top] = n;
419 dir_stack[top] = d;
420 top++;
421 if (top>=100) {
422 PRINTF("Fatal error: Stack exceeded\n");
423 exit(-1);
424 }
425 }
426
427
428 #ifdef ANSI_C
pop_stack(void)429 void pop_stack(void)
430 #else
431 void pop_stack()
432 #endif
433 {
434 top--;
435 if (top<0) top=0;
436 }
437
438
439
440 #ifdef ANSI_C
top_node(void)441 NODE top_node(void)
442 #else
443 NODE top_node()
444 #endif
445 {
446 if (top<=0) {
447 PRINTF("Fatal error: Stack empty\n");
448 exit(-1);
449 }
450 return(node_stack[top-1]);
451 }
452
453
454 #ifdef ANSI_C
top_dir(void)455 int top_dir(void)
456 #else
457 int top_dir()
458 #endif
459 {
460 if (top<=0) {
461 PRINTF("Fatal error: Stack empty\n");
462 exit(-1);
463 }
464 return(dir_stack[top-1]);
465 }
466
467
468 /*--------------------------------------------------------------------*/
469
470
471 /* Search function: push the acces path for x on the stack
472 * -------------------------------------------------------
473 * Return 0 if not found.
474 */
475
476 #ifdef ANSI_C
search(int x)477 NODE search(int x)
478 #else
479 NODE search(x)
480 int x;
481 #endif
482 {
483
484 NODE result;
485 NODE p;
486
487 result = 0;
488
489 init_stack();
490
491 p = root;
492 if (p) {
493 while (p->sons!=0) {
494 if (x==p->num) {
495 result = p;
496 push_stack(p, LEFT);
497 p = p->son[LEFT];
498 }
499 else if (x<p->num) {
500 push_stack(p, LEFT);
501 p = p->son[LEFT];
502 }
503 else {
504 push_stack(p, RIGHT);
505 p = p->son[RIGHT];
506 }
507 }
508 /* Finally: push the leaf */
509 push_stack(p,-1);
510 }
511 return(result);
512 }
513
514
515 /* Rotation
516 * --------
517 */
518
519 #ifdef ANSI_C
rotation(NODE p,NODE q,int dir)520 void rotation(NODE p, NODE q, int dir)
521 #else
522 void rotation(p, q, dir)
523 NODE p;
524 NODE q;
525 int dir;
526 #endif
527 {
528 p->son[dir] = q->son[1-dir];
529 q->son[1-dir] = p;
530 }
531
532
533 /* Double Rotation
534 * ---------------
535 */
536
537 #ifdef ANSI_C
double_rotation(NODE p,NODE q,NODE r,int dir1,int dir2)538 void double_rotation(NODE p, NODE q, NODE r, int dir1, int dir2)
539 #else
540 void double_rotation(p, q, r, dir1, dir2)
541 NODE p;
542 NODE q;
543 NODE r;
544 int dir1;
545 int dir2;
546 #endif
547 {
548 p->son[dir1] = r->son[dir2];
549 q->son[dir2] = r->son[dir1];
550 r->son[dir1] = q;
551 r->son[dir2] = p;
552 }
553
554
555
556
557 NODE newnode1 = 0;
558 NODE spec1 = 0;
559 NODE spec2 = 0;
560 NODE spec3 = 0;
561
562 #ifdef ANSI_C
free_spec(void)563 void free_spec(void)
564 #else
565 void free_spec()
566 #endif
567 {
568 newnode1 = 0;
569 spec1 = 0;
570 spec2 = 0;
571 spec3 = 0;
572 }
573
574
575 /* Insert function: insert x into the RB-tree
576 * ---------------
577 */
578
579 #ifdef ANSI_C
insert(int x)580 void insert(int x)
581 #else
582 void insert(x)
583 int x;
584 #endif
585 {
586
587 NODE p, q, r;
588 int dir1, dir2;
589
590 q = alloc_node(x);
591 newnode1 = q;
592
593 if (!root) {
594 root = q;
595 return;
596 }
597
598 r = search(x);
599 if (r) return;
600
601 r = alloc_node(x);
602 r->col = RED;
603
604 p = top_node();
605 pop_stack();
606
607 if (x<p->num) {
608 r->num = x;
609 r->son[LEFT] = q;
610 r->son[RIGHT] = p;
611 r->sons = 2;
612 }
613 else {
614 r->num = p->num;
615 r->son[LEFT] = p;
616 r->son[RIGHT] = q;
617 r->sons = 2;
618 }
619
620 if (stack_empty()) {
621 r->col = BLACK;
622 root = r;
623 return;
624 }
625
626 q = top_node();
627 dir2 = top_dir();
628 pop_stack();
629 q->son[dir2] = r;
630 if (q->col==BLACK) return;
631
632 /* Since the root is never red, (it has no incoming edge,
633 * thus we use the convention that it is black) we have
634 * one more on stack
635 */
636
637 while (1) {
638 p = top_node();
639 dir1 = top_dir();
640 pop_stack();
641
642 if ((p->son[1-dir1])->col==RED) {
643
644 /* p has two red sons: change color */
645
646 p->son[LEFT]->col =BLACK;
647 p->son[RIGHT]->col=BLACK;
648 p->col=RED;
649 if (p==root) {
650 p->col=BLACK;
651 return;
652 }
653 r = p;
654
655 q = top_node();
656 dir2 = top_dir();
657 pop_stack();
658 if (q->col==BLACK) return;
659 }
660 else if (dir1 == dir2) {
661 spec1 = p;
662 spec2 = q;
663 spec3 = 0;
664 print_tree();
665 get_time(filename);
666 signal_vcg(- SIGUSR1);
667 wait_for_vcg();
668
669 rotation(p,q,dir1);
670 p->col = RED;
671 q->col = BLACK;
672 if (p==root) root = q;
673 else {
674 r = top_node();
675 dir2 = top_dir();
676 pop_stack();
677 r->son[dir2] = q;
678 }
679
680 print_tree();
681 get_time(filename);
682 signal_vcg(- SIGUSR1);
683 wait_for_vcg();
684 spec1 = spec2 = spec3 = 0;
685 newnode1 = 0;
686 return;
687 }
688 else {
689 spec1 = p;
690 spec2 = q;
691 spec3 = r;
692 print_tree();
693 get_time(filename);
694 signal_vcg(- SIGUSR1);
695 wait_for_vcg();
696
697 double_rotation(p,q,r,dir1,dir2);
698 p->col = RED;
699 r->col = BLACK;
700 if (p==root) root = r;
701 else {
702 p = top_node();
703 dir2 = top_dir();
704 pop_stack();
705 p->son[dir2] = r;
706 }
707
708 print_tree();
709 get_time(filename);
710 signal_vcg(- SIGUSR1);
711 wait_for_vcg();
712 spec1 = spec2 = spec3 = 0;
713 newnode1 = 0;
714 return;
715 }
716 }
717 }
718
719
720 /* Print tree into VCG file
721 * ------------------------
722 */
723
724
725 #ifdef ANSI_C
print_tree(void)726 void print_tree(void)
727 #else
728 void print_tree()
729 #endif
730 {
731 f = fopen(filename,"w");
732 if (!f) return;
733
734 FPRINTF(f,"graph: { title:\"test\"\n");
735 FPRINTF(f," x: 30 y: 30\n");
736 FPRINTF(f," width: 900 height: 800\n");
737 FPRINTF(f," layoutalgorithm: tree\n");
738 FPRINTF(f," color: aquamarine\n");
739 FPRINTF(f," infoname 1 : \"()\"\n");
740 FPRINTF(f," infoname 2 : \"()\"\n");
741 FPRINTF(f," classname 1 : \"()\"\n");
742
743 if (root) print_node(f,root,0);
744
745 FPRINTF(f,"}\n");
746
747 fsync(fileno(f));
748 fsync(fileno(f));
749 fsync(fileno(f));
750 if (f) fclose(f);
751 }
752
753
754
755 #ifdef ANSI_C
print_node(FILE * f,NODE n,int i)756 void print_node(FILE *f, NODE n, int i)
757 #else
758 void print_node(f, n, i)
759 FILE *f;
760 NODE n;
761 int i;
762 #endif
763 {
764 FPRINTF(f," node: { title: \"%d\" label: \"%d\" ",
765 n, n->num);
766 FPRINTF(f,"width: 34 ");
767 FPRINTF(f,"height: 34 ");
768
769 if (n==newnode1) {
770 FPRINTF(f,"color: white ");
771 FPRINTF(f,"textcolor: blue ");
772 FPRINTF(f,"bordercolor: blue ");
773 FPRINTF(f,"shape: triangle ");
774 }
775 else if ((n==spec1)||(n==spec2)||(n==spec3)) {
776 FPRINTF(f,"color: yellow ");
777 FPRINTF(f,"textcolor: blue ");
778 FPRINTF(f,"bordercolor: blue ");
779 FPRINTF(f,"shape: ellipse ");
780 }
781 else if (n->col==RED) {
782 FPRINTF(f,"color: red ");
783 FPRINTF(f,"textcolor: white ");
784 FPRINTF(f,"bordercolor: white ");
785 FPRINTF(f,"shape: rhomb ");
786 }
787 else {
788 FPRINTF(f,"color: black ");
789 FPRINTF(f,"textcolor: white ");
790 FPRINTF(f,"bordercolor: white ");
791 FPRINTF(f,"shape: box ");
792 }
793 FPRINTF(f,"horizontal_order: %d ", i);
794 FPRINTF(f,"}\n");
795
796 if (n->sons==2) {
797 print_node(f,n->son[0], 0);
798
799 FPRINTF(f," edge: { sourcename: \"%d\" ", n);
800 FPRINTF(f,"targetname: \"%d\" ", n->son[0]);
801 if ((n->son[0])->col == RED) {
802 FPRINTF(f,"color: red ");
803 FPRINTF(f,"linestyle: dotted ");
804 }
805 else { FPRINTF(f,"color: black ");
806 FPRINTF(f,"linestyle: solid ");
807 }
808 FPRINTF(f,"thickness: 5 }\n");
809
810 print_node(f,n->son[1], 1);
811
812 FPRINTF(f," edge: { sourcename: \"%d\" ", n);
813 FPRINTF(f,"targetname: \"%d\" ", n->son[1]);
814 if ((n->son[1])->col == RED) {
815 FPRINTF(f,"color: red ");
816 FPRINTF(f,"linestyle: dotted ");
817 }
818 else { FPRINTF(f,"color: black ");
819 FPRINTF(f,"linestyle: solid ");
820 }
821 FPRINTF(f,"thickness: 5 }\n");
822 }
823
824 }
825
826