1 #include "main.h"
2
3 #define CALL_GRAPH_FILE "call.grp"
4 #define RECURSIVE_PROC_FILE "recur.prc"
5
6 class proc_desc;
7
8 class call_spec {
9 public:
10 call_spec* next;
11 proc_desc* callee;
12
call_spec(proc_desc * desc,call_spec * chain)13 call_spec(proc_desc* desc, call_spec* chain)
14 { next = chain; callee = desc; }
15 };
16
17 #define HASH_TABLE_SIZE 1987
18
19 class proc_desc {
20 protected:
21 proc_desc* next; // collision chain
22 static proc_desc* table[ HASH_TABLE_SIZE ];
23
24 public:
25 call_spec* chain;
26 char* name;
27
28 enum { called=1, recursive=2 };
29 int tag;
30
call(proc_desc * callee)31 void call(proc_desc* callee) { chain = new call_spec(callee, chain); }
32 void closure();
33
34 static proc_desc* add(char* proc_name);
35 static void analyse();
36 static void output(FILE* f);
37
proc_desc(char * proc_name)38 proc_desc(char* proc_name)
39 : chain(NULL), name(strdup(proc_name)), tag(0) {}
40 };
41
42 proc_desc* proc_desc::table[HASH_TABLE_SIZE];
43
add(char * name)44 proc_desc* proc_desc::add(char* name)
45 {
46 proc_desc* p;
47 unsigned h = 0;
48 unsigned c;
49 char* s = name;
50
51 while ((c = (unsigned)*s++) != 0) {
52 h = (h<<1) + c;
53 }
54
55 int hash_value = h % HASH_TABLE_SIZE;
56 for (p = table[hash_value]; p != NULL; p = p->next) {
57 if (strcmp(name, p->name) == 0) return p;
58 }
59 p = new proc_desc(name);
60 p->next = table[hash_value];
61 table[hash_value] = p;
62 return p;
63 }
64
analyse()65 void proc_desc::analyse() {
66 for (int i = 0; i < HASH_TABLE_SIZE; i++ ) {
67 for (proc_desc* p = table[i]; p != NULL; p = p->next) {
68 p->closure();
69 }
70 }
71 }
72
output(FILE * f)73 void proc_desc::output(FILE* f) {
74 for (int i = 0; i < HASH_TABLE_SIZE; i++ ) {
75 for (proc_desc* p = table[i]; p != NULL; p = p->next) {
76 if (p->tag & recursive) {
77 fprintf(f,"%s\n", p->name);
78 }
79 }
80 }
81 }
82
closure()83 void proc_desc::closure() {
84 if (tag & called) {
85 tag |= recursive;
86 } else {
87 tag |= called;
88 for (call_spec* c = chain; c != NULL; c = c->next) {
89 c->callee->closure();
90 }
91 tag &= ~called;
92 }
93 }
94
95
main()96 int main() {
97 FILE* in = fopen(CALL_GRAPH_FILE, "r");
98 FILE* out = fopen(RECURSIVE_PROC_FILE, "w");
99
100 if (in == NULL || out == NULL) {
101 fputs("Error while opening files...\n", stderr);
102 return 1;
103 }
104 char callee[256];
105 char caller[256];
106 while (fscanf(in, "%s -> %s", caller, callee) == 2) {
107 proc_desc::add(caller)->call(proc_desc::add(callee));
108 }
109 proc_desc::analyse();
110 proc_desc::output(out);
111
112 fclose(in);
113 fclose(out);
114 return 0;
115 }
116
117
118
119
120