![[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] / 42BSD / usr.bin|
Return to tsort.c CVS log | Up to [CSRG BSD Unix] / 42BSD / usr.bin |
1.1 ! root 1: static char *sccsid = "@(#)tsort.c 4.2 (Berkeley) 10/20/82"; ! 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: } ! 87: ! 88: /* is i present on j's predecessor list? ! 89: */ ! 90: present(i,j) ! 91: struct nodelist *i, *j; ! 92: { ! 93: register struct predlist *t; ! 94: for(t=j->inedges; t!=NULL; t=t->nextpred) ! 95: if(t->pred==i) ! 96: return(1); ! 97: return(0); ! 98: } ! 99: ! 100: /* is there any live predecessor for i? ! 101: */ ! 102: anypred(i) ! 103: struct nodelist *i; ! 104: { ! 105: register struct predlist *t; ! 106: for(t=i->inedges; t!=NULL; t=t->nextpred) ! 107: if(t->pred->live==LIVE) ! 108: return(1); ! 109: return(0); ! 110: } ! 111: ! 112: /* turn a string into a node pointer ! 113: */ ! 114: struct nodelist * ! 115: index(s) ! 116: register char *s; ! 117: { ! 118: register struct nodelist *i; ! 119: register char *t; ! 120: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) ! 121: if(cmp(s,i->name)) ! 122: return(i); ! 123: for(t=s; *t; t++) ; ! 124: t = malloc((unsigned)(t+1-s)); ! 125: i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist)); ! 126: if(i->nextnode==NULL||t==NULL) ! 127: error("too many items",empty); ! 128: i->name = t; ! 129: i->live = LIVE; ! 130: i->nextnode->nextnode = NULL; ! 131: i->nextnode->inedges = NULL; ! 132: i->nextnode->live = DEAD; ! 133: while(*t++ = *s++); ! 134: return(i); ! 135: } ! 136: ! 137: cmp(s,t) ! 138: register char *s, *t; ! 139: { ! 140: while(*s==*t) { ! 141: if(*s==0) ! 142: return(1); ! 143: s++; ! 144: t++; ! 145: } ! 146: return(0); ! 147: } ! 148: ! 149: error(s,t) ! 150: char *s, *t; ! 151: { ! 152: note(s,t); ! 153: exit(1); ! 154: } ! 155: ! 156: note(s,t) ! 157: char *s,*t; ! 158: { ! 159: fprintf(stderr,"tsort: %s%s\n",s,t); ! 160: } ! 161: ! 162: /* given that there is a cycle, find some ! 163: * node in it ! 164: */ ! 165: struct nodelist * ! 166: findloop() ! 167: { ! 168: register struct nodelist *i, *j; ! 169: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) ! 170: if(i->live==LIVE) ! 171: break; ! 172: note("cycle in data",empty); ! 173: i = mark(i); ! 174: if(i==NULL) ! 175: error("program error",empty); ! 176: for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode) ! 177: if(j->live==VISITED) ! 178: j->live = LIVE; ! 179: return(i); ! 180: } ! 181: ! 182: /* depth-first search of LIVE predecessors ! 183: * to find some element of a cycle; ! 184: * VISITED is a temporary state recording the ! 185: * visits of the search ! 186: */ ! 187: struct nodelist * ! 188: mark(i) ! 189: register struct nodelist *i; ! 190: { ! 191: register struct nodelist *j; ! 192: register struct predlist *t; ! 193: if(i->live==DEAD) ! 194: return(NULL); ! 195: if(i->live==VISITED) ! 196: return(i); ! 197: i->live = VISITED; ! 198: for(t=i->inedges; t!=NULL; t=t->nextpred) { ! 199: j = mark(t->pred); ! 200: if(j!=NULL) { ! 201: note(i->name,empty); ! 202: return(j); ! 203: } ! 204: } ! 205: return(NULL); ! 206: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.