add a hash table mechanism based upon hcreate(3) but one that allows

us to maintain multiple hash tables concurrently.

immediatly start using it to keep track of what directories
we have already created and what CVS dirs we already created so
we do not recreate them when we do not need to.

we will be switching more internals to use this soon.
rejoice for cheaper lookups.

ok tobias@

6 files changed, 252 insertions, 7 deletions

diff --git a/usr.bin/cvs/Makefile b/usr.bin/cvs/Makefile
index c5631c72084..79117100072 100644
--- a/usr.bin/cvs/Makefile
+++ b/usr.bin/cvs/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.46 2008/06/10 01:00:34 joris Exp $
+#	$OpenBSD: Makefile,v 1.47 2008/06/21 15:39:15 joris Exp $
 
 PROG=	opencvs
 MAN=	cvsintro.7 # cvs.1 cvs.5
@@ -6,10 +6,11 @@ CPPFLAGS+=-I${.CURDIR}
 
 SRCS=	cvs.c add.c admin.c annotate.c atomicio.c commit.c config.c \
 	checkout.c client.c buf.c cmd.c date.y diff.c diff3.c \
-	diff_internals.c edit.c entries.c fatal.c file.c getlog.c history.c \
-	log.c logmsg.c modules.c import.c init.c release.c remove.c \
-	repository.c rcs.c rcsnum.c remote.c root.c server.c status.c tag.c \
-	trigger.c worklist.c util.c update.c version.c watch.c xmalloc.c
+	diff_internals.c edit.c entries.c fatal.c file.c getlog.c hash.c \
+	hash_func.c history.c log.c logmsg.c modules.c import.c init.c  \
+	release.c remove.c repository.c rcs.c rcsnum.c remote.c root.c \
+	server.c status.c tag.c trigger.c worklist.c util.c update.c version.c \
+	watch.c xmalloc.c
 
 CFLAGS+=-Wall
 CFLAGS+=-Wstrict-prototypes -Wmissing-prototypes
diff --git a/usr.bin/cvs/cvs.c b/usr.bin/cvs/cvs.c
index 83b7fbf459d..25d2d6efe62 100644
--- a/usr.bin/cvs/cvs.c
+++ b/usr.bin/cvs/cvs.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: cvs.c,v 1.149 2008/06/17 11:05:39 joris Exp $	*/
+/*	$OpenBSD: cvs.c,v 1.150 2008/06/21 15:39:15 joris Exp $	*/
 /*
  * Copyright (c) 2006, 2007 Joris Vink <joris@openbsd.org>
  * Copyright (c) 2004 Jean-Francois Brousseau <jfb@openbsd.org>
@@ -37,6 +37,7 @@
 
 #include "cvs.h"
 #include "remote.h"
+#include "hash.h"
 
 extern char *__progname;
 
@@ -80,6 +81,9 @@ volatile sig_atomic_t sig_received = 0;
 
 extern CVSENTRIES *current_list;
 
+struct hash_table created_directories;
+struct hash_table created_cvs_directories;
+
 void
 sighandler(int sig)
 {
@@ -189,6 +193,9 @@ main(int argc, char **argv)
 	SLIST_INIT(&repo_locks);
 	SLIST_INIT(&temp_files);
 
+	hash_table_init(&created_directories, 100);
+	hash_table_init(&created_cvs_directories, 100);
+
 	/* check environment so command-line options override it */
 	if ((envstr = getenv("CVS_RSH")) != NULL)
 		cvs_rsh = envstr;
diff --git a/usr.bin/cvs/hash.c b/usr.bin/cvs/hash.c
new file mode 100644
index 00000000000..54a41466adf
--- /dev/null
+++ b/usr.bin/cvs/hash.c
@@ -0,0 +1,86 @@
+/*	$OpenBSD: hash.c,v 1.1 2008/06/21 15:39:15 joris Exp $	*/
+/*
+ * Copyright (c) 2008 Joris Vink <joris@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/param.h>
+#include <sys/queue.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "cvs.h"
+#include "hash.h"
+#include "xmalloc.h"
+
+void
+hash_table_init(struct hash_table *htable, size_t hsize)
+{
+	size_t i;
+	u_int power;
+
+	if (hsize < MIN_HASH_SIZE)
+		hsize = MIN_HASH_SIZE;
+
+	if (hsize > MAX_HASH_SIZE)
+		hsize = MAX_HASH_SIZE;
+
+	if ((hsize & (hsize - 1)) != 0) {
+		for (power = 0; hsize != 0; power++)
+			hsize >>= 1;
+		hsize = 1 << power;
+	}
+
+	htable->h_table = xcalloc(hsize, sizeof(struct hash_head *));
+	htable->h_size = hsize;
+
+	for (i = 0; i < htable->h_size; i++)
+		SLIST_INIT(&(htable->h_table[i]));
+}
+
+void
+hash_table_enter(struct hash_table *htable, struct hash_data *e)
+{
+	uint32_t hashv;
+	struct hash_head *tableh;
+	struct hash_table_entry *entry;
+
+	hashv = hash4(e->h_key, strlen(e->h_key));
+	tableh = &(htable->h_table[(hashv & (htable->h_size - 1))]);
+
+	entry = xmalloc(sizeof(*entry));
+	entry->h_data.h_key = e->h_key;
+	entry->h_data.h_data = e->h_data;
+	SLIST_INSERT_HEAD(tableh, entry, h_list);
+}
+
+struct hash_data *
+hash_table_find(struct hash_table *htable, const char *key, size_t len)
+{
+	uint32_t hashv;
+	struct hash_head *tableh;
+	struct hash_table_entry *entry;
+
+	hashv = hash4(key, len);
+	tableh = &(htable->h_table[(hashv & (htable->h_size - 1))]);
+
+	SLIST_FOREACH(entry, tableh, h_list) {
+		if (!strcmp(entry->h_data.h_key, key))
+			return (&(entry->h_data));
+	}
+
+	return (NULL);
+}
diff --git a/usr.bin/cvs/hash.h b/usr.bin/cvs/hash.h
new file mode 100644
index 00000000000..012421d67d8
--- /dev/null
+++ b/usr.bin/cvs/hash.h
@@ -0,0 +1,55 @@
+/*	$OpenBSD: hash.h,v 1.1 2008/06/21 15:39:15 joris Exp $	*/
+/*
+ * Copyright (c) 2008 Joris Vink <joris@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/*
+ * This is based upon:
+ *	src/lib/libc/stdlib/hcreate.c
+ */
+
+#ifndef _H_HASH
+#define _H_HASH
+
+struct hash_data {
+	char	*h_key;
+	void	*h_data;
+};
+
+struct hash_table_entry {
+	SLIST_ENTRY(hash_table_entry)	h_list;
+	struct hash_data		h_data;
+};
+
+SLIST_HEAD(hash_head, hash_table_entry);
+
+struct hash_table {
+	struct hash_head	*h_table;
+	size_t			h_size;
+};
+
+#define MIN_HASH_SIZE	(1 << 4)
+#define MAX_HASH_SIZE	((size_t)1 << (sizeof(size_t) * 8 - 1 - 5))
+
+void	hash_table_init(struct hash_table *, size_t);
+void	hash_table_enter(struct hash_table *, struct hash_data *);
+struct hash_data *hash_table_find(struct hash_table *, const char *, size_t);
+
+u_int32_t hash4(const char *, size_t);
+
+extern struct hash_table created_directories;
+extern struct hash_table created_cvs_directories;
+
+#endif
diff --git a/usr.bin/cvs/hash_func.c b/usr.bin/cvs/hash_func.c
new file mode 100644
index 00000000000..adb4f2bded5
--- /dev/null
+++ b/usr.bin/cvs/hash_func.c
@@ -0,0 +1,77 @@
+/*	$OpenBSD: hash_func.c,v 1.1 2008/06/21 15:39:15 joris Exp $	*/
+
+/*-
+ * Copyright (c) 1990, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Margo Seltzer.
+ *
+ * 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.
+ */
+
+#include <sys/types.h>
+#include <sys/queue.h>
+
+#include "hash.h"
+
+/* Chris Torek's hash function. */
+u_int32_t
+hash4(const char *key, size_t len)
+{
+	u_int32_t h, loop;
+	const char *k;
+
+#define HASH4   h = (h << 5) + h + *k++;
+
+	h = 0;
+	k = key;
+	if (len > 0) {
+		loop = (len + 8 - 1) >> 3;
+
+		switch (len & (8 - 1)) {
+		case 0:
+			do {	/* All fall throughs */
+				HASH4;
+		case 7:
+				HASH4;
+		case 6:
+				HASH4;
+		case 5:
+				HASH4;
+		case 4:
+				HASH4;
+		case 3:
+				HASH4;
+		case 2:
+				HASH4;
+		case 1:
+				HASH4;
+			} while (--loop);
+		}
+
+	}
+	return (h);
+}
diff --git a/usr.bin/cvs/util.c b/usr.bin/cvs/util.c
index 3ad983df1c3..339179155e1 100644
--- a/usr.bin/cvs/util.c
+++ b/usr.bin/cvs/util.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: util.c,v 1.146 2008/06/14 03:19:15 joris Exp $	*/
+/*	$OpenBSD: util.c,v 1.147 2008/06/21 15:39:15 joris Exp $	*/
 /*
  * Copyright (c) 2004 Jean-Francois Brousseau <jfb@openbsd.org>
  * Copyright (c) 2005, 2006 Joris Vink <joris@openbsd.org>
@@ -41,6 +41,7 @@
 
 #include "cvs.h"
 #include "remote.h"
+#include "hash.h"
 
 extern int print_stdout;
 extern int build_dirs;
@@ -525,6 +526,15 @@ cvs_mkadmin(const char *path, const char *root, const char *repo,
 	FILE *fp;
 	int fd;
 	char buf[MAXPATHLEN];
+	struct hash_data *hdata, hd;
+
+	hdata = hash_table_find(&created_cvs_directories, path, strlen(path));
+	if (hdata != NULL)
+		return;
+
+	hd.h_key = xstrdup(path);
+	hd.h_data = NULL;
+	hash_table_enter(&created_cvs_directories, &hd);
 
 	if (cvs_server_active == 0)
 		cvs_log(LP_TRACE, "cvs_mkadmin(%s, %s, %s, %s, %s)",
@@ -578,9 +588,18 @@ cvs_mkpath(const char *path, char *tag)
 	CVSENTRIES *ent;
 	FILE *fp;
 	size_t len;
+	struct hash_data *hdata, hd;
 	char *entry, sticky[CVS_REV_BUFSZ];
 	char *sp, *dp, *dir, *p, rpath[MAXPATHLEN], repo[MAXPATHLEN];
 
+	hdata = hash_table_find(&created_directories, path, strlen(path));
+	if (hdata != NULL)
+		return;
+
+	hd.h_key = xstrdup(path);
+	hd.h_data = NULL;
+	hash_table_enter(&created_directories, &hd);
+
 	if (current_cvsroot->cr_method != CVS_METHOD_LOCAL ||
 	    cvs_server_active == 1)
 		cvs_validate_directory(path);