From e2ff9f51c4bdec7286268301a0b307c3fa01b31e Mon Sep 17 00:00:00 2001
From: espie <espie@openbsd.org>
Date: Mon, 12 May 2014 19:11:19 +0000
Subject: [PATCH] adjust to ohash being in libutil now, and to the interface
 changes. fix potential integer overflows in memory allocation (mostly for
 pedagogical purposes, these are unlikely to overflow in practice) move the
 rest of lst.lib stuff into its own directory.

---
 usr.bin/m4/Makefile               |   6 +-
 usr.bin/m4/extern.h               |   4 +-
 usr.bin/m4/gnum4.c                |   7 +-
 usr.bin/m4/look.c                 |  25 ++---
 usr.bin/m4/main.c                 |   7 +-
 usr.bin/m4/misc.c                 |  26 +----
 usr.bin/make/Makefile             |  21 ++--
 usr.bin/make/arch.c               |   6 +-
 usr.bin/make/dir.c                |   8 +-
 usr.bin/make/garray.h             |   4 +-
 usr.bin/make/lst.lib/Makefile.inc |   9 ++
 usr.bin/make/lst.lib/lst.h        | 181 ++++++++++++++++++++++++++++++
 usr.bin/make/lst.lib/lst_t.h      |  33 ++++++
 usr.bin/make/memory.c             |  19 +---
 usr.bin/make/memory.h             |   8 +-
 usr.bin/make/str.c                |   4 +-
 usr.bin/make/suff.c               |   4 +-
 usr.bin/make/targ.c               |   4 +-
 usr.bin/make/targequiv.c          |   4 +-
 usr.bin/make/var.c                |   4 +-
 usr.bin/make/varmodifiers.c       |   6 +-
 usr.bin/mandoc/Makefile           |   5 +-
 usr.bin/mandoc/mandocdb.c         |  20 ++--
 usr.bin/mandoc/mansearch.c        |  18 ++-
 usr.bin/tsort/Makefile            |   9 +-
 usr.bin/tsort/tsort.c             |  14 +--
 26 files changed, 327 insertions(+), 129 deletions(-)
 create mode 100644 usr.bin/make/lst.lib/Makefile.inc
 create mode 100644 usr.bin/make/lst.lib/lst.h
 create mode 100644 usr.bin/make/lst.lib/lst_t.h

diff --git a/usr.bin/m4/Makefile b/usr.bin/m4/Makefile
index 16e1b6560e0..ecb89c8ede3 100644
--- a/usr.bin/m4/Makefile
+++ b/usr.bin/m4/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.12 2012/04/12 17:00:11 espie Exp $
+#	$OpenBSD: Makefile,v 1.13 2014/05/12 19:11:19 espie Exp $
 
 # -DEXTENDED 
 # 	if you want the paste & spaste macros.
@@ -8,8 +8,8 @@ CFLAGS+=-DEXTENDED -I.
 CDIAGFLAGS=-W -Wall -Wstrict-prototypes -pedantic \
 	-Wno-unused -Wno-char-subscripts -Wno-sign-compare
 
-LDADD= -ly -ll -lm
-DPADD= ${LIBY} ${LIBL} ${LIBM}
+LDADD= -ly -ll -lm -lutil
+DPADD= ${LIBY} ${LIBL} ${LIBM} ${LIBUTIL}
 
 SRCS=	eval.c expr.c look.c main.c misc.c gnum4.c trace.c tokenizer.l parser.y
 MAN=	m4.1
diff --git a/usr.bin/m4/extern.h b/usr.bin/m4/extern.h
index 38a9635acc0..d9cd64ba9f5 100644
--- a/usr.bin/m4/extern.h
+++ b/usr.bin/m4/extern.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: extern.h,v 1.53 2014/04/28 12:34:11 espie Exp $	*/
+/*	$OpenBSD: extern.h,v 1.54 2014/05/12 19:11:19 espie Exp $	*/
 /*	$NetBSD: extern.h,v 1.3 1996/01/13 23:25:24 pk Exp $	*/
 
 /*-
@@ -103,7 +103,7 @@ extern void	pbunsigned(unsigned long);
 extern void	pbstr(const char *);
 extern void	pushback(int);
 extern void	*xalloc(size_t, const char *, ...);
-extern void	*xallocarray(size_t, size_t, const char *, ...);
+extern void	*xcalloc(size_t, size_t, const char *, ...);
 extern void	*xrealloc(void *, size_t, const char *, ...);
 extern void	*xreallocarray(void *, size_t, size_t, const char *, ...);
 extern char	*xstrdup(const char *);
diff --git a/usr.bin/m4/gnum4.c b/usr.bin/m4/gnum4.c
index 9d6621e2bdc..b6a64134721 100644
--- a/usr.bin/m4/gnum4.c
+++ b/usr.bin/m4/gnum4.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: gnum4.c,v 1.44 2014/04/28 12:34:11 espie Exp $ */
+/* $OpenBSD: gnum4.c,v 1.45 2014/05/12 19:11:19 espie Exp $ */
 
 /*
  * Copyright (c) 1999 Marc Espie
@@ -469,7 +469,8 @@ dopatsubst(const char *argv[], int argc)
 		if (error != 0)
 			exit_regerror(error, &re);
 
-		pmatch = xallocarray(re.re_nsub+1, sizeof(regmatch_t), NULL);
+		pmatch = xreallocarray(NULL, re.re_nsub+1, sizeof(regmatch_t), 
+		    NULL);
 		do_subst(argv[2], &re,
 		    argc > 4 && argv[4] != NULL ? argv[4] : "", pmatch);
 		free(pmatch);
@@ -501,7 +502,7 @@ doregexp(const char *argv[], int argc)
 	if (error != 0)
 		exit_regerror(error, &re);
 
-	pmatch = xallocarray(re.re_nsub+1, sizeof(regmatch_t), NULL);
+	pmatch = xreallocarray(NULL, re.re_nsub+1, sizeof(regmatch_t), NULL);
 	if (argc == 4 || argv[4] == NULL)
 		do_regexpindex(argv[2], &re, pmatch);
 	else
diff --git a/usr.bin/m4/look.c b/usr.bin/m4/look.c
index 041cbb9a868..eeec6569430 100644
--- a/usr.bin/m4/look.c
+++ b/usr.bin/m4/look.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: look.c,v 1.22 2010/09/07 19:58:09 marco Exp $	*/
+/*	$OpenBSD: look.c,v 1.23 2014/05/12 19:11:19 espie Exp $	*/
 
 /*
  * Copyright (c) 1989, 1993
@@ -48,43 +48,34 @@
 #include "stdd.h"
 #include "extern.h"
 
-static void *hash_alloc(size_t, void *);
-static void hash_free(void *, size_t, void *);
+static void *hash_calloc(size_t, size_t, void *);
+static void hash_free(void *, void *);
 static void *element_alloc(size_t, void *);
 static void setup_definition(struct macro_definition *, const char *,
     const char *);
 
 static struct ohash_info macro_info = {
 	offsetof(struct ndblock, name),
-	NULL, hash_alloc, hash_free, element_alloc };
+	NULL, hash_calloc, hash_free, element_alloc };
 
 struct ohash macros;
 
 /* Support routines for hash tables.  */
 void *
-hash_alloc(s, u)
-	size_t s;
-	void *u		UNUSED;
+hash_calloc(size_t n, size_t s, void *u UNUSED)
 {
-	void *storage = xalloc(s, "hash alloc");
-	if (storage)
-		memset(storage, 0, s);
+	void *storage = xcalloc(n, s, "hash alloc");
 	return storage;
 }
 
 void
-hash_free(p, s, u)
-	void *p;
-	size_t s	UNUSED;
-	void *u		UNUSED;
+hash_free(void *p, void *u UNUSED)
 {
 	free(p);
 }
 
 void *
-element_alloc(s, u)
-	size_t s;
-	void *u		UNUSED;
+element_alloc(size_t s, void *u UNUSED)
 {
 	return xalloc(s, "element alloc");
 }
diff --git a/usr.bin/m4/main.c b/usr.bin/m4/main.c
index dc2b9e5f821..1dce48e50e0 100644
--- a/usr.bin/m4/main.c
+++ b/usr.bin/m4/main.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: main.c,v 1.82 2014/04/28 12:34:11 espie Exp $	*/
+/*	$OpenBSD: main.c,v 1.83 2014/05/12 19:11:19 espie Exp $	*/
 /*	$NetBSD: main.c,v 1.12 1997/02/08 23:54:49 cgd Exp $	*/
 
 /*-
@@ -181,7 +181,7 @@ main(int argc, char *argv[])
 	initspaces();
 	STACKMAX = INITSTACKMAX;
 
-	mstack = xallocarray(STACKMAX, sizeof(stae), NULL);
+	mstack = xreallocarray(NULL, STACKMAX, sizeof(stae), NULL);
 	sstack = xalloc(STACKMAX, NULL);
 
 	maxout = 0;
@@ -416,7 +416,8 @@ macro(void)
 				}
 			}
 		} else if (t == EOF) {
-			if (sp > -1 && ilevel <= 0) {
+			if (!mimic_gnu /* you can puke right there */
+			    && sp > -1 && ilevel <= 0) {
 				warnx( "unexpected end of input, unclosed parenthesis:");
 				dump_stack(paren, PARLEV);
 				exit(1);
diff --git a/usr.bin/m4/misc.c b/usr.bin/m4/misc.c
index 16697a47ac5..556ecd637b9 100644
--- a/usr.bin/m4/misc.c
+++ b/usr.bin/m4/misc.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: misc.c,v 1.43 2014/04/28 12:34:11 espie Exp $	*/
+/*	$OpenBSD: misc.c,v 1.44 2014/05/12 19:11:19 espie Exp $	*/
 /*	$NetBSD: misc.c,v 1.6 1995/09/28 05:37:41 tls Exp $	*/
 
 /*
@@ -311,20 +311,13 @@ xalloc(size_t n, const char *fmt, ...)
 }
 
 void *
-xallocarray(size_t s1, size_t s2, const char *fmt, ...)
+xcalloc(size_t n, size_t s, const char *fmt, ...)
 {
-	void *p;
-
-	if (s1 && SIZE_MAX / s1 < s2) {
-		errno = ENOMEM;
-		p = NULL;
-	} else {
-		p = malloc(s1 * s2);
-	}
+	void *p = calloc(n, s);
 
 	if (p == NULL) {
 		if (fmt == NULL)
-			err(1, "malloc");
+			err(1, "calloc");
 		else {
 			va_list va;
 
@@ -359,19 +352,12 @@ xrealloc(void *old, size_t n, const char *fmt, ...)
 void *
 xreallocarray(void *old, size_t s1, size_t s2, const char *fmt, ...)
 {
-	void *p;
-
-	if (s1 && SIZE_MAX / s1 < s2) {
-		errno = ENOMEM;
-		p = NULL;
-	} else {
-		p = realloc(old, s1 * s2);
-	}
+	void *p = reallocarray(old, s1, s2);
 
 	if (p == NULL) {
 		free(old);
 		if (fmt == NULL)
-			err(1, "realloc");
+			err(1, "reallocarray");
 		else {
 			va_list va;
 
diff --git a/usr.bin/make/Makefile b/usr.bin/make/Makefile
index c20dd00f03b..055b2382c10 100644
--- a/usr.bin/make/Makefile
+++ b/usr.bin/make/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.57 2014/03/22 10:36:22 espie Exp $
+#	$OpenBSD: Makefile,v 1.58 2014/05/12 19:11:19 espie Exp $
 
 PROG=	make
 CFLAGS+= -I${.OBJDIR} -I${.CURDIR}
@@ -11,6 +11,8 @@ CDEFS+=-DHAS_PATHS_H
 CDEFS+=-DHAS_EXTENDED_GETCWD
 #CDEFS+=-DHAS_STATS
 
+DPADD += ${LIBUTIL}
+LDADD += -lutil
 CFLAGS+=${CDEFS}
 HOSTCFLAGS+=${CDEFS}
 
@@ -19,14 +21,11 @@ SRCS=	arch.c buf.c cmd_exec.c compat.c cond.c dir.c direxpand.c dump.c \
 	error.c for.c init.c job.c lowparse.c main.c make.c memory.c parse.c \
 	parsevar.c str.c stats.c suff.c targ.c targequiv.c timestamp.c \
 	var.c varmodifiers.c varname.c
-SRCS+=	lstAddNew.c lstAppend.c lstConcat.c lstConcatDestroy.c \
-	lstDeQueue.c lstDestroy.c lstDupl.c lstFindFrom.c lstForEachFrom.c \
-	lstInsert.c lstMember.c lstRemove.c lstReplace.c lstRequeue.c lstSucc.c
-.PATH:	${.CURDIR}/lst.lib
+
+.include "${.CURDIR}/lst.lib/Makefile.inc"
 
 CLEANFILES+=generate generate.o regress.o check
 
-CLEANFILES+=${LIBOBJS} libohash.a
 CLEANFILES+= varhashconsts.h condhashconsts.h nodehashconsts.h
 
 beforedepend: varhashconsts.h condhashconsts.h nodehashconsts.h
@@ -43,11 +42,13 @@ condhashconsts.h: generate
 nodehashconsts.h: generate
 	${.OBJDIR}/generate 3 0 >$@.tmp && mv $@.tmp $@
 
-generate: generate.c stats.c memory.c
-	${HOSTCC} ${LDSTATIC} -o ${.TARGET} ${HOSTCFLAGS} ${.ALLSRC} ${LDADD}
+generate: generate.c stats.c memory.c ${DPADD}
+	${HOSTCC} ${HOSTCFLAGS} ${LDSTATIC} -o ${.TARGET} ${.ALLSRC} ${LDFLAGS} ${LDADD}
+
+CHECKOBJS = regress.o str.o memory.o buf.o
 
-check: regress.o str.o memory.o buf.o
-	${CC} -o ${.TARGET} ${CFLAGS} ${.ALLSRC} ${LDADD}
+check: ${CHECKOBJS} ${DPADD}
+	${CC} -o ${.TARGET} ${CFLAGS} ${CHECKOBJS} ${LDADD}
 
 regress: check
 	${.OBJDIR}/check
diff --git a/usr.bin/make/arch.c b/usr.bin/make/arch.c
index 1addfbabb09..fc1e870fcfa 100644
--- a/usr.bin/make/arch.c
+++ b/usr.bin/make/arch.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: arch.c,v 1.82 2013/11/22 15:47:35 espie Exp $ */
+/*	$OpenBSD: arch.c,v 1.83 2014/05/12 19:11:19 espie Exp $ */
 /*	$NetBSD: arch.c,v 1.17 1996/11/06 17:58:59 christos Exp $	*/
 
 /*
@@ -141,11 +141,11 @@ struct arch_member {
 
 static struct ohash_info members_info = {
 	offsetof(struct arch_member, name), NULL,
-	hash_alloc, hash_free, element_alloc
+	hash_calloc, hash_free, element_alloc
 };
 
 static struct ohash_info arch_info = {
-	offsetof(Arch, name), NULL, hash_alloc, hash_free, element_alloc
+	offsetof(Arch, name), NULL, hash_calloc, hash_free, element_alloc
 };
 
 
diff --git a/usr.bin/make/dir.c b/usr.bin/make/dir.c
index eac0920b83e..ced781c134e 100644
--- a/usr.bin/make/dir.c
+++ b/usr.bin/make/dir.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dir.c,v 1.63 2013/05/22 12:14:08 espie Exp $ */
+/*	$OpenBSD: dir.c,v 1.64 2014/05/12 19:11:19 espie Exp $ */
 /*	$NetBSD: dir.c,v 1.14 1997/03/29 16:51:26 christos Exp $	*/
 
 /*
@@ -177,7 +177,7 @@ struct PathEntry {
 
 /* PathEntry kept on knownDirectories */
 static struct ohash_info dir_info = {
-	offsetof(struct PathEntry, name), NULL, hash_alloc, hash_free,
+	offsetof(struct PathEntry, name), NULL, hash_calloc, hash_free,
 	element_alloc
 };
 
@@ -186,7 +186,7 @@ static struct ohash   knownDirectories;	/* cache all open directories */
 
 /* file names kept in a path entry */
 static struct ohash_info file_info = {
-	0, NULL, hash_alloc, hash_free, element_alloc
+	0, NULL, hash_calloc, hash_free, element_alloc
 };
 
 
@@ -204,7 +204,7 @@ static struct ohash mtimes;
 
 
 static struct ohash_info stamp_info = {
-	offsetof(struct file_stamp, name), NULL, hash_alloc, hash_free,
+	offsetof(struct file_stamp, name), NULL, hash_calloc, hash_free,
 	element_alloc
 };
 
diff --git a/usr.bin/make/garray.h b/usr.bin/make/garray.h
index c8d67082266..4cd33699bfd 100644
--- a/usr.bin/make/garray.h
+++ b/usr.bin/make/garray.h
@@ -1,7 +1,7 @@
 #ifndef GARRAY_H
 #define GARRAY_H
 
-/* $OpenBSD: garray.h,v 1.7 2014/04/22 08:26:31 espie Exp $ */
+/* $OpenBSD: garray.h,v 1.8 2014/05/12 19:11:19 espie Exp $ */
 /* Growable array implementation */
 
 /*
@@ -52,7 +52,7 @@ do {								\
 do { 							\
 	if ((l)->n >= (l)->size) { 			\
 		(l)->size *= 2; 			\
-		(l)->a = emult_realloc((l)->a, 		\
+		(l)->a = ereallocarray((l)->a, 		\
 		    (l)->size, sizeof(struct GNode *)); \
 		MAY_INCREASE_STATS;			\
 	} 						\
diff --git a/usr.bin/make/lst.lib/Makefile.inc b/usr.bin/make/lst.lib/Makefile.inc
new file mode 100644
index 00000000000..f046a4df3b4
--- /dev/null
+++ b/usr.bin/make/lst.lib/Makefile.inc
@@ -0,0 +1,9 @@
+# $OpenBSD: Makefile.inc,v 1.1 2014/05/12 19:11:20 espie Exp $
+
+.PATH:	${.CURDIR}/lst.lib
+CFLAGS += -I${.CURDIR}/lst.lib
+HOSTCFLAGS += -I${.CURDIR}/lst.lib
+
+SRCS+=	lstAddNew.c lstAppend.c lstConcat.c lstConcatDestroy.c \
+	lstDeQueue.c lstDestroy.c lstDupl.c lstFindFrom.c lstForEachFrom.c \
+	lstInsert.c lstMember.c lstRemove.c lstReplace.c lstRequeue.c lstSucc.c
diff --git a/usr.bin/make/lst.lib/lst.h b/usr.bin/make/lst.lib/lst.h
new file mode 100644
index 00000000000..fecbb438691
--- /dev/null
+++ b/usr.bin/make/lst.lib/lst.h
@@ -0,0 +1,181 @@
+#ifndef _LST_H_
+#define _LST_H_
+
+/*	$OpenBSD: lst.h,v 1.1 2014/05/12 19:11:20 espie Exp $ */
+/*	$NetBSD: lst.h,v 1.7 1996/11/06 17:59:12 christos 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. 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: @(#)lst.h 8.1 (Berkeley) 6/6/93
+ */
+
+/*-
+ * lst.h --
+ *	Header for using the list library
+ */
+
+/* These data structures are PRIVATE !!!
+ * Here for efficiency, so that some functions can be recoded as inlines,
+ * and so that lst headers don't need dynamic allocation most of the time.  */
+struct ListNode_ {
+	struct ListNode_    *prevPtr;	/* previous element in list */
+	struct ListNode_    *nextPtr;	/* next in list */
+	void		    *datum;	/* datum associated with this element */
+};
+
+#ifndef LIST_TYPE
+#include "lst_t.h"
+#endif
+
+typedef void (*SimpleProc)(void *);
+typedef int (*FindProc)(void *, void *);
+typedef int (*ForEachNodeWhileProc)(LstNode, void *);
+typedef int (*FindProcConst)(void *, const void *);
+typedef void (*ForEachProc)(void *, void *);
+typedef void *(*DuplicateProc)(void *);
+
+/*
+ * NOFREE can be used as the freeProc to Lst_Destroy when the elements are
+ *	not to be freed.
+ * NOCOPY performs similarly when given as the copyProc to Lst_Duplicate.
+ */
+#define NOFREE		((SimpleProc) 0)
+#define NOCOPY		((DuplicateProc) 0)
+
+/*
+ * Creation/destruction functions
+ */
+/* Create a new list */
+#define Lst_Init(l)	(l)->firstPtr = (l)->lastPtr = NULL
+/* Static lists are already okay */
+#define Static_Lst_Init(l)
+
+/* Duplicate an existing list */
+extern Lst		Lst_Clone(Lst, Lst, DuplicateProc);
+/* Destroy an old one */
+extern void		Lst_Destroy(LIST *, SimpleProc);
+/* True if list is empty */
+#define 	Lst_IsEmpty(l)	((l)->firstPtr == NULL)
+
+/*
+ * Functions to modify a list
+ */
+/* Insert an element before another */
+extern void		Lst_Insert(Lst, LstNode, void *);
+extern void		Lst_AtFront(Lst, void *);
+/* Insert an element after another */
+extern void		Lst_Append(Lst, LstNode, void *);
+extern void		Lst_AtEnd(Lst, void *);
+/* Remove an element */
+extern void		Lst_Remove(Lst, LstNode);
+/* Replace a node with a new value */
+extern void		Lst_Replace(LstNode, void *);
+/* Concatenate two lists, destructive.	*/
+extern void		Lst_ConcatDestroy(Lst, Lst);
+/* Concatenate two lists, non-destructive.  */
+extern void		Lst_Concat(Lst, Lst);
+/* requeue element already in list at front of list */
+extern void		Lst_Requeue(Lst, LstNode);
+
+/*
+ * Node-specific functions
+ */
+/* Return first element in list */
+/* Return last element in list */
+/* Return successor to given element */
+extern LstNode		Lst_Succ(LstNode);
+
+/*
+ * Functions for entire lists
+ */
+/* Find an element starting from somewhere */
+extern LstNode		Lst_FindFrom(LstNode, FindProc, void *);
+/*
+ * See if the given datum is on the list. Returns the LstNode containing
+ * the datum
+ */
+extern LstNode		Lst_Member(Lst, void *);
+/* Apply a function to elements of a lst starting from a certain point.  */
+extern void		Lst_ForEachFrom(LstNode, ForEachProc, void *);
+extern void		Lst_Every(Lst, SimpleProc);
+
+extern void		Lst_ForEachNodeWhile(Lst, ForEachNodeWhileProc, void *);
+
+extern bool		Lst_AddNew(Lst, void *);
+/*
+ * for using the list as a queue
+ */
+/* Place an element at tail of queue */
+#define Lst_EnQueue	Lst_AtEnd
+#define Lst_QueueNew	Lst_AddNew
+
+/*
+ * for using the list as a stack
+ */
+#define Lst_Push	Lst_AtFront
+#define Lst_Pop		Lst_DeQueue
+
+/* Remove an element from head of queue */
+extern void *	Lst_DeQueue(Lst);
+
+#define Lst_Datum(ln)	((ln)->datum)
+#define Lst_First(l)	((l)->firstPtr)
+#define Lst_Last(l)	((l)->lastPtr)
+#define Lst_ForEach(l, proc, d) Lst_ForEachFrom(Lst_First(l), proc, d)
+#define Lst_Find(l, cProc, d)	Lst_FindFrom(Lst_First(l), cProc, d)
+#define Lst_Adv(ln)	((ln)->nextPtr)
+#define Lst_Rev(ln)	((ln)->prevPtr)
+
+
+/* Inlines are preferable to macros here because of the type checking. */
+#ifdef HAS_INLINES
+static INLINE LstNode
+Lst_FindConst(Lst l, FindProcConst cProc, const void *d)
+{
+	return Lst_FindFrom(Lst_First(l), (FindProc)cProc, (void *)d);
+}
+
+static INLINE LstNode
+Lst_FindFromConst(LstNode ln, FindProcConst cProc, const void *d)
+{
+	return Lst_FindFrom(ln, (FindProc)cProc, (void *)d);
+}
+#else
+#define Lst_FindConst(l, cProc, d) \
+	Lst_FindFrom(Lst_First(l), (FindProc)cProc, (void *)d)
+#define Lst_FindFromConst(ln, cProc, d) \
+	Lst_FindFrom(ln, (FindProc)cProc, (void *)d)
+#endif
+
+#endif /* _LST_H_ */
diff --git a/usr.bin/make/lst.lib/lst_t.h b/usr.bin/make/lst.lib/lst_t.h
new file mode 100644
index 00000000000..82ec49f2b87
--- /dev/null
+++ b/usr.bin/make/lst.lib/lst_t.h
@@ -0,0 +1,33 @@
+/*	$OpenBSD: lst_t.h,v 1.1 2014/05/12 19:11:20 espie Exp $ */
+
+/*
+ * Copyright (c) 2001 Marc Espie.
+ *
+ * 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT 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 OPENBSD
+ * PROJECT 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.
+ */
+
+typedef struct	List_ {
+	LstNode 	firstPtr; /* first node in list */
+	LstNode 	lastPtr;  /* last node in list */
+} LIST;
+
+#define LIST_TYPE
diff --git a/usr.bin/make/memory.c b/usr.bin/make/memory.c
index 091c986a519..1b2ec463ef1 100644
--- a/usr.bin/make/memory.c
+++ b/usr.bin/make/memory.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: memory.c,v 1.9 2013/04/23 14:32:53 espie Exp $ */
+/* $OpenBSD: memory.c,v 1.10 2014/05/12 19:11:19 espie Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -104,29 +104,22 @@ ecalloc(size_t s1, size_t s2)
 }
 
 void *
-emult_realloc(void *ptr, size_t s1, size_t s2)
+ereallocarray(void *ptr, size_t s1, size_t s2)
 {
-	size_t size;
-
-	if (s1 && SIZE_MAX / s1 < s2) {
-		errno = ENOMEM;
-		enocmem(s1, s2);
-	}
-	size = s1 * s2;
-	if ((ptr = realloc(ptr, size)) == NULL)
+	if ((ptr = reallocarray(ptr, s1, s2)) == NULL)
 		enocmem(s1, s2);
 	return ptr;
 }
 
 /* Support routines for hash tables.  */
 void *
-hash_alloc(size_t s, void *u UNUSED)
+hash_calloc(size_t n, size_t s, void *u UNUSED)
 {
-	return ecalloc(s, 1);
+	return ecalloc(n, s);
 }
 
 void
-hash_free(void *p, size_t s UNUSED, void *u UNUSED)
+hash_free(void *p, void *u UNUSED)
 {
 	free(p);
 }
diff --git a/usr.bin/make/memory.h b/usr.bin/make/memory.h
index 1e7cb10f863..70e7bfd111b 100644
--- a/usr.bin/make/memory.h
+++ b/usr.bin/make/memory.h
@@ -1,7 +1,7 @@
 #ifndef MEMORY_H
 #define MEMORY_H
 
-/* $OpenBSD: memory.h,v 1.7 2010/07/19 19:46:44 espie Exp $ */
+/* $OpenBSD: memory.h,v 1.8 2014/05/12 19:11:19 espie Exp $ */
 
 /*-
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -42,7 +42,7 @@ extern void *emalloc(size_t);
 extern char *estrdup(const char *);
 extern void *erealloc(void *, size_t);
 extern void *ecalloc(size_t, size_t);
-extern void *emult_realloc(void *, size_t, size_t);
+extern void *ereallocarray(void *, size_t, size_t);
 extern int eunlink(const char *);
 extern void esetenv(const char *, const char *);
 
@@ -50,8 +50,8 @@ extern void esetenv(const char *, const char *);
  * definition for cross-builds on deficient systems */
 #define efree	free
 
-extern void *hash_alloc(size_t, void *);
-extern void hash_free(void *, size_t, void *);
+extern void *hash_calloc(size_t, size_t, void *);
+extern void hash_free(void *, void *);
 extern void *element_alloc(size_t, void *);
 
 struct ohash;
diff --git a/usr.bin/make/str.c b/usr.bin/make/str.c
index 755d65f2a25..b4dfc7ac5a4 100644
--- a/usr.bin/make/str.c
+++ b/usr.bin/make/str.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: str.c,v 1.29 2014/04/22 08:26:31 espie Exp $	*/
+/*	$OpenBSD: str.c,v 1.30 2014/05/12 19:11:19 espie Exp $	*/
 /*	$NetBSD: str.c,v 1.13 1996/11/06 17:59:23 christos Exp $	*/
 
 /*-
@@ -150,7 +150,7 @@ brk_string(const char *str, int *store_argc, char **buffer)
 			*t++ = '\0';
 			if (argc == argmax) {
 				argmax *= 2;	/* ramp up fast */
-				argv = emult_realloc(argv,
+				argv = ereallocarray(argv,
 				    (argmax + 1), sizeof(char *));
 			}
 			argv[argc++] = start;
diff --git a/usr.bin/make/suff.c b/usr.bin/make/suff.c
index e26eb652970..8c4b56f82e2 100644
--- a/usr.bin/make/suff.c
+++ b/usr.bin/make/suff.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: suff.c,v 1.87 2014/01/06 12:08:18 espie Exp $ */
+/*	$OpenBSD: suff.c,v 1.88 2014/05/12 19:11:19 espie Exp $ */
 /*	$NetBSD: suff.c,v 1.13 1996/11/06 17:59:25 christos Exp $	*/
 
 /*
@@ -133,7 +133,7 @@ struct Suff_ {
 
 static struct ohash_info suff_info = {
 	offsetof(struct Suff_, name), NULL,
-	hash_alloc, hash_free, element_alloc
+	hash_calloc, hash_free, element_alloc
 };
 
 /*
diff --git a/usr.bin/make/targ.c b/usr.bin/make/targ.c
index ec04e3b3378..134bbde2f02 100644
--- a/usr.bin/make/targ.c
+++ b/usr.bin/make/targ.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: targ.c,v 1.74 2013/05/30 08:58:38 espie Exp $ */
+/*	$OpenBSD: targ.c,v 1.75 2014/05/12 19:11:19 espie Exp $ */
 /*	$NetBSD: targ.c,v 1.11 1997/02/20 16:51:50 christos Exp $	*/
 
 /*
@@ -119,7 +119,7 @@
 
 static struct ohash targets;	/* hash table of targets */
 struct ohash_info gnode_info = {
-	offsetof(GNode, name), NULL, hash_alloc, hash_free, element_alloc
+	offsetof(GNode, name), NULL, hash_calloc, hash_free, element_alloc
 };
 
 #define Targ_FindConstantNode(n, f) Targ_FindNodeh(n, sizeof(n), K_##n, f)
diff --git a/usr.bin/make/targequiv.c b/usr.bin/make/targequiv.c
index a38b4dd4892..ccd0ecc9b6a 100644
--- a/usr.bin/make/targequiv.c
+++ b/usr.bin/make/targequiv.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: targequiv.c,v 1.4 2013/04/23 14:32:53 espie Exp $ */
+/*	$OpenBSD: targequiv.c,v 1.5 2014/05/12 19:11:19 espie Exp $ */
 /*
  * Copyright (c) 2007-2008 Marc Espie.
  *
@@ -53,7 +53,7 @@ struct equiv_list {
 };
 
 static struct ohash_info equiv_info = {
-	offsetof(struct equiv_list, name), NULL, hash_alloc, hash_free,
+	offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free,
 	element_alloc
 };
 
diff --git a/usr.bin/make/var.c b/usr.bin/make/var.c
index 558bbb37b88..03a6001d170 100644
--- a/usr.bin/make/var.c
+++ b/usr.bin/make/var.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: var.c,v 1.97 2014/01/29 23:53:20 espie Exp $	*/
+/*	$OpenBSD: var.c,v 1.98 2014/05/12 19:11:19 espie Exp $	*/
 /*	$NetBSD: var.c,v 1.18 1997/03/18 19:24:46 christos Exp $	*/
 
 /*
@@ -225,7 +225,7 @@ typedef struct Var_ {
 static struct ohash_info var_info = {
 	offsetof(Var, name),
 	NULL,
-	hash_alloc, hash_free, element_alloc
+	hash_calloc, hash_free, element_alloc
 };
 
 static int classify_var(const char *, const char **, uint32_t *);
diff --git a/usr.bin/make/varmodifiers.c b/usr.bin/make/varmodifiers.c
index 149d5c3959f..e12dde88714 100644
--- a/usr.bin/make/varmodifiers.c
+++ b/usr.bin/make/varmodifiers.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: varmodifiers.c,v 1.36 2014/04/22 08:26:31 espie Exp $	*/
+/*	$OpenBSD: varmodifiers.c,v 1.37 2014/05/12 19:11:19 espie Exp $	*/
 /*	$NetBSD: var.c,v 1.18 1997/03/18 19:24:46 christos Exp $	*/
 
 /*
@@ -460,14 +460,14 @@ do_sort(const char *s, const struct Name *dummy UNUSED, void *arg UNUSED)
 	const char *start, *end;
 
 	n = 1024;	/* start at 1024 words */
-	t = ecalloc(n, sizeof(struct Name));
+	t = ereallocarray(NULL, n, sizeof(struct Name));
 	start = s;
 	end = start;
 
 	for (i = 0;; i++) {
 		if (i == n) {
 			n *= 2;
-			t = emult_realloc(t, n, sizeof(struct Name));
+			t = ereallocarray(t, n, sizeof(struct Name));
 		}
 		start = iterate_words(&end);
 		if (start == NULL)
diff --git a/usr.bin/mandoc/Makefile b/usr.bin/mandoc/Makefile
index 68cfecc754e..e2a6c0dc232 100644
--- a/usr.bin/mandoc/Makefile
+++ b/usr.bin/mandoc/Makefile
@@ -1,10 +1,11 @@
-#	$OpenBSD: Makefile,v 1.76 2014/04/18 10:00:48 schwarze Exp $
+#	$OpenBSD: Makefile,v 1.77 2014/05/12 19:11:20 espie Exp $
 
 .include <bsd.own.mk>
 
 CFLAGS  += -DVERSION=\"1.13.0\"
 CFLAGS  += -W -Wall -Wstrict-prototypes -Wno-unused-parameter
-LDADD	+= -lsqlite3
+DPADD += ${LIBUTIL}
+LDADD	+= -lsqlite3 -lutil
 
 SRCS=	mandoc.c mandoc_aux.c read.c \
 	roff.c tbl.c tbl_opts.c tbl_layout.c tbl_data.c eqn.c
diff --git a/usr.bin/mandoc/mandocdb.c b/usr.bin/mandoc/mandocdb.c
index ee4f12f4e05..dd6b7d5182c 100644
--- a/usr.bin/mandoc/mandocdb.c
+++ b/usr.bin/mandoc/mandocdb.c
@@ -1,4 +1,4 @@
-/*	$Id: mandocdb.c,v 1.105 2014/05/07 16:18:57 schwarze Exp $ */
+/*	$Id: mandocdb.c,v 1.106 2014/05/12 19:11:20 espie Exp $ */
 /*
  * Copyright (c) 2011, 2012 Kristaps Dzonsons <kristaps@bsd.lv>
  * Copyright (c) 2011, 2012, 2013, 2014 Ingo Schwarze <schwarze@openbsd.org>
@@ -137,8 +137,8 @@ static	int	 dbopen(int);
 static	void	 dbprune(void);
 static	void	 filescan(const char *);
 static	void	*hash_alloc(size_t, void *);
-static	void	 hash_free(void *, size_t, void *);
-static	void	*hash_halloc(size_t, void *);
+static	void	 hash_free(void *, void *);
+static	void	*hash_calloc(size_t, size_t, void *);
 static	void	 mlink_add(struct mlink *, const struct stat *);
 static	void	 mlink_check(struct mpage *, struct mlink *);
 static	void	 mlink_free(struct mlink *);
@@ -328,8 +328,8 @@ mandocdb(int argc, char *argv[])
 	memset(&dirs, 0, sizeof(struct manpaths));
 
 	mpages_info.alloc  = mlinks_info.alloc  = hash_alloc;
-	mpages_info.halloc = mlinks_info.halloc = hash_halloc;
-	mpages_info.hfree  = mlinks_info.hfree  = hash_free;
+	mpages_info.calloc = mlinks_info.calloc = hash_calloc;
+	mpages_info.free  = mlinks_info.free  = hash_free;
 
 	mpages_info.key_offset = offsetof(struct mpage, inodev);
 	mlinks_info.key_offset = offsetof(struct mlink, file);
@@ -1082,8 +1082,8 @@ mpages_merge(struct mchars *mc, struct mparse *mp)
 	enum mandoclevel	 lvl;
 
 	str_info.alloc = hash_alloc;
-	str_info.halloc = hash_halloc;
-	str_info.hfree = hash_free;
+	str_info.calloc = hash_calloc;
+	str_info.free = hash_free;
 	str_info.key_offset = offsetof(struct str, key);
 
 	if (0 == nodb)
@@ -2339,10 +2339,10 @@ prepare_statements:
 }
 
 static void *
-hash_halloc(size_t sz, void *arg)
+hash_calloc(size_t n, size_t sz, void *arg)
 {
 
-	return(mandoc_calloc(1, sz));
+	return(mandoc_calloc(n, sz));
 }
 
 static void *
@@ -2353,7 +2353,7 @@ hash_alloc(size_t sz, void *arg)
 }
 
 static void
-hash_free(void *p, size_t sz, void *arg)
+hash_free(void *p, void *arg)
 {
 
 	free(p);
diff --git a/usr.bin/mandoc/mansearch.c b/usr.bin/mandoc/mansearch.c
index eb68043b878..87f43cf59b5 100644
--- a/usr.bin/mandoc/mansearch.c
+++ b/usr.bin/mandoc/mansearch.c
@@ -1,4 +1,4 @@
-/*	$Id: mansearch.c,v 1.26 2014/04/23 21:06:33 schwarze Exp $ */
+/*	$Id: mansearch.c,v 1.27 2014/05/12 19:11:20 espie Exp $ */
 /*
  * Copyright (c) 2012 Kristaps Dzonsons <kristaps@bsd.lv>
  * Copyright (c) 2013, 2014 Ingo Schwarze <schwarze@openbsd.org>
@@ -77,8 +77,8 @@ static	void		 buildnames(struct manpage *, sqlite3 *,
 static	char		*buildoutput(sqlite3 *, sqlite3_stmt *,
 				 uint64_t, uint64_t);
 static	void		*hash_alloc(size_t, void *);
-static	void		 hash_free(void *, size_t, void *);
-static	void		*hash_halloc(size_t, void *);
+static	void		 hash_free(void *, void *);
+static	void		*hash_calloc(size_t, size_t, void *);
 static	struct expr	*exprcomp(const struct mansearch *,
 				int, char *[]);
 static	void		 exprfree(struct expr *);
@@ -163,11 +163,9 @@ mansearch(const struct mansearch *search,
 	unsigned int	 idx;
 	size_t		 i, j, cur, maxres;
 
-	memset(&info, 0, sizeof(struct ohash_info));
-
-	info.halloc = hash_halloc;
+	info.calloc = hash_calloc;
 	info.alloc = hash_alloc;
-	info.hfree = hash_free;
+	info.free = hash_free;
 	info.key_offset = offsetof(struct match, pageid);
 
 	*sz = cur = maxres = 0;
@@ -782,10 +780,10 @@ exprfree(struct expr *p)
 }
 
 static void *
-hash_halloc(size_t sz, void *arg)
+hash_calloc(size_t nmemb, size_t sz, void *arg)
 {
 
-	return(mandoc_calloc(1, sz));
+	return(mandoc_calloc(nmemb, sz));
 }
 
 static void *
@@ -796,7 +794,7 @@ hash_alloc(size_t sz, void *arg)
 }
 
 static void
-hash_free(void *p, size_t sz, void *arg)
+hash_free(void *p, void *arg)
 {
 
 	free(p);
diff --git a/usr.bin/tsort/Makefile b/usr.bin/tsort/Makefile
index b60a80c05f4..23e36f5e7db 100644
--- a/usr.bin/tsort/Makefile
+++ b/usr.bin/tsort/Makefile
@@ -1,7 +1,10 @@
-#	$OpenBSD: Makefile,v 1.5 2001/07/19 10:20:01 espie Exp $
+#	$OpenBSD: Makefile,v 1.6 2014/05/12 19:11:20 espie Exp $
 
-PROG=	tsort
+PROG =	tsort
+SRCS = tsort.c
 
-CDIAGFLAGS=-Wall -Wno-char-subscripts -Wstrict-prototypes -pedantic -W
+CDIAGFLAGS = -Wall -Wno-char-subscripts -Wstrict-prototypes -pedantic -W
+DPADD += ${LIBUTIL}
+LDADD += -lutil
 
 .include <bsd.prog.mk>
diff --git a/usr.bin/tsort/tsort.c b/usr.bin/tsort/tsort.c
index de242dcb581..5b360cd3592 100644
--- a/usr.bin/tsort/tsort.c
+++ b/usr.bin/tsort/tsort.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: tsort.c,v 1.22 2013/11/27 00:13:24 deraadt Exp $ */
+/* $OpenBSD: tsort.c,v 1.23 2014/05/12 19:11:20 espie Exp $ */
 /* ex:ts=8 sw=4:
  *
  * Copyright (c) 1999-2004 Marc Espie <espie@openbsd.org>
@@ -146,14 +146,14 @@ static void enqueue(struct array *, struct node *);
 
 
 #define erealloc(n, s)	emem(realloc(n, s))
-static void *hash_alloc(size_t, void *);
-static void hash_free(void *, size_t, void *);
+static void *hash_calloc(size_t, size_t, void *);
+static void hash_free(void *, void *);
 static void* entry_alloc(size_t, void *);
 static void *emalloc(size_t);
 static void *emem(void *);
 #define DEBUG_TRAVERSE 0
 static struct ohash_info node_info = {
-	offsetof(struct node, k), NULL, hash_alloc, hash_free, entry_alloc };
+	offsetof(struct node, k), NULL, hash_calloc, hash_free, entry_alloc };
 
 
 int main(int, char *[]);
@@ -173,13 +173,13 @@ emem(void *p)
 }
 
 static void *
-hash_alloc(size_t s, void *u UNUSED)
+hash_calloc(size_t n, size_t s, void *u UNUSED)
 {
-	return emem(calloc(s, 1));
+	return emem(calloc(n, s));
 }
 
 static void
-hash_free(void *p, size_t s UNUSED, void *u UNUSED)
+hash_free(void *p, void *u UNUSED)
 {
 	free(p);
 }
-- 
2.20.1