[src/trunk]: src/usr.bin/tic Replace linear lookup with hash table, reducing ...

[joerg <joerg%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/6629ed62a029
branches:  trunk
changeset: 779506:6629ed62a029
user:      joerg <joerg%NetBSD.org@localhost>
date:      Thu May 31 20:10:06 2012 +0000

description:
Replace linear lookup with hash table, reducing runtime by 60%.

diffstat:

 usr.bin/tic/Makefile |   6 +++---
 usr.bin/tic/tic.c    |  27 +++++++++++++++++++--------
 2 files changed, 22 insertions(+), 11 deletions(-)

diffs (108 lines):

diff -r 10f2f39ee424 -r 6629ed62a029 usr.bin/tic/Makefile
--- a/usr.bin/tic/Makefile      Thu May 31 19:56:32 2012 +0000
+++ b/usr.bin/tic/Makefile      Thu May 31 20:10:06 2012 +0000
@@ -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 @@
 CPPFLAGS+=     -I${.CURDIR}/../../lib/libterminfo
 
 .ifndef HOSTPROG
-LDADD+=                -lterminfo
-DPADD+=                ${LIBTERMINFO}
+LDADD+=                -lterminfo -lutil
+DPADD+=                ${LIBTERMINFO} ${LIBUTIL}
 .endif
 
 .include <bsd.prog.mk>
diff -r 10f2f39ee424 -r 6629ed62a029 usr.bin/tic/tic.c
--- a/usr.bin/tic/tic.c Thu May 31 19:56:32 2012 +0000
+++ b/usr.bin/tic/tic.c Thu May 31 20:10:06 2012 +0000
@@ -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 @@
 #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 @@
 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 @@
        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 @@
        } 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 @@
                fprintf(stderr, "%zu entries and %zu aliases written to %s\n",
                    nterm, nalias, p);
 
+       hdestroy();
+
        return EXIT_SUCCESS;
 }