/* SCCS-info %W% %E% */ /*--------------------------------------------------------------------*/ /* */ /* VCG : Visualization of Compiler Graphs */ /* -------------------------------------- */ /* */ /* file: animation3.c */ /* version: 1.00.00 */ /* creation: 12.11.93 */ /* author: G. Sander (Version 1.00.00-...) */ /* Universitaet des Saarlandes, 66041 Saarbruecken */ /* ESPRIT Project #5399 Compare */ /* description: Animation demo 3 for VCG */ /* status: in work */ /* */ /*--------------------------------------------------------------------*/ /* $Id: animation3.c,v 1.2 1995/02/08 18:43:55 sander Exp $ */ /* * Copyright (C) 1993-2005 Saarland University * * This program and documentation is free software; you can redistribute * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * The software is available per anonymous ftp at ftp.cs.uni-sb.de. * Contact sander@cs.uni-sb.de for additional information. */ /* $Log: animation3.c,v $ * Revision 1.2 1995/02/08 18:43:55 sander * time renamed into timep for compatibility. * * Revision 1.1 1995/02/08 11:21:41 sander * Initial revision * */ /*--------------------------------------------------------------------* * This is a small example how to program a animation. The protocol * used here is the following: * * The client (this program) sends signals to the server (VCG) when * the server should display the graph. * The server touches the file, if it is ready with displaying, * thus the client waits for a change of the time stamp of the * file. * * In this example, we insert numbers into a red-black-tree. The * steps to rebalance the tree are visualized. *--------------------------------------------------------------------*/ #include #include #include #include #include #include #include "../src/globals.h" /* Prototypes * ---------- */ void main _PP((int argc, char *argv[])); void call_vcg _PP((void)); void signal_vcg _PP((int k)); void wait_for_vcg _PP((void)); void get_time _PP((char *fn)); void insert _PP((int x)); void print_tree _PP((void)); void free_spec _PP((void)); /* This must be an absolute path to the vcg-tool ! * No ~, .. or similar trash allowed. */ #ifndef VCGCALL #define VCGCALL "/RW/users/sander/pub/bin/xvcg" #endif #ifndef VCGTOOL #define VCGTOOL "vcg" #endif /* Global Variables * ---------------- */ FILE *f = NULL; char filename[] = "rbtree.vcg"; /*--------------------------------------------------------------------*/ /* Main Routine * ------------ * The main program consists of a small sequence of pictures. * Each picture is generated by create_graph and reloaded into * the vcg by signal_vcg. The calls of get_time and wait_for_vcg * are used for time synchronisation. */ /* These are the numbers to be inserted into the rb-tree */ int ins[15] = { 2, 8, 15, 17, 1, 18, 4, 20, 13, 11, 6, 10, 12, 14, 9 }; char timep[20] = "1"; #ifdef ANSI_C void main(int argc, char *argv[]) #else void main(argc, argv) int argc; char *argv[]; #endif { int i; if (argc==2) { strcpy(timep,argv[1]); } free_spec(); insert(3); insert(5); insert(7); print_tree(); get_time(filename); call_vcg(); wait_for_vcg(); sleep(5); /* time to open the window */ for (i=0; i<15; i++) { insert(ins[i]); print_tree(); get_time(filename); signal_vcg(- SIGUSR1); wait_for_vcg(); } free_spec(); print_tree(); get_time(filename); signal_vcg(- SIGUSR1); wait_for_vcg(); signal_vcg(- SIGUSR2); /* close vcg (does not work with X11) */ sleep(3); signal_vcg(- SIGQUIT); /* exit vcg */ } /*--------------------------------------------------------------------*/ /* Communication with vcg */ /*--------------------------------------------------------------------*/ /* Call the vcg-tool * ----------------- * Calling means fork a child process that is the vcg-tool. */ int pid; /* Process Id of the vcg process */ #ifdef ANSI_C void call_vcg(void) #else void call_vcg() #endif { FILE *f; pid = fork(); switch (pid) { case -1: /* this is an error */ FPRINTF(stderr,"Cannot fork process vcg\n"); exit(-1); /* NEVER REACHED */ case 0: /* this is the child process: call vcg */ { char toolname[1024]; strcpy(toolname,"../src/"); strcat(toolname,VCGTOOL); if ((f = fopen(toolname,"r")) != NULL) { fclose(f); } else if ((f = fopen(VCGCALL,"r")) != NULL) { fclose(f); strcpy(toolname,VCGCALL); } else strcpy(toolname,VCGTOOL); PRINTF("Call %s timing: %s\n",toolname, timep); execl(toolname,toolname, "-silent", "-a",timep, #ifdef X11 "-geometry","200x200-30+30", #endif filename,0L); } /* NEVER REACHED */ default: /* this is the father process: */ /* pid is now the ID of the child process */ ; } } /* Send a signal to the vcg-tool * ----------------------------- */ char cmdline[1024]; /* Buffer for the kill-command */ #ifdef ANSI_C void signal_vcg(int k) #else void signal_vcg(k) int k; #endif { SPRINTF(cmdline,"kill %d %d \n",k,pid); system(cmdline); } /* Wait until a new time stamp * --------------------------- * The file containing the graph specification is touched after * loading it. Thus we wait for a new time stamp of the file, * that indicates that the loading is finished. */ time_t file_touch_time1, file_touch_time2; /* time stamps */ #ifdef ANSI_C void wait_for_vcg(void) #else void wait_for_vcg() #endif { int i; i = 0; /* Wait maximal 60 seconds */ while (i<60) { file_touch_time2 = file_touch_time1; get_time(filename); sleep(1); /* 1 seconds */ if (file_touch_time1!=file_touch_time2) { return; } i++; } FPRINTF(stderr,"Timeout\n"); exit(-1); } /* get the touch-time of a file named fn * ------------------------------------- */ #ifdef ANSI_C void get_time(char *fn) #else void get_time(fn) char *fn; #endif { struct stat file_stat; if (!stat(fn,&file_stat)) file_touch_time1 = file_stat.st_mtime; else { FPRINTF(stderr,"Cannot get time of %s\n", filename); exit(-1); } } /*--------------------------------------------------------------------*/ /* RED BLACK TREES */ /*--------------------------------------------------------------------*/ /* Colors for the red-black tree's */ #define RED 0 #define BLACK 1 /* Children */ #define LEFT 0 #define RIGHT 1 /* Type */ typedef struct rb_node { int num; int col; int sons; struct rb_node *son[2]; } *NODE; /* Root of the tree */ NODE root = 0; /* Prototypes for red-black-tree functions */ /*-----------------------------------------*/ NODE alloc_node _PP((int n)); void init_stack _PP((void)); int stack_empty _PP((void)); void push_stack _PP((NODE n, int d)); void pop_stack _PP((void)); NODE top_node _PP((void)); int top_dir _PP((void)); NODE search _PP((int x)); void rotation _PP((NODE p, NODE q, int dir)); void double_rotation _PP((NODE p, NODE q, NODE r, int dir1, int dir2)); void print_node _PP((FILE *f,NODE n,int i)); /* Create a rb_node * ---------------- */ #ifdef ANSI_C NODE alloc_node(int n) #else NODE alloc_node(n) int n; #endif { NODE h; h = (NODE)malloc(sizeof(struct rb_node)); if (!h) { PRINTF("Fatal error: no memory\n"); exit(-1); } h->num = n; h->col = BLACK; h->sons = 0; h->son[0] = 0; h->son[1] = 0; return(h); } /* The stack for the access * ------------------------ */ NODE node_stack[100]; int dir_stack[100]; int top; #ifdef ANSI_C void init_stack(void) #else void init_stack() #endif { top = 0; } #ifdef ANSI_C int stack_empty(void) #else int stack_empty() #endif { return(top==0); } #ifdef ANSI_C void push_stack(NODE n, int d) #else void push_stack(n, d) NODE n; int d; #endif { node_stack[top] = n; dir_stack[top] = d; top++; if (top>=100) { PRINTF("Fatal error: Stack exceeded\n"); exit(-1); } } #ifdef ANSI_C void pop_stack(void) #else void pop_stack() #endif { top--; if (top<0) top=0; } #ifdef ANSI_C NODE top_node(void) #else NODE top_node() #endif { if (top<=0) { PRINTF("Fatal error: Stack empty\n"); exit(-1); } return(node_stack[top-1]); } #ifdef ANSI_C int top_dir(void) #else int top_dir() #endif { if (top<=0) { PRINTF("Fatal error: Stack empty\n"); exit(-1); } return(dir_stack[top-1]); } /*--------------------------------------------------------------------*/ /* Search function: push the acces path for x on the stack * ------------------------------------------------------- * Return 0 if not found. */ #ifdef ANSI_C NODE search(int x) #else NODE search(x) int x; #endif { NODE result; NODE p; result = 0; init_stack(); p = root; if (p) { while (p->sons!=0) { if (x==p->num) { result = p; push_stack(p, LEFT); p = p->son[LEFT]; } else if (xnum) { push_stack(p, LEFT); p = p->son[LEFT]; } else { push_stack(p, RIGHT); p = p->son[RIGHT]; } } /* Finally: push the leaf */ push_stack(p,-1); } return(result); } /* Rotation * -------- */ #ifdef ANSI_C void rotation(NODE p, NODE q, int dir) #else void rotation(p, q, dir) NODE p; NODE q; int dir; #endif { p->son[dir] = q->son[1-dir]; q->son[1-dir] = p; } /* Double Rotation * --------------- */ #ifdef ANSI_C void double_rotation(NODE p, NODE q, NODE r, int dir1, int dir2) #else void double_rotation(p, q, r, dir1, dir2) NODE p; NODE q; NODE r; int dir1; int dir2; #endif { p->son[dir1] = r->son[dir2]; q->son[dir2] = r->son[dir1]; r->son[dir1] = q; r->son[dir2] = p; } NODE newnode1 = 0; NODE spec1 = 0; NODE spec2 = 0; NODE spec3 = 0; #ifdef ANSI_C void free_spec(void) #else void free_spec() #endif { newnode1 = 0; spec1 = 0; spec2 = 0; spec3 = 0; } /* Insert function: insert x into the RB-tree * --------------- */ #ifdef ANSI_C void insert(int x) #else void insert(x) int x; #endif { NODE p, q, r; int dir1, dir2; q = alloc_node(x); newnode1 = q; if (!root) { root = q; return; } r = search(x); if (r) return; r = alloc_node(x); r->col = RED; p = top_node(); pop_stack(); if (xnum) { r->num = x; r->son[LEFT] = q; r->son[RIGHT] = p; r->sons = 2; } else { r->num = p->num; r->son[LEFT] = p; r->son[RIGHT] = q; r->sons = 2; } if (stack_empty()) { r->col = BLACK; root = r; return; } q = top_node(); dir2 = top_dir(); pop_stack(); q->son[dir2] = r; if (q->col==BLACK) return; /* Since the root is never red, (it has no incoming edge, * thus we use the convention that it is black) we have * one more on stack */ while (1) { p = top_node(); dir1 = top_dir(); pop_stack(); if ((p->son[1-dir1])->col==RED) { /* p has two red sons: change color */ p->son[LEFT]->col =BLACK; p->son[RIGHT]->col=BLACK; p->col=RED; if (p==root) { p->col=BLACK; return; } r = p; q = top_node(); dir2 = top_dir(); pop_stack(); if (q->col==BLACK) return; } else if (dir1 == dir2) { spec1 = p; spec2 = q; spec3 = 0; print_tree(); get_time(filename); signal_vcg(- SIGUSR1); wait_for_vcg(); rotation(p,q,dir1); p->col = RED; q->col = BLACK; if (p==root) root = q; else { r = top_node(); dir2 = top_dir(); pop_stack(); r->son[dir2] = q; } print_tree(); get_time(filename); signal_vcg(- SIGUSR1); wait_for_vcg(); spec1 = spec2 = spec3 = 0; newnode1 = 0; return; } else { spec1 = p; spec2 = q; spec3 = r; print_tree(); get_time(filename); signal_vcg(- SIGUSR1); wait_for_vcg(); double_rotation(p,q,r,dir1,dir2); p->col = RED; r->col = BLACK; if (p==root) root = r; else { p = top_node(); dir2 = top_dir(); pop_stack(); p->son[dir2] = r; } print_tree(); get_time(filename); signal_vcg(- SIGUSR1); wait_for_vcg(); spec1 = spec2 = spec3 = 0; newnode1 = 0; return; } } } /* Print tree into VCG file * ------------------------ */ #ifdef ANSI_C void print_tree(void) #else void print_tree() #endif { f = fopen(filename,"w"); if (!f) return; FPRINTF(f,"graph: { title:\"test\"\n"); FPRINTF(f," x: 30 y: 30\n"); FPRINTF(f," width: 900 height: 800\n"); FPRINTF(f," layoutalgorithm: tree\n"); FPRINTF(f," color: aquamarine\n"); FPRINTF(f," infoname 1 : \"()\"\n"); FPRINTF(f," infoname 2 : \"()\"\n"); FPRINTF(f," classname 1 : \"()\"\n"); if (root) print_node(f,root,0); FPRINTF(f,"}\n"); fsync(fileno(f)); fsync(fileno(f)); fsync(fileno(f)); if (f) fclose(f); } #ifdef ANSI_C void print_node(FILE *f, NODE n, int i) #else void print_node(f, n, i) FILE *f; NODE n; int i; #endif { FPRINTF(f," node: { title: \"%d\" label: \"%d\" ", n, n->num); FPRINTF(f,"width: 34 "); FPRINTF(f,"height: 34 "); if (n==newnode1) { FPRINTF(f,"color: white "); FPRINTF(f,"textcolor: blue "); FPRINTF(f,"bordercolor: blue "); FPRINTF(f,"shape: triangle "); } else if ((n==spec1)||(n==spec2)||(n==spec3)) { FPRINTF(f,"color: yellow "); FPRINTF(f,"textcolor: blue "); FPRINTF(f,"bordercolor: blue "); FPRINTF(f,"shape: ellipse "); } else if (n->col==RED) { FPRINTF(f,"color: red "); FPRINTF(f,"textcolor: white "); FPRINTF(f,"bordercolor: white "); FPRINTF(f,"shape: rhomb "); } else { FPRINTF(f,"color: black "); FPRINTF(f,"textcolor: white "); FPRINTF(f,"bordercolor: white "); FPRINTF(f,"shape: box "); } FPRINTF(f,"horizontal_order: %d ", i); FPRINTF(f,"}\n"); if (n->sons==2) { print_node(f,n->son[0], 0); FPRINTF(f," edge: { sourcename: \"%d\" ", n); FPRINTF(f,"targetname: \"%d\" ", n->son[0]); if ((n->son[0])->col == RED) { FPRINTF(f,"color: red "); FPRINTF(f,"linestyle: dotted "); } else { FPRINTF(f,"color: black "); FPRINTF(f,"linestyle: solid "); } FPRINTF(f,"thickness: 5 }\n"); print_node(f,n->son[1], 1); FPRINTF(f," edge: { sourcename: \"%d\" ", n); FPRINTF(f,"targetname: \"%d\" ", n->son[1]); if ((n->son[1])->col == RED) { FPRINTF(f,"color: red "); FPRINTF(f,"linestyle: dotted "); } else { FPRINTF(f,"color: black "); FPRINTF(f,"linestyle: solid "); } FPRINTF(f,"thickness: 5 }\n"); } }