Import ptsort 0.20170215 from https://www.github.com/dag-erling/ptsort

Issue #387

22 files changed, 1589 insertions, 0 deletions

diff --git a/external/ptsort/.travis.yml b/external/ptsort/.travis.yml
new file mode 100644
index 00000000..865e672f
--- /dev/null
+++ b/external/ptsort/.travis.yml
@@ -0,0 +1,12 @@
+language: c
+
+compiler:
+  - clang
+  - gcc
+
+before_script:
+  - ./autogen.sh
+
+script:
+  - ./configure --enable-developer-warnings --enable-werror
+  - make check
diff --git a/external/ptsort/HISTORY b/external/ptsort/HISTORY
new file mode 100644
index 00000000..7a417bc0
--- /dev/null
+++ b/external/ptsort/HISTORY
@@ -0,0 +1 @@
+https://github.com/dag-erling/ptsort/commits/master
diff --git a/external/ptsort/INSTALL b/external/ptsort/INSTALL
new file mode 100644
index 00000000..4e5d7f25
--- /dev/null
+++ b/external/ptsort/INSTALL
@@ -0,0 +1 @@
+You know what to do.
diff --git a/external/ptsort/LICENSE b/external/ptsort/LICENSE
new file mode 100644
index 00000000..947ffed5
--- /dev/null
+++ b/external/ptsort/LICENSE
@@ -0,0 +1,29 @@
+Copyright (c) 2016-2017 Dag-Erling Smørgrav
+All rights reserved.
+
+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. The name of the author may not be used to endorse or promote
+   products derived from this software without specific prior written
+   permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+
+Portions of this code are copyright (c) 2016 The University of Oslo
+under the same terms as above.
diff --git a/external/ptsort/Makefile.am b/external/ptsort/Makefile.am
new file mode 100644
index 00000000..7f0673be
--- /dev/null
+++ b/external/ptsort/Makefile.am
@@ -0,0 +1,3 @@
+ACLOCAL_AMFLAGS = -I m4
+SUBDIRS = lib bin t
+EXTRA_DIST = HISTORY INSTALL LICENSE README autogen.sh
diff --git a/external/ptsort/README b/external/ptsort/README
new file mode 100644
index 00000000..f2c8c431
--- /dev/null
+++ b/external/ptsort/README
@@ -0,0 +1,11 @@
+The ptsort utility is a variant of the standard tsort (topological
+sort) utility which allows nodes to be prioritized, moving them and
+all their predecessors up in the final order.
+
+The latest version of the source code is available from Github:
+
+  https://github.com/dag-erling/ptsort
+
+Bugs can be reported as issues in Github:
+
+  https://github.com/dag-erling/ptsort/issues
diff --git a/external/ptsort/autogen.des b/external/ptsort/autogen.des
new file mode 100755
index 00000000..94c7afea
--- /dev/null
+++ b/external/ptsort/autogen.des
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+set -e
+
+. ./autogen.sh
+
+./configure \
+	--enable-developer-warnings \
+	--enable-debugging-symbols \
+	--enable-werror \
+	"$@"
diff --git a/external/ptsort/autogen.sh b/external/ptsort/autogen.sh
new file mode 100755
index 00000000..150d5986
--- /dev/null
+++ b/external/ptsort/autogen.sh
@@ -0,0 +1,7 @@
+#!/bin/sh
+
+mkdir -p m4
+aclocal -I m4
+autoheader
+automake -a -c --foreign
+autoconf
diff --git a/external/ptsort/bin/.gitignore b/external/ptsort/bin/.gitignore
new file mode 100644
index 00000000..b47779ce
--- /dev/null
+++ b/external/ptsort/bin/.gitignore
@@ -0,0 +1 @@
+ptsort
diff --git a/external/ptsort/bin/Makefile.am b/external/ptsort/bin/Makefile.am
new file mode 100644
index 00000000..ef82a3f4
--- /dev/null
+++ b/external/ptsort/bin/Makefile.am
@@ -0,0 +1,5 @@
+AM_CPPFLAGS = -I$(top_srcdir)/lib
+bin_PROGRAMS = ptsort
+ptsort_SOURCES = ptsort.c
+ptsort_LDADD = $(top_builddir)/lib/libptsort.a
+dist_man1_MANS = ptsort.1
diff --git a/external/ptsort/bin/ptsort.1 b/external/ptsort/bin/ptsort.1
new file mode 100644
index 00000000..c37de93a
--- /dev/null
+++ b/external/ptsort/bin/ptsort.1
@@ -0,0 +1,158 @@
+.\"-
+.\" Copyright (c) 2016-2017 Dag-Erling Smørgrav
+.\" All rights reserved.
+.\"
+.\" 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. The name of the author may not be used to endorse or promote
+.\"    products derived from this software without specific prior written
+.\"    permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+.\"
+.Dd February 15, 2017
+.Dt PTSORT 1
+.Os
+.Sh NAME
+.Nm ptsort
+.Nd Prioritized topological sort
+.Sh SYNOPSIS
+.Nm
+.Op Fl Ddpqsv
+.Op Fl o Ar output
+.Op Ar input ...
+.Sh DESCRIPTION
+The
+.Nm
+utility takes a directed acyclic graph of nodes as input and outputs
+the nodes in topological order.
+Unlike
+.Xr tsort 1 ,
+the
+.Nm ptsort
+utility allows nodes to be given a numeric priority.
+Priorities are propagated along edges so that each node's priority is
+greater than the priority of all its successors.
+Thus, it is possible to boost a specific node so that it, and all its
+predecessors, will be listed ahead of other unrelated nodes.
+.Pp
+The following options are available:
+.Bl -tag -width Fl
+.It Fl D
+Sort the output by depth first instead of priority first.
+.It Fl d
+Include each node's depth in the output.
+.It Fl p
+Include each node's priority in the output.
+.It Fl q
+Quiet mode.
+Do not warn about cycles in the input.
+.It Fl s
+Strict mode.
+Cycles in the input will cause
+.Nm
+to terminate with an exit code of 3.
+.It Fl v
+Verbose mode.
+Show detailed information while building and traversing the graph.
+.El
+.Pp
+The
+.Nm
+utility takes its input either from the files listed on the command
+line or, if no files were specified, from the standard input.
+All input is read into the same graph before processing.
+.Pp
+Each input line contains either two names or a name and a decimal
+integer, separated by any amount of whitespace.
+Any amount of leading or trailing whitespace is permitted.
+Names are arbitrary non-empty sequences of up to 255 printable,
+non-whitespace ASCII characters.
+It is strictly speaking possible, but not a good idea, for a node's
+name to consist entirely of digits.
+.Pp
+If the line contains two names, the effect is to insert a directed
+edge into the graph going from the first (predecessor) node to the
+second (successor) node.
+Either or both nodes are created if they do not already exist.
+If both names are identical, no edge is inserted, but the node is
+still created unless it already exists.
+.Pp
+If the line contains a name and a number, the effect is to raise the
+priority of that node to the given number, unless it is already
+higher.
+The node will be created if it does not already exist.
+.Pp
+Blank lines in the input are ignored.
+.Pp
+Any error in the input will cause
+.Nm
+to print an error message which includes the offending line and
+terminate with an exit code of 2.
+.Pp
+If no error occurred, the
+.Nm
+utility ouputs one line for each node in the graph, consisting of the
+node's name optionally preceded by its depth (if the
+.Fl d
+option was specified) and / or priority (if the
+.Fl p
+option was specified).
+By default, the list is sorted in decreasing order of priority, then
+depth, then name.
+If the
+.Fl D
+option was specified, it is sorted in decreasing order of depth, then
+priority, then name.
+.Sh DIAGNOSTICS
+If an error occurred, the
+.Nm
+utility exits with one of the following codes:
+.Bl -tag -width 999
+.It 1
+An error occurred while opening or reading from an input file or while
+trying to allocate memory.
+.It 2
+A syntax error was encountered in the input.
+.It 3
+A cycle was detected while running in strict mode.
+.El
+.Pp
+Otherwise, it exits with code 0.
+.Sh SEE ALSO
+.Xr tsort 1
+.Sh AUTHORS
+The
+.Nm
+utility and this manual page were written by
+.An Dag-Erling Sm\(/orgrav Aq Mt des@des.no .
+.Sh BUGS
+The
+.Nm
+utility uses a completely different algorithm than the similar
+.Xr tsort 1
+and will therefore not produce the same output when given the same
+input, although the results will be topologically equivalent.
+.Pp
+The
+.Nm
+utility should probably have been named
+.Nm klatch ,
+but the author has no imagination or appreciation for the literary
+arts.
diff --git a/external/ptsort/bin/ptsort.c b/external/ptsort/bin/ptsort.c
new file mode 100644
index 00000000..177e1bcb
--- /dev/null
+++ b/external/ptsort/bin/ptsort.c
@@ -0,0 +1,461 @@
+/*-
+ * Copyright (c) 2016-2017 Dag-Erling Smørgrav
+ * All rights reserved.
+ *
+ * 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. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <err.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "aa_tree.h"
+#include "fline.h"
+
+static int bydepth;
+static int printdepth;
+static int printprio;
+static int quiet;
+static int strict;
+static int vlevel;
+
+#define verbose(...)							\
+	do {								\
+		if (vlevel > 0)						\
+			warnx(__VA_ARGS__);				\
+	} while (0)
+
+/*
+ * Quick character classification, assuming ASCII
+ */
+#define is_name(ch)							\
+	((unsigned char)(ch) >= '!' && (unsigned char)(ch) <= '~')
+#define is_number(ch)							\
+	((unsigned char)(ch) >= '0' && (unsigned char)(ch) <= '9')
+#define is_space(ch)							\
+	((unsigned char)(ch) == ' ' || (unsigned char)(ch) == '\t')
+
+/*
+ * Nodes in the graph.
+ *
+ * Each node has a name, a list of predecessors, a depth and a priority.
+ * The depth is the length of the node's longest chain of successors.  The
+ * priority is an integer in the range [prio, prio + P) where P is the
+ * highest number by which the node itself or any of its successors has
+ * been boosted.
+ */
+#define NAMELEN		 255
+
+typedef struct pnode {
+	char		 name[NAMELEN + 1];
+	aa_tree		 pred;
+	unsigned long	 depth;
+	unsigned long	 prio;
+} pnode;
+
+static aa_tree nodes;
+static unsigned long tnedges, tnnodes;
+
+/*
+ * Compare two nodes by their names.
+ */
+static aa_comparator pnode_namecmp = (aa_comparator)strcmp;
+
+/*
+ * Compare two nodes by their depths first and priorities second.
+ */
+static int
+pnode_depthcmp(const void *av, const void *bv)
+{
+	const pnode *a = av;
+	const pnode *b = bv;
+
+	return (a->depth > b->depth ? 1 : a->depth < b->depth ? -1 :
+	    a->prio > b->prio ? 1 : a->prio < b->prio ? -1 : 0);
+}
+
+static int
+pnodep_depthcmp(const void *av, const void *bv)
+{
+	const pnode *const *a = av;
+	const pnode *const *b = bv;
+
+	return (pnode_depthcmp(*a, *b));
+}
+
+/*
+ * Compare two nodes by their priorities first and depths second.
+ */
+static int
+pnode_priocmp(const void *av, const void *bv)
+{
+	const pnode *a = av;
+	const pnode *b = bv;
+
+	return (a->prio > b->prio ? 1 : a->prio < b->prio ? -1 :
+	    a->depth > b->depth ? 1 : a->depth < b->depth ? -1 : 0);
+}
+
+static int
+pnodep_priocmp(const void *av, const void *bv)
+{
+	const pnode *const *a = av;
+	const pnode *const *b = bv;
+
+	return (pnode_priocmp(*a, *b));
+}
+
+/*
+ * Allocate and initialize a new node.
+ */
+static pnode *
+pnode_new(void)
+{
+	pnode *n;
+
+	if ((n = calloc(1, sizeof *n)) == NULL)
+		err(1, "calloc()");
+	aa_init(&n->pred, pnode_namecmp);
+	n->prio = 0;
+	return (n);
+}
+
+#if 0
+/*
+ * Destroy a node.
+ */
+static void
+pnode_destroy(pnode *n)
+{
+
+	aa_destroy(&n->pred);
+	free(n);
+}
+#endif
+
+/*
+ * Recursively recalculate the depth and priority of a node and all its
+ * predecessors.  If the depth or priority of a node is less than the
+ * specified value, set it to that value and propagate the change to all
+ * of its predecessors, maintaining the invariant that a node's depth and
+ * priority are strictly greater than the depths and priorities of all its
+ * predecessors.
+ *
+ * In order to detect and break cycles, we mark a node busy by changing
+ * the last byte of its name buffer (which should be 0) while iterating
+ * over its children, then change it back when we are done.
+ */
+static void
+pnode_recalc(pnode *n, unsigned long depth, unsigned long prio)
+{
+	aa_iterator *nit;
+	pnode *p;
+
+	if (n->depth >= depth && n->prio >= prio)
+		return;
+	if (depth > n->depth)
+		verbose("increasing the depth of node %s from %lu to %lu",
+		    n->name, n->depth, depth);
+	if (prio > n->prio)
+		verbose("raising the priority of node %s from %lu to %lu",
+		    n->name, n->prio, prio);
+	n->depth = depth;
+	n->prio = prio;
+	n->name[NAMELEN] = '*';
+	for (p = aa_first(&n->pred, &nit); p != NULL; p = aa_next(&nit)) {
+		if (p->name[NAMELEN] != '\0') {
+			if (!quiet)
+				warnx("cycle involving %.*s and %.*s",
+				    NAMELEN, p->name, NAMELEN, n->name);
+			if (strict)
+				exit(3);
+			continue;
+		}
+		pnode_recalc(p, n->depth + 1, n->prio + 1);
+	}
+	aa_finish(&nit);
+	n->name[NAMELEN] = '\0';
+}
+
+/*
+ * Read nodes and edges from a file and construct our graph, setting and
+ * propagating node priorities as we go along.
+ *
+ * Each line is either:
+ *
+ * PREDNODE SUCCNODE
+ *    Insert an edge from PREDNODE to SUCCNODE
+ *
+ * NODE NUMBER
+ *    Raise NODE's priority to NUMBER if not already higher
+ *
+ * NODE NODE
+ *    Insert NODE if it doesn't already exist
+ *
+ * Node names are arbitrary sequences of up to 255 ASCII printable,
+ * non-whitespace characters.  However, it is not safe to give a node a
+ * name consisting entirely of digits, as it may be interpreted as a
+ * priority.
+ *
+ * We keep nodes in a sorted balanced search tree for easy lookup and
+ * deduplication.  Each node contains a NUL-terminated name (which is also
+ * the sorting key), a sorted balanced search tree of its predecessors and
+ * a priority.  When traversing the graph to propagate priorities, the
+ * last byte of the name is used as a processing mark for loop detection.
+ *
+ * We keep a node in reserve so we don't have to keep allocating new nodes
+ * and then freeing them when they turn out to already be in the tree.
+ * This way, we only allocate a new node when we've consumed the one we
+ * had on hand.
+ */
+static void
+input(const char *fn)
+{
+	FILE *f;
+	struct fline_buf *lb;
+	struct pnode *pn, *sn, *rn; /* pred / succ / reserve node */
+	struct pnode *n;
+	const char *pnb, *pne, *snb, *sne; /* pred / succ name beg / end */
+	const char *line, *p;
+	char *e;
+	unsigned long nlines, nedges, nnodes;
+	unsigned long prio;
+
+	/* allocate fline structure */
+	if ((lb = fline_new()) == NULL)
+		err(1, "fline_new()");
+
+	/* open input file */
+	if (fn == NULL || strcmp(fn, "-") == 0) {
+		fn = "stdin";
+		f = stdin;
+	} else if ((f = fopen(fn, "r")) == NULL) {
+		err(1, "%s", fn);
+	}
+
+	/* allocate our reserve node */
+	rn = pnode_new();
+
+	/* read line by line */
+	nlines = nedges = nnodes = 0;
+	while ((line = fline_read(f, lb)) != NULL) {
+		nlines++;
+		/* leading whitespace */
+		for (p = line; is_space(*p); p++)
+			/* nothing */;
+		/* ignore blank lines */
+		if (*p == '\n' || *p == '\0')
+			continue;
+		/* name of predecessor */
+		for (pnb = p; is_name(*p); p++)
+			/* nothing */;
+		/* separating whitespace */
+		for (pne = p; is_space(*p); p++)
+			/* nothing */;
+		/* name of successor *or* numeric priority */
+		for (snb = p; is_name(*p); p++)
+			/* nothing */;
+		/* trailing whitespace */
+		for (sne = p; is_space(*p); p++)
+			/* nothing */;
+		/* terminating newline */
+		if (*p == '\n')
+			p++;
+		/* check lengths */
+		if (pne - pnb == 0 || pne - pnb > NAMELEN ||
+		    sne - snb == 0 || sne - pnb > NAMELEN ||
+		    *p != '\0') {
+			errx(2, "%s:%lu: syntax error:\n%s", fn, nlines, line);
+			continue;
+		}
+		/* prepare predecessor node */
+		strncpy(rn->name, pnb, pne - pnb);
+		if ((pn = aa_insert(&nodes, rn)) == NULL)
+			err(1, "aa_insert()");
+		if (pn == rn) {
+			/* new node */
+			verbose("insert new node %s", pn->name);
+			rn = pnode_new();
+			nnodes++;
+		} else {
+			/* clear reserve for reuse */
+			memset(rn->name, 0, sizeof rn->name);
+		}
+		/* successor or priority */
+		prio = strtoul(snb, &e, 10);
+		if (e == sne) {
+			/* raise this node's priority */
+			pnode_recalc(pn, 0, prio);
+		} else if (pne - pnb == sne - snb &&
+		    strncmp(pnb, snb, pne - pnb) == 0) {
+			/* no-op for compatibility with tsort */
+			continue;
+		} else {
+			/* prepare successor node */
+			strncpy(rn->name, snb, sne - snb);
+			if ((sn = aa_insert(&nodes, rn)) == NULL)
+				err(1, "aa_insert()");
+			if (sn == rn) {
+				/* new node */
+				verbose("insert new node %s", sn->name);
+				rn = pnode_new();
+				nnodes++;
+			} else {
+				/* clear reserve for reuse */
+				memset(rn->name, 0, sizeof rn->name);
+			}
+			/* create the edge between predecessor and successor */
+			if ((n = aa_insert(&sn->pred, pn)) == NULL)
+				err(1, "aa_insert()");
+			if (n == pn) {
+				/* new edge */
+				verbose("insert new edge from %s to %s",
+				    pn->name, sn->name);
+				nedges++;
+				pnode_recalc(pn, sn->depth + 1, sn->prio + 1);
+			}
+		}
+	}
+	if (ferror(f))
+		err(1, "%s", fn);
+	if (f != stdin)
+		fclose(f);
+	fline_free(lb);
+	free(rn);
+	verbose("read %lu lines from %s", nlines, fn);
+	verbose("inserted %lu new nodes and %lu new edges", nnodes, nedges);
+	tnedges += nedges;
+	tnnodes += nnodes;
+}
+
+/*
+ * Output a partial ordering of the nodes in the graph.  We form an array
+ * of pointers to all of our notes, sort them by priority and print the
+ * names in reverse order.
+ */
+static void
+output(const char *fn)
+{
+	aa_iterator *nit;
+	pnode **all, **p;
+	pnode *n;
+	FILE *f;
+
+	/* allocate array of pointers */
+	if ((p = all = malloc(tnnodes * sizeof *all)) == NULL)
+		err(1, "malloc()");
+
+	/* copy nodes into array in lexical order */
+	for (n = aa_first(&nodes, &nit); n != NULL; n = aa_next(&nit))
+		*p++ = n;
+	aa_finish(&nit);
+	/* p now points one past the end of the array */
+
+	/* sort by priority */
+	qsort(all, tnnodes, sizeof *all,
+	    bydepth ? pnodep_depthcmp : pnodep_priocmp);
+
+	/* output to file or stdout */
+	if (fn == NULL)
+		f = stdout;
+	else if ((f = fopen(fn, "w")) == NULL)
+		err(1, "%s", fn);
+
+	/* reverse through the array and print each node's name */
+	while (p-- > all) {
+		if (printdepth)
+			fprintf(f, "%7lu ", (*p)->depth);
+		if (printprio)
+			fprintf(f, "%7lu ", (*p)->prio);
+		fprintf(f, "%s\n", (*p)->name);
+	}
+
+	/* done */
+	if (f != stdout)
+		fclose(f);
+}
+
+static void
+usage(void)
+{
+
+	fprintf(stderr, "usage: ptsort [-Ddpqsv] [-o output] [input ...]\n");
+	exit(1);
+}
+
+int
+main(int argc, char *argv[])
+{
+	const char *ofn = NULL;
+	int opt;
+
+	aa_init(&nodes, (aa_comparator)strcmp);
+
+	while ((opt = getopt(argc, argv, "Ddo:pqsv")) != -1)
+		switch (opt) {
+		case 'o':
+			ofn = optarg;
+			break;
+		case 'D':
+			bydepth = 1;
+			break;
+		case 'd':
+			printdepth = 1;
+			break;
+		case 'p':
+			printprio = 1;
+			break;
+		case 'q':
+			quiet = 1;
+			break;
+		case 's':
+			strict = 1;
+			break;
+		case 'v':
+			vlevel++;
+			break;
+		default:
+			usage();
+		}
+
+	argc -= optind;
+	argv += optind;
+
+	if (argc == 0)
+		input(NULL);
+	else
+		while (argc--)
+			input(*argv++);
+	verbose("graph has %lu nodes and %lu edges", tnnodes, tnedges);
+	output(ofn);
+	exit(0);
+}
diff --git a/external/ptsort/configure.ac b/external/ptsort/configure.ac
new file mode 100644
index 00000000..4429f0d4
--- /dev/null
+++ b/external/ptsort/configure.ac
@@ -0,0 +1,49 @@
+AC_PREREQ([2.63])
+AC_INIT([ptsort], [0.20170215], [des@des.no],
+    [ptsort], [https://www.github.com/dag-erling/ptsort])
+AC_CONFIG_SRCDIR([bin/ptsort.c])
+AC_CONFIG_MACRO_DIR([m4])
+AM_INIT_AUTOMAKE([foreign subdir-objects])
+AM_CONFIG_HEADER(lib/config.h)
+
+# C compiler and features
+AC_LANG(C)
+AC_PROG_CC
+AC_PROG_CC_STDC
+AC_PROG_CPP
+AC_GNU_SOURCE
+AC_C_CONST
+AC_C_VOLATILE
+
+# other programs
+AC_PROG_INSTALL
+AC_PROG_RANLIB
+
+# libraries
+save_LIBS="${LIBS}"
+LIBS=""
+AC_CHECK_LIB([cryb-test], [t_add_tests])
+LIBCRYB_TEST="${LIBS}"
+LIBS="${save_LIBS}"
+AC_SUBST(LIBCRYB_TEST)
+AM_CONDITIONAL([WITH_TESTS], [test x"${LIBCRYB_TEST}" != x""])
+
+# options
+AC_ARG_ENABLE([developer-warnings],
+    AS_HELP_STRING([--enable-developer-warnings], [enable strict warnings (default is NO)]),
+    [CFLAGS="${CFLAGS} -Wall -Wextra -Wcast-qual -Wshadow"])
+AC_ARG_ENABLE([debugging-symbols],
+    AS_HELP_STRING([--enable-debugging-symbols], [enable debugging symbols (default is NO)]),
+    [CFLAGS="${CFLAGS} -O0 -g -fno-inline"])
+AC_ARG_ENABLE([werror],
+    AS_HELP_STRING([--enable-werror], [use -Werror (default is NO)]),
+    [CFLAGS="${CFLAGS} -Werror"])
+
+# output
+AC_CONFIG_FILES([
+    Makefile
+    bin/Makefile
+    lib/Makefile
+    t/Makefile
+])
+AC_OUTPUT
diff --git a/external/ptsort/lib/.gitignore b/external/ptsort/lib/.gitignore
new file mode 100644
index 00000000..f282c157
--- /dev/null
+++ b/external/ptsort/lib/.gitignore
@@ -0,0 +1,3 @@
+config.h.in
+config.h
+stamp-h1
diff --git a/external/ptsort/lib/Makefile.am b/external/ptsort/lib/Makefile.am
new file mode 100644
index 00000000..20404cbd
--- /dev/null
+++ b/external/ptsort/lib/Makefile.am
@@ -0,0 +1,4 @@
+AM_CPPFLAGS = -I$(top_srcdir)/lib
+noinst_LIBRARIES = libptsort.a
+libptsort_a_SOURCES = aa_tree.c fline.c
+noinst_HEADERS = aa_tree.h fline.h
diff --git a/external/ptsort/lib/aa_tree.c b/external/ptsort/lib/aa_tree.c
new file mode 100644
index 00000000..1f391251
--- /dev/null
+++ b/external/ptsort/lib/aa_tree.c
@@ -0,0 +1,403 @@
+/*-
+ * Copyright (c) 2016 Universitetet i Oslo
+ * All rights reserved.
+ *
+ * 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. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "aa_tree.h"
+
+static aa_node aa_nil = {
+	.up = &aa_nil,
+	.left = &aa_nil,
+	.right = &aa_nil,
+	.level = 0,
+	.data = NULL,
+};
+
+#if AA_SLAB_ALLOCATOR
+
+typedef struct aa_slab aa_slab;
+
+struct aa_slab {
+	unsigned int	 size;
+	unsigned int	 free;
+	unsigned int	 lastused;
+	aa_slab		*next;
+	aa_node		*firstfree;
+	aa_node		 nodes[];
+};
+
+#define INITIAL_SLAB_SIZE 1048576
+static aa_slab *slabs;
+
+static aa_node *
+aa_alloc(aa_node *parent, void *data)
+{
+	aa_node *node;
+	aa_slab *slab;
+	unsigned int size;
+
+	/* search for a slab with free space */
+	for (slab = slabs; slab != NULL; slab = slab->next)
+		if (slab->free > 0)
+			break;
+	/* none?  create new slab */
+	if (slab == NULL) {
+		size = /* slabs ? slabs->size * 2 : */ INITIAL_SLAB_SIZE;
+		slab = malloc(sizeof *slab + size * sizeof slab->nodes[0]);
+		if (slab == NULL)
+			return (NULL);
+		slab->size = slab->free = size;
+		slab->lastused = 0;
+		slab->next = slabs;
+		slab->firstfree = NULL;
+		slabs = slab;
+	}
+	/* get first free node off slab */
+	if (slab->firstfree != NULL) {
+		/* previously returned */
+		node = slab->firstfree;
+		slab->firstfree = node->right;
+	} else {
+		/* never used before */
+		assert(slab->lastused < slab->size);
+		node = &slab->nodes[slab->lastused++];
+	}
+	slab->free--;
+	node->up = parent;
+	node->left = node->right = &aa_nil;
+	node->level = 1;
+	node->data = data;
+	return (node);
+}
+
+static void
+aa_free(aa_node *node)
+{
+	aa_slab *slab;
+
+	/* search for slab from which node was allocated */
+	for (slab = slabs; slab != NULL; slab = slab->next)
+		if (node >= slab->nodes && node < slab->nodes + slab->size)
+			break;
+	assert(slab != NULL);
+	/* clear node and prepend it to the free list */
+	node->up = NULL;
+	node->left = NULL;
+	node->right = slab->firstfree;
+	node->level = 0;
+	node->data = NULL;
+	slab->firstfree = node;
+	slab->free++;
+	if (slab->free == slab->size) {
+		/* XXX free the slab! */
+	}
+}
+
+#else
+
+static aa_node *
+aa_alloc(aa_node *parent, void *data)
+{
+	aa_node *node;
+
+	if ((node = calloc(1, sizeof *node)) == NULL)
+		return (NULL);
+	node->up = parent;
+	node->left = node->right = &aa_nil;
+	node->level = 1;
+	node->data = data;
+	return (node);
+}
+
+static void
+aa_free(aa_node *node)
+{
+
+	free(node);
+}
+
+#endif
+
+aa_tree *
+aa_init(aa_tree *tree, aa_comparator compare)
+{
+
+	if (tree == NULL && (tree = calloc(1, sizeof *tree)) == NULL)
+		return (NULL);
+	tree->compare = compare;
+	tree->root = &aa_nil;
+	tree->size = 0;
+	return (tree);
+}
+
+static aa_node *
+aa_skew(aa_node *node)
+{
+	aa_node *lc;
+
+	if (node != &aa_nil &&
+	    (lc = node->left) != &aa_nil &&
+	    node->level == lc->level) {
+		node->left = lc->right;
+		if (node->left != &aa_nil)
+			node->left->up = node;
+		lc->right = node;
+		lc->up = node->up;
+		node->up = lc;
+		node = lc;
+	}
+	return (node);
+}
+
+static aa_node *
+aa_split(aa_node *node)
+{
+	aa_node *rc;
+
+	if (node != &aa_nil &&
+	    (rc = node->right) != &aa_nil &&
+	    rc->right != &aa_nil &&
+	    node->level == rc->right->level) {
+		node->right = rc->left;
+		if (node->right != &aa_nil)
+			node->right->up = node;
+		rc->left = node;
+		rc->up = node->up;
+		node->up = rc;
+		rc->level++;
+		node = rc;
+	}
+	return (node);
+}
+
+static void *
+aa_insert_r(aa_tree *tree, aa_node *parent, aa_node **nodep, void *data)
+{
+	aa_node *node;
+	void *ret;
+	int cmp;
+
+	ret = NULL;
+	if ((node = *nodep) == &aa_nil) {
+		if ((node = aa_alloc(parent, data)) == NULL)
+			return (NULL);
+		tree->size++;
+		*nodep = node;
+		return (node->data);
+	} else if ((cmp = tree->compare(data, node->data)) == 0) {
+		return (node->data);
+	} else if (cmp < 0) {
+		ret = aa_insert_r(tree, node, &node->left, data);
+	} else if (cmp > 0) {
+		ret = aa_insert_r(tree, node, &node->right, data);
+	}
+	node = aa_split(aa_skew(node));
+	*nodep = node;
+	return (ret);
+}
+
+void *
+aa_insert(aa_tree *tree, void *data)
+{
+
+	assert(data != NULL);
+	return (aa_insert_r(tree, &aa_nil, &tree->root, data));
+}
+
+static aa_node *
+aa_delete_r(aa_tree *tree, aa_node **nodep, void *key)
+{
+	aa_node *node, *pred, *succ;
+	void *ret;
+	int cmp;
+
+	ret = NULL;
+	if ((node = *nodep) == &aa_nil) {
+		return (NULL);
+	} else if ((cmp = tree->compare(key, node->data)) == 0) {
+		if (node->left == &aa_nil && node->right == &aa_nil) {
+			ret = node->data;
+			aa_free(node);
+			*nodep = &aa_nil;
+			tree->size--;
+			return (ret);
+		} else if (node->left == &aa_nil) {
+			succ = node->right;
+			while (succ->left != &aa_nil)
+				succ = succ->left;
+			node->data = succ->data;
+			ret = aa_delete_r(tree, &node->right, succ->data);
+		} else {
+			pred = node->left;
+			while (pred->right != &aa_nil)
+				pred = pred->right;
+			node->data = pred->data;
+			ret = aa_delete_r(tree, &node->left, pred->data);
+		}
+	} else if (cmp < 0) {
+		ret = aa_delete_r(tree, &node->left, key);
+	} else if (cmp > 0) {
+		ret = aa_delete_r(tree, &node->right, key);
+	}
+	if (node->left->level < node->level - 1 ||
+	    node->right->level < node->level - 1)
+		node->level = node->level - 1;
+	node = aa_skew(node);
+	node->right = aa_skew(node->right);
+	node->right->right = aa_skew(node->right->right);
+	node = aa_split(node);
+	node->right = aa_split(node->right);
+	*nodep = node;
+	return (ret);
+}
+
+void *
+aa_delete(aa_tree *tree, void *key)
+{
+
+	assert(key != NULL);
+	return (aa_delete_r(tree, &tree->root, key));
+}
+
+void
+aa_destroy(aa_tree *tree)
+{
+
+	while (tree->root != &aa_nil)
+		aa_delete_r(tree, &tree->root, tree->root->data);
+}
+
+static void *
+aa_find_r(const aa_node *node, const void *key, aa_comparator compare)
+{
+	aa_node *ret;
+	int cmp;
+
+	ret = NULL;
+	if (node == &aa_nil)
+		ret = NULL;
+	else if ((cmp = compare(key, node->data)) == 0)
+		ret = node->data;
+	else if (cmp < 0)
+		ret = aa_find_r(node->left, key, compare);
+	else if (cmp > 0)
+		ret = aa_find_r(node->right, key, compare);
+	return (ret);
+}
+
+void *
+aa_find(const aa_tree *tree, const void *key)
+{
+
+	assert(key != NULL);
+	return (aa_find_r(tree->root, key, tree->compare));
+}
+
+void *
+aa_first(const aa_tree *tree, aa_iterator **iterp)
+{
+	aa_iterator *iter;
+	aa_node *node;
+
+	if ((*iterp = iter = calloc(1, sizeof *iter)) == NULL)
+		return (NULL);
+	node = tree->root;
+	while (node->left != &aa_nil)
+		node = node->left;
+	iter->cur = node;
+	return (node->data);
+}
+
+void *
+aa_next(aa_iterator **iterp)
+{
+	aa_iterator *iter = *iterp;
+
+	if (iter == NULL || iter->cur == &aa_nil)
+		return (NULL);
+
+	if (iter->cur->left != &aa_nil) {
+		/*
+		 * If this node has a left subtree, we have already
+		 * visited it, and we now need to go as far down the right
+		 * subtree as possible.
+		 */
+		iter->cur = iter->cur->right;
+		while (iter->cur->left != &aa_nil)
+			iter->cur = iter->cur->left;
+	} else if (iter->cur->right != &aa_nil) {
+		/*
+		 * If this node only has a right subtree, we have not yet
+		 * visited it, and we now need to go as far down the right
+		 * subtree as possible.
+		 */
+		iter->cur = iter->cur->right;
+		while (iter->cur->left != &aa_nil)
+			iter->cur = iter->cur->left;
+	} else if (iter->cur == iter->cur->up->left) {
+		/*
+		 * This node is its parent's left child; visit the parent.
+		 */
+		iter->cur = iter->cur->up;
+	} else if (iter->cur == iter->cur->up->right) {
+		/*
+		 * This node is its parent's right child; go up until we
+		 * reach a node which is its parent left child, then up
+		 * again.  This is also the path back to the root after
+		 * having visited the last node.
+		 */
+		iter->cur = iter->cur->up;
+		while (iter->cur != iter->cur->up->left)
+			iter->cur = iter->cur->up;
+		iter->cur = iter->cur->up;
+	} else {
+		/*
+		 * This is the only node in the tree; it has neither
+		 * children nor a parent, and we are done.
+		 */
+		iter->cur = &aa_nil;
+	}
+	return (iter->cur->data);
+}
+
+void
+aa_finish(aa_iterator **iterp)
+{
+	aa_iterator *iter = *iterp;
+
+	free(iter);
+	*iterp = NULL;
+}
diff --git a/external/ptsort/lib/aa_tree.h b/external/ptsort/lib/aa_tree.h
new file mode 100644
index 00000000..5c26c4dc
--- /dev/null
+++ b/external/ptsort/lib/aa_tree.h
@@ -0,0 +1,63 @@
+/*-
+ * Copyright (c) 2016 Universitetet i Oslo
+ * All rights reserved.
+ *
+ * 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. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+#ifndef AA_TREE_H_INCLUDED
+#define AA_TREE_H_INCLUDED
+
+typedef int (*aa_comparator)(const void *, const void *);
+
+typedef struct aa_tree {
+	struct aa_node	*root;
+	unsigned int	 size;
+	aa_comparator	 compare;
+} aa_tree;
+
+typedef struct aa_node {
+	struct aa_node	*up;
+	struct aa_node	*left;
+	struct aa_node	*right;
+	unsigned int	 level;
+	void		*data;
+} aa_node;
+
+typedef struct aa_iterator {
+	struct aa_node	*cur;
+} aa_iterator;
+
+aa_tree *aa_init(aa_tree *, aa_comparator);
+void aa_destroy(aa_tree *);
+void *aa_insert(aa_tree *, void *);
+void *aa_delete(aa_tree *, void *);
+void *aa_find(const aa_tree *, const void *);
+
+void *aa_first(const aa_tree *, aa_iterator **);
+void *aa_next(aa_iterator **);
+void aa_finish(aa_iterator **);
+
+#endif
diff --git a/external/ptsort/lib/fline.c b/external/ptsort/lib/fline.c
new file mode 100644
index 00000000..e2f89f75
--- /dev/null
+++ b/external/ptsort/lib/fline.c
@@ -0,0 +1,146 @@
+/*-
+ * Copyright (c) 2016 Dag-Erling Smørgrav
+ * All rights reserved.
+ *
+ * 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. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "fline.h"
+
+struct fline_buf {
+	FILE *curf;
+	char *buf, *line, *next, *end;
+	size_t len, size;
+};
+
+/*
+ * Allocate and initialize a fline buffer
+ */
+struct fline_buf *
+fline_new(void)
+{
+
+	return (calloc(1, sizeof(struct fline_buf)));
+}
+
+/*
+ * Free a fline buffer
+ */
+void
+fline_free(struct fline_buf *lb)
+{
+
+	free(lb->buf);
+	memset(lb, 0, sizeof *lb);
+	free(lb);
+}
+
+/*
+ * Read a full line of text from a stream
+ */
+const char *
+fline_read(FILE *f, struct fline_buf *lb)
+{
+	char *p, *q;
+	char *tmpbuf;
+	size_t r;
+
+	if (lb->buf == NULL) {
+		/* first call, allocate buffer */
+		lb->size = 1024;
+		if ((lb->buf = malloc(lb->size)) == NULL)
+			return (NULL);
+	}
+	if (f != lb->curf) {
+		/* first call for new file, reset pointers */
+		lb->next = lb->line = lb->end = lb->buf;
+		lb->len = 0;
+		lb->curf = f;
+	}
+
+	/*
+	 * See if we already have a full line waiting.
+	 */
+	for (p = q = lb->next; q < lb->end; ++q) {
+		if (*q == '\n') {
+			lb->next = q + 1;
+			*q = '\0';
+			return (p);
+		}
+	}
+
+	/*
+	 * Either our buffer is empty, or it only contains a partial line.
+	 * We need to read more data into it, and possibly expand it.
+	 * Start by moving the partial line (if any) up to the front.
+	 */
+	if (lb->next > lb->buf) {
+		/* shift everything up by next - buf */
+		lb->len = lb->end - lb->next;
+		memmove(lb->buf, lb->next, lb->len);
+		lb->next = lb->buf;
+		lb->end = lb->buf + lb->len;
+	}
+	for (;;) {
+		if (lb->len == lb->size) {
+			/* expand the buffer */
+			lb->size = lb->size * 2;
+			if ((tmpbuf = realloc(lb->buf, lb->size)) == NULL)
+				return (NULL);
+			lb->buf = tmpbuf;
+			lb->end = lb->buf + lb->len;
+		}
+		if ((r = fread(lb->end, 1, lb->size - lb->len, f)) == 0) {
+			/* either EOF or error */
+			if (lb->len == 0) {
+				/* we got nothing */
+				return (NULL);
+			}
+			/* whatever is left */
+			lb->next = lb->end + 1;
+			*lb->end = '\0';
+			return (lb->buf);
+		}
+		/* we got something, let's look for EOL */
+		lb->len += r;
+		lb->end += r;
+		for (p = q = lb->next; q < lb->end; ++q) {
+			if (*q == '\n') {
+				lb->next = q + 1;
+				*q = '\0';
+				return (p);
+			}
+		}
+		/* nothing, loop around */
+	}
+}
diff --git a/external/ptsort/lib/fline.h b/external/ptsort/lib/fline.h
new file mode 100644
index 00000000..4a1df51e
--- /dev/null
+++ b/external/ptsort/lib/fline.h
@@ -0,0 +1,37 @@
+/*-
+ * Copyright (c) 2016 Dag-Erling Smørgrav
+ * All rights reserved.
+ *
+ * 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. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+#ifndef FLINE_H_INCLUDED
+#define FLINE_H_INCLUDED
+
+struct fline_buf *fline_new(void);
+void fline_free(struct fline_buf *);
+const char *fline_read(FILE *, struct fline_buf *);
+
+#endif
diff --git a/external/ptsort/t/.gitignore b/external/ptsort/t/.gitignore
new file mode 100644
index 00000000..a4b118f6
--- /dev/null
+++ b/external/ptsort/t/.gitignore
@@ -0,0 +1,3 @@
+*.log
+*.trs
+t_aa
diff --git a/external/ptsort/t/Makefile.am b/external/ptsort/t/Makefile.am
new file mode 100644
index 00000000..05f46bea
--- /dev/null
+++ b/external/ptsort/t/Makefile.am
@@ -0,0 +1,11 @@
+AM_CPPFLAGS = -I$(top_srcdir)/lib
+LIBPSORT = $(top_builddir)/lib/libptsort.a
+
+if WITH_TESTS
+
+check_PROGRAMS = t_aa
+t_aa_LDADD = $(LIBPSORT) $(LIBCRYB_TEST)
+
+TESTS = $(check_PROGRAMS)
+
+endif
diff --git a/external/ptsort/t/t_aa.c b/external/ptsort/t/t_aa.c
new file mode 100644
index 00000000..f31493dc
--- /dev/null
+++ b/external/ptsort/t/t_aa.c
@@ -0,0 +1,170 @@
+/*-
+ * Copyright (c) 2016 Dag-Erling Smørgrav
+ * All rights reserved.
+ *
+ * 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. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior written
+ *    permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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.
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdint.h>
+#include <string.h>
+
+#include <cryb/test.h>
+
+#include "aa_tree.h"
+
+static struct t_aa_case {
+	const char	*desc;
+	int		 n;
+	int		 i[16];
+	int		 o[16];
+} t_aa_cases[] = {
+	/* trivial cases */
+	{
+		.desc	 = "empty",
+		.n	 = 0,
+		.i	 = { },
+		.o	 = { },
+	},
+	{
+		.desc	 = "single",
+		.n	 = 1,
+		.i	 = { 1 },
+		.o	 = { 1 },
+	},
+	/* seven basic shapes */
+	{
+		.desc	 = "right",
+		.n	 = 2,
+		.i	 = { 1, 2 },
+		.o	 = { 1, 2 },
+	},
+	{
+		.desc	 = "left",
+		.n	 = 2,
+		.i	 = { 2, 1 },
+		.o	 = { 1, 2 },
+	},
+	{
+		.desc	 = "both",
+		.n	 = 3,
+		.i	 = { 2, 1, 3 },
+		.o	 = { 1, 2, 3 },
+	},
+	{
+		.desc	 = "right dogleg",
+		.n	 = 3,
+		.i	 = { 1, 3, 2 },
+		.o	 = { 1, 2, 3 },
+	},
+	{
+		.desc	 = "left dogleg",
+		.n	 = 3,
+		.i	 = { 3, 1, 2 },
+		.o	 = { 1, 2, 3 },
+	},
+	{
+		.desc	 = "left-left",
+		.n	 = 3,
+		.i	 = { 3, 2, 1 },
+		.o	 = { 1, 2, 3 },
+	},
+	{
+		.desc	 = "right-right",
+		.n	 = 3,
+		.i	 = { 1, 2, 3 },
+		.o	 = { 1, 2, 3 },
+	},
+};
+
+#if 0
+static int num_s[] = {
+	 1,  2,  3,  4,
+	 5,  6,  7,  8,
+	 9, 10, 11, 12,
+	13, 14, 15, 16,
+};
+
+static int num_u[] = {
+	 1, 16,  6,  5,
+	 2, 15,  8,  7,
+	 3, 14, 10,  9,
+	 4, 13, 12, 11,
+};
+#endif
+
+static int
+t_aa_compare_i(const void *a, const void *b)
+{
+
+	return (*(const int *)a - *(const int *)b);
+}
+
+static int
+t_aa_test(char **desc CRYB_UNUSED, void *arg)
+{
+	struct t_aa_case *tc = arg;
+	aa_tree t;
+	aa_iterator *it;
+	int *e;
+	int i, ret;
+
+	aa_init(&t, t_aa_compare_i);
+	ret = t_compare_i(0, t.size);
+	for (i = 0; i < tc->n; ++i)
+		ret &= t_compare_ptr(&tc->i[i], aa_insert(&t, &tc->i[i]));
+	ret &= t_compare_i(tc->n, t.size);
+	e = aa_first(&t, &it);
+	if (tc->n == 0)
+		ret &= t_is_null(e);
+	else
+		ret &= t_compare_i(tc->o[0], *(int *)e);
+	for (i = 1; i < tc->n; ++i)
+		ret &= t_compare_i(tc->o[i], *(int *)aa_next(&it));
+	ret &= t_is_null(aa_next(&it));
+	aa_finish(&it);
+	aa_destroy(&t);
+	return (ret);
+}
+
+static int
+t_prepare(int argc CRYB_UNUSED, char *argv[] CRYB_UNUSED)
+{
+	unsigned int i;
+
+	for (i = 0; i < sizeof t_aa_cases / sizeof t_aa_cases[0]; ++i)
+		t_add_test(t_aa_test, &t_aa_cases[i], t_aa_cases[i].desc);
+	return (0);
+}
+
+int
+main(int argc, char *argv[])
+{
+
+	t_main(t_prepare, NULL, argc, argv);
+}