Initial import of rcorder from NetBSD-current, using libnbcompat.

rcorder is designed to print out a dependency ordering of a set of
interdependent files. Typically it is used to find an execution
sequence for a set of shell scripts in which certain files must be
executed before others.

11 files changed, 1881 insertions, 0 deletions

diff --git a/pkgtools/rcorder/DESCR b/pkgtools/rcorder/DESCR
new file mode 100644
index 00000000000..3c454acb60a
--- /dev/null
+++ b/pkgtools/rcorder/DESCR
@@ -0,0 +1,4 @@
+rcorder is designed to print out a dependency ordering of a set of
+interdependent files. Typically it is used to find an execution
+sequence for a set of shell scripts in which certain files must be
+executed before others.
diff --git a/pkgtools/rcorder/Makefile b/pkgtools/rcorder/Makefile
new file mode 100644
index 00000000000..9384e9cf955
--- /dev/null
+++ b/pkgtools/rcorder/Makefile
@@ -0,0 +1,22 @@
+# $NetBSD: Makefile,v 1.1.1.1 2004/08/27 01:49:15 schmonz Exp $
+#
+
+DISTNAME=		rcorder-20040826
+CATEGORIES=		pkgtools
+MASTER_SITES=		# empty
+DISTFILES=		# empty
+
+MAINTAINER=		schmonz@NetBSD.org
+HOMEPAGE=		http://www.NetBSD.org/
+COMMENT=		Print a dependency ordering of interdependent files
+
+USE_BUILDLINK3=		# defined
+
+NO_CHECKSUM=		# defined
+MANCOMPRESSED_IF_MANZ=	yes
+
+do-extract:
+	@${CP} -Rp ${FILESDIR} ${WRKSRC}
+
+.include "../../pkgtools/libnbcompat/buildlink3.mk"
+.include "../../mk/bsd.pkg.mk"
diff --git a/pkgtools/rcorder/PLIST b/pkgtools/rcorder/PLIST
new file mode 100644
index 00000000000..59a61ee5456
--- /dev/null
+++ b/pkgtools/rcorder/PLIST
@@ -0,0 +1,4 @@
+@comment $NetBSD: PLIST,v 1.1.1.1 2004/08/27 01:49:15 schmonz Exp $
+sbin/rcorder
+man/cat8/rcorder.0
+man/man8/rcorder.8
diff --git a/pkgtools/rcorder/files/Makefile b/pkgtools/rcorder/files/Makefile
new file mode 100644
index 00000000000..5fd8cdfc86d
--- /dev/null
+++ b/pkgtools/rcorder/files/Makefile
@@ -0,0 +1,11 @@
+#       $NetBSD: Makefile,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $
+
+PROG=   rcorder
+LDADD=	-lnbcompat
+SRCS=   ealloc.c hash.c rcorder.c
+MAN=	rcorder.8
+
+BINDIR=	${PREFIX}/sbin
+MANDIR=	${PREFIX}/man
+
+.include <bsd.prog.mk>
diff --git a/pkgtools/rcorder/files/ealloc.c b/pkgtools/rcorder/files/ealloc.c
new file mode 100644
index 00000000000..6a73e515e5d
--- /dev/null
+++ b/pkgtools/rcorder/files/ealloc.c
@@ -0,0 +1,161 @@
+/*	$NetBSD: ealloc.c,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Adam de Boor.
+ *
+ * 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.
+ */
+
+/*
+ * Copyright (c) 1989 by Berkeley Softworks
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Adam de Boor.
+ *
+ * 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. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. 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.
+ */
+
+#include <nbcompat.h>
+
+#if HAVE_SYS_CDEFS_H
+#include <sys/cdefs.h>
+#endif
+#ifndef lint
+__RCSID("$NetBSD: ealloc.c,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $");
+#endif /* not lint */
+
+#if HAVE_STDIO_H
+#include <stdio.h>
+#endif
+#if HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if HAVE_STRING_H
+#include <string.h>
+#endif
+#if HAVE_ERR_H
+#include <err.h>
+#endif
+
+#include "ealloc.h"
+
+static void enomem(void);
+
+/*
+ * enomem --
+ *	die when out of memory.
+ */
+static void
+enomem(void)
+{
+
+	errx(2, "Cannot allocate memory.");
+}
+
+/*
+ * emalloc --
+ *	malloc, but die on error.
+ */
+void *
+emalloc(size_t len)
+{
+	void	*p;
+
+	if ((p = malloc(len)) == NULL)
+		enomem();
+	return(p);
+}
+
+/*
+ * estrdup --
+ *	strdup, but die on error.
+ */
+char *
+estrdup(const char *str)
+{
+	char	*p;
+
+	if ((p = strdup(str)) == NULL)
+		enomem();
+	return(p);
+}
+
+/*
+ * erealloc --
+ *	realloc, but die on error.
+ */
+void *
+erealloc(void *ptr, size_t size)
+{
+
+	if ((ptr = realloc(ptr, size)) == NULL)
+		enomem();
+	return(ptr);
+}
+
+/*
+ * ecalloc --
+ *	calloc, but die on error.
+ */
+void *
+ecalloc(size_t nmemb, size_t size)
+{
+	void	*ptr;
+
+	if ((ptr = calloc(nmemb, size)) == NULL)
+		enomem();
+	return(ptr);
+}
diff --git a/pkgtools/rcorder/files/ealloc.h b/pkgtools/rcorder/files/ealloc.h
new file mode 100644
index 00000000000..7dee832fb47
--- /dev/null
+++ b/pkgtools/rcorder/files/ealloc.h
@@ -0,0 +1,6 @@
+/*	$NetBSD: ealloc.h,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $	*/
+
+void	*emalloc(size_t);
+char	*estrdup(const char *);
+void	*erealloc(void *, size_t);
+void	*ecalloc(size_t, size_t);
diff --git a/pkgtools/rcorder/files/hash.c b/pkgtools/rcorder/files/hash.c
new file mode 100644
index 00000000000..8a3deb91842
--- /dev/null
+++ b/pkgtools/rcorder/files/hash.c
@@ -0,0 +1,479 @@
+/*	$NetBSD: hash.c,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Adam de Boor.
+ *
+ * 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.
+ */
+
+/*
+ * Copyright (c) 1988, 1989 by Adam de Boor
+ * Copyright (c) 1989 by Berkeley Softworks
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Adam de Boor.
+ *
+ * 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. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. 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.
+ */
+
+#include <nbcompat.h>
+
+#ifdef MAKE_BOOTSTRAP
+static char rcsid[] = "$NetBSD: hash.c,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $";
+#else
+#if HAVE_SYS_CDEFS_H
+#include <sys/cdefs.h>
+#endif
+#ifndef lint
+#if 0
+static char sccsid[] = "@(#)hash.c	8.1 (Berkeley) 6/6/93";
+#else
+__RCSID("$NetBSD: hash.c,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $");
+#endif
+#endif /* not lint */
+#endif
+
+#if HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+
+#if HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if HAVE_STRING_H
+#include <string.h>
+#endif
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+
+/* hash.c --
+ *
+ * 	This module contains routines to manipulate a hash table.
+ * 	See hash.h for a definition of the structure of the hash
+ * 	table.  Hash tables grow automatically as the amount of
+ * 	information increases.
+ */
+#include "hash.h"
+#include "ealloc.h"
+
+/*
+ * Forward references to local procedures that are used before they're
+ * defined:
+ */
+
+static void RebuildTable(Hash_Table *);
+
+/*
+ * The following defines the ratio of # entries to # buckets
+ * at which we rebuild the table to make it larger.
+ */
+
+#define rebuildLimit 8
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_InitTable --
+ *
+ *	This routine just sets up the hash table.
+ *
+ * Input:
+ *	t		Structure to use to hold table.
+ *	numBuckets	How many buckets to create for starters.  This number
+ *			is rounded up to a power of two.  If <= 0, a reasonable
+ *			default is chosen. The table will grow in size later
+ *			as needed.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	Memory is allocated for the initial bucket area.
+ *
+ *---------------------------------------------------------
+ */
+
+void
+Hash_InitTable(Hash_Table *t, int numBuckets)
+{
+	int i;
+	struct Hash_Entry **hp;
+
+	/*
+	 * Round up the size to a power of two.
+	 */
+	if (numBuckets <= 0)
+		i = 16;
+	else {
+		for (i = 2; i < numBuckets; i <<= 1)
+			 continue;
+	}
+	t->numEntries = 0;
+	t->size = i;
+	t->mask = i - 1;
+	t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
+	while (--i >= 0)
+		*hp++ = NULL;
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_DeleteTable --
+ *
+ *	This routine removes everything from a hash table
+ *	and frees up the memory space it occupied (except for
+ *	the space in the Hash_Table structure).
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	Lots of memory is freed up.
+ *
+ *---------------------------------------------------------
+ */
+
+void
+Hash_DeleteTable(Hash_Table *t)
+{
+	struct Hash_Entry **hp, *h, *nexth;
+	int i;
+
+	nexth = NULL;
+	for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
+		for (h = *hp++; h != NULL; h = nexth) {
+			nexth = h->next;
+			free((char *)h);
+		}
+	}
+	free((char *)t->bucketPtr);
+
+	/*
+	 * Set up the hash table to cause memory faults on any future access
+	 * attempts until re-initialization.
+	 */
+	t->bucketPtr = NULL;
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_FindEntry --
+ *
+ * 	Searches a hash table for an entry corresponding to key.
+ *
+ * Input:
+ *	t	Hash table to search.
+ *	key	A hash key.
+ *
+ * Results:
+ *	The return value is a pointer to the entry for key,
+ *	if key was present in the table.  If key was not
+ *	present, NULL is returned.
+ *
+ * Side Effects:
+ *	None.
+ *
+ *---------------------------------------------------------
+ */
+
+Hash_Entry *
+Hash_FindEntry(Hash_Table *t, char *key)
+{
+	Hash_Entry *e;
+	unsigned h;
+	char *p;
+
+	for (h = 0, p = key; *p;)
+		h = (h << 5) - h + *p++;
+	p = key;
+	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
+		if (e->namehash == h && strcmp(e->name, p) == 0)
+			return (e);
+	return (NULL);
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_CreateEntry --
+ *
+ *	Searches a hash table for an entry corresponding to
+ *	key.  If no entry is found, then one is created.
+ *
+ * Input:
+ * 	t	Hash table to search.
+ *	key	A hash key.
+ *	newPtr	Filled in with 1 if new entry created, 0 otherwise.
+ *
+ * Results:
+ *	The return value is a pointer to the entry.  If *newPtr
+ *	isn't NULL, then *newPtr is filled in with TRUE if a
+ *	new entry was created, and FALSE if an entry already existed
+ *	with the given key.
+ *
+ * Side Effects:
+ *	Memory may be allocated, and the hash buckets may be modified.
+ *---------------------------------------------------------
+ */
+
+Hash_Entry *
+Hash_CreateEntry(Hash_Table *t, char *key, int *newPtr)
+{
+	Hash_Entry *e;
+	unsigned h;
+	char *p;
+	int keylen;
+	struct Hash_Entry **hp;
+
+	/*
+	 * Hash the key.  As a side effect, save the length (strlen) of the
+	 * key in case we need to create the entry.
+	 */
+	for (h = 0, p = key; *p;)
+		h = (h << 5) - h + *p++;
+	keylen = p - key;
+	p = key;
+	for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
+		if (e->namehash == h && strcmp(e->name, p) == 0) {
+			if (newPtr != NULL)
+				*newPtr = 0;
+			return (e);
+		}
+	}
+
+	/*
+	 * The desired entry isn't there.  Before allocating a new entry,
+	 * expand the table if necessary (and this changes the resulting
+	 * bucket chain).
+	 */
+	if (t->numEntries >= rebuildLimit * t->size)
+		RebuildTable(t);
+	e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
+	hp = &t->bucketPtr[h & t->mask];
+	e->next = *hp;
+	*hp = e;
+	e->clientData = NULL;
+	e->namehash = h;
+	(void) strcpy(e->name, p);
+	t->numEntries++;
+
+	if (newPtr != NULL)
+		*newPtr = 1;
+	return (e);
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_DeleteEntry --
+ *
+ * 	Delete the given hash table entry and free memory associated with
+ *	it.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	Hash chain that entry lives in is modified and memory is freed.
+ *
+ *---------------------------------------------------------
+ */
+
+void
+Hash_DeleteEntry(Hash_Table *t, Hash_Entry *e)
+{
+	Hash_Entry **hp, *p;
+
+	if (e == NULL)
+		return;
+	for (hp = &t->bucketPtr[e->namehash & t->mask];
+	     (p = *hp) != NULL; hp = &p->next) {
+		if (p == e) {
+			*hp = p->next;
+			free((char *)p);
+			t->numEntries--;
+			return;
+		}
+	}
+	(void)write(2, "bad call to Hash_DeleteEntry\n", 29);
+	abort();
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_EnumFirst --
+ *	This procedure sets things up for a complete search
+ *	of all entries recorded in the hash table.
+ *
+ * Input:
+ *	t		Table to be searched.
+ *	searchPtr	Area in which to keep state about search.
+ *
+ * Results:
+ *	The return value is the address of the first entry in
+ *	the hash table, or NULL if the table is empty.
+ *
+ * Side Effects:
+ *	The information in searchPtr is initialized so that successive
+ *	calls to Hash_Next will return successive HashEntry's
+ *	from the table.
+ *
+ *---------------------------------------------------------
+ */
+
+Hash_Entry *
+Hash_EnumFirst(Hash_Table *t, Hash_Search *searchPtr)
+{
+
+	searchPtr->tablePtr = t;
+	searchPtr->nextIndex = 0;
+	searchPtr->hashEntryPtr = NULL;
+	return Hash_EnumNext(searchPtr);
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * Hash_EnumNext --
+ *    This procedure returns successive entries in the hash table.
+ *
+ * Results:
+ *    The return value is a pointer to the next HashEntry
+ *    in the table, or NULL when the end of the table is
+ *    reached.
+ *
+ * Side Effects:
+ *    The information in searchPtr is modified to advance to the
+ *    next entry.
+ *
+ *---------------------------------------------------------
+ */
+
+Hash_Entry *
+Hash_EnumNext(Hash_Search *searchPtr)
+{
+	Hash_Entry *e;
+	Hash_Table *t = searchPtr->tablePtr;
+
+	/*
+	 * The hashEntryPtr field points to the most recently returned
+	 * entry, or is nil if we are starting up.  If not nil, we have
+	 * to start at the next one in the chain.
+	 */
+	e = searchPtr->hashEntryPtr;
+	if (e != NULL)
+		e = e->next;
+	/*
+	 * If the chain ran out, or if we are starting up, we need to
+	 * find the next nonempty chain.
+	 */
+	while (e == NULL) {
+		if (searchPtr->nextIndex >= t->size)
+			return (NULL);
+		e = t->bucketPtr[searchPtr->nextIndex++];
+	}
+	searchPtr->hashEntryPtr = e;
+	return (e);
+}
+
+/*
+ *---------------------------------------------------------
+ *
+ * RebuildTable --
+ *	This local routine makes a new hash table that
+ *	is larger than the old one.
+ *
+ * Results:
+ * 	None.
+ *
+ * Side Effects:
+ *	The entire hash table is moved, so any bucket numbers
+ *	from the old table are invalid.
+ *
+ *---------------------------------------------------------
+ */
+
+static void
+RebuildTable(Hash_Table *t)
+{
+	Hash_Entry *e, *next, **hp, **xp;
+	int i, mask;
+        Hash_Entry **oldhp;
+	int oldsize;
+
+	next = NULL;
+	oldhp = t->bucketPtr;
+	oldsize = i = t->size;
+	i <<= 1;
+	t->size = i;
+	t->mask = mask = i - 1;
+	t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);
+	while (--i >= 0)
+		*hp++ = NULL;
+	for (hp = oldhp, i = oldsize; --i >= 0;) {
+		for (e = *hp++; e != NULL; e = next) {
+			next = e->next;
+			xp = &t->bucketPtr[e->namehash & mask];
+			e->next = *xp;
+			*xp = e;
+		}
+	}
+	free((char *)oldhp);
+}
diff --git a/pkgtools/rcorder/files/hash.h b/pkgtools/rcorder/files/hash.h
new file mode 100644
index 00000000000..99bf669211d
--- /dev/null
+++ b/pkgtools/rcorder/files/hash.h
@@ -0,0 +1,161 @@
+/*	$NetBSD: hash.h,v 1.1.1.1 2004/08/27 01:49:16 schmonz Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Adam de Boor.
+ *
+ * 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.
+ *
+ *	from: @(#)hash.h	8.1 (Berkeley) 6/6/93
+ */
+
+/*
+ * Copyright (c) 1988, 1989 by Adam de Boor
+ * Copyright (c) 1989 by Berkeley Softworks
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Adam de Boor.
+ *
+ * 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. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. 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.
+ *
+ *	from: @(#)hash.h	8.1 (Berkeley) 6/6/93
+ */
+
+/* hash.h --
+ *
+ * 	This file contains definitions used by the hash module,
+ * 	which maintains hash tables.
+ */
+
+#ifndef	_HASH
+#define	_HASH
+
+/*
+ * The following defines one entry in the hash table.
+ */
+
+typedef struct Hash_Entry {
+	struct	Hash_Entry *next;	/* Used to link together all the
+					 * entries associated with the same
+					 * bucket. */
+	void		*clientData;	/* Arbitrary piece of data associated
+					 * with key. */
+	unsigned	namehash;	/* hash value of key */
+	char		name[1];	/* key string */
+} Hash_Entry;
+
+typedef struct Hash_Table {
+	struct	Hash_Entry **bucketPtr;
+				/* Pointers to Hash_Entry, one
+				 * for each bucket in the table. */
+	int 	size;		/* Actual size of array. */
+	int 	numEntries;	/* Number of entries in the table. */
+	int 	mask;		/* Used to select bits for hashing. */
+} Hash_Table;
+
+/*
+ * The following structure is used by the searching routines
+ * to record where we are in the search.
+ */
+
+typedef struct Hash_Search {
+	Hash_Table	*tablePtr;	/* Table being searched. */
+	int	 	nextIndex;	/* Next bucket to check (after
+					 * current). */
+	Hash_Entry 	*hashEntryPtr;	/* Next entry to check in current
+					 * bucket. */
+} Hash_Search;
+
+/*
+ * Macros.
+ */
+
+/*
+ * void *Hash_GetValue(h)
+ *     Hash_Entry *h;
+ */
+
+#define Hash_GetValue(h) ((h)->clientData)
+
+/*
+ * Hash_SetValue(h, val);
+ *     Hash_Entry *h;
+ *     char *val;
+ */
+
+#define Hash_SetValue(h, val) ((h)->clientData = (void *) (val))
+
+/*
+ * Hash_GetKey(h);
+ *     Hash_Entry *h;
+ */
+
+#define Hash_GetKey(h) ((h)->name)
+
+/*
+ * Hash_Size(n) returns the number of words in an object of n bytes
+ */
+
+#define	Hash_Size(n)	(((n) + sizeof (int) - 1) / sizeof (int))
+
+void Hash_InitTable(Hash_Table *, int);
+void Hash_DeleteTable(Hash_Table *);
+Hash_Entry *Hash_FindEntry(Hash_Table *, char *);
+Hash_Entry *Hash_CreateEntry(Hash_Table *, char *, int *);
+void Hash_DeleteEntry(Hash_Table *, Hash_Entry *);
+Hash_Entry *Hash_EnumFirst(Hash_Table *, Hash_Search *);
+Hash_Entry *Hash_EnumNext(Hash_Search *);
+
+#endif /* _HASH */
diff --git a/pkgtools/rcorder/files/rcorder.8 b/pkgtools/rcorder/files/rcorder.8
new file mode 100644
index 00000000000..852ec746524
--- /dev/null
+++ b/pkgtools/rcorder/files/rcorder.8
@@ -0,0 +1,168 @@
+.\"	$NetBSD: rcorder.8,v 1.1.1.1 2004/08/27 01:49:15 schmonz Exp $
+.\"
+.\" Copyright (c) 1998
+.\" 	Perry E. Metzger.  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. All advertising materials mentioning features or use of this software
+.\"    must display the following acknowledgment:
+.\"	This product includes software developed for the NetBSD Project
+.\"	by Perry E. Metzger.
+.\" 4. 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 ``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 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 April 23, 2003
+.Dt RCORDER 8
+.Os
+.Sh NAME
+.Nm rcorder
+.Nd print a dependency ordering of interdependent files
+.Sh SYNOPSIS
+.Nm
+.Op Fl k Ar keep
+.Op Fl s Ar skip
+.Ar
+.Sh DESCRIPTION
+.Nm
+is designed to print out a dependency ordering of a set of
+interdependent files.
+Typically it is used to find an execution sequence for a set of
+shell scripts in which certain files must be executed before others.
+.Pp
+Each file passed to
+.Nm
+should be annotated with special lines (which look like comments to the
+shell) which indicate the dependencies the files have upon certain
+points in the sequence, known as
+.Dq conditions ,
+and which indicate, for each file, which
+.Dq conditions
+may be expected to be filled by that file.
+.Pp
+Within each file, a block containing a series of
+.Dq REQUIRE ,
+.Dq PROVIDE ,
+.Dq BEFORE
+and
+.Dq KEYWORD
+lines should appear.
+The format of the lines is rigid.
+Each line must begin with a single
+.Dq # ,
+followed by a single space, followed by
+.Dq PROVIDE: ,
+.Dq REQUIRE: ,
+.Dq BEFORE: ,
+or
+.Dq KEYWORD: .
+No deviation is permitted.
+Each dependency line is then followed by a series of conditions,
+separated by whitespace.
+Multiple
+.Dq PROVIDE ,
+.Dq REQUIRE ,
+.Dq BEFORE
+and
+.Dq KEYWORD
+lines may appear, but all such lines must appear in a sequence without
+any intervening lines, as once a line that does not follow the format
+is reached, parsing stops.
+.Pp
+The options are as follows:
+.Bl -tag -width Ds
+.It Fl k
+Add the specified keyword to the
+.Dq keep list .
+If any
+.Fl k
+option is given, only those files containing the matching keyword are listed.
+.It Fl s
+Add the specified keyword to the
+.Dq skip list .
+If any
+.Fl s
+option is given, files containing the matching keyword are not listed.
+.El
+.Pp
+ An example block follows:
+.Bd -literal -offset indent
+# REQUIRE: networking syslog
+# REQUIRE: usr
+# PROVIDE: dns nscd
+.Ed
+.Pp
+This block states that the file in which it appears depends upon the
+.Dq networking ,
+.Dq syslog ,
+and
+.Dq usr
+conditions, and provides the
+.Dq dns
+and
+.Dq nscd
+conditions.
+.Pp
+A file may contain zero
+.Dq PROVIDE
+lines, in which case it provides no conditions, and may contain zero
+.Dq REQUIRE
+lines, in which case it has no dependencies.
+A file containing no
+.Dq PROVIDE ,
+.Dq REQUIRE ,
+or
+.Dq BEFORE
+lines may be output at an arbitrary position in the dependency
+ordering.
+.Pp
+There must be at least one file with no dependencies in the set of
+arguments passed to
+.Nm
+in order for it to find a starting place in the dependency ordering.
+.Sh DIAGNOSTICS
+.Nm
+may print one of the following error messages and exit with a non-zero
+status if it encounters an error while processing the file list.
+.Bl -diag
+.It "Requirement %s has no providers, aborting."
+No file has a
+.Dq PROVIDE
+line corresponding to a condition present in a
+.Dq REQUIRE
+line in another file.
+.It "Circular dependency on provision %s, aborting."
+A set of files has a circular dependency which was detected while
+processing the stated condition.
+.It "Circular dependency on file %s, aborting."
+A set of files has a circular dependency which was detected while
+processing the stated file.
+.El
+.Sh SEE ALSO
+.Xr rc 8
+.Sh HISTORY
+The
+.Nm
+program first appeared in
+.Nx 1.5 .
+.Sh AUTHORS
+Written by Perry E. Metzger (perry@piermont.com) and
+Matthew R. Green (mrg@eterna.com.au).
diff --git a/pkgtools/rcorder/files/rcorder.c b/pkgtools/rcorder/files/rcorder.c
new file mode 100644
index 00000000000..cca0e8d77c4
--- /dev/null
+++ b/pkgtools/rcorder/files/rcorder.c
@@ -0,0 +1,779 @@
+/*	$NetBSD: rcorder.c,v 1.1.1.1 2004/08/27 01:49:15 schmonz Exp $	*/
+
+/*
+ * Copyright (c) 1998, 1999 Matthew R. Green
+ * 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 ``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 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.
+ */
+
+/*
+ * Copyright (c) 1998
+ * 	Perry E. Metzger.  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. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed for the NetBSD Project
+ *	by Perry E. Metzger.
+ * 4. 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 ``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 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.
+ */
+
+#include <nbcompat.h>
+
+#if HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+#if HAVE_SYS_STAT_H
+#include <sys/stat.h>
+#endif
+
+#if HAVE_ERR_H
+#include <err.h>
+#endif
+#if HAVE_STDIO_H
+#include <stdio.h>
+#endif
+#if HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if HAVE_STRING_H
+#include <string.h>
+#endif
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+
+#include "ealloc.h"
+#include "hash.h"
+
+#ifdef DEBUG
+int debug = 0;
+# define	DPRINTF(args) if (debug) { fflush(stdout); fprintf args; }
+#else
+# define	DPRINTF(args)
+#endif
+
+#define REQUIRE_STR	"# REQUIRE:"
+#define REQUIRE_LEN	(sizeof(REQUIRE_STR) - 1)
+#define REQUIRES_STR	"# REQUIRES:"
+#define REQUIRES_LEN	(sizeof(REQUIRES_STR) - 1)
+#define PROVIDE_STR	"# PROVIDE:"
+#define PROVIDE_LEN	(sizeof(PROVIDE_STR) - 1)
+#define PROVIDES_STR	"# PROVIDES:"
+#define PROVIDES_LEN	(sizeof(PROVIDES_STR) - 1)
+#define BEFORE_STR	"# BEFORE:"
+#define BEFORE_LEN	(sizeof(BEFORE_STR) - 1)
+#define KEYWORD_STR	"# KEYWORD:"
+#define KEYWORD_LEN	(sizeof(KEYWORD_STR) - 1)
+#define KEYWORDS_STR	"# KEYWORDS:"
+#define KEYWORDS_LEN	(sizeof(KEYWORDS_STR) - 1)
+
+int exit_code;
+int file_count;
+char **file_list;
+
+enum {
+	RESET	= 0,
+	SET	= 1,
+};
+
+Hash_Table provide_hash_s, *provide_hash;
+
+typedef struct provnode provnode;
+typedef struct filenode filenode;
+typedef struct f_provnode f_provnode;
+typedef struct f_reqnode f_reqnode;
+typedef struct strnodelist strnodelist;
+
+struct provnode {
+	int		head;
+	int		in_progress;
+	filenode	*fnode;
+	provnode	*next, *last;
+};
+
+struct f_provnode {
+	provnode	*pnode;
+	f_provnode	*next;
+};
+
+struct f_reqnode {
+	Hash_Entry	*entry;
+	f_reqnode	*next;
+};
+
+struct strnodelist {
+	filenode	*node;
+	strnodelist	*next;
+	char		s[1];
+};
+
+struct filenode {
+	char		*filename;
+	int		in_progress;
+	filenode	*next, *last;
+	f_reqnode	*req_list;
+	f_provnode	*prov_list;
+	strnodelist	*keyword_list;
+};
+
+filenode fn_head_s, *fn_head;
+
+strnodelist *bl_list;
+strnodelist *keep_list;
+strnodelist *skip_list;
+
+void do_file(filenode *fnode);
+void strnode_add(strnodelist **, char *, filenode *);
+int skip_ok(filenode *fnode);
+int keep_ok(filenode *fnode);
+void satisfy_req(f_reqnode *rnode, char *);
+void crunch_file(char *);
+void parse_line(filenode *, char *, void (*)(filenode *, char *));
+filenode *filenode_new(char *);
+void add_require(filenode *, char *);
+void add_provide(filenode *, char *);
+void add_before(filenode *, char *);
+void add_keyword(filenode *, char *);
+void insert_before(void);
+Hash_Entry *make_fake_provision(filenode *);
+void crunch_all_files(void);
+void initialize(void);
+void generate_ordering(void);
+int main(int, char *[]);
+
+int
+main(int argc, char *argv[])
+{
+	int ch;
+
+	while ((ch = getopt(argc, argv, "dk:s:")) != -1)
+		switch (ch) {
+		case 'd':
+#ifdef DEBUG
+			debug = 1;
+#else
+			warnx("debugging not compiled in, -d ignored");
+#endif
+			break;
+		case 'k':
+			strnode_add(&keep_list, optarg, 0);
+			break;
+		case 's':
+			strnode_add(&skip_list, optarg, 0);
+			break;
+		default:
+			/* XXX should crunch it? */
+			break;
+		}
+	argc -= optind;
+	argv += optind;
+
+	file_count = argc;
+	file_list = argv;
+
+	DPRINTF((stderr, "parse_args\n"));
+	initialize();
+	DPRINTF((stderr, "initialize\n"));
+	crunch_all_files();
+	DPRINTF((stderr, "crunch_all_files\n"));
+	generate_ordering();
+	DPRINTF((stderr, "generate_ordering\n"));
+
+	exit(exit_code);
+}
+
+/*
+ * initialise various variables.
+ */
+void
+initialize(void)
+{
+
+	fn_head = &fn_head_s;
+
+	provide_hash = &provide_hash_s;
+	Hash_InitTable(provide_hash, file_count);
+}
+
+/* generic function to insert a new strnodelist element */
+void
+strnode_add(strnodelist **listp, char *s, filenode *fnode)
+{
+	strnodelist *ent;
+
+	ent = emalloc(sizeof *ent + strlen(s));
+	ent->node = fnode;
+	strcpy(ent->s, s);
+	ent->next = *listp;
+	*listp = ent;
+}
+
+/*
+ * below are the functions that deal with creating the lists
+ * from the filename's given and the dependancies and provisions
+ * in each of these files.  no ordering or checking is done here.
+ */
+
+/*
+ * we have a new filename, create a new filenode structure.
+ * fill in the bits, and put it in the filenode linked list
+ */
+filenode *
+filenode_new(char *filename)
+{
+	filenode *temp;
+
+	temp = emalloc(sizeof(*temp));
+	memset(temp, 0, sizeof(*temp));
+	temp->filename = estrdup(filename);
+	temp->req_list = NULL;
+	temp->prov_list = NULL;
+	temp->keyword_list = NULL;
+	temp->in_progress = RESET;
+	/*
+	 * link the filenode into the list of filenodes.
+	 * note that the double linking means we can delete a
+	 * filenode without searching for where it belongs.
+	 */
+	temp->next = fn_head->next;
+	if (temp->next != NULL)
+		temp->next->last = temp;
+	temp->last = fn_head;
+	fn_head->next = temp;
+	return (temp);
+}
+
+/*
+ * add a requirement to a filenode.
+ */
+void
+add_require(filenode *fnode, char *s)
+{
+	Hash_Entry *entry;
+	f_reqnode *rnode;
+	int new;
+
+	entry = Hash_CreateEntry(provide_hash, s, &new);
+	if (new)
+		Hash_SetValue(entry, NULL);
+	rnode = emalloc(sizeof(*rnode));
+	rnode->entry = entry;
+	rnode->next = fnode->req_list;
+	fnode->req_list = rnode;
+}
+
+/*
+ * add a provision to a filenode.  if this provision doesn't
+ * have a head node, create one here.
+ */
+void
+add_provide(filenode *fnode, char *s)
+{
+	Hash_Entry *entry;
+	f_provnode *f_pnode;
+	provnode *pnode, *head;
+	int new;
+
+	entry = Hash_CreateEntry(provide_hash, s, &new);
+	head = Hash_GetValue(entry);
+
+	/* create a head node if necessary. */
+	if (head == NULL) {
+		head = emalloc(sizeof(*head));
+		head->head = SET;
+		head->in_progress = RESET;
+		head->fnode = NULL;
+		head->last = head->next = NULL;
+		Hash_SetValue(entry, head);
+	}
+#if 0
+	/*
+	 * Don't warn about this.  We want to be able to support
+	 * scripts that do two complex things:
+	 *
+	 *	- Two independent scripts which both provide the
+	 *	  same thing.  Both scripts must be executed in
+	 *	  any order to meet the barrier.  An example:
+	 *
+	 *		Script 1:
+	 *
+	 *			PROVIDE: mail
+	 *			REQUIRE: LOGIN
+	 *
+	 *		Script 2:
+	 *
+	 *			PROVIDE: mail
+	 *			REQUIRE: LOGIN
+	 *
+	 * 	- Two interdependent scripts which both provide the
+	 *	  same thing.  Both scripts must be executed in
+	 *	  graph order to meet the barrier.  An example:
+	 *
+	 *		Script 1:
+	 *
+	 *			PROVIDE: nameservice dnscache
+	 *			REQUIRE: SERVERS
+	 *
+	 *		Script 2:
+	 *
+	 *			PROVIDE: nameservice nscd
+	 *			REQUIRE: dnscache
+	 */
+	else if (new == 0) {
+		warnx("file `%s' provides `%s'.", fnode->filename, s);
+		warnx("\tpreviously seen in `%s'.",
+		    head->next->fnode->filename);
+	}
+#endif
+
+	pnode = emalloc(sizeof(*pnode));
+	pnode->head = RESET;
+	pnode->in_progress = RESET;
+	pnode->fnode = fnode;
+	pnode->next = head->next;
+	pnode->last = head;
+	head->next = pnode;
+	if (pnode->next != NULL)
+		pnode->next->last = pnode;
+
+	f_pnode = emalloc(sizeof(*f_pnode));
+	f_pnode->pnode = pnode;
+	f_pnode->next = fnode->prov_list;
+	fnode->prov_list = f_pnode;
+}
+
+/*
+ * put the BEFORE: lines to a list and handle them later.
+ */
+void
+add_before(filenode *fnode, char *s)
+{
+
+	strnode_add(&bl_list, s, fnode);
+}
+
+/*
+ * add a key to a filenode.
+ */
+void
+add_keyword(filenode *fnode, char *s)
+{
+
+	strnode_add(&fnode->keyword_list, s, fnode);
+}
+
+/*
+ * loop over the rest of a line, giving each word to
+ * add_func() to do the real work.
+ */
+void
+parse_line(filenode *node, char *buffer, void (*add_func)(filenode *, char *))
+{
+	char *s;
+	
+	while ((s = strsep(&buffer, " \t\n")) != NULL)
+		if (*s != '\0')
+			(*add_func)(node, s);
+}
+
+/*
+ * given a file name, create a filenode for it, read in lines looking
+ * for provision and requirement lines, building the graphs as needed.
+ */
+void
+crunch_file(char *filename)
+{
+	FILE *fp;
+	char *buf;
+	int require_flag, provide_flag, before_flag, keyword_flag;
+	enum { BEFORE_PARSING, PARSING, PARSING_DONE } state;
+	filenode *node;
+	char delims[3] = { '\\', '\\', '\0' };
+	struct stat st;
+
+	if ((fp = fopen(filename, "r")) == NULL) {
+		warn("could not open %s", filename);
+		return;
+	}
+
+	if (fstat(fileno(fp), &st) == -1) {
+		warn("could not stat %s", filename);
+		fclose(fp);
+		return;
+	}
+
+	if (!S_ISREG(st.st_mode)) {
+#if 0
+		warnx("%s is not a file", filename);
+#endif
+		fclose(fp);
+		return;
+	}
+
+	node = filenode_new(filename);
+
+	/*
+	 * we don't care about length, line number, don't want # for comments,
+	 * and have no flags.
+	 */
+	for (state = BEFORE_PARSING; state != PARSING_DONE &&
+	    (buf = fparseln(fp, NULL, NULL, delims, 0)) != NULL; free(buf)) {
+		require_flag = provide_flag = before_flag = keyword_flag = 0;
+		if (strncmp(REQUIRE_STR, buf, REQUIRE_LEN) == 0)
+			require_flag = REQUIRE_LEN;
+		else if (strncmp(REQUIRES_STR, buf, REQUIRES_LEN) == 0)
+			require_flag = REQUIRES_LEN;
+		else if (strncmp(PROVIDE_STR, buf, PROVIDE_LEN) == 0)
+			provide_flag = PROVIDE_LEN;
+		else if (strncmp(PROVIDES_STR, buf, PROVIDES_LEN) == 0)
+			provide_flag = PROVIDES_LEN;
+		else if (strncmp(BEFORE_STR, buf, BEFORE_LEN) == 0)
+			before_flag = BEFORE_LEN;
+		else if (strncmp(KEYWORD_STR, buf, KEYWORD_LEN) == 0)
+			keyword_flag = KEYWORD_LEN;
+		else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0)
+			keyword_flag = KEYWORDS_LEN;
+		else {
+			if (state == PARSING)
+				state = PARSING_DONE;
+			continue;
+		}
+
+		state = PARSING;
+		if (require_flag)
+			parse_line(node, buf + require_flag, add_require);
+		else if (provide_flag)
+			parse_line(node, buf + provide_flag, add_provide);
+		else if (before_flag)
+			parse_line(node, buf + before_flag,  add_before);
+		else if (keyword_flag)
+			parse_line(node, buf + keyword_flag, add_keyword);
+	}
+	fclose(fp);
+}
+
+Hash_Entry *
+make_fake_provision(filenode *node)
+{
+	Hash_Entry *entry;
+	f_provnode *f_pnode;
+	provnode *head, *pnode;
+	static	int i = 0;
+	int	new;
+	char buffer[30];
+
+	do {
+		snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++);
+		entry = Hash_CreateEntry(provide_hash, buffer, &new);
+	} while (new == 0);
+	head = emalloc(sizeof(*head));
+	head->head = SET;
+	head->in_progress = RESET;
+	head->fnode = NULL;
+	head->last = head->next = NULL;
+	Hash_SetValue(entry, head);
+
+	pnode = emalloc(sizeof(*pnode));
+	pnode->head = RESET;
+	pnode->in_progress = RESET;
+	pnode->fnode = node;
+	pnode->next = head->next;
+	pnode->last = head;
+	head->next = pnode;
+	if (pnode->next != NULL)
+		pnode->next->last = pnode;
+
+	f_pnode = emalloc(sizeof(*f_pnode));
+	f_pnode->pnode = pnode;
+	f_pnode->next = node->prov_list;
+	node->prov_list = f_pnode;
+
+	return (entry);
+}
+
+/*
+ * go through the BEFORE list, inserting requirements into the graph(s)
+ * as required.  in the before list, for each entry B, we have a file F
+ * and a string S.  we create a "fake" provision (P) that F provides.
+ * for each entry in the provision list for S, add a requirement to
+ * that provisions filenode for P.
+ */
+void
+insert_before(void)
+{
+	Hash_Entry *entry, *fake_prov_entry;
+	provnode *pnode;
+	f_reqnode *rnode;
+	strnodelist *bl;
+	int new;
+	
+	while (bl_list != NULL) {
+		bl = bl_list->next;
+
+		fake_prov_entry = make_fake_provision(bl_list->node);
+
+		entry = Hash_CreateEntry(provide_hash, bl_list->s, &new);
+		if (new == 1)
+			warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);
+
+		for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) {
+			if (pnode->head)
+				continue;
+
+			rnode = emalloc(sizeof(*rnode));
+			rnode->entry = fake_prov_entry;
+			rnode->next = pnode->fnode->req_list;
+			pnode->fnode->req_list = rnode;
+		}
+
+		free(bl_list);
+		bl_list = bl;
+	}
+}
+
+/*
+ * loop over all the files calling crunch_file() on them to do the
+ * real work.  after we have built all the nodes, insert the BEFORE:
+ * lines into graph(s).
+ */
+void
+crunch_all_files(void)
+{
+	int i;
+	
+	for (i = 0; i < file_count; i++)
+		crunch_file(file_list[i]);
+	insert_before();
+}
+
+/*
+ * below are the functions that traverse the graphs we have built
+ * finding out the desired ordering, printing each file in turn.
+ * if missing requirements, or cyclic graphs are detected, a
+ * warning will be issued, and we will continue on..
+ */
+
+/*
+ * given a requirement node (in a filename) we attempt to satisfy it.
+ * we do some sanity checking first, to ensure that we have providers,
+ * aren't already satisfied and aren't already being satisfied (ie,
+ * cyclic).  if we pass all this, we loop over the provision list
+ * calling do_file() (enter recursion) for each filenode in this
+ * provision.
+ */
+void
+satisfy_req(f_reqnode *rnode, char *filename)
+{
+	Hash_Entry *entry;
+	provnode *head;
+
+	entry = rnode->entry;
+	head = Hash_GetValue(entry);
+
+	if (head == NULL) {
+		warnx("requirement `%s' in file `%s' has no providers.",
+		    Hash_GetKey(entry), filename);
+		exit_code = 1;
+		return;
+	}
+
+	/* return if the requirement is already satisfied. */
+	if (head->next == NULL)
+		return;
+
+	/* 
+	 * if list is marked as in progress,
+	 *	print that there is a circular dependency on it and abort
+	 */
+	if (head->in_progress == SET) {
+		warnx("Circular dependency on provision `%s' in file `%s'.",
+		    Hash_GetKey(entry), filename);
+		exit_code = 1;
+		return;
+	}
+
+	head->in_progress = SET;
+	
+	/*
+	 * while provision_list is not empty
+	 *	do_file(first_member_of(provision_list));
+	 */
+	while (head->next != NULL)
+		do_file(head->next->fnode);
+}
+
+int
+skip_ok(filenode *fnode)
+{
+	strnodelist *s;
+	strnodelist *k;
+
+	for (s = skip_list; s; s = s->next)
+		for (k = fnode->keyword_list; k; k = k->next)
+			if (strcmp(k->s, s->s) == 0)
+				return (0);
+
+	return (1);
+}
+
+int
+keep_ok(filenode *fnode)
+{
+	strnodelist *s;
+	strnodelist *k;
+
+	for (s = keep_list; s; s = s->next)
+		for (k = fnode->keyword_list; k; k = k->next)
+			if (strcmp(k->s, s->s) == 0)
+				return (1);
+
+	/* an empty keep_list means every one */
+	return (!keep_list);
+}
+
+/*
+ * given a filenode, we ensure we are not a cyclic graph.  if this
+ * is ok, we loop over the filenodes requirements, calling satisfy_req()
+ * for each of them.. once we have done this, remove this filenode
+ * from each provision table, as we are now done.
+ */
+void
+do_file(filenode *fnode)
+{
+	f_reqnode *r, *r_tmp;
+	f_provnode *p, *p_tmp;
+	provnode *pnode;
+	int was_set;	
+
+	DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
+
+	/*
+	 * if fnode is marked as in progress,
+	 *	 print that fnode; is circularly depended upon and abort.
+	 */
+	if (fnode->in_progress == SET) {
+		warnx("Circular dependency on file `%s'.",
+			fnode->filename);
+		was_set = exit_code = 1;
+	} else
+		was_set = 0;
+
+	/* mark fnode */
+	fnode->in_progress = SET;
+
+	/*
+	 * for each requirement of fnode -> r
+	 *	satisfy_req(r, filename)
+	 */
+	r = fnode->req_list;
+	while (r != NULL) {
+		r_tmp = r;
+		satisfy_req(r, fnode->filename);
+		r = r->next;
+		free(r_tmp);
+	}
+	fnode->req_list = NULL;
+
+	/*
+	 * for each provision of fnode -> p
+	 *	remove fnode from provision list for p in hash table
+	 */
+	p = fnode->prov_list;
+	while (p != NULL) {
+		p_tmp = p;
+		pnode = p->pnode;
+		if (pnode->next != NULL) {
+			pnode->next->last = pnode->last;
+		}
+		if (pnode->last != NULL) {
+			pnode->last->next = pnode->next;
+		}
+		free(pnode);
+		p = p->next;
+		free(p_tmp);
+	}
+	fnode->prov_list = NULL;
+
+	/* do_it(fnode) */
+	DPRINTF((stderr, "next do: "));
+
+	/* if we were already in progress, don't print again */
+	if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode))
+		printf("%s\n", fnode->filename);
+	
+	if (fnode->next != NULL) {
+		fnode->next->last = fnode->last;
+	}
+	if (fnode->last != NULL) {
+		fnode->last->next = fnode->next;
+	}
+
+	DPRINTF((stderr, "nuking %s\n", fnode->filename));
+	free(fnode->filename);
+	free(fnode);
+}
+
+void
+generate_ordering(void)
+{
+
+	/*
+	 * while there remain undone files{f},
+	 *	pick an arbitrary f, and do_file(f)
+	 * Note that the first file in the file list is perfectly
+	 * arbitrary, and easy to find, so we use that.
+	 */
+
+	/*
+	 * N.B.: the file nodes "self delete" after they execute, so
+	 * after each iteration of the loop, the head will be pointing
+	 * to something totally different. The loop ends up being
+	 * executed only once for every strongly connected set of
+	 * nodes.
+	 */
+	while (fn_head->next != NULL) {
+		DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
+		do_file(fn_head->next);
+	}
+}
diff --git a/pkgtools/rcorder/files/rcorder.cat8 b/pkgtools/rcorder/files/rcorder.cat8
new file mode 100644
index 00000000000..4271d485fd0
--- /dev/null
+++ b/pkgtools/rcorder/files/rcorder.cat8
@@ -0,0 +1,86 @@
+RCORDER(8)              NetBSD System Manager's Manual              RCORDER(8)
+
+NNAAMMEE
+     rrccoorrddeerr - print a dependency ordering of interdependent files
+
+SSYYNNOOPPSSIISS
+     rrccoorrddeerr [--kk _k_e_e_p] [--ss _s_k_i_p] _f_i_l_e _._._.
+
+DDEESSCCRRIIPPTTIIOONN
+     rrccoorrddeerr is designed to print out a dependency ordering of a set of inter-
+     dependent files.  Typically it is used to find an execution sequence for
+     a set of shell scripts in which certain files must be executed before
+     others.
+
+     Each file passed to rrccoorrddeerr should be annotated with special lines (which
+     look like comments to the shell) which indicate the dependencies the
+     files have upon certain points in the sequence, known as ``conditions'',
+     and which indicate, for each file, which ``conditions'' may be expected
+     to be filled by that file.
+
+     Within each file, a block containing a series of ``REQUIRE'',
+     ``PROVIDE'', ``BEFORE'' and ``KEYWORD'' lines should appear.  The format
+     of the lines is rigid.  Each line must begin with a single ``#'', fol-
+     lowed by a single space, followed by ``PROVIDE:'', ``REQUIRE:'',
+     ``BEFORE:'', or ``KEYWORD:''.  No deviation is permitted.  Each depen-
+     dency line is then followed by a series of conditions, separated by
+     whitespace.  Multiple ``PROVIDE'', ``REQUIRE'', ``BEFORE'' and
+     ``KEYWORD'' lines may appear, but all such lines must appear in a
+     sequence without any intervening lines, as once a line that does not fol-
+     low the format is reached, parsing stops.
+
+     The options are as follows:
+
+     --kk      Add the specified keyword to the ``keep list''.  If any --kk option
+             is given, only those files containing the matching keyword are
+             listed.
+
+     --ss      Add the specified keyword to the ``skip list''.  If any --ss option
+             is given, files containing the matching keyword are not listed.
+
+      An example block follows:
+
+           # REQUIRE: networking syslog
+           # REQUIRE: usr
+           # PROVIDE: dns nscd
+
+     This block states that the file in which it appears depends upon the
+     ``networking'', ``syslog'', and ``usr'' conditions, and provides the
+     ``dns'' and ``nscd'' conditions.
+
+     A file may contain zero ``PROVIDE'' lines, in which case it provides no
+     conditions, and may contain zero ``REQUIRE'' lines, in which case it has
+     no dependencies.  A file containing no ``PROVIDE'', ``REQUIRE'', or
+     ``BEFORE'' lines may be output at an arbitrary position in the dependency
+     ordering.
+
+     There must be at least one file with no dependencies in the set of argu-
+     ments passed to rrccoorrddeerr in order for it to find a starting place in the
+     dependency ordering.
+
+DDIIAAGGNNOOSSTTIICCSS
+     rrccoorrddeerr may print one of the following error messages and exit with a
+     non-zero status if it encounters an error while processing the file list.
+
+     RReeqquuiirreemmeenntt %%ss hhaass nnoo pprroovviiddeerrss,, aabboorrttiinngg..  No file has a ``PROVIDE''
+     line corresponding to a condition present in a ``REQUIRE'' line in
+     another file.
+
+     CCiirrccuullaarr ddeeppeennddeennccyy oonn pprroovviissiioonn %%ss,, aabboorrttiinngg..  A set of files has a cir-
+     cular dependency which was detected while processing the stated condi-
+     tion.
+
+     CCiirrccuullaarr ddeeppeennddeennccyy oonn ffiillee %%ss,, aabboorrttiinngg..  A set of files has a circular
+     dependency which was detected while processing the stated file.
+
+SSEEEE AALLSSOO
+     rc(8)
+
+HHIISSTTOORRYY
+     The rrccoorrddeerr program first appeared in NetBSD 1.5.
+
+AAUUTTHHOORRSS
+     Written by Perry E. Metzger (perry@piermont.com) and Matthew R. Green
+     (mrg@eterna.com.au).
+
+NetBSD 2.0_BETA                 April 23, 2003                 NetBSD 2.0_BETA