[src/trunk]: src/usr.bin/tpfmt try to speed up symbol lookup

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

details:   https://anonhg.NetBSD.org/src/rev/a0ee407a30bb
branches:  trunk
changeset: 771609:a0ee407a30bb
user:      yamt <yamt%NetBSD.org@localhost>
date:      Sat Nov 26 05:04:09 2011 +0000

description:
try to speed up symbol lookup

diffstat:

 usr.bin/tpfmt/sym.c |  25 ++++++++++++++++++++++---
 1 files changed, 22 insertions(+), 3 deletions(-)

diffs (48 lines):

diff -r d6536e5e0824 -r a0ee407a30bb usr.bin/tpfmt/sym.c
--- a/usr.bin/tpfmt/sym.c       Sat Nov 26 05:02:44 2011 +0000
+++ b/usr.bin/tpfmt/sym.c       Sat Nov 26 05:04:09 2011 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: sym.c,v 1.2 2010/11/24 13:17:56 christos Exp $ */
+/*     $NetBSD: sym.c,v 1.3 2011/11/26 05:04:09 yamt Exp $     */
 
 /*-
  * Copyright (c) 2010 YAMAMOTO Takashi,
@@ -28,7 +28,7 @@
 
 #include <sys/cdefs.h>
 #ifndef lint
-__RCSID("$NetBSD: sym.c,v 1.2 2010/11/24 13:17:56 christos Exp $");
+__RCSID("$NetBSD: sym.c,v 1.3 2011/11/26 05:04:09 yamt Exp $");
 #endif /* not lint */
 
 #include <assert.h>
@@ -135,9 +135,28 @@
 const char *
 ksymlookup(uint64_t value, uint64_t *offset)
 {
+       size_t hi;
+       size_t lo;
        size_t i;
 
-       for (i = 0; i < nsyms; i++) {
+       /*
+        * find the smallest i for which syms[i]->value <= value.
+        * syms[] is ordered with value in the descending order.
+        */
+
+       hi = nsyms - 1;
+       lo = 0;
+       while (lo < hi) {
+               const size_t mid = (lo + hi) / 2;
+               const struct sym *sym = syms[mid];
+
+               if (sym->value <= value) {
+                       hi = mid;
+                       continue;
+               }
+               lo = mid + 1;
+       }
+       for (i = lo; i < nsyms; i++) {
                const struct sym *sym = syms[i];
 
                if (sym->value <= value) {