# 2.11BSD#431 - /usr/src/usr.bin/tsort.c

##### Functions

    anypred           X
    cmp               X
    error             X
    findloop          X
    index             X
    main              X
    mark              X
    note              X
    present           X

##### Variables

    empty             X
    firstnode         X

##### Macros

    DEAD              X
    LIVE              X
    VISITED           X

##### struct's

    nodelist          X
    predlist          X

       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: /*	a predecessor list tells all the immediate
      19:  *	predecessors of a given node
      20: */
      21: struct predlist {
      22:     struct predlist *nextpred;
      23:     struct nodelist *pred;
      24: };
      25:
      26: struct nodelist {
      27:     struct nodelist *nextnode;
      28:     struct predlist *inedges;
      29:     char *name;
      30:     int live;
      31: } firstnode = {NULL, NULL, NULL, DEAD};
      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: }

#### Defined functions

anypred defined in line 102; used 1 times

- in line 75

cmp defined in line 137; used 1 times

- in line 121

error defined in line 149; used 4 times

- in line 53, 60, 127, 175

findloop defined in line 165; used 2 times

- in line 34, 82

index defined in line 114; used 5 times

- in line 33, 61-62(2)
- in /usr/src/usr.bin/file.c line 450-452(2)

main defined in line 42; never used
mark defined in line 187; used 3 times

- in line 35, 173, 199

note defined in line 156; used 3 times

- in line 152, 172, 201

present defined in line 90; used 1 times

- in line 63

#### Defined variables

empty defined in line 37; used 5 times

- in line 60, 127, 172-175(2), 201

firstnode defined in line 31; used 4 times

- in line 72, 120, 169, 176

sccsid defined in line 1; never used

#### Defined struct's

nodelist defined in line 26; used 33 times

- in line 23-27(3), 33-35(6), 47(2), 91(2), 103(2), 114-118(4), 125(4), 165-168(4), 187-191(6)

predlist defined in line 21; used 16 times

- in line 22(2), 28(2), 45(2), 65(4), 93(2), 105(2), 192(2)

#### Defined macros

DEAD defined in line 14; used 4 times

- in line 31, 84, 132, 193

LIVE defined in line 15; used 5 times

- in line 73, 107, 129, 170, 178

VISITED defined in line 16; used 3 times

- in line 177, 195-197(2)

Last modified: 1987-03-11 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1218 |