![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to subs.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / tsort|
Return to subs.c CVS log | Up to [Research Unix] / researchv10no / cmd / tsort |
1.1 root 1: #include <stdio.h>
2: #include "ts.h"
3:
4: #define HSIZE 307
5: #define ALSIZE 2040
6:
7: static struct obj **objhash, *cobj = 0, *lastobj;
8: static struct ref **refhash;
9: static struct group **grouphash, *group0;
10: struct ref *undefrefs = 0, *defedrefs = 0;
11: struct group *cgroup = 0; /* current group */
12: struct obj *obj0 = 0; /* special null object */
13:
14: unsigned lasthash = 0, ngroup = 0, nrefc = 0;
15: int nextseq;
16:
17: char *malloc(), *strcpy();
18: extern char *progname;
19: extern int cyclep, verbose, verify;
20:
21: init(){
22: int i;
23:
24: objhash = (struct obj **) malloc(HSIZE*sizeof(struct obj *));
25: refhash = (struct ref **) malloc(HSIZE*sizeof(struct ref *));
26: grouphash = (struct group **) malloc(HSIZE*sizeof(struct group *));
27: if (!objhash || !refhash || !grouphash)
28: scream("initial mallocs fail\n","");
29: for (i = 0; i < HSIZE; i++)
30: { objhash[i] = 0; refhash[i] = 0; grouphash[i] = 0;}
31: cgroup = 0;
32: newgroup("");
33: group0 = cgroup;
34: newobj("",1);
35: obj0 = cobj;
36: }
37:
38: unsigned
39: hash(s)
40: unsigned char *s;
41: {
42: unsigned x = 0;
43: unsigned char c;
44:
45: while(c = *s++) x = (x<<1) + c;
46: return x % HSIZE;
47: }
48:
49: char *
50: newstruct(n)
51: unsigned n;
52: {
53: static char *next = 0, *last = 0;
54: char *s;
55:
56: if (next + n > last) {
57: next = malloc(ALSIZE);
58: if (!next) scream("malloc fails in newstruct\n","");
59: last = next + ALSIZE;
60: }
61: s = next;
62: next += n;
63: return s;
64: }
65:
66: char *
67: newstring(s)
68: char *s;
69: {
70: static char *next = 0, *last = 0;
71: char *s1;
72: unsigned n, strlen();
73:
74: n = strlen(s) + 1;
75: if (next + n > last) {
76: next = malloc(ALSIZE);
77: if (!next) scream("malloc fails in newstring\n","");
78: last = next + ALSIZE;
79: }
80: s1 = next;
81: next += n;
82: strcpy(s1,s);
83: return s1;
84: }
85:
86: newgroup(s)
87: char *s;
88: {
89: struct group *g, *gnext = 0, *gprev;
90:
91: cobj = 0;
92: gprev = (struct group *) &grouphash[hash(s)];
93: g = gprev->next;
94: for(;; gprev = g, g = g->next) {
95: if (!g) {
96: g = (struct group *)
97: newstruct(sizeof(struct group));
98: g->name = newstring(s);
99: g->next = 0;
100: g->gseq = ngroup++;
101: gprev->next = g;
102: break;
103: }
104: if (!strcmp(s,g->name)) break;
105: }
106: cgroup = g;
107: }
108:
109: struct ref *
110: lookup(s,add)
111: char *s;
112: int add;
113: {
114: struct ref *h, *hprev;
115:
116: hprev = (struct ref *) &refhash[lasthash = hash(s)];
117: h = hprev->next;
118: while(h) {
119: if (!strcmp(h->name,s)) return h;
120: hprev = h;
121: h = h->next;
122: }
123: if (add) {
124: h = (struct ref *) newstruct(sizeof(struct ref));
125: hprev->next = h;
126: h->next = 0;
127: h->name = cobj && !strcmp(cobj->name,s) ? cobj->name : newstring(s);
128: h->robj = 0;
129: }
130: return h;
131: }
132:
133: newobj(s,dup)
134: char *s;
135: int dup;
136: {
137: struct obj *h, *hnext = 0, *hprev, *o;
138: struct ref *r1;
139:
140: hprev = (struct obj *) &objhash[hash(s)];
141: h = hprev->next;
142: while(h) {
143: if (!strcmp(h->name,s) && h->ogroup == cgroup) {
144: if (dup || h == obj0) { cobj = h; return; }
145: if (verbose) {
146: fprintf(stderr, "duplicate %s", s);
147: if (*cgroup->name) fprintf(stderr, " in %s", cgroup->name);
148: fputs(" ignored\n", stderr);
149: }
150: cobj = 0;
151: return;
152: }
153: hprev = h;
154: h = h->next;
155: }
156: cobj = o = (struct obj *) newstruct(sizeof(struct obj));
157: hprev->next = o;
158: o->next = hnext;
159: r1 = lookup(s,0);
160: o->name = r1 ? r1->name : newstring(s);
161: o->ogroup = cgroup;
162: o->seq = o->iptr = o->jct = 0;
163: }
164:
165: defobjref(s,dup)
166: char *s;
167: int dup;
168: {
169: rdefobjref(lookup(s,1), s, dup);
170: }
171:
172: rdefobjref(r,s,dup)
173: struct ref *r;
174: char *s;
175: int dup;
176: {
177: struct obj *o;
178:
179: if (o = r->robj) {
180: newobj(s,dup);
181: if (!dup || o->ogroup != cgroup) dupmsg(0,r,s);
182: }
183: else {
184: r->robj = cobj = o = (struct obj *) newstruct(sizeof(struct obj));
185: o->next = objhash[lasthash];
186: objhash[lasthash] = o;
187: o->name = r->name;
188: o->ogroup = cgroup;
189: o->seq = o->iptr = o->jct = 0;
190: }
191: }
192:
193: dupmsg(oprt,r,s)
194: int oprt;
195: struct ref *r;
196: char *s;
197: {
198: struct obj *o = r->robj;
199: char *in;
200:
201: if (verbose && o != obj0) {
202: fprintf(stderr, "def of %s", s);
203: if (oprt && strcmp(s,cobj->name)) {
204: fprintf(stderr, " in %s", cobj->name);
205: in = "of";
206: }
207: else in = "in";
208: if (*cgroup->name) fprintf(stderr, " %s lib %s", in, cgroup->name);
209: else in = "of";
210: fprintf(stderr, " ignored; first defined in %s", o->name);
211: if (*(s = o->ogroup->name)) fprintf(stderr, " of lib %s", s);
212: putc('\n', stderr);
213: }
214: }
215:
216:
217: newref(s)
218: char *s;
219: { newrefr(lookup(s,1)); }
220:
221: newrefr(r)
222: struct ref *r;
223: {
224: struct refc rc;
225: struct obj *o1;
226: unsigned i;
227:
228: if (!cobj) return;
229: if (verify && r->robj && cobj != obj0) {
230: fputs(cobj->name, stderr);
231: if (cgroup != group0) fprintf(stderr, " of %s", cgroup->name);
232: fprintf(stderr, " needs %s\n", r->name);
233: }
234: rc.rcnext = cobj->iptr;
235: rc.rcref = r;
236: o1 = rc.rcref->robj;
237: if (o1 != cobj && o1 != obj0) { /* discard self references */
238: /* and refs to null object */
239: i = cobj->iptr = ++nrefc;
240: refstore(i, &rc);
241: }
242: }
243:
244: defref(s)
245: char *s;
246: { defrefr(lookup(s,1), s); }
247:
248: defrefr(r,s)
249: struct ref *r;
250: char *s;
251: {
252: if (!cobj) return;
253: if (r->robj) dupmsg(1,r,s);
254: else r->robj = cobj;
255: }
256:
257: struct obj *
258: ts0()
259: {
260: int i;
261: struct obj *firstobj, *o, *onext;
262: struct ref *r, *rnext;
263:
264: /* chain objects together */
265:
266: firstobj = 0;
267: for (i = 0; i < HSIZE; i++) {
268: for(o = objhash[i]; o; o = onext) {
269: onext = o->next;
270: o->next = firstobj;
271: firstobj = o;
272: }
273: }
274:
275: /* chain undefined refs together */
276:
277: defedrefs = undefrefs = 0;
278: for (i = 0; i < HSIZE; i++) {
279: for (r = refhash[i]; r; r = rnext) {
280: rnext = r->next;
281: if (!r->robj) { r->next = undefrefs; undefrefs = r; }
282: else { r->next = defedrefs; defedrefs = r; }
283: }
284: }
285:
286: free((char *) grouphash);
287: free((char *) refhash);
288: free((char *) objhash);
289: return firstobj;
290: }
291:
292: struct obj *
293: ts(all)
294: {
295: int i, i0, k;
296: unsigned j;
297: struct obj *firstobj, *o, *o1, *onext, *oprev, **ready, **rs;
298: struct refc rc;
299:
300: firstobj = ts0();
301:
302: /* do depth-first search (to break cycles) */
303:
304: nextseq = 1;
305: for (o = firstobj; o; o = o->next)
306: if (!o->seq && (all || o->ogroup == group0)) dfs(1,o);
307:
308: /* discard unreached objects */
309:
310: if (!all) {
311: oprev = (struct obj *) &firstobj;
312: for (o = firstobj; o; o = o->next)
313: if (o->seq) { oprev->next = o; oprev = o; }
314: oprev->next = 0;
315: }
316:
317: /* set up for funny breadth-first search */
318:
319: ready = (struct obj **) malloc(ngroup * sizeof(struct obj *));
320: if (!ready) scream("malloc of ready list fails\n","");
321:
322: obj0->jct = 0; /* force initial inclusion of obj0 */
323: for (i = 0; i < ngroup; i++) ready[i] = 0;
324: for (o = firstobj; o; o = onext) {
325: onext = o->next;
326: if (!o->jct) {
327: rs = ready + o->ogroup->gseq;
328: o->next = *rs;
329: *rs = o;
330: }
331: }
332: firstobj = lastobj = 0;
333: i = i0 = 0;
334: for(;;) {
335: if (!(o = ready[i])) {
336: i = i0;
337: while(!(o = ready[i]))
338: if (++i >= ngroup) {
339: if (lastobj) lastobj->next = 0;
340: return firstobj;
341: }
342: i0 = i;
343: }
344: ready[i] = o->next;
345: if (!lastobj) firstobj = o;
346: else lastobj->next = o;
347: lastobj = o;
348: for (j = o->iptr; j; ) {
349: reffetch(j, &rc);
350: j = rc.rcnext;
351: if (j >= nrefc) { j -= nrefc; continue; }
352: o1 = rc.rcref->robj;
353: if (!o1) continue;
354: if (!--o1->jct) {
355: k = o1->ogroup->gseq;
356: o1->next = ready[k];
357: ready[k] = o1;
358: if (i0 > k) i0 = k;
359: }
360: }
361: }
362: }
363:
364: dfs(level, o)
365: int level;
366: struct obj *o;
367: {
368: struct refc rc;
369: struct obj *o1;
370: int level0, s;
371: static int cycle = 0;
372: unsigned i, nextrc;
373:
374: o->seq = -level;
375: level0 = -(level + 1);
376: for (i = o->iptr; i; i = nextrc) {
377: reffetch(i, &rc);
378: nextrc = rc.rcnext;
379: o1 = rc.rcref->robj;
380: if (!o1 || o == o1 || o1 == obj0) continue;
381: s = o1->seq;
382: if (s >= 0) {
383: o1->jct++;
384: if (s > 0) continue; /* cross link */
385: s = dfs(level+1, o1);
386: }
387: else { /* back link */
388: if (cyclep && !cycle) {
389: fprintf(stderr, "%s: cycle...\n", progname);
390: cycle = 1;
391: }
392: rc.rcnext += nrefc;
393: refstore(i, &rc);
394: }
395: if (level0 < s) level0 = s;
396: }
397: o->seq = nextseq;
398: level = -level;
399: if (level <= level0 && cyclep) {
400: fprintf(stderr, "%s\n", o->name);
401: if (level == level0) { cycle = 0; putc('\n',stderr); }
402: else cycle = 1;
403: }
404: if (level > level0 || level == -1) { nextseq++; level0 = level; }
405: return level0;
406: }
407:
408: scream(s, s1)
409: char *s, *s1;
410: {
411: fprintf(stderr, "%s: ", progname);
412: fprintf(stderr, s, s1);
413: exit(1);
414: }
415:
416: undef(s,infile)
417: char *s;
418: FILE *infile;
419: {
420: newgroup("");
421: newobj("", 1);
422: newref(s);
423: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.