![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cflow|
Return to dag.c CVS log | Up to [Research Unix] / researchv10no / cmd / cflow |
1.1 root 1: /* @(#)dag.c 1.4 */
2: #include "stdio.h"
3: #include "ctype.h"
4:
5: #define NLINK 8
6:
7: typedef struct node {
8: struct node *n_next;
9: struct node *n_left;
10: struct node *n_right;
11: char *n_name;
12: char *n_data;
13: int n_rcnt;
14: int n_visit;
15: int n_lcnt;
16: struct link *n_link;
17: } node;
18:
19: node *first = NULL;
20: node *last = NULL;
21: node *root = NULL;
22:
23: typedef struct link {
24: struct link *l_next;
25: struct node *l_node[NLINK];
26: } link;
27:
28: #define isnamec(c) (isalpha(c)||isdigit(c)||c=='_')
29: #define NUL '\0'
30: #define BIGINT 32767
31:
32: node *getnode();
33: char *copy();
34: int lines, nodes, links, chars;
35: int lineno = 0;
36: int lvmax = BIGINT;
37: char stdbuf[BUFSIZ];
38:
39: main(argc, argv)
40: char *argv[];
41: {
42: extern int optind;
43: extern char *optarg;
44: register node *np;
45: node *getnode();
46: int c;
47: void reader(), dfs();
48:
49: setbuf(stdout, stdbuf);
50: while ((c = getopt(argc, argv, "d:")) != EOF)
51: if (c == 'd')
52: {
53: if ((lvmax = getnum(optarg, 10)) == 0)
54: {
55: lvmax = BIGINT;
56: goto argerr;
57: }
58: }
59: else
60: argerr:
61: (void)fprintf(stderr, "dag: bad option %c ignored\n", c);
62: reader(stdin);
63: argc -= optind + 1;
64: if (argc <= 1)
65: for (np = first; np != NULL; np = np->n_next)
66: {
67: if (np->n_rcnt == 0)
68: dfs(np, 0);
69: }
70: else
71: while (--argc > 0)
72: dfs(getnode(*++argv), 0);
73: }
74:
75: getnum(p, base)
76: register int base;
77: register char *p;
78: {
79: register int n;
80:
81: n = 0;
82: while (isdigit(*p))
83: n = n * base + (*p++ - '0');
84: return(n);
85: }
86:
87: void reader(fp)
88: register FILE *fp;
89: {
90: register char *p1, *p2;
91: int c;
92: node *np, *getnode();
93: char line[BUFSIZ], *copy();
94:
95: while (getst(line, fp)) {
96: ++lines;
97: p1 = line;
98: while (isspace(*p1))
99: ++p1;
100: if (*p1 == NUL)
101: continue;
102: p2 = p1;
103: while (isnamec(*p2))
104: ++p2;
105: do {
106: c = *p2;
107: *p2++ = NUL;
108: } while (isspace(c));
109: switch (c) {
110:
111: case '=':
112: np = getnode(p1);
113: while (isspace(*p2))
114: ++p2;
115: if (np->n_data != NULL) {
116: (void)fprintf(stderr, "redefinition of %s\n", np->n_name);
117: (void)cfree(np->n_data);
118: }
119: np->n_data = copy(p2);
120: continue;
121: case ':':
122: np = getnode(p1);
123: while (*(p1 = p2) != NUL) {
124: while (isspace(*p1))
125: ++p1;
126: p2 = p1;
127: while (isnamec(*p2))
128: ++p2;
129: (void)addlink(np, getnode(p1));
130: if (*p2 != NUL)
131: *p2++ = NUL;
132: }
133: continue;
134: }
135: }
136: }
137:
138: getst(s, fp)
139: char *s;
140: FILE *fp;
141: {
142: register i, c;
143:
144: i = 0;
145: while ((c = getc(fp)) != EOF) {
146: if (c == '\n') {
147: *s = NUL;
148: return 1;
149: }
150: if (i++ < BUFSIZ)
151: *s++ = c;
152: }
153: return 0;
154: }
155:
156: char *
157: copy(s)
158: char *s;
159: {
160: char *p, *strcpy(), *calloc();
161: void exit();
162:
163: p = calloc(sizeof(char), (unsigned)(strlen(s)+2));
164: if (p == NULL) {
165: (void)fprintf(stderr, "too many characters\n");
166: exit(1);
167: }
168: (void)strcpy(p, s);
169: chars += strlen(p);
170: return p;
171: }
172:
173: node *
174: getnode(name)
175: char *name;
176: {
177: register i;
178: register node *np, **pp;
179: void exit();
180: char *copy(), *calloc();
181:
182: pp = &root;
183: while ((np = *pp) != NULL) {
184: i = strcmp(name, np->n_name);
185: if (i > 0)
186: pp = &np->n_right;
187: else if (i < 0)
188: pp = &np->n_left;
189: else
190: return np;
191: }
192: *pp = (node *)calloc(sizeof(node), 1);
193: if ((np = *pp) == NULL) {
194: (void)fprintf(stderr, "too many nodes");
195: exit(1);
196: }
197: ++nodes;
198: np->n_name = copy(name);
199: np->n_data = NULL;
200: if (first == NULL)
201: first = np;
202: if (last != NULL)
203: last->n_next = np;
204: last = np;
205: np->n_next = NULL;
206: np->n_left = np->n_right = NULL;
207: np->n_rcnt = np->n_lcnt = np->n_visit = 0;
208: np->n_link = NULL;
209: return np;
210: }
211:
212: addlink(np, rp)
213: node *np, *rp;
214: {
215: register i, j;
216: char *calloc();
217: link *lp, **pp;
218: void exit();
219:
220: i = j = 0;
221: pp = &np->n_link;
222: while ((lp = *pp) != NULL && i < np->n_lcnt) {
223: if (rp == lp->l_node[j])
224: return 0;
225: if (++j >= NLINK) {
226: j = 0;
227: pp = &lp->l_next;
228: }
229: ++i;
230: }
231: if (lp == NULL) {
232: *pp = (link *)calloc(sizeof(link), 1);
233: if ((lp = *pp) == NULL) {
234: (void)fprintf(stderr, "too many links\n");
235: exit(1);
236: }
237: ++links;
238: lp->l_next = NULL;
239: }
240: lp->l_node[j] = rp;
241: if (np != rp)
242: ++rp->n_rcnt;
243: ++np->n_lcnt;
244: return 1;
245: }
246:
247: void dfs(np, lv)
248: register
249: node *np;
250: {
251: register i, j;
252: link *lp;
253:
254: if (np == NULL || lv > lvmax)
255: return;
256: i = 0;
257: (void)printf("%d\t",++lineno);
258: while (i++ < lv)
259: (void)putchar('\t');
260: (void)printf("%s: ", np->n_name);
261: if (np->n_visit > 0) {
262: (void)printf("%d\n", np->n_visit);
263: return;
264: }
265: if (np->n_data != NULL)
266: (void)printf("%s\n", np->n_data);
267: else
268: (void)printf("<>\n");
269: np->n_visit = lineno;
270: i = j = 0;
271: lp = np->n_link;
272: while (i < np->n_lcnt && lp != NULL) {
273: dfs(lp->l_node[j], lv+1);
274: if (++j >= NLINK) {
275: j = 0;
276: lp = lp->l_next;
277: }
278: ++i;
279: }
280: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.