X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/a68924a6e07d69bc4b8d6106b3af0ac5a7490905..0d57d6f5b835a23d0e3a1a0ac933b74d10474bec:/usr/src/cmd/tsort.c

diff --git a/usr/src/cmd/tsort.c b/usr/src/cmd/tsort.c
index 39b06e0d02..d876a5e66f 100644
--- 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
-*/
+ *	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;
-	enum {DEAD, LIVE, ONCE, TWICE} live;
+	int live;
 } firstnode = {NULL, NULL, NULL, DEAD};
 
 /*	a predecessor list tells all the immediate
@@ -162,35 +165,41 @@ struct nodelist *
 findloop()
 {
 	register struct nodelist *i, *j;
-	register struct predlist *p;
 	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)
-		if(j->live!=DEAD)
+		if(j->live==VISITED)
 			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);
+}