Update to ptsort 1.20170904

12 files changed, 256 insertions, 15 deletions

diff --git a/external/ptsort/HISTORY b/external/ptsort/HISTORY
index 7a417bc0..cb16f452 100644
--- a/external/ptsort/HISTORY
+++ b/external/ptsort/HISTORY
@@ -1 +1,2 @@
-https://github.com/dag-erling/ptsort/commits/master
+2017-09-04	1.20170904
+	First stable release.
diff --git a/external/ptsort/bin/ptsort.1 b/external/ptsort/bin/ptsort.1
index c37de93a..f0c42053 100644
--- a/external/ptsort/bin/ptsort.1
+++ b/external/ptsort/bin/ptsort.1
@@ -26,7 +26,7 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.Dd February 15, 2017
+.Dd September 4, 2017
 .Dt PTSORT 1
 .Os
 .Sh NAME
@@ -147,8 +147,8 @@ 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.
+and may therefore produce different (but toplogically equivalent)
+output when given the same input.
 .Pp
 The
 .Nm
diff --git a/external/ptsort/bin/ptsort.c b/external/ptsort/bin/ptsort.c
index 177e1bcb..57e9c1a0 100644
--- a/external/ptsort/bin/ptsort.c
+++ b/external/ptsort/bin/ptsort.c
@@ -182,14 +182,16 @@ pnode_recalc(pnode *n, unsigned long depth, unsigned long prio)
 
 	if (n->depth >= depth && n->prio >= prio)
 		return;
-	if (depth > n->depth)
+	if (depth > n->depth) {
 		verbose("increasing the depth of node %s from %lu to %lu",
 		    n->name, n->depth, depth);
-	if (prio > n->prio)
+		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->prio = prio;
+	}
 	n->name[NAMELEN] = '*';
 	for (p = aa_first(&n->pred, &nit); p != NULL; p = aa_next(&nit)) {
 		if (p->name[NAMELEN] != '\0') {
@@ -380,7 +382,7 @@ output(const char *fn)
 	aa_finish(&nit);
 	/* p now points one past the end of the array */
 
-	/* sort by priority */
+	/* sort by either priority or depth */
 	qsort(all, tnnodes, sizeof *all,
 	    bydepth ? pnodep_depthcmp : pnodep_priocmp);
 
@@ -402,6 +404,7 @@ output(const char *fn)
 	/* done */
 	if (f != stdout)
 		fclose(f);
+	free(all);
 }
 
 static void
diff --git a/external/ptsort/configure.ac b/external/ptsort/configure.ac
index 4429f0d4..a226cf08 100644
--- a/external/ptsort/configure.ac
+++ b/external/ptsort/configure.ac
@@ -1,5 +1,5 @@
 AC_PREREQ([2.63])
-AC_INIT([ptsort], [0.20170215], [des@des.no],
+AC_INIT([ptsort], [1.20170904], [des@des.no],
     [ptsort], [https://www.github.com/dag-erling/ptsort])
 AC_CONFIG_SRCDIR([bin/ptsort.c])
 AC_CONFIG_MACRO_DIR([m4])
@@ -45,5 +45,6 @@ AC_CONFIG_FILES([
     bin/Makefile
     lib/Makefile
     t/Makefile
+    t/t_subr.sh
 ])
 AC_OUTPUT
diff --git a/external/ptsort/lib/aa_tree.c b/external/ptsort/lib/aa_tree.c
index 1f391251..22676e4a 100644
--- a/external/ptsort/lib/aa_tree.c
+++ b/external/ptsort/lib/aa_tree.c
@@ -221,7 +221,7 @@ aa_insert_r(aa_tree *tree, aa_node *parent, aa_node **nodep, void *data)
 		return (node->data);
 	} else if (cmp < 0) {
 		ret = aa_insert_r(tree, node, &node->left, data);
-	} else if (cmp > 0) {
+	} else /* (cmp > 0) */ {
 		ret = aa_insert_r(tree, node, &node->right, data);
 	}
 	node = aa_split(aa_skew(node));
@@ -269,7 +269,7 @@ aa_delete_r(aa_tree *tree, aa_node **nodep, void *key)
 		}
 	} else if (cmp < 0) {
 		ret = aa_delete_r(tree, &node->left, key);
-	} else if (cmp > 0) {
+	} else /* (cmp > 0) */ {
 		ret = aa_delete_r(tree, &node->right, key);
 	}
 	if (node->left->level < node->level - 1 ||
@@ -313,7 +313,7 @@ aa_find_r(const aa_node *node, const void *key, aa_comparator compare)
 		ret = node->data;
 	else if (cmp < 0)
 		ret = aa_find_r(node->left, key, compare);
-	else if (cmp > 0)
+	else /* (cmp > 0) */
 		ret = aa_find_r(node->right, key, compare);
 	return (ret);
 }
@@ -338,7 +338,7 @@ aa_first(const aa_tree *tree, aa_iterator **iterp)
 	while (node->left != &aa_nil)
 		node = node->left;
 	iter->cur = node;
-	return (node->data);
+	return (iter->cur->data);
 }
 
 void *
diff --git a/external/ptsort/m4/.gitconfig b/external/ptsort/m4/.gitconfig
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/external/ptsort/m4/.gitconfig
diff --git a/external/ptsort/t/.gitignore b/external/ptsort/t/.gitignore
index a4b118f6..d4e3ff50 100644
--- a/external/ptsort/t/.gitignore
+++ b/external/ptsort/t/.gitignore
@@ -1,3 +1,4 @@
 *.log
 *.trs
 t_aa
+t_subr.sh
diff --git a/external/ptsort/t/Makefile.am b/external/ptsort/t/Makefile.am
index 05f46bea..093e2836 100644
--- a/external/ptsort/t/Makefile.am
+++ b/external/ptsort/t/Makefile.am
@@ -6,6 +6,14 @@ if WITH_TESTS
 check_PROGRAMS = t_aa
 t_aa_LDADD = $(LIBPSORT) $(LIBCRYB_TEST)
 
-TESTS = $(check_PROGRAMS)
+dist_check_SCRIPTS = t_dp_red.sh
+
+${dist_check_SCRIPTS}: t_subr.sh
+
+EXTRA_DIST = t_dp_red.ti t_dp_red.to
+
+TESTS = $(check_PROGRAMS) $(dist_check_SCRIPTS)
+
+CLEANFILES = t_subr.sh
 
 endif
diff --git a/external/ptsort/t/t_dp_red.sh b/external/ptsort/t/t_dp_red.sh
new file mode 100755
index 00000000..3fe29be8
--- /dev/null
+++ b/external/ptsort/t/t_dp_red.sh
@@ -0,0 +1,55 @@
+#!/bin/sh
+#-
+# Copyright (c) 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.
+#
+
+. t_subr.sh
+
+ifile="${abs_srcdir}/t_dp_red.ti"
+ofile="${abs_srcdir}/t_dp_red.to"
+tfile="${abs_builddir}/t_dp_red.t$$"
+
+ptsort() {
+	grep '^[^#]' "$1" |
+	    "${abs_top_builddir}/bin/ptsort" -dp ${_verbose:+"-v"} >"$2"
+}
+
+ptsort "${ifile}" "${tfile}"
+
+if cmp -s "${ofile}" "${tfile}" ; then
+	ok depth / priority reduction
+else
+	if [ -n "${_verbose}" ] ; then
+		diff --side-by-side --width 80 "${ofile}" "${tfile}" >&2
+	fi
+	not_ok depth / priority reduction
+fi
+
+rm -f "${tfile}"
+
+tap
diff --git a/external/ptsort/t/t_dp_red.ti b/external/ptsort/t/t_dp_red.ti
new file mode 100644
index 00000000..b662c2e6
--- /dev/null
+++ b/external/ptsort/t/t_dp_red.ti
@@ -0,0 +1,17 @@
+# Create a root node and enough successors to increase its depth to 3.
+r	a1
+a1	a2
+a2	a3
+r	b1
+b1	b2
+b2	b3
+
+# Boost the root node's priority.  Normally, this has no effect as it
+# is the root of the graph, but the bug causes the root's depth to be
+# reset to 0.
+r	99
+
+# Add more successors, which should have no effect on the root node,
+# but the bug causes its priority to be reset to 1 (and its depth
+# increased from 0 to 1).
+r	c1
diff --git a/external/ptsort/t/t_dp_red.to b/external/ptsort/t/t_dp_red.to
new file mode 100644
index 00000000..c8532250
--- /dev/null
+++ b/external/ptsort/t/t_dp_red.to
@@ -0,0 +1,8 @@
+      3      99 r
+      2       2 b1
+      2       2 a1
+      1       1 b2
+      1       1 a2
+      0       0 a3
+      0       0 c1
+      0       0 b3
diff --git a/external/ptsort/t/t_subr.sh.in b/external/ptsort/t/t_subr.sh.in
new file mode 100644
index 00000000..f08ba618
--- /dev/null
+++ b/external/ptsort/t/t_subr.sh.in
@@ -0,0 +1,147 @@
+#!/bin/sh
+#-
+# Copyright (c) 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.
+#
+
+#
+# Support code for writing TAP tests in Bourne shell
+#
+# To use this, add the following at the top of your test script:
+#
+# . t_subr.sh
+#
+# Run your tests, invoking either not_ok() or ok() after each.
+#
+# Finally, call tap() to print the output.
+#
+
+set -E
+
+# Who and where am I?
+selfbin=$(realpath "$0")
+selfdir="${selfbin%/*}"
+progname="${selfbin##*/}"
+
+# Source directories
+srcdir="@srcdir@"
+top_srcdir="@top_srcdir@"
+abs_srcdir="@abs_srcdir@"
+abs_top_srcdir="@abs_top_srcdir@"
+
+# Build directories
+builddir="@builddir@"
+top_builddir="@top_builddir@"
+abs_builddir="@abs_builddir@"
+abs_top_builddir="@abs_top_builddir@"
+
+# Verbose flag
+_verbose=
+
+# Number of tests, number of failed / passed tests, test output
+_n=0
+_n_not_ok=0
+
+_n_ok=0
+_tap=
+
+#
+# Print an error message and terminate.
+#
+error() {
+	echo "${progname}: $@" >&2
+	exit 1
+}
+
+#
+# Print a warning message.
+#
+warning() {
+	echo "${progname}: $@" >&2
+}
+
+#
+# Insert an informational message into the TAP output if the verbose
+# flag is set.
+#
+verbose() {
+	if [ -n "${_verbose}" ] ; then
+		_tap="${_tap}
+$@"
+	fi
+}
+
+#
+# Record a test as failed
+#
+not_ok() {
+	: $((_n=_n+1))
+	: $((_n_not_ok=_n_not_ok+1))
+	_tap="${_tap}
+not ok ${n} - $@"
+}
+
+#
+# Record a test as successful.
+#
+ok() {
+	: $((_n=_n+1))
+	: $((_n_ok=_n_ok+1))
+	_tap="${_tap}
+ok ${n} - $@"
+}
+
+#
+# Print the result.
+#
+tap() {
+	[ "${_n}" -gt 0 ] || exit 1
+	echo "1..${_n}${_tap}"
+	[ "${_n_not_ok}" -eq 0 ]
+}
+
+#
+# Print a usage message and terminate.
+#
+usage() {
+	echo "${progname} [-v]" >&2
+	exit 1
+}
+
+#
+# Parse command-line options.
+#
+while getopts "v" opt ; do
+	case "${opt}" in
+	v)
+		_verbose=1
+		;;
+	*)
+		usage
+		;;
+	esac
+done