Bell 32V development

[unix-history] / usr / src / cmd / tsort.c

diff --git a/usr/src/cmd/tsort.c b/usr/src/cmd/tsort.c
index 39b06e0..d876a5e 100644 (file)
--- a/usr/src/cmd/tsort.c
+++ b/usr/src/cmd/tsort.c
@@ -9,13 +9,16 @@
 
 /*     the nodelist always has an empty element at the end to
  *     make it easy to grow in natural order
 
 /*     the nodelist always has an empty element at the end to
  *     make it easy to grow in natural order

-*/
+ *     states of the "live" field:*/
+#define DEAD 0 /* already printed*/
+#define LIVE 1 /* not yet printed*/
+#define VISITED 2      /*used only in findloop()*/

 
 struct nodelist {
        struct nodelist *nextnode;
        struct predlist *inedges;
        char *name;
 
 struct nodelist {
        struct nodelist *nextnode;
        struct predlist *inedges;
        char *name;

-       enum {DEAD, LIVE, ONCE, TWICE} live;
+       int live;

 } firstnode = {NULL, NULL, NULL, DEAD};
 
 /*     a predecessor list tells all the immediate
 } firstnode = {NULL, NULL, NULL, DEAD};
 
 /*     a predecessor list tells all the immediate


@@ -162,35 +165,41 @@ struct nodelist *
 findloop()
 {
        register struct nodelist *i, *j;
 findloop()
 {
        register struct nodelist *i, *j;

-       register struct predlist *p;

        for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
                if(i->live==LIVE)
                        break;
        for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
                if(i->live==LIVE)
                        break;

-       note("cycle in reverse order",empty);
-       while(i->live==LIVE) {
-               i->live = ONCE;
-               for(p=i->inedges; ; p=p->nextpred) {
-                       if(p==NULL)
-                               error("error 1");
-                       i = p->pred;
-                       if(i->live!=DEAD)
-                               break;
-               }
-       }
-       while(i->live==ONCE) {
-               i->live = TWICE;
-               note(i->name,empty);
-               for(p=i->inedges; ; p=p->nextpred) {
-                       if(p==NULL)
-                               error("error 2");
-                       i = p->pred;
-                       if(i->live!=DEAD)
-                               break;
-               }
-       }
+       note("cycle in data",empty);
+       i = mark(i);
+       if(i==NULL)
+               error("program error",empty);

        for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode)
        for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode)

-               if(j->live!=DEAD)
+               if(j->live==VISITED)

                        j->live = LIVE;
        return(i);
 }
 
                        j->live = LIVE;
        return(i);
 }
 

+/*     depth-first search of LIVE predecessors
+ *     to find some element of a cycle;
+ *     VISITED is a temporary state recording the
+ *     visits of the search
+*/
+struct nodelist *
+mark(i)
+register struct nodelist *i;
+{
+       register struct nodelist *j;
+       register struct predlist *t;
+       if(i->live==DEAD)
+               return(NULL);
+       if(i->live==VISITED)
+               return(i);
+       i->live = VISITED;
+       for(t=i->inedges; t!=NULL; t=t->nextpred) {
+               j = mark(t->pred);
+               if(j!=NULL) {
+                       note(i->name,empty);
+                       return(j);
+               }
+       }
+       return(NULL);
+}