switch our file and directory lists to RB trees (see tree(3)),

so we can benefit from faster lookup times while recursing.

6 files changed, 73 insertions, 57 deletions

diff --git a/usr.bin/cvs/checkout.c b/usr.bin/cvs/checkout.c
index 76468d3ff33..d0f7fcf701f 100644
--- a/usr.bin/cvs/checkout.c
+++ b/usr.bin/cvs/checkout.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: checkout.c,v 1.161 2009/03/18 09:14:09 joris Exp $	*/
+/*	$OpenBSD: checkout.c,v 1.162 2009/03/25 21:50:33 joris Exp $	*/
 /*
  * Copyright (c) 2006 Joris Vink <joris@openbsd.org>
  *
@@ -299,10 +299,10 @@ checkout_check_repository(int argc, char **argv)
 		mc = cvs_module_lookup(argv[i]);
 		current_module = mc;
 
-		TAILQ_FOREACH(fl, &(mc->mc_ignores), flist)
+		RB_FOREACH(fl, cvs_flisthead, &(mc->mc_ignores))
 			cvs_file_ignore(fl->file_path, &checkout_ign_pats);
 
-		TAILQ_FOREACH(fl, &(mc->mc_modules), flist) {
+		RB_FOREACH(fl, cvs_flisthead, &(mc->mc_modules)) {
 			module_repo_root = NULL;
 
 			(void)xsnprintf(repo, sizeof(repo), "%s/%s",
@@ -363,10 +363,12 @@ checkout_check_repository(int argc, char **argv)
 		}
 
 		if (mc->mc_canfree == 1) {
-			for (fl = TAILQ_FIRST(&(mc->mc_modules));
-			    fl != TAILQ_END(&(mc->mc_modules)); fl = nxt) {
-				nxt = TAILQ_NEXT(fl, flist);
-				TAILQ_REMOVE(&(mc->mc_modules), fl, flist);
+			for (fl = RB_MIN(cvs_flisthead, &(mc->mc_modules));
+			    fl != NULL; fl = nxt) {
+				nxt = RB_NEXT(cvs_flisthead,
+				    &(mc->mc_modules), fl);
+				RB_REMOVE(cvs_flisthead,
+				    &(mc->mc_modules), fl);
 				xfree(fl->file_path);
 				xfree(fl);
 			}
@@ -424,8 +426,8 @@ checkout_repository(const char *repobase, const char *wdbase)
 	struct cvs_flisthead fl, dl;
 	struct cvs_recursion cr;
 
-	TAILQ_INIT(&fl);
-	TAILQ_INIT(&dl);
+	RB_INIT(&fl);
+	RB_INIT(&dl);
 
 	cvs_history_add((cvs_cmdop == CVS_OP_CHECKOUT) ?
 	    CVS_HISTORY_CHECKOUT : CVS_HISTORY_EXPORT, NULL, wdbase);
diff --git a/usr.bin/cvs/commit.c b/usr.bin/cvs/commit.c
index f2a86bf08f6..4163bdf9631 100644
--- a/usr.bin/cvs/commit.c
+++ b/usr.bin/cvs/commit.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: commit.c,v 1.145 2008/08/29 09:54:22 tobias Exp $	*/
+/*	$OpenBSD: commit.c,v 1.146 2009/03/25 21:50:33 joris Exp $	*/
 /*
  * Copyright (c) 2006 Joris Vink <joris@openbsd.org>
  * Copyright (c) 2006 Xavier Santolaria <xsa@openbsd.org>
@@ -110,10 +110,10 @@ cvs_commit(int argc, char **argv)
 	if (Fflag && mflag)
 		fatal("cannot specify both a log file and a message");
 
-	TAILQ_INIT(&files_affected);
-	TAILQ_INIT(&files_added);
-	TAILQ_INIT(&files_removed);
-	TAILQ_INIT(&files_modified);
+	RB_INIT(&files_affected);
+	RB_INIT(&files_added);
+	RB_INIT(&files_removed);
+	RB_INIT(&files_modified);
 
 	TAILQ_INIT(&files_info);
 	conflicts_found = 0;
@@ -132,7 +132,7 @@ cvs_commit(int argc, char **argv)
 		fatal("%d conflicts found, please correct these first",
 		    conflicts_found);
 
-	if (TAILQ_EMPTY(&files_affected))
+	if (RB_EMPTY(&files_affected))
 		return (0);
 
 	if (current_cvsroot->cr_method != CVS_METHOD_LOCAL) {
@@ -163,7 +163,7 @@ cvs_commit(int argc, char **argv)
 
 		line_list = cvs_trigger_getlines(CVS_PATH_COMMITINFO, repo);
 		if (line_list != NULL) {
-			TAILQ_FOREACH(l, &files_affected, flist) {
+			RB_FOREACH(l, cvs_flisthead, &files_affected) {
 				fi = xcalloc(1, sizeof(*fi));
 				fi->file_path = xstrdup(l->file_path);
 				TAILQ_INSERT_TAIL(&files_info, fi,
@@ -241,10 +241,10 @@ cvs_commit_loginfo(char *repo)
 
 	cvs_trigger_loginfo_header(buf, repo);
 
-	if (!TAILQ_EMPTY(&files_added)) {
+	if (!RB_EMPTY(&files_added)) {
 		cvs_buf_puts(buf, "Added Files:");
 
-		TAILQ_FOREACH(cf, &files_added, flist) {
+		RB_FOREACH(cf, cvs_flisthead, &files_added) {
 			cvs_buf_putc(buf, '\n');
 			cvs_buf_putc(buf, '\t');
 			cvs_buf_puts(buf, cf->file_path);
@@ -253,10 +253,10 @@ cvs_commit_loginfo(char *repo)
 		cvs_buf_putc(buf, '\n');
 	}
 
-	if (!TAILQ_EMPTY(&files_modified)) {
+	if (!RB_EMPTY(&files_modified)) {
 		cvs_buf_puts(buf, "Modified Files:");
 
-		TAILQ_FOREACH(cf, &files_modified, flist) {
+		RB_FOREACH(cf, cvs_flisthead, &files_modified) {
 			cvs_buf_putc(buf, '\n');
 			cvs_buf_putc(buf, '\t');
 			cvs_buf_puts(buf, cf->file_path);
@@ -265,10 +265,10 @@ cvs_commit_loginfo(char *repo)
 		cvs_buf_putc(buf, '\n');
 	}
 
-	if (!TAILQ_EMPTY(&files_removed)) {
+	if (!RB_EMPTY(&files_removed)) {
 		cvs_buf_puts(buf, "Removed Files:");
 
-		TAILQ_FOREACH(cf, &files_removed, flist) {
+		RB_FOREACH(cf, cvs_flisthead, &files_removed) {
 			cvs_buf_putc(buf, '\n');
 			cvs_buf_putc(buf, '\t');
 			cvs_buf_puts(buf, cf->file_path);
diff --git a/usr.bin/cvs/file.c b/usr.bin/cvs/file.c
index 701aaff623d..ab37beea288 100644
--- a/usr.bin/cvs/file.c
+++ b/usr.bin/cvs/file.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: file.c,v 1.255 2009/03/24 18:33:25 joris Exp $	*/
+/*	$OpenBSD: file.c,v 1.256 2009/03/25 21:50:33 joris Exp $	*/
 /*
  * Copyright (c) 2006 Joris Vink <joris@openbsd.org>
  * Copyright (c) 2004 Jean-Francois Brousseau <jfb@openbsd.org>
@@ -81,6 +81,8 @@ struct ignore_head cvs_ign_pats;
 struct ignore_head dir_ign_pats;
 struct ignore_head checkout_ign_pats;
 
+RB_GENERATE(cvs_flisthead, cvs_filelist, flist, cvs_filelist_cmp);
+
 void
 cvs_file_init(void)
 {
@@ -187,7 +189,7 @@ cvs_file_run(int argc, char **argv, struct cvs_recursion *cr)
 	int i;
 	struct cvs_flisthead fl;
 
-	TAILQ_INIT(&fl);
+	RB_INIT(&fl);
 
 	for (i = 0; i < argc; i++)
 		cvs_file_get(argv[i], FILE_USER_SUPPLIED, &fl);
@@ -197,23 +199,24 @@ cvs_file_run(int argc, char **argv, struct cvs_recursion *cr)
 }
 
 struct cvs_filelist *
-cvs_file_get(const char *name, int flags, struct cvs_flisthead *fl)
+cvs_file_get(char *name, int flags, struct cvs_flisthead *fl)
 {
-	const char *p;
-	struct cvs_filelist *l;
+	char *p;
+	struct cvs_filelist *l, find;
 
 	for (p = name; p[0] == '.' && p[1] == '/';)
 		p += 2;
 
-	TAILQ_FOREACH(l, fl, flist)
-		if (!strcmp(l->file_path, p))
-			return (l);
+	find.file_path = p;
+	l = RB_FIND(cvs_flisthead, fl, &find);
+	if (l != NULL)
+		return (l);
 
 	l = (struct cvs_filelist *)xmalloc(sizeof(*l));
 	l->file_path = xstrdup(p);
 	l->flags = flags;
 
-	TAILQ_INSERT_TAIL(fl, l, flist);
+	RB_INSERT(cvs_flisthead, fl, l);
 	return (l);
 }
 
@@ -259,7 +262,7 @@ cvs_file_walklist(struct cvs_flisthead *fl, struct cvs_recursion *cr)
 	struct cvs_filelist *l, *nxt;
 	char *d, *f, repo[MAXPATHLEN], fpath[MAXPATHLEN];
 
-	for (l = TAILQ_FIRST(fl); l != NULL; l = nxt) {
+	for (l = RB_MIN(cvs_flisthead, fl); l != NULL; l = nxt) {
 		if (cvs_quit)
 			fatal("received signal %d", sig_received);
 
@@ -373,7 +376,7 @@ cvs_file_walklist(struct cvs_flisthead *fl, struct cvs_recursion *cr)
 		cvs_file_free(cf);
 
 next:
-		nxt = TAILQ_NEXT(l, flist);
+		nxt = RB_NEXT(cvs_flisthead, fl, l);
 	}
 }
 
@@ -410,8 +413,8 @@ cvs_file_walkdir(struct cvs_file *cf, struct cvs_recursion *cr)
 	 * locally available directories or try to create them.
 	 */
 	if (!(cmdp->cmd_flags & CVS_USE_WDIR)) {
-		TAILQ_INIT(&fl);
-		TAILQ_INIT(&dl);
+		RB_INIT(&fl);
+		RB_INIT(&dl);
 		goto walkrepo;
 	}
 
@@ -459,8 +462,8 @@ cvs_file_walkdir(struct cvs_file *cf, struct cvs_recursion *cr)
 		bufsize = st.st_blksize;
 
 	buf = xmalloc(bufsize);
-	TAILQ_INIT(&fl);
-	TAILQ_INIT(&dl);
+	RB_INIT(&fl);
+	RB_INIT(&dl);
 
 	while ((nbytes = getdirentries(cf->fd, buf, bufsize, &base)) > 0) {
 		ebuf = buf + nbytes;
@@ -615,10 +618,11 @@ walkrepo:
 void
 cvs_file_freelist(struct cvs_flisthead *fl)
 {
-	struct cvs_filelist *f;
+	struct cvs_filelist *f, *nxt;
 
-	while ((f = TAILQ_FIRST(fl)) != NULL) {
-		TAILQ_REMOVE(fl, f, flist);
+	for (f = RB_MIN(cvs_flisthead, fl); f != NULL; f = nxt) {
+		nxt = RB_NEXT(cvs_flisthead, fl, f);
+		RB_REMOVE(cvs_flisthead, fl, f);
 		xfree(f->file_path);
 		xfree(f);
 	}
@@ -1104,3 +1108,9 @@ out:
 
 	return (ret);
 }
+
+int
+cvs_filelist_cmp(struct cvs_filelist *f1, struct cvs_filelist *f2)
+{
+	return (strcmp(f1->file_path, f2->file_path));
+}
diff --git a/usr.bin/cvs/file.h b/usr.bin/cvs/file.h
index 2845cbeed00..c7902a5e2fc 100644
--- a/usr.bin/cvs/file.h
+++ b/usr.bin/cvs/file.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: file.h,v 1.51 2009/02/21 13:44:18 joris Exp $	*/
+/*	$OpenBSD: file.h,v 1.52 2009/03/25 21:50:33 joris Exp $	*/
 /*
  * Copyright (c) 2006 Joris Vink <joris@openbsd.org>
  * Copyright (c) 2004 Jean-Francois Brousseau <jfb@openbsd.org>
@@ -29,6 +29,7 @@
 #define FILE_H
 
 #include <sys/queue.h>
+#include <sys/tree.h>
 
 #include <dirent.h>
 #include <stdio.h>
@@ -76,12 +77,13 @@ struct cvs_file {
 #define FILE_ON_DISK		0x08
 
 struct cvs_filelist {
+	RB_ENTRY(cvs_filelist) flist;
 	char	*file_path;
 	int	flags;
-	TAILQ_ENTRY(cvs_filelist) flist;
 };
 
-TAILQ_HEAD(cvs_flisthead, cvs_filelist);
+RB_HEAD(cvs_flisthead, cvs_filelist);
+RB_PROTOTYPE(cvs_flisthead, cvs_filelist, flist, cvs_filelist_cmp);
 
 struct cvs_recursion;
 
@@ -106,8 +108,9 @@ void	cvs_file_run(int, char **, struct cvs_recursion *);
 void	cvs_file_walklist(struct cvs_flisthead *, struct cvs_recursion *);
 void	cvs_file_walkdir(struct cvs_file *, struct cvs_recursion *);
 void	cvs_file_freelist(struct cvs_flisthead *);
-struct cvs_filelist *cvs_file_get(const char *, int, struct cvs_flisthead *);
+struct cvs_filelist *cvs_file_get(char *, int, struct cvs_flisthead *);
 
+int	cvs_filelist_cmp(struct cvs_filelist *, struct cvs_filelist *);
 int	cvs_file_chkign(const char *);
 int	cvs_file_cmpname(const char *, const char *);
 int	cvs_file_cmp(const char *, const char *);
diff --git a/usr.bin/cvs/logmsg.c b/usr.bin/cvs/logmsg.c
index 79a33fa5a25..90aeaa816e4 100644
--- a/usr.bin/cvs/logmsg.c
+++ b/usr.bin/cvs/logmsg.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: logmsg.c,v 1.51 2008/11/26 00:09:02 ray Exp $	*/
+/*	$OpenBSD: logmsg.c,v 1.52 2009/03/25 21:50:33 joris Exp $	*/
 /*
  * Copyright (c) 2007 Joris Vink <joris@openbsd.org>
  *
@@ -163,27 +163,27 @@ cvs_logmsg_create(char *dir, struct cvs_flisthead *added,
 		    dir != NULL ? dir : ".", CVS_LOGMSG_PREFIX);
 	}
 
-	if (added != NULL && !TAILQ_EMPTY(added)) {
+	if (added != NULL && !RB_EMPTY(added)) {
 		fprintf(fp, "%s Added Files:", CVS_LOGMSG_PREFIX);
-		TAILQ_FOREACH(cf, added, flist)
+		RB_FOREACH(cf, cvs_flisthead, added)
 			fprintf(fp, "\n%s\t%s", CVS_LOGMSG_PREFIX,
 			    dir != NULL ? basename(cf->file_path) :
 			    cf->file_path);
 		fputs("\n", fp);
 	}
 
-	if (removed != NULL && !TAILQ_EMPTY(removed)) {
+	if (removed != NULL && !RB_EMPTY(removed)) {
 		fprintf(fp, "%s Removed Files:", CVS_LOGMSG_PREFIX);
-		TAILQ_FOREACH(cf, removed, flist)
+		RB_FOREACH(cf, cvs_flisthead, removed)
 			fprintf(fp, "\n%s\t%s", CVS_LOGMSG_PREFIX,
 			    dir != NULL ? basename(cf->file_path) :
 			    cf->file_path);
 		fputs("\n", fp);
 	}
 
-	if (modified != NULL && !TAILQ_EMPTY(modified)) {
+	if (modified != NULL && !RB_EMPTY(modified)) {
 		fprintf(fp, "%s Modified Files:", CVS_LOGMSG_PREFIX);
-		TAILQ_FOREACH(cf, modified, flist)
+		RB_FOREACH(cf, cvs_flisthead, modified)
 			fprintf(fp, "\n%s\t%s", CVS_LOGMSG_PREFIX,
 			    dir != NULL ? basename(cf->file_path) :
 			    cf->file_path);
diff --git a/usr.bin/cvs/modules.c b/usr.bin/cvs/modules.c
index a0ac43feafc..b1565f36bae 100644
--- a/usr.bin/cvs/modules.c
+++ b/usr.bin/cvs/modules.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: modules.c,v 1.13 2008/03/08 21:58:34 tobias Exp $	*/
+/*	$OpenBSD: modules.c,v 1.14 2009/03/25 21:50:33 joris Exp $	*/
 /*
  * Copyright (c) 2008 Joris Vink <joris@openbsd.org>
  *
@@ -159,8 +159,9 @@ modules_parse_line(char *line, int lineno)
 	mi->mi_str = bline;
 
 	dirname = NULL;
-	TAILQ_INIT(&(mi->mi_modules));
-	TAILQ_INIT(&(mi->mi_ignores));
+	RB_INIT(&(mi->mi_modules));
+	RB_INIT(&(mi->mi_ignores));
+
 	for (sp = val; *sp != '\0'; sp = dp) {
 		dp = sp;
 		while (!isspace(*dp) && *dp != '\0')
@@ -195,7 +196,7 @@ modules_parse_line(char *line, int lineno)
 		}
 	}
 
-	if (!(mi->mi_flags & MODULE_ALIAS) && TAILQ_EMPTY(&(mi->mi_modules)))
+	if (!(mi->mi_flags & MODULE_ALIAS) && RB_EMPTY(&(mi->mi_modules)))
 		cvs_file_get(dirname, 0, &(mi->mi_modules));
 
 	TAILQ_INSERT_TAIL(&modules, mi, m_list);
@@ -229,8 +230,8 @@ cvs_module_lookup(char *name)
 		}
 	}
 
-	TAILQ_INIT(&(mc->mc_modules));
-	TAILQ_INIT(&(mc->mc_ignores));
+	RB_INIT(&(mc->mc_modules));
+	RB_INIT(&(mc->mc_ignores));
 	cvs_file_get(name, 0, &(mc->mc_modules));
 	mc->mc_canfree = 1;
 	mc->mc_name = name;