Module Name: src
Committed By: joerg
Date: Thu May 31 20:10:06 UTC 2012
Modified Files:
src/usr.bin/tic: Makefile tic.c
Log Message:
Replace linear lookup with hash table, reducing runtime by 60%.
To generate a diff of this commit:
cvs rdiff -u -r1.1 -r1.2 src/usr.bin/tic/Makefile
cvs rdiff -u -r1.14 -r1.15 src/usr.bin/tic/tic.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/tic/Makefile
diff -u src/usr.bin/tic/Makefile:1.1 src/usr.bin/tic/Makefile:1.2
--- src/usr.bin/tic/Makefile:1.1 Wed Feb 3 15:16:32 2010
+++ src/usr.bin/tic/Makefile Thu May 31 20:10:06 2012
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.1 2010/02/03 15:16:32 roy Exp $
+# $NetBSD: Makefile,v 1.2 2012/05/31 20:10:06 joerg Exp $
PROG= tic
WARNS= 4
@@ -6,8 +6,8 @@ WARNS= 4
CPPFLAGS+= -I${.CURDIR}/../../lib/libterminfo
.ifndef HOSTPROG
-LDADD+= -lterminfo
-DPADD+= ${LIBTERMINFO}
+LDADD+= -lterminfo -lutil
+DPADD+= ${LIBTERMINFO} ${LIBUTIL}
.endif
.include <bsd.prog.mk>
Index: src/usr.bin/tic/tic.c
diff -u src/usr.bin/tic/tic.c:1.14 src/usr.bin/tic/tic.c:1.15
--- src/usr.bin/tic/tic.c:1.14 Thu May 31 19:56:32 2012
+++ src/usr.bin/tic/tic.c Thu May 31 20:10:06 2012
@@ -1,4 +1,4 @@
-/* $NetBSD: tic.c,v 1.14 2012/05/31 19:56:32 joerg Exp $ */
+/* $NetBSD: tic.c,v 1.15 2012/05/31 20:10:06 joerg Exp $ */
/*
* Copyright (c) 2009, 2010 The NetBSD Foundation, Inc.
@@ -32,7 +32,7 @@
#endif
#include <sys/cdefs.h>
-__RCSID("$NetBSD: tic.c,v 1.14 2012/05/31 19:56:32 joerg Exp $");
+__RCSID("$NetBSD: tic.c,v 1.15 2012/05/31 20:10:06 joerg Exp $");
#include <sys/types.h>
#include <sys/queue.h>
@@ -48,12 +48,16 @@ __RCSID("$NetBSD: tic.c,v 1.14 2012/05/3
#include <limits.h>
#include <fcntl.h>
#include <ndbm.h>
+#include <search.h>
#include <stdarg.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <term_private.h>
#include <term.h>
+#include <util.h>
+
+#define HASH_SIZE 16384 /* 2012-06-01: 3600 entries */
/* We store the full list of terminals we have instead of iterating
through the database as the sequential iterator doesn't work
@@ -124,19 +128,19 @@ save_term(DBM *db, TERM *term)
static TERM *
find_term(const char *name)
{
- TERM *term;
+ ENTRY elem, *elemp;
- SLIST_FOREACH(term, &terms, next) {
- if (strcmp(term->name, name) == 0)
- return term;
- }
- return NULL;
+ elem.key = __UNCONST(name);
+ elem.data = NULL;
+ elemp = hsearch(elem, FIND);
+ return elemp ? (TERM *)elemp->data : NULL;
}
static TERM *
store_term(const char *name, char type)
{
TERM *term;
+ ENTRY elem;
term = calloc(1, sizeof(*term));
if (term == NULL)
@@ -146,6 +150,9 @@ store_term(const char *name, char type)
if (term->name == NULL)
errx(1, "malloc");
SLIST_INSERT_HEAD(&terms, term, next);
+ elem.key = estrdup(name);
+ elem.data = term;
+ hsearch(elem, ENTER);
return term;
}
@@ -508,6 +515,8 @@ main(int argc, char **argv)
} else
db = NULL; /* satisfy gcc warning */
+ hcreate(HASH_SIZE);
+
buf = NULL;
buflen = tbuf.buflen = tbuf.bufpos = 0;
while ((len = getline(&buf, &buflen, f)) != -1) {
@@ -576,5 +585,7 @@ main(int argc, char **argv)
fprintf(stderr, "%zu entries and %zu aliases written to %s\n",
nterm, nalias, p);
+ hdestroy();
+
return EXIT_SUCCESS;
}
