/*
* 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
* 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 */
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* 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 STR(X) #X
/* These should make FORMAT "%1024s%1024s", if FILENAME_MAX is 1024. */
static
struct nodelist {
char *name;
int live;
/*
* a predecessor list tells all the immediate
* predecessors of a given node
*/
struct predlist {
};
/*
* the first for loop reads in the graph,
* the second prints out the ordering
*/
int
{
struct predlist *t;
struct nodelist *i, *j;
int x;
#if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
#endif
(void) textdomain(TEXT_DOMAIN);
errprefix("UX");
errverb("notag,notofix");
switch (argc) {
case 1:
break;
case 2:
break;
break;
break;
case 3:
break;
default:
errusage("[ file ]");
}
for (;;) {
if (x == EOF)
break;
if (x != 2)
if (i == j || present(i, j))
continue;
t = (struct predlist *)
t->pred = i;
j->inedges = t;
}
for (;;) {
x = 0; /* anything LIVE on this sweep? */
x = 1;
if (!anypred(i))
break;
}
}
if (x == 0)
break;
i = findloop();
}
return (0); /* Ensure zero return on normal termination */
}
/*
* is i present on j's predecessor list?
*/
static int
{
struct predlist *t;
if (t->pred == i)
return (1);
return (0);
}
/*
* is there any live predecessor for i?
*/
static int
{
struct predlist *t;
return (1);
return (0);
}
/*
* turn a string into a node pointer
*/
static struct nodelist *
index(char *s)
{
struct nodelist *i;
char *t;
return (i);
for (t = s; *t; t++);
i->name = t;
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;
break;
i = mark(i);
if (i == NULL)
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 *
{
struct nodelist *j;
struct predlist *t;
return (NULL);
return (i);
if (j != NULL) {
return (j);
}
}
return (NULL);
}