walls@killer.UUCP (Monty Walls) (03/18/88)
--------------------------------------------------------------------------
Because of the test data I used when writing tsort I managed to
design the dump logic wrong. This is posting is a complete
replacement for my earlier version of tsort. A word of warning,
libc contains a cycle(signal.s & catchsig.s), so tsort will
complain about it. Also included is a fix for lorder - I reversed
the order of the names on the output lines.
-Monty Walls
---------------------------cut here---------------------------------------
echo x - lorder.diff
gres '^X' '' > lorder.diff << '/'
X20a21
X> * oops reversed output filename order. 3/14/88 - mrw
X176c177
X< fprintf(stdout,"%s %s\n",t->file, fp->name);
X---
X> fprintf(stdout,"%s %s\n",fp->name, t->file);
X
/
echo x - tsort.c
gres '^X' '' > tsort.c << '/'
X/*
X * tsort - do a topological sort on the ordered pairs of names
X *
X * syntax - tsort [ file ]
X *
X * based on the discussion in 'The AWK programming Language', by
X * Aho, Kernighan, & Weinberger.
X *
X * author: Monty Walls
X * written: 1/28/88
X * Copyright: Copyright (c) 1988 by Monty Walls.
X * Not derived from licensed software.
X *
X * Permission to copy and/or distribute granted under the
X * following conditions:
X *
X * 1). This notice must remain intact.
X * 2). The author is not responsible for the consequences of use
X * this software, no matter how awful, even if they
X * arise from defects in it.
X * 3). Altered version must not be represented as being the
X * original software.
X *
X * change log:
X * possible bug in ungetc(), fixed readone() to avoid - 2/19/88 - mrw
X * massive design error, rewrote dump logic - 3/15/88 - mrw
X */
X
X#include <stdio.h>
X#include <errno.h>
X#include <ctype.h>
X
X#define printmem(_s) (fprintf(stdout,"%s ",(_s)))
X#define MAXNAMELEN 32
X#define MAXMEMBERS 1024
X
Xstruct dependents {
X struct node *nd;
X struct dependents *next;
X};
X
Xstruct node {
X char *name;
X int pcnt, scnt, visited;
X struct dependents *succ, *pred;
X struct node *left, *right;
X};
X
Xchar *progname;
X
Xextern struct node *readnode(), *findnode();
Xextern char *malloc(), *xalloc(), *readone(), *strsave();
Xextern struct dependents *finddep();
Xextern void dumptree(), walktree(), emptytree(), addqueue(), walklist();
X
Xextern int errno;
Xextern char *sys_errlist[];
X
Xstruct node *tree, *lastnode, *q[MAXMEMBERS];
Xstruct dependents *lastdepd;
Xint node_cnt, rc, front, back;
X
Xmain(argc, argv)
Xint argc;
Xchar **argv;
X{
X progname = argv[0];
X if (argc > 1)
X if (freopen(argv[1], "r", stdin) == (FILE *)NULL) {
X fprintf(stderr,"Error: %s - %s\n",progname, sys_errlist[errno]);
X exit(1);
X }
X
X /* read in the tree of entries */
X while (readnode() != (struct node *)NULL)
X ;
X dumptree(tree);
X fflush(stdout);
X
X if (node_cnt != back) {
X fprintf(stderr,"Error: %s - input contains a cycle\n",progname);
X rc = 1;
X }
X
X exit(rc);
X}
X
X
Xstruct node *
Xreadnode()
X{
X char *s1, *s2;
X register struct node *n1, *n2;
X struct dependents *pd;
X
X if ((s1 = readone()) != (char *)NULL) {
X if ((n1 = findnode(s1)) == (struct node *)NULL) {
X /* is a new node so build it */
X n1 = (struct node *)xalloc(sizeof(struct node));
X n1->name = strsave(s1);
X n1->succ = (struct dependents *)NULL;
X n1->pred = (struct dependents *)NULL;
X n1->left = (struct node *)NULL;
X n1->right = (struct node *)NULL;
X n1->pcnt = 0;
X n1->scnt = 0;
X n1->visited = 0;
X linknode(n1);
X }
X if ((s2 = readone()) != (char *)NULL) {
X if ((n2 = findnode(s2)) == (struct node *)NULL) {
X /* is a new node so build it */
X n2 = (struct node *)xalloc(sizeof(struct node));
X n2->name = strsave(s2);
X n2->succ = (struct dependents *)NULL;
X n2->pred = (struct dependents *)NULL;
X n2->left = (struct node *)NULL;
X n2->right = (struct node *)NULL;
X n2->pcnt = 0;
X n2->scnt = 0;
X n2->visited = 0;
X linknode(n2);
X }
X if (n1 != n2) {
X if (finddep(n2->pred,s1) == (struct dependents *)NULL) {
X /* new dependence here */
X pd = (struct dependents *)xalloc(sizeof(struct dependents));
X pd->nd = n1;
X pd->next = (struct dependents *)NULL;
X n2->pcnt++;
X if (n2->pred == (struct dependents *)NULL)
X n2->pred = pd;
X else
X lastdepd->next = pd;
X }
X if (finddep(n1->succ,s2) == (struct dependents *)NULL) {
X /* new dependence here */
X pd = (struct dependents *)xalloc(sizeof(struct dependents));
X pd->nd = n2;
X pd->next = (struct dependents *)NULL;
X n1->scnt++;
X if (n1->succ == (struct dependents *)NULL)
X n1->succ = pd;
X else
X lastdepd->next = pd;
X }
X }
X return (n1);
X }
X else
X return ((struct node *)NULL);
X }
X else
X return ((struct node *)NULL);
X}
X
Xvoid
Xdumptree(top)
Xregister struct node *top;
X{
X walktree(top); /* get all entries in order with no predecessors */
X for (front = 1; front <= back; front++) {
X printmem(q[front]->name);
X walklist(q[front]->succ);
X }
X emptytree(top); /* dumps all isolated nodes left over */
X}
X
Xvoid
Xwalklist(s)
Xregister struct dependents *s;
X{
X for (; s; s = s->next) {
X if (--s->nd->pcnt == 0) {
X addqueue(s->nd);
X s->nd->visited = 1;
X walklist(s->nd->succ);
X }
X }
X}
X
Xvoid
Xwalktree(t)
Xregister struct node *t;
X{
X if (t) {
X node_cnt++;
X walktree(t->right);
X if (t->pcnt == 0) {
X addqueue(t);
X t->visited = 1;
X }
X walktree(t->left);
X }
X}
X
Xvoid
Xemptytree(t)
Xregister struct node *t;
X{
X struct dependents *s;
X
X /* t - represents a remaining entry which is in a cycle */
X if (t) {
X emptytree(t->right);
X if (t->visited == 0) {
X t->visited = 1;
X printmem(t->name);
X for (s = t->succ; s; s = s->next)
X if (s->nd->visited == 0) {
X fprintf(stderr,"Error: %s - %s and %s are in a cycle\n",progname, t->name, s->nd->name);
X }
X }
X emptytree(t->left);
X }
X}
X
Xvoid
Xaddqueue(t)
Xstruct node *t;
X{
X if (++back >= MAXMEMBERS) {
X fprintf(stderr,"Error: %s - member queue overflow\n",progname);
X exit(1);
X }
X else
X q[back] = t;
X}
X
Xchar *
Xreadone()
X{
X register int c, n = 0;
X static char name[MAXNAMELEN];
X
X /* eat up leading spaces */
X while ((c = getchar()) != EOF && isspace(c))
X ;
X
X if (c != EOF) {
X name[n++] = c; /* save into name first non blank */
X while ((c = getchar()) != EOF && !isspace(c)) {
X if (n < MAXNAMELEN)
X name[n++] = c;
X }
X name[n] = '\0';
X return (name);
X }
X else
X return ((char *)NULL);
X
X}
X
Xstruct node *
Xfindnode(s)
Xchar *s;
X{
X register struct node *n;
X register int cmp;
X
X if (tree) {
X lastnode = n = tree;
X while (n && n->name) {
X lastnode = n;
X if (!(cmp = strcmp(s,n->name)))
X return (n);
X else if (cmp > 0)
X n = n->left;
X else
X n = n->right;
X }
X }
X return ((struct node *)NULL);
X}
X
Xstruct dependents *
Xfinddep(dp, s)
Xregister struct dependents *dp;
Xregister char *s;
X{
X lastdepd = (struct dependents *)NULL;
X while (dp && dp->nd) {
X lastdepd = dp;
X if (strcmp(dp->nd->name,s) == 0)
X return (dp);
X else {
X dp = dp->next;
X }
X }
X return ((struct dependents *)NULL);
X}
X
Xlinknode(n)
Xregister struct node *n;
X{
X register int cmp;
X
X if (tree) {
X cmp = strcmp(n->name,lastnode->name);
X if (cmp > 0)
X lastnode->left = n;
X else
X lastnode->right = n;
X }
X else
X tree = n;
X}
X
Xchar *
Xxalloc(n)
Xint n;
X{
X char *p;
X
X if ((p = malloc(n)) != (char *)NULL)
X return (p);
X else {
X fprintf(stderr,"Error: %s out of memory\n",progname);
X exit(1);
X }
X}
X
Xchar *
Xstrsave(s)
Xchar *s;
X{
X char *p;
X
X p = xalloc(strlen(s)+1);
X strcpy(p,s);
X return (p);
X}
/
---------------------------end here---------------------------------------
Monty Walls
MIS Division, Tech. Support
Oklahoma Tax Commission
2501 N. Lincoln
OKC, OK, 73194