xref: /illumos-gate/usr/src/cmd/sgs/tsort/common/tsort.c (revision 2a8bcb4e)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1988 AT&T	*/
/*	  All Rights Reserved  	*/

/*
 *	topological sort
 *	input is sequence of pairs of items (blank-free strings)
 *	nonidentical pair is a directed edge in graph
 *	identical pair merely indicates presence of node
 *	output is ordered list of items consistent with
 *	the partial ordering specified by the graph
 */
#include "errmsg.h"
#include "stdio.h"
#include "string.h"
#include <locale.h>

/*
 *	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() */

#define	STR(X) #X
#define	XSTR(X) STR(X)
#define	FORMAT "%" XSTR(FILENAME_MAX) "s%" XSTR(FILENAME_MAX) "s"
/* These should make FORMAT "%1024s%1024s", if FILENAME_MAX is 1024. */

static
struct nodelist {
	struct nodelist *nextnode;
	struct predlist *inedges;
	char *name;
	int live;
} firstnode = {NULL, NULL, NULL, DEAD};

/*
 *	a predecessor list tells all the immediate
 *	predecessors of a given node
 */
struct predlist {
	struct predlist *nextpred;
	struct nodelist *pred;
};

static struct nodelist *index(char *s);
static struct nodelist *findloop(void);
static struct nodelist *mark(struct nodelist *i);
static int present(struct nodelist *i, struct nodelist *j);
static int anypred(struct nodelist *i);

/*
 *	the first for loop reads in the graph,
 *	the second prints out the ordering
 */
int
main(int argc, char **argv)
{
	struct predlist *t;
	FILE *input = stdin;
	struct nodelist *i, *j;
	int x;
	char precedes[FILENAME_MAX+1], follows[FILENAME_MAX+1];

	(void) setlocale(LC_ALL, "");
#if !defined(TEXT_DOMAIN)	/* Should be defined by cc -D */
#define	TEXT_DOMAIN "SYS_TEST"	/* Use this only if not previously defined */
#endif
	(void) textdomain(TEXT_DOMAIN);

	errprefix("UX");
	errsource(*argv);
	errverb("notag,notofix");
	switch (argc) {
	case 1:
		break;
	case 2:
		if (strcmp(argv[1], "-") == 0)
			break;
		if (strcmp(argv[1], "--") == 0)
			break;
		input = zfopen(EERROR, argv[1], "r");
		break;
	case 3:
		if (strcmp(argv[1], "--") != 0)
			errusage(gettext("[ file ]"));
		input = zfopen(EERROR, argv[2], "r");
		break;
	default:
		errusage("[ file ]");
	}
	for (;;) {
		x = fscanf(input, FORMAT, precedes, follows);
		if (x == EOF)
			break;
		if (x != 2)
			errmsg(EERROR, gettext("odd data"));
		i = index(precedes);
		j = index(follows);
		if (i == j || present(i, j))
			continue;
		t = (struct predlist *)
			zmalloc(EERROR, sizeof (struct predlist));
		t->nextpred = j->inedges;
		t->pred = i;
		j->inedges = t;
	}
	for (;;) {
		x = 0;	/* anything LIVE on this sweep? */
		for (i = &firstnode; i->nextnode != NULL; i = i->nextnode) {
			if (i->live == LIVE) {
				x = 1;
				if (!anypred(i))
					break;
			}
		}
		if (x == 0)
			break;
		if (i->nextnode == NULL)
			i = findloop();
		(void) puts(i->name);
		i->live = DEAD;
	}
	return (0);	/* Ensure zero return on normal termination */
}

/*
 *	is i present on j's predecessor list?
 */
static int
present(struct nodelist *i, struct nodelist *j)
{
	struct predlist *t;
	for (t = j->inedges; t != NULL; t = t->nextpred)
		if (t->pred == i)
			return (1);
	return (0);
}

/*
 *	is there any live predecessor for i?
 */
static int
anypred(struct nodelist *i)
{
	struct predlist *t;
	for (t = i->inedges; t != NULL; t = t->nextpred)
		if (t->pred->live == LIVE)
			return (1);
	return (0);
}

/*
 *	turn a string into a node pointer
 */
static struct nodelist *
index(char *s)
{
	struct nodelist *i;
	char *t;
	for (i = &firstnode; i->nextnode != NULL; i = i->nextnode)
		if (strcmp(s, i->name) == 0)
			return (i);
	for (t = s; *t; t++);
	t = zmalloc(EERROR, (unsigned)(t + 1 - s));
	i->nextnode = (struct nodelist *)
		zmalloc(EERROR, sizeof (struct nodelist));
	i->name = t;
	i->live = LIVE;
	i->nextnode->nextnode = NULL;
	i->nextnode->inedges = NULL;
	i->nextnode->live = DEAD;
	while (*t++ = *s++);
	return (i);
}

/*
 *	given that there is a cycle, find some
 *	node in it
 */
static struct nodelist *
findloop(void)
{
	struct nodelist *i, *j;

	for (i = &firstnode; i->nextnode != NULL; i = i->nextnode)
		if (i->live == LIVE)
			break;
	errmsg(EINFO, "cycle in data");
	i = mark(i);
	if (i == NULL)
		errmsg(EHALT, gettext("program error"));
	for (j = &firstnode; j->nextnode != NULL; j = j->nextnode)
		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
 */
static struct nodelist *
mark(struct nodelist *i)
{
	struct nodelist *j;
	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) {
			(void) fprintf(stderr, "\t%s\n", i->name);
			return (j);
		}
	}
	return (NULL);
}