![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tsort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin|
Return to tsort.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin |
1.1 ! root 1: static char *sccsid = "@(#)tsort.c 4.3 (Berkeley) 9/14/87"; ! 2: /* topological sort ! 3: * input is sequence of pairs of items (blank-free strings) ! 4: * nonidentical pair is a directed edge in graph ! 5: * identical pair merely indicates presence of node ! 6: * output is ordered list of items consistent with ! 7: * the partial ordering specified by the graph ! 8: */ ! 9: #include <stdio.h> ! 10: ! 11: /* the nodelist always has an empty element at the end to ! 12: * make it easy to grow in natural order ! 13: * states of the "live" field:*/ ! 14: #define DEAD 0 /* already printed*/ ! 15: #define LIVE 1 /* not yet printed*/ ! 16: #define VISITED 2 /*used only in findloop()*/ ! 17: ! 18: struct nodelist { ! 19: struct nodelist *nextnode; ! 20: struct predlist *inedges; ! 21: char *name; ! 22: int live; ! 23: } firstnode = {NULL, NULL, NULL, DEAD}; ! 24: ! 25: /* a predecessor list tells all the immediate ! 26: * predecessors of a given node ! 27: */ ! 28: struct predlist { ! 29: struct predlist *nextpred; ! 30: struct nodelist *pred; ! 31: }; ! 32: ! 33: struct nodelist *index(); ! 34: struct nodelist *findloop(); ! 35: struct nodelist *mark(); ! 36: char *malloc(); ! 37: char *empty = ""; ! 38: ! 39: /* the first for loop reads in the graph, ! 40: * the second prints out the ordering ! 41: */ ! 42: main(argc,argv) ! 43: char **argv; ! 44: { ! 45: register struct predlist *t; ! 46: FILE *input = stdin; ! 47: register struct nodelist *i, *j; ! 48: int x; ! 49: char precedes[50], follows[50]; ! 50: if(argc>1) { ! 51: input = fopen(argv[1],"r"); ! 52: if(input==NULL) ! 53: error("cannot open ", argv[1]); ! 54: } ! 55: for(;;) { ! 56: x = fscanf(input,"%s%s",precedes, follows); ! 57: if(x==EOF) ! 58: break; ! 59: if(x!=2) ! 60: error("odd data",empty); ! 61: i = index(precedes); ! 62: j = index(follows); ! 63: if(i==j||present(i,j)) ! 64: continue; ! 65: t = (struct predlist *)malloc(sizeof(struct predlist)); ! 66: t->nextpred = j->inedges; ! 67: t->pred = i; ! 68: j->inedges = t; ! 69: } ! 70: for(;;) { ! 71: x = 0; /*anything LIVE on this sweep?*/ ! 72: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) { ! 73: if(i->live==LIVE) { ! 74: x = 1; ! 75: if(!anypred(i)) ! 76: break; ! 77: } ! 78: } ! 79: if(x==0) ! 80: break; ! 81: if(i->nextnode==NULL) ! 82: i = findloop(); ! 83: printf("%s\n",i->name); ! 84: i->live = DEAD; ! 85: } ! 86: exit(0); ! 87: } ! 88: ! 89: /* is i present on j's predecessor list? ! 90: */ ! 91: present(i,j) ! 92: struct nodelist *i, *j; ! 93: { ! 94: register struct predlist *t; ! 95: for(t=j->inedges; t!=NULL; t=t->nextpred) ! 96: if(t->pred==i) ! 97: return(1); ! 98: return(0); ! 99: } ! 100: ! 101: /* is there any live predecessor for i? ! 102: */ ! 103: anypred(i) ! 104: struct nodelist *i; ! 105: { ! 106: register struct predlist *t; ! 107: for(t=i->inedges; t!=NULL; t=t->nextpred) ! 108: if(t->pred->live==LIVE) ! 109: return(1); ! 110: return(0); ! 111: } ! 112: ! 113: /* turn a string into a node pointer ! 114: */ ! 115: struct nodelist * ! 116: index(s) ! 117: register char *s; ! 118: { ! 119: register struct nodelist *i; ! 120: register char *t; ! 121: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) ! 122: if(cmp(s,i->name)) ! 123: return(i); ! 124: for(t=s; *t; t++) ; ! 125: t = malloc((unsigned)(t+1-s)); ! 126: i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist)); ! 127: if(i->nextnode==NULL||t==NULL) ! 128: error("too many items",empty); ! 129: i->name = t; ! 130: i->live = LIVE; ! 131: i->nextnode->nextnode = NULL; ! 132: i->nextnode->inedges = NULL; ! 133: i->nextnode->live = DEAD; ! 134: while(*t++ = *s++); ! 135: return(i); ! 136: } ! 137: ! 138: cmp(s,t) ! 139: register char *s, *t; ! 140: { ! 141: while(*s==*t) { ! 142: if(*s==0) ! 143: return(1); ! 144: s++; ! 145: t++; ! 146: } ! 147: return(0); ! 148: } ! 149: ! 150: error(s,t) ! 151: char *s, *t; ! 152: { ! 153: note(s,t); ! 154: exit(1); ! 155: } ! 156: ! 157: note(s,t) ! 158: char *s,*t; ! 159: { ! 160: fprintf(stderr,"tsort: %s%s\n",s,t); ! 161: } ! 162: ! 163: /* given that there is a cycle, find some ! 164: * node in it ! 165: */ ! 166: struct nodelist * ! 167: findloop() ! 168: { ! 169: register struct nodelist *i, *j; ! 170: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) ! 171: if(i->live==LIVE) ! 172: break; ! 173: note("cycle in data",empty); ! 174: i = mark(i); ! 175: if(i==NULL) ! 176: error("program error",empty); ! 177: for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode) ! 178: if(j->live==VISITED) ! 179: j->live = LIVE; ! 180: return(i); ! 181: } ! 182: ! 183: /* depth-first search of LIVE predecessors ! 184: * to find some element of a cycle; ! 185: * VISITED is a temporary state recording the ! 186: * visits of the search ! 187: */ ! 188: struct nodelist * ! 189: mark(i) ! 190: register struct nodelist *i; ! 191: { ! 192: register struct nodelist *j; ! 193: register struct predlist *t; ! 194: if(i->live==DEAD) ! 195: return(NULL); ! 196: if(i->live==VISITED) ! 197: return(i); ! 198: i->live = VISITED; ! 199: for(t=i->inedges; t!=NULL; t=t->nextpred) { ! 200: j = mark(t->pred); ! 201: if(j!=NULL) { ! 202: note(i->name,empty); ! 203: return(j); ! 204: } ! 205: } ! 206: return(NULL); ! 207: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.