aboutsummaryrefslogtreecommitdiff
path: root/usr.bin/tsort
diff options
context:
space:
mode:
Diffstat (limited to 'usr.bin/tsort')
-rw-r--r--usr.bin/tsort/CVS/Entries4
-rw-r--r--usr.bin/tsort/CVS/Repository1
-rw-r--r--usr.bin/tsort/CVS/Root1
-rw-r--r--usr.bin/tsort/Makefile9
-rw-r--r--usr.bin/tsort/tsort.1167
-rw-r--r--usr.bin/tsort/tsort.c1014
6 files changed, 0 insertions, 1196 deletions
diff --git a/usr.bin/tsort/CVS/Entries b/usr.bin/tsort/CVS/Entries
deleted file mode 100644
index 528f3f2..0000000
--- a/usr.bin/tsort/CVS/Entries
+++ /dev/null
@@ -1,4 +0,0 @@
-/Makefile/1.7/Thu Sep 23 13:56:23 2021//
-/tsort.1/1.24/Thu Sep 23 13:56:23 2021//
-/tsort.c/1.37/Thu Sep 23 13:56:23 2021//
-D
diff --git a/usr.bin/tsort/CVS/Repository b/usr.bin/tsort/CVS/Repository
deleted file mode 100644
index 3079881..0000000
--- a/usr.bin/tsort/CVS/Repository
+++ /dev/null
@@ -1 +0,0 @@
-src/usr.bin/tsort
diff --git a/usr.bin/tsort/CVS/Root b/usr.bin/tsort/CVS/Root
deleted file mode 100644
index 3811072..0000000
--- a/usr.bin/tsort/CVS/Root
+++ /dev/null
@@ -1 +0,0 @@
-/cvs
diff --git a/usr.bin/tsort/Makefile b/usr.bin/tsort/Makefile
deleted file mode 100644
index 0c57770..0000000
--- a/usr.bin/tsort/Makefile
+++ /dev/null
@@ -1,9 +0,0 @@
-# $OpenBSD: Makefile,v 1.7 2017/07/09 21:23:19 espie Exp $
-
-PROG = tsort
-
-CDIAGFLAGS = -Wall -Wno-char-subscripts -Wstrict-prototypes -pedantic -W
-DPADD += ${LIBUTIL}
-LDADD += -lutil
-
-.include <bsd.prog.mk>
diff --git a/usr.bin/tsort/tsort.1 b/usr.bin/tsort/tsort.1
deleted file mode 100644
index 56f5fc3..0000000
--- a/usr.bin/tsort/tsort.1
+++ /dev/null
@@ -1,167 +0,0 @@
-.\" $OpenBSD: tsort.1,v 1.24 2019/04/23 18:13:11 schwarze Exp $
-.\" $NetBSD: tsort.1,v 1.6 1996/01/17 20:37:49 mycroft Exp $
-.\"
-.\" Copyright (c) 1990, 1993, 1994
-.\" The Regents of the University of California. All rights reserved.
-.\"
-.\" This manual is derived from one contributed to Berkeley by
-.\" Michael Rendell of Memorial University of Newfoundland.
-.\"
-.\" Redistribution and use in source and binary forms, with or without
-.\" modification, are permitted provided that the following conditions
-.\" are met:
-.\" 1. Redistributions of source code must retain the above copyright
-.\" notice, this list of conditions and the following disclaimer.
-.\" 2. Redistributions in binary form must reproduce the above copyright
-.\" notice, this list of conditions and the following disclaimer in the
-.\" documentation and/or other materials provided with the distribution.
-.\" 3. Neither the name of the University nor the names of its contributors
-.\" may be used to endorse or promote products derived from this software
-.\" without specific prior written permission.
-.\"
-.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
-.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
-.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
-.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
-.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
-.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
-.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
-.\" SUCH DAMAGE.
-.\"
-.\" @(#)tsort.1 8.3 (Berkeley) 4/1/94
-.\"
-.Dd $Mdocdate: April 23 2019 $
-.Dt TSORT 1
-.Os
-.Sh NAME
-.Nm tsort
-.Nd topological sort of a directed graph
-.Sh SYNOPSIS
-.Nm tsort
-.Op Fl flqrvw
-.Op Fl h Ar file
-.Op Ar file
-.Sh DESCRIPTION
-.Nm tsort
-takes a list of pairs of node names representing directed arcs in
-a graph and prints the nodes in topological order on standard output.
-That is, the input describes a partial ordering relation, from which
-.Nm
-computes a total order compatible with this partial ordering.
-.Pp
-Input is taken from the named
-.Ar file ,
-or from standard input if no file
-is given.
-.Pp
-Node names in the input are separated by white space and there must
-be an even number of node names.
-.Pp
-Presence of a node in a graph can be represented by an arc from the node
-to itself.
-This is useful when a node is not connected to any other nodes.
-.Pp
-If the graph contains a cycle (and therefore cannot be properly sorted),
-one of the arcs in the cycle is ignored and the sort continues.
-Cycles are reported on standard error.
-.Pp
-The options are as follows:
-.Bl -tag -width Ds
-.It Fl f
-Resolve ambiguities by selecting nodes based on the order of appearance
-of the first component of the pairs.
-.It Fl h Ar file
-Use
-.Ar file ,
-which holds an ordered list of nodes, to resolve ambiguities.
-In case of duplicates, the first entry is chosen.
-.It Fl l
-Search for and display the longest cycle.
-Can take a very long time, as it may need to solve an NP-complete problem.
-.It Fl q
-Do not display informational messages about cycles.
-This is primarily intended for building libraries, where optimal ordering
-is not critical, and cycles occur often.
-.It Fl r
-Reverse the ordering relation.
-.It Fl v
-Inform on the exact number of edges broken while breaking cycles.
-If a hints file was used, inform on seen nodes absent from that file.
-.It Fl w
-Exit with exit code the number of cycles
-.Nm
-had to break.
-.El
-.Sh EXIT STATUS
-.Ex -std tsort
-.Sh EXAMPLES
-Faced with the input:
-.Bd -literal -offset indent
-a b
-b c
-b d
-d f
-c e
-.Ed
-.Pp
-.Nm
-outputs:
-.Bd -literal -offset indent
-a
-b
-c
-e
-d
-f
-.Ed
-.Pp
-which is one total ordering compatible with the individual relations.
-There is no unicity, another compatible total ordering would be:
-.Bd -literal -offset indent
-a
-b
-c
-d
-e
-f
-.Ed
-.Pp
-.Nm
-is commonly used to analyze dependencies and find a correct build order
-in a static way, whereas
-.Xr make 1
-accomplishes the same task in a dynamic way.
-.Sh SEE ALSO
-.Xr ar 1 ,
-.Xr lorder 1 ,
-.Xr make 1
-.Rs
-.%A Donald E. Knuth
-.%B The Art of Computer Programming
-.%V Vol. 1
-.%P pp. 258\(en268
-.%D 1973
-.Re
-.Sh STANDARDS
-The
-.Nm
-utility is compliant with the
-.St -p1003.1-2008
-specification.
-.Pp
-The flags
-.Op Fl fhlqrvw
-are extensions to that specification.
-.Sh HISTORY
-A
-.Nm
-command appeared in
-.At v7 .
-This
-.Nm tsort
-command was completely rewritten by Marc Espie for
-.Ox ,
-to finally use the well-known optimal algorithms for topological sorting.
diff --git a/usr.bin/tsort/tsort.c b/usr.bin/tsort/tsort.c
deleted file mode 100644
index 3e0e1ab..0000000
--- a/usr.bin/tsort/tsort.c
+++ /dev/null
@@ -1,1014 +0,0 @@
-/* $OpenBSD: tsort.c,v 1.37 2019/07/11 17:28:32 mestre Exp $ */
-/* ex:ts=8 sw=4:
- *
- * Copyright (c) 1999-2004 Marc Espie <espie@openbsd.org>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- */
-
-#include <assert.h>
-#include <ctype.h>
-#include <err.h>
-#include <limits.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-#include <ohash.h>
-
-/* The complexity of topological sorting is O(e), where e is the
- * size of input. While reading input, vertices have to be identified,
- * thus add the complexity of e keys retrieval among v keys using
- * an appropriate data structure. This program uses open double hashing
- * for that purpose. See Knuth for the expected complexity of double
- * hashing (Brent variation should probably be used if v << e, as a user
- * option).
- *
- * The algorithm used for longest cycle reporting is accurate, but somewhat
- * expensive. It may need to build all free paths of the graph (a free
- * path is a path that never goes twice through the same node), whose
- * number can be as high as O(2^e). Usually, the number of free paths is
- * much smaller though. This program's author does not believe that a
- * significantly better worst-case complexity algorithm exists.
- *
- * In case of a hints file, the set of minimal nodes is maintained as a
- * heap. The resulting complexity is O(e+v log v) for the worst case.
- * The average should actually be near O(e).
- *
- * If the hints file is incomplete, there is some extra complexity incurred
- * by make_transparent, which does propagate order values to unmarked
- * nodes. In the worst case, make_transparent is O(e u),
- * where u is the number of originally unmarked nodes.
- * In practice, it is much faster.
- *
- * The simple topological sort algorithm detects cycles. This program
- * goes further, breaking cycles through the use of simple heuristics.
- * Each cycle break checks the whole set of nodes, hence if c cycles break
- * are needed, this is an extra cost of O(c v).
- *
- * Possible heuristics are as follows:
- * - break cycle at node with lowest number of predecessors (default case),
- * - break longest cycle at node with lowest number of predecessors,
- * - break cycle at next node from the hints file.
- *
- * Except for the hints file case, which sets an explicit constraint on
- * which cycle to break, those heuristics locally result in the smallest
- * number of broken edges.
- *
- * Those are admittedly greedy strategies, as is the selection of the next
- * node from the hints file amongst equivalent candidates that is used for
- * `stable' topological sorting.
- */
-
-#ifdef __GNUC__
-#define UNUSED __attribute__((unused))
-#else
-#define UNUSED
-#endif
-
-struct node;
-
-/* The set of arcs from a given node is stored as a linked list. */
-struct link {
- struct link *next;
- struct node *node;
-};
-
-#define NO_ORDER UINT_MAX
-
-struct node {
- unsigned int refs; /* Number of arcs left, coming into this node.
- * Note that nodes with a null count can't
- * be part of cycles. */
- unsigned int order; /* Order of nodes according to a hint file. */
-
- struct link *arcs; /* List of forward arcs. */
-
- /* Cycle detection algorithms build a free path of nodes. */
- struct node *from; /* Previous node in the current path. */
- struct link *traverse; /* Next link to traverse when backtracking. */
- unsigned int mark; /* Mark processed nodes in cycle discovery. */
-
- char k[1]; /* Name of this node. */
-};
-
-#define HASH_START 9
-
-struct array {
- unsigned int entries;
- struct node **t;
-};
-
-static void nodes_init(struct ohash *);
-static struct node *node_lookup(struct ohash *, const char *, const char *);
-static __dead void usage(void);
-static struct node *new_node(const char *, const char *);
-
-static unsigned int read_pairs(FILE *, struct ohash *, int,
- const char *, unsigned int, int);
-static void split_nodes(struct ohash *, struct array *, struct array *);
-static void make_transparent(struct ohash *);
-static void insert_arc(struct node *, struct node *);
-
-#ifdef DEBUG
-static void dump_node(struct node *);
-static void dump_array(struct array *);
-static void dump_hash(struct ohash *);
-#endif
-static unsigned int read_hints(FILE *, struct ohash *, int,
- const char *, unsigned int);
-static struct node *find_smallest_node(struct array *);
-static struct node *find_good_cycle_break(struct array *);
-static void print_cycle(struct array *);
-static struct node *find_cycle_from(struct node *, struct array *);
-static struct node *find_predecessor(struct array *, struct node *);
-static unsigned int traverse_node(struct node *, unsigned int, struct array *);
-static struct node *find_longest_cycle(struct array *, struct array *);
-static struct node *find_normal_cycle(struct array *, struct array *);
-
-static void heap_down(struct array *, unsigned int);
-static void heapify(struct array *, int);
-static struct node *dequeue(struct array *);
-static void enqueue(struct array *, struct node *);
-
-
-
-static void *hash_calloc(size_t, size_t, void *);
-static void hash_free(void *, void *);
-static void* entry_alloc(size_t, void *);
-static void *ereallocarray(void *, size_t, size_t);
-static void *emem(void *);
-#define DEBUG_TRAVERSE 0
-static struct ohash_info node_info = {
- offsetof(struct node, k), NULL, hash_calloc, hash_free, entry_alloc };
-static void parse_args(int, char *[], struct ohash *);
-static int tsort(struct ohash *);
-
-static int quiet_flag, long_flag,
- warn_flag, hints_flag, verbose_flag;
-
-
-int main(int, char *[]);
-
-/***
- *** Memory handling.
- ***/
-
-static void *
-emem(void *p)
-{
- if (p)
- return p;
- else
- errx(1, "Memory exhausted");
-}
-
-static void *
-hash_calloc(size_t n, size_t s, void *u UNUSED)
-{
- return emem(calloc(n, s));
-}
-
-static void
-hash_free(void *p, void *u UNUSED)
-{
- free(p);
-}
-
-static void *
-entry_alloc(size_t s, void *u UNUSED)
-{
- return ereallocarray(NULL, 1, s);
-}
-
-static void *
-ereallocarray(void *p, size_t n, size_t s)
-{
- return emem(reallocarray(p, n, s));
-}
-
-
-/***
- *** Hash table.
- ***/
-
-/* Inserting and finding nodes in the hash structure.
- * We handle interval strings for efficiency wrt fgetln. */
-static struct node *
-new_node(const char *start, const char *end)
-{
- struct node *n;
-
- n = ohash_create_entry(&node_info, start, &end);
- n->from = NULL;
- n->arcs = NULL;
- n->refs = 0;
- n->mark = 0;
- n->order = NO_ORDER;
- n->traverse = NULL;
- return n;
-}
-
-
-static void
-nodes_init(struct ohash *h)
-{
- ohash_init(h, HASH_START, &node_info);
-}
-
-static struct node *
-node_lookup(struct ohash *h, const char *start, const char *end)
-{
- unsigned int i;
- struct node * n;
-
- i = ohash_qlookupi(h, start, &end);
-
- n = ohash_find(h, i);
- if (n == NULL)
- n = ohash_insert(h, i, new_node(start, end));
- return n;
-}
-
-#ifdef DEBUG
-static void
-dump_node(struct node *n)
-{
- struct link *l;
-
- if (n->refs == 0)
- return;
- printf("%s (%u/%u): ", n->k, n->order, n->refs);
- for (l = n->arcs; l != NULL; l = l->next)
- if (n->refs != 0)
- printf("%s(%u/%u) ", l->node->k, l->node->order, l->node->refs);
- putchar('\n');
-}
-
-static void
-dump_array(struct array *a)
-{
- unsigned int i;
-
- for (i = 0; i < a->entries; i++)
- dump_node(a->t[i]);
-}
-
-static void
-dump_hash(struct ohash *h)
-{
- unsigned int i;
- struct node *n;
-
- for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
- dump_node(n);
-}
-#endif
-
-/***
- *** Reading data.
- ***/
-
-static void
-insert_arc(struct node *a, struct node *b)
-{
- struct link *l;
-
- /* Check that this arc is not already present. */
- for (l = a->arcs; l != NULL; l = l->next) {
- if (l->node == b)
- return;
- }
- b->refs++;
- l = ereallocarray(NULL, 1, sizeof(struct link));
- l->node = b;
- l->next = a->arcs;
- a->arcs = l;
-}
-
-static unsigned int
-read_pairs(FILE *f, struct ohash *h, int reverse, const char *name,
- unsigned int order, int hint)
-{
- int toggle;
- struct node *a;
- size_t size;
- char *str;
-
- toggle = 1;
- a = NULL;
-
- while ((str = fgetln(f, &size)) != NULL) {
- char *sentinel;
-
- sentinel = str + size;
- for (;;) {
- char *e;
-
- while (str < sentinel &&
- isspace((unsigned char)*str))
- str++;
- if (str == sentinel)
- break;
- for (e = str;
- e < sentinel && !isspace((unsigned char)*e); e++)
- continue;
- if (toggle) {
- a = node_lookup(h, str, e);
- if (a->order == NO_ORDER && hint)
- a->order = order++;
- } else {
- struct node *b;
-
- b = node_lookup(h, str, e);
- assert(a != NULL);
- if (b != a) {
- if (reverse)
- insert_arc(b, a);
- else
- insert_arc(a, b);
- }
- }
- toggle = !toggle;
- str = e;
- }
- }
- if (toggle == 0)
- errx(1, "odd number of node names in %s", name);
- if (!feof(f))
- err(1, "error reading %s", name);
- return order;
-}
-
-static unsigned int
-read_hints(FILE *f, struct ohash *h, int quiet, const char *name,
- unsigned int order)
-{
- char *str;
- size_t size;
-
- while ((str = fgetln(f, &size)) != NULL) {
- char *sentinel;
-
- sentinel = str + size;
- for (;;) {
- char *e;
- struct node *a;
-
- while (str < sentinel && isspace((unsigned char)*str))
- str++;
- if (str == sentinel)
- break;
- for (e = str;
- e < sentinel && !isspace((unsigned char)*e); e++)
- continue;
- a = node_lookup(h, str, e);
- if (a->order != NO_ORDER) {
- if (!quiet)
- warnx(
- "duplicate node %s in hints file %s",
- a->k, name);
- } else
- a->order = order++;
- str = e;
- }
- }
- if (!feof(f))
- err(1, "error reading %s", name);
- return order;
-}
-
-
-/***
- *** Standard heap handling routines.
- ***/
-
-static void
-heap_down(struct array *h, unsigned int i)
-{
- unsigned int j;
- struct node *swap;
-
- for (; (j=2*i+1) < h->entries; i = j) {
- if (j+1 < h->entries && h->t[j+1]->order < h->t[j]->order)
- j++;
- if (h->t[i]->order <= h->t[j]->order)
- break;
- swap = h->t[i];
- h->t[i] = h->t[j];
- h->t[j] = swap;
- }
-}
-
-static void
-heapify(struct array *h, int verbose)
-{
- unsigned int i;
-
- for (i = h->entries; i != 0;) {
- if (h->t[--i]->order == NO_ORDER && verbose)
- warnx("node %s absent from hints file", h->t[i]->k);
- heap_down(h, i);
- }
-}
-
-#define DEQUEUE(h) ( hints_flag ? dequeue(h) : (h)->t[--(h)->entries] )
-
-static struct node *
-dequeue(struct array *h)
-{
- struct node *n;
-
- if (h->entries == 0)
- n = NULL;
- else {
- n = h->t[0];
- if (--h->entries != 0) {
- h->t[0] = h->t[h->entries];
- heap_down(h, 0);
- }
- }
- return n;
-}
-
-#define ENQUEUE(h, n) do { \
- if (hints_flag) \
- enqueue((h), (n)); \
- else \
- (h)->t[(h)->entries++] = (n); \
- } while(0);
-
-static void
-enqueue(struct array *h, struct node *n)
-{
- unsigned int i, j;
- struct node *swap;
-
- h->t[h->entries++] = n;
- for (i = h->entries-1; i > 0; i = j) {
- j = (i-1)/2;
- if (h->t[j]->order < h->t[i]->order)
- break;
- swap = h->t[j];
- h->t[j] = h->t[i];
- h->t[i] = swap;
- }
-}
-
-/* Nodes without order should not hinder direct dependencies.
- * Iterate until no nodes are left.
- */
-static void
-make_transparent(struct ohash *hash)
-{
- struct node *n;
- unsigned int i;
- struct link *l;
- int adjusted;
- int bad;
- unsigned int min;
-
- /* first try to solve complete nodes */
- do {
- adjusted = 0;
- bad = 0;
- for (n = ohash_first(hash, &i); n != NULL;
- n = ohash_next(hash, &i)) {
- if (n->order == NO_ORDER) {
- min = NO_ORDER;
-
- for (l = n->arcs; l != NULL; l = l->next) {
- /* unsolved node -> delay resolution */
- if (l->node->order == NO_ORDER) {
- bad = 1;
- break;
- } else if (l->node->order < min)
- min = l->node->order;
- }
- if (min < NO_ORDER && l == NULL) {
- n->order = min;
- adjusted = 1;
- }
- }
- }
-
- } while (adjusted);
-
- /* then, if incomplete nodes are left, do them */
- if (bad) do {
- adjusted = 0;
- for (n = ohash_first(hash, &i); n != NULL;
- n = ohash_next(hash, &i))
- if (n->order == NO_ORDER)
- for (l = n->arcs; l != NULL; l = l->next)
- if (l->node->order < n->order) {
- n->order = l->node->order;
- adjusted = 1;
- }
- } while (adjusted);
-}
-
-
-/***
- *** Search through hash array for nodes.
- ***/
-
-/* Split nodes into unrefed nodes/live nodes. */
-static void
-split_nodes(struct ohash *hash, struct array *heap, struct array *remaining)
-{
-
- struct node *n;
- unsigned int i;
-
- heap->t = ereallocarray(NULL, ohash_entries(hash),
- sizeof(struct node *));
- remaining->t = ereallocarray(NULL, ohash_entries(hash),
- sizeof(struct node *));
- heap->entries = 0;
- remaining->entries = 0;
-
- for (n = ohash_first(hash, &i); n != NULL; n = ohash_next(hash, &i)) {
- if (n->refs == 0)
- heap->t[heap->entries++] = n;
- else
- remaining->t[remaining->entries++] = n;
- }
-}
-
-/* Good point to break a cycle: live node with as few refs as possible. */
-static struct node *
-find_good_cycle_break(struct array *h)
-{
- unsigned int i;
- unsigned int best;
- struct node *u;
-
- best = UINT_MAX;
- u = NULL;
-
- assert(h->entries != 0);
- for (i = 0; i < h->entries; i++) {
- struct node *n = h->t[i];
- /* No need to look further. */
- if (n->refs == 1)
- return n;
- if (n->refs != 0 && n->refs < best) {
- best = n->refs;
- u = n;
- }
- }
- assert(u != NULL);
- return u;
-}
-
-/* Retrieve the node with the smallest order. */
-static struct node *
-find_smallest_node(struct array *h)
-{
- unsigned int i;
- unsigned int best;
- struct node *u;
-
- best = UINT_MAX;
- u = NULL;
-
- assert(h->entries != 0);
- for (i = 0; i < h->entries; i++) {
- struct node *n = h->t[i];
- if (n->refs != 0 && n->order < best) {
- best = n->order;
- u = n;
- }
- }
- assert(u != NULL);
- return u;
-}
-
-
-/***
- *** Graph algorithms.
- ***/
-
-/* Explore the nodes reachable from i to find a cycle, store it in c.
- * This may fail. */
-static struct node *
-find_cycle_from(struct node *i, struct array *c)
-{
- struct node *n;
-
- n = i;
- /* XXX Previous cycle findings may have left this pointer non-null. */
- i->from = NULL;
-
- for (;;) {
- /* Note that all marks are reversed before this code exits. */
- n->mark = 1;
- if (n->traverse)
- n->traverse = n->traverse->next;
- else
- n->traverse = n->arcs;
- /* Skip over dead nodes. */
- while (n->traverse && n->traverse->node->refs == 0)
- n->traverse = n->traverse->next;
- if (n->traverse) {
- struct node *go = n->traverse->node;
-
- if (go->mark) {
- c->entries = 0;
- for (; n != NULL && n != go; n = n->from) {
- c->t[c->entries++] = n;
- n->mark = 0;
- }
- for (; n != NULL; n = n->from)
- n->mark = 0;
- c->t[c->entries++] = go;
- return go;
- } else {
- go->from = n;
- n = go;
- }
- } else {
- n->mark = 0;
- n = n->from;
- if (n == NULL)
- return NULL;
- }
- }
-}
-
-/* Find a live predecessor of node n. This is a slow routine, as it needs
- * to go through the whole array, but it is not needed often.
- */
-static struct node *
-find_predecessor(struct array *a, struct node *n)
-{
- unsigned int i;
-
- for (i = 0; i < a->entries; i++) {
- struct node *m;
-
- m = a->t[i];
- if (m->refs != 0) {
- struct link *l;
-
- for (l = m->arcs; l != NULL; l = l->next)
- if (l->node == n)
- return m;
- }
- }
- assert(1 == 0);
- return NULL;
-}
-
-/* Traverse all strongly connected components reachable from node n.
- Start numbering them at o. Return the maximum order reached.
- Update the largest cycle found so far.
- */
-static unsigned int
-traverse_node(struct node *n, unsigned int o, struct array *c)
-{
- unsigned int min, max;
-
- n->from = NULL;
- min = o;
- max = ++o;
-
- for (;;) {
- n->mark = o;
- if (DEBUG_TRAVERSE)
- printf("%s(%u) ", n->k, n->mark);
- /* Find next arc to explore. */
- if (n->traverse)
- n->traverse = n->traverse->next;
- else
- n->traverse = n->arcs;
- /* Skip over dead nodes. */
- while (n->traverse && n->traverse->node->refs == 0)
- n->traverse = n->traverse->next;
- /* If arc left. */
- if (n->traverse) {
- struct node *go;
-
- go = n->traverse->node;
- /* Optimisation: if go->mark < min, we already
- * visited this strongly-connected component in
- * a previous pass. Hence, this can yield no new
- * cycle. */
-
- /* Not part of the current path: go for it. */
- if (go->mark == 0 || go->mark == min) {
- go->from = n;
- n = go;
- o++;
- if (o > max)
- max = o;
- /* Part of the current path: check cycle length. */
- } else if (go->mark > min) {
- if (DEBUG_TRAVERSE)
- printf("%d\n", o - go->mark + 1);
- if (o - go->mark + 1 > c->entries) {
- struct node *t;
- unsigned int i;
-
- c->entries = o - go->mark + 1;
- i = 0;
- c->t[i++] = go;
- for (t = n; t != go; t = t->from)
- c->t[i++] = t;
- }
- }
-
- /* No arc left: backtrack. */
- } else {
- n->mark = min;
- n = n->from;
- if (!n)
- return max;
- o--;
- }
- }
-}
-
-static void
-print_cycle(struct array *c)
-{
- unsigned int i;
-
- /* Printing in reverse order, since cycle discoveries finds reverse
- * edges. */
- for (i = c->entries; i != 0;) {
- i--;
- warnx("%s", c->t[i]->k);
- }
-}
-
-static struct node *
-find_longest_cycle(struct array *h, struct array *c)
-{
- unsigned int i;
- unsigned int o;
- unsigned int best;
- struct node *n;
- static int notfirst = 0;
-
- assert(h->entries != 0);
-
- /* No cycle found yet. */
- c->entries = 0;
-
- /* Reset the set of marks, except the first time around. */
- if (notfirst) {
- for (i = 0; i < h->entries; i++)
- h->t[i]->mark = 0;
- } else
- notfirst = 1;
-
- o = 0;
-
- /* Traverse the array. Each unmarked, live node heralds a
- * new set of strongly connected components. */
- for (i = 0; i < h->entries; i++) {
- n = h->t[i];
- if (n->refs != 0 && n->mark == 0) {
- /* Each call to traverse_node uses a separate
- * interval of numbers to mark nodes. */
- o++;
- o = traverse_node(n, o, c);
- }
- }
-
- assert(c->entries != 0);
- n = c->t[0];
- best = n->refs;
- for (i = 0; i < c->entries; i++) {
- if (c->t[i]->refs < best) {
- n = c->t[i];
- best = n->refs;
- }
- }
- return n;
-}
-
-static struct node *
-find_normal_cycle(struct array *h, struct array *c)
-{
- struct node *b, *n;
-
- if (hints_flag)
- n = find_smallest_node(h);
- else
- n = find_good_cycle_break(h);
- while ((b = find_cycle_from(n, c)) == NULL)
- n = find_predecessor(h, n);
- return b;
-}
-
-
-#define plural(n) ((n) > 1 ? "s" : "")
-
-static void
-parse_args(int argc, char *argv[], struct ohash *pairs)
-{
- int c;
- unsigned int order;
- int reverse_flag;
- const char **files;
- int i, j;
-
- i = 0;
-
- reverse_flag = quiet_flag = long_flag =
- warn_flag = hints_flag = verbose_flag = 0;
- /* argc is good enough, as we start at argv[1] */
- files = ereallocarray(NULL, argc, sizeof (char *));
- while ((c = getopt(argc, argv, "h:flqrvw")) != -1) {
- switch(c) {
- case 'h':
- files[i++] = optarg;
- hints_flag = 1;
- break;
- /*FALLTHRU*/
- case 'f':
- hints_flag = 2;
- break;
- case 'l':
- long_flag = 1;
- break;
- case 'q':
- quiet_flag = 1;
- break;
- case 'r':
- reverse_flag = 1;
- break;
- case 'v':
- verbose_flag = 1;
- break;
- case 'w':
- warn_flag = 1;
- break;
- default:
- usage();
- }
- }
-
- argc -= optind;
- argv += optind;
-
- switch(argc) {
- case 1:
- files[i++] = argv[0];
- break;
- case 0:
- break;
- default:
- usage();
- }
-
- files[i] = NULL;
-
- nodes_init(pairs);
- order = 0;
-
- for (j = 0; j != i-argc; j++) {
- FILE *f;
-
- f = fopen(files[j], "r");
- if (f == NULL)
- err(1, "Can't open hint file %s", files[i]);
- order = read_hints(f, pairs, quiet_flag, files[i], order);
- fclose(f);
- }
- free(files);
-
- if (argc == 1) {
- FILE *f;
-
- f = fopen(argv[0], "r");
- if (f == NULL)
- err(1, "Can't open file %s", argv[0]);
- order = read_pairs(f, pairs, reverse_flag, argv[0], order,
- hints_flag == 2);
- fclose(f);
- } else {
- order = read_pairs(stdin, pairs, reverse_flag, "stdin",
- order, hints_flag == 2);
- }
-}
-
-static int
-tsort(struct ohash *pairs)
-{
- struct array aux; /* Unrefed nodes/cycle reporting. */
- struct array remaining;
- unsigned int broken_arcs, broken_cycles;
- unsigned int left;
-
- broken_arcs = 0;
- broken_cycles = 0;
-
- if (hints_flag)
- make_transparent(pairs);
- split_nodes(pairs, &aux, &remaining);
- ohash_delete(pairs);
-
- if (hints_flag)
- heapify(&aux, verbose_flag);
-
- left = remaining.entries + aux.entries;
- while (left != 0) {
-
- /* Standard topological sort. */
- while (aux.entries) {
- struct link *l;
- struct node *n;
-
- n = DEQUEUE(&aux);
- printf("%s\n", n->k);
- left--;
- /* We can't free nodes, as we don't know which
- * entry we can remove in the hash table. We
- * rely on refs == 0 to recognize live nodes.
- * Decrease ref count of live nodes, enter new
- * candidates into the unrefed list. */
- for (l = n->arcs; l != NULL; l = l->next)
- if (l->node->refs != 0 &&
- --l->node->refs == 0) {
- ENQUEUE(&aux, l->node);
- }
- }
- /* There are still cycles to break. */
- if (left != 0) {
- struct node *n;
-
- broken_cycles++;
- /* XXX Simple cycle detection and long cycle
- * detection are mutually exclusive. */
-
- if (long_flag)
- n = find_longest_cycle(&remaining, &aux);
- else
- n = find_normal_cycle(&remaining, &aux);
-
- if (!quiet_flag) {
- warnx("cycle in data");
- print_cycle(&aux);
- }
-
- if (verbose_flag)
- warnx("%u edge%s broken", n->refs,
- plural(n->refs));
- broken_arcs += n->refs;
- n->refs = 0;
- /* Reinitialization, cycle reporting uses aux. */
- aux.t[0] = n;
- aux.entries = 1;
- }
- }
- if (verbose_flag && broken_cycles != 0)
- warnx("%u cycle%s broken, for a total of %u edge%s",
- broken_cycles, plural(broken_cycles),
- broken_arcs, plural(broken_arcs));
- if (warn_flag)
- return (broken_cycles < 256 ? broken_cycles : 255);
- else
- return (0);
-}
-
-int
-main(int argc, char *argv[])
-{
- struct ohash pairs;
-
- if (pledge("stdio rpath", NULL) == -1)
- err(1, "pledge");
-
- parse_args(argc, argv, &pairs);
-
- if (pledge("stdio", NULL) == -1)
- err(1, "pledge");
-
- return tsort(&pairs);
-}
-
-
-extern char *__progname;
-
-static void
-usage(void)
-{
- fprintf(stderr, "Usage: %s [-flqrvw] [-h file] [file]\n", __progname);
- exit(1);
-}