Import the NetBSD 1.5 RC system.

Note that `rc' and `rc.shutdown' could not be imported because we already
have files with those names.

8 files changed, 1800 insertions, 0 deletions

diff --git a/sbin/rcorder/Makefile b/sbin/rcorder/Makefile
new file mode 100644
index 000000000000..ccac08a39b14
--- /dev/null
+++ b/sbin/rcorder/Makefile
@@ -0,0 +1,13 @@
+#       $NetBSD: Makefile,v 1.1 1999/11/23 05:28:20 mrg Exp $
+
+PROG=   rcorder
+SRCS=   ealloc.c hash.c rcorder.c
+MAN=	rcorder.8
+
+LDADD+=	-lutil
+DPADD+=	${LIBUTIL}
+
+# XXX hack for make's hash.[ch]
+CPPFLAGS+= -DORDER
+
+.include <bsd.prog.mk>
diff --git a/sbin/rcorder/ealloc.c b/sbin/rcorder/ealloc.c
new file mode 100644
index 000000000000..9accebe36206
--- /dev/null
+++ b/sbin/rcorder/ealloc.c
@@ -0,0 +1,123 @@
+/*	$NetBSD: ealloc.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ * 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 <sys/cdefs.h>
+#ifndef lint
+__RCSID("$NetBSD: ealloc.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $");
+#endif /* not lint */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <err.h>
+
+#include "ealloc.h"
+
+static void enomem __P((void));
+
+/*
+ * enomem --
+ *	die when out of memory.
+ */
+static void
+enomem()
+{
+	errx(2, "Cannot allocate memory.");
+}
+
+/*
+ * emalloc --
+ *	malloc, but die on error.
+ */
+void *
+emalloc(len)
+	size_t len;
+{
+	void *p;
+
+	if ((p = malloc(len)) == NULL)
+		enomem();
+	return(p);
+}
+
+/*
+ * estrdup --
+ *	strdup, but die on error.
+ */
+char *
+estrdup(str)
+	const char *str;
+{
+	char *p;
+
+	if ((p = strdup(str)) == NULL)
+		enomem();
+	return(p);
+}
+
+/*
+ * erealloc --
+ *	realloc, but die on error.
+ */
+void *
+erealloc(ptr, size)
+	void *ptr;
+	size_t size;
+{
+	if ((ptr = realloc(ptr, size)) == NULL)
+		enomem();
+	return(ptr);
+}
+
+/*
+ * ecalloc --
+ *	calloc, but die on error.
+ */
+void *
+ecalloc(nmemb, size)
+	size_t nmemb;
+	size_t size;
+{
+	void	*ptr;
+
+	if ((ptr = calloc(nmemb, size)) == NULL)
+		enomem();
+	return(ptr);
+}
diff --git a/sbin/rcorder/ealloc.h b/sbin/rcorder/ealloc.h
new file mode 100644
index 000000000000..fb753d5fca42
--- /dev/null
+++ b/sbin/rcorder/ealloc.h
@@ -0,0 +1,6 @@
+/*	$NetBSD: ealloc.h,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $	*/
+
+void	*emalloc __P((size_t len));
+char	*estrdup __P((const char *str));
+void	*erealloc __P((void *ptr, size_t size));
+void	*ecalloc __P((size_t nmemb, size_t size));
diff --git a/sbin/rcorder/hash.c b/sbin/rcorder/hash.c
new file mode 100644
index 000000000000..5ec335a367bd
--- /dev/null
+++ b/sbin/rcorder/hash.c
@@ -0,0 +1,438 @@
+/*	$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
+ * 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.
+ */
+
+#ifdef MAKE_BOOTSTRAP
+static char rcsid[] = "$NetBSD: hash.c,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $";
+#else
+#include <sys/cdefs.h>
+#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 1999/11/19 04:30:56 mrg Exp $");
+#endif
+#endif /* not lint */
+#endif
+
+#include <sys/types.h>
+
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+/* 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 "sprite.h"
+#ifndef ORDER
+#include "make.h"
+#endif /* ORDER */
+#include "hash.h"
+#include "ealloc.h"
+
+/*
+ * Forward references to local procedures that are used before they're
+ * defined:
+ */
+
+static void RebuildTable __P((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.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	Memory is allocated for the initial bucket area.
+ *
+ *---------------------------------------------------------
+ */
+
+void
+Hash_InitTable(t, numBuckets)
+	register Hash_Table *t;	/* Structure to use to hold table. */
+	int 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. */
+{
+	register int i;
+	register 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(t)
+	Hash_Table *t;
+{
+	register struct Hash_Entry **hp, *h, *nexth = NULL;
+	register int i;
+
+	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.
+ *
+ * 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(t, key)
+	Hash_Table *t;		/* Hash table to search. */
+	char *key;		/* A hash key. */
+{
+	register Hash_Entry *e;
+	register unsigned h;
+	register 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.
+ *
+ * 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(t, key, newPtr)
+	register Hash_Table *t;	/* Hash table to search. */
+	char *key;		/* A hash key. */
+	Boolean *newPtr;	/* Filled in with TRUE if new entry created,
+				 * FALSE otherwise. */
+{
+	register Hash_Entry *e;
+	register unsigned h;
+	register 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 = FALSE;
+			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 = TRUE;
+	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(t, e)
+	Hash_Table *t;
+	Hash_Entry *e;
+{
+	register 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.
+ *
+ * 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(t, searchPtr)
+	Hash_Table *t;			/* Table to be searched. */
+	register Hash_Search *searchPtr;/* Area in which to keep state
+					 * about search.*/
+{
+	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(searchPtr)
+	register Hash_Search *searchPtr; /* Area used to keep state about
+					    search. */
+{
+	register 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(t)
+	register Hash_Table *t;
+{
+	register Hash_Entry *e, *next = NULL, **hp, **xp;
+	register int i, mask;
+        register Hash_Entry **oldhp;
+	int oldsize;
+
+	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/sbin/rcorder/hash.h b/sbin/rcorder/hash.h
new file mode 100644
index 000000000000..cf15256d1140
--- /dev/null
+++ b/sbin/rcorder/hash.h
@@ -0,0 +1,130 @@
+/*	$NetBSD: hash.h,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
+ * 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. */
+	ClientData	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.
+ */
+
+/*
+ * ClientData 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 = (ClientData) (val))
+
+#ifdef ORDER
+/*
+ * Hash_GetKey(h);
+ *     Hash_Entry *h;
+ */
+
+#define Hash_GetKey(h) ((h)->name)
+#endif /* ORDER */
+
+/*
+ * 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 __P((Hash_Table *, int));
+void Hash_DeleteTable __P((Hash_Table *));
+Hash_Entry *Hash_FindEntry __P((Hash_Table *, char *));
+Hash_Entry *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *));
+void Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *));
+Hash_Entry *Hash_EnumFirst __P((Hash_Table *, Hash_Search *));
+Hash_Entry *Hash_EnumNext __P((Hash_Search *));
+
+#endif /* _HASH */
diff --git a/sbin/rcorder/rcorder.8 b/sbin/rcorder/rcorder.8
new file mode 100644
index 000000000000..2ba623b69b17
--- /dev/null
+++ b/sbin/rcorder/rcorder.8
@@ -0,0 +1,158 @@
+.\"	$NetBSD: rcorder.8,v 1.2 2000/07/05 15:45:30 msaitoh 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 July 17, 2000
+.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
+must 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 must 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.
+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/sbin/rcorder/rcorder.c b/sbin/rcorder/rcorder.c
new file mode 100644
index 000000000000..03a397f2b690
--- /dev/null
+++ b/sbin/rcorder/rcorder.c
@@ -0,0 +1,819 @@
+/*	$NetBSD: rcorder.c,v 1.6 2000/07/19 09:58:03 enami Exp $	*/
+
+/*
+ * Copyright (c) 1998, 1999 Matthew R. Green
+ * All rights reserved.
+ * 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 <sys/types.h>
+#include <sys/stat.h>
+
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <util.h>
+
+#include "ealloc.h"
+#include "sprite.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;
+
+typedef int bool;
+#define TRUE 1
+#define FALSE 0
+typedef bool flag;
+#define SET TRUE
+#define RESET FALSE
+
+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 {
+	flag		head;
+	flag		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;
+	flag		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 __P((filenode *fnode));
+void strnode_add __P((strnodelist **, char *, filenode *));
+int skip_ok __P((filenode *fnode));
+int keep_ok __P((filenode *fnode));
+void satisfy_req __P((f_reqnode *rnode, char *filename));
+void crunch_file __P((char *));
+void parse_require __P((filenode *, char *));
+void parse_provide __P((filenode *, char *));
+void parse_before __P((filenode *, char *));
+void parse_keywords __P((filenode *, char *));
+filenode *filenode_new __P((char *));
+void add_require __P((filenode *, char *));
+void add_provide __P((filenode *, char *));
+void add_before __P((filenode *, char *));
+void add_keyword __P((filenode *, char *));
+void insert_before __P((void));
+Hash_Entry *make_fake_provision __P((filenode *));
+void crunch_all_files __P((void));
+void initialize __P((void));
+void generate_ordering __P((void));
+int main __P((int, char *[]));
+
+int
+main(argc, argv)
+	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()
+{
+
+	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(listp, s, fnode)
+	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(filename)
+	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(fnode, s)
+	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(fnode, s)
+	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(fnode, s)
+	filenode *fnode;
+	char *s;
+{
+	strnodelist *bf_ent;
+
+	bf_ent = emalloc(sizeof *bf_ent + strlen(s));
+	bf_ent->node = fnode;
+	strcpy(bf_ent->s, s);
+	bf_ent->next = bl_list;
+	bl_list = bf_ent;
+}
+
+/*
+ * add a key to a filenode.
+ */
+void
+add_keyword(fnode, s)
+	filenode *fnode;
+	char *s;
+{
+
+	strnode_add(&fnode->keyword_list, s, fnode);
+}
+
+/*
+ * loop over the rest of a REQUIRE line, giving each word to
+ * add_require() to do the real work.
+ */
+void
+parse_require(node, buffer)
+	filenode *node;
+	char *buffer;
+{
+	char *s;
+	
+	while ((s = strsep(&buffer, " \t\n")) != NULL)
+		if (*s != '\0')
+			add_require(node, s);
+}
+
+/*
+ * loop over the rest of a PROVIDE line, giving each word to
+ * add_provide() to do the real work.
+ */
+void
+parse_provide(node, buffer)
+	filenode *node;
+	char *buffer;
+{
+	char *s;
+	
+	while ((s = strsep(&buffer, " \t\n")) != NULL)
+		if (*s != '\0')
+			add_provide(node, s);
+}
+
+/*
+ * loop over the rest of a BEFORE line, giving each word to
+ * add_before() to do the real work.
+ */
+void
+parse_before(node, buffer)
+	filenode *node;
+	char *buffer;
+{
+	char *s;
+	
+	while ((s = strsep(&buffer, " \t\n")) != NULL)
+		if (*s != '\0')
+			add_before(node, s);
+}
+
+/*
+ * loop over the rest of a KEYWORD line, giving each word to
+ * add_keyword() to do the real work.
+ */
+void
+parse_keywords(node, buffer)
+	filenode *node;
+	char *buffer;
+{
+	char *s;
+	
+	while ((s = strsep(&buffer, " \t\n")) != NULL)
+		if (*s != '\0')
+			add_keyword(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(filename)
+	char *filename;
+{
+	FILE *fp;
+	char *buf;
+	int require_flag, provide_flag, before_flag, keywords_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)) {
+		warnx("%s is not a file", filename);
+		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 = keywords_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)
+			keywords_flag = KEYWORD_LEN;
+		else if (strncmp(KEYWORDS_STR, buf, KEYWORDS_LEN) == 0)
+			keywords_flag = KEYWORDS_LEN;
+		else {
+			if (state == PARSING)
+				state = PARSING_DONE;
+			continue;
+		}
+
+		state = PARSING;
+		if (require_flag)
+			parse_require(node, buf + require_flag);
+		else if (provide_flag)
+			parse_provide(node, buf + provide_flag);
+		else if (before_flag)
+			parse_before(node, buf + before_flag);
+		else if (keywords_flag)
+			parse_keywords(node, buf + keywords_flag);
+	}
+	fclose(fp);
+}
+
+Hash_Entry *
+make_fake_provision(node)
+	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()
+{
+	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()
+{
+	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(rnode, filename)
+	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(fnode)
+	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(fnode)
+	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(fnode)
+	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()
+{
+
+	/*
+	 * 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/sbin/rcorder/sprite.h b/sbin/rcorder/sprite.h
new file mode 100644
index 000000000000..5e5d7f3640f7
--- /dev/null
+++ b/sbin/rcorder/sprite.h
@@ -0,0 +1,113 @@
+/*	$NetBSD: sprite.h,v 1.1 1999/11/23 05:28:22 mrg Exp $	*/
+
+/*
+ * Copyright (c) 1988, 1989, 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ * 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: @(#)sprite.h	8.1 (Berkeley) 6/6/93
+ */
+
+/*
+ * sprite.h --
+ *
+ * Common constants and type declarations for Sprite.
+ */
+
+#ifndef _SPRITE
+#define _SPRITE
+
+
+/*
+ * A boolean type is defined as an integer, not an enum. This allows a
+ * boolean argument to be an expression that isn't strictly 0 or 1 valued.
+ */
+
+typedef int Boolean;
+#ifndef TRUE
+#define TRUE	1
+#endif /* TRUE */
+#ifndef FALSE
+#define FALSE	0
+#endif /* FALSE */
+
+/*
+ * Functions that must return a status can return a ReturnStatus to
+ * indicate success or type of failure.
+ */
+
+typedef int  ReturnStatus;
+
+/*
+ * The following statuses overlap with the first 2 generic statuses
+ * defined in status.h:
+ *
+ * SUCCESS			There was no error.
+ * FAILURE			There was a general error.
+ */
+
+#define	SUCCESS			0x00000000
+#define	FAILURE			0x00000001
+
+
+/*
+ * A nil pointer must be something that will cause an exception if
+ * referenced.  There are two nils: the kernels nil and the nil used
+ * by user processes.
+ */
+
+#define NIL 		~0
+#define USER_NIL 	0
+#ifndef NULL
+#define NULL	 	0
+#endif /* NULL */
+
+/*
+ * An address is just a pointer in C.  It is defined as a character pointer
+ * so that address arithmetic will work properly, a byte at a time.
+ */
+
+typedef char *Address;
+
+/*
+ * ClientData is an uninterpreted word.  It is defined as an int so that
+ * kdbx will not interpret client data as a string.  Unlike an "Address",
+ * client data will generally not be used in arithmetic.
+ * But we don't have kdbx anymore so we define it as void (christos)
+ */
+
+typedef void *ClientData;
+
+#endif /* _SPRITE */