From 2a1b4b314d3ac327c46f7aba65e67bf92b4b7e60 Mon Sep 17 00:00:00 2001 From: Ingo Schwarze Date: Mon, 21 Sep 2009 21:11:38 +0000 Subject: sync to 1.9.5: lookup hashes are now static tables shortening the code, and, according to kristaps@, speeding it up --- usr.bin/mandoc/libman.h | 8 +-- usr.bin/mandoc/libmdoc.h | 8 +-- usr.bin/mandoc/man.c | 14 ++-- usr.bin/mandoc/man_hash.c | 46 ++++--------- usr.bin/mandoc/mdoc.c | 13 ++-- usr.bin/mandoc/mdoc_action.c | 6 +- usr.bin/mandoc/mdoc_hash.c | 152 +++++++++++-------------------------------- usr.bin/mandoc/mdoc_macro.c | 31 ++++----- 8 files changed, 84 insertions(+), 194 deletions(-) (limited to 'usr.bin') diff --git a/usr.bin/mandoc/libman.h b/usr.bin/mandoc/libman.h index 70c1e8e4edf..f0a5de14a4b 100644 --- a/usr.bin/mandoc/libman.h +++ b/usr.bin/mandoc/libman.h @@ -1,4 +1,4 @@ -/* $Id: libman.h,v 1.8 2009/08/22 23:17:39 schwarze Exp $ */ +/* $Id: libman.h,v 1.9 2009/09/21 21:11:36 schwarze Exp $ */ /* * Copyright (c) 2009 Kristaps Dzonsons * @@ -27,7 +27,6 @@ enum man_next { struct man { void *data; struct man_cb cb; - void *htab; int pflags; int flags; #define MAN_HALT (1 << 0) @@ -95,9 +94,8 @@ int man_body_alloc(struct man *, int, int, int); int man_elem_alloc(struct man *, int, int, int); void man_node_free(struct man_node *); void man_node_freelist(struct man_node *); -void *man_hash_alloc(void); -int man_hash_find(const void *, const char *); -void man_hash_free(void *); +void man_hash_init(void); +int man_hash_find(const char *); int man_macroend(struct man *); int man_args(struct man *, int, int *, char *, char **); #define ARGS_ERROR (-1) diff --git a/usr.bin/mandoc/libmdoc.h b/usr.bin/mandoc/libmdoc.h index e8c4ac6abea..f51f9d709a1 100644 --- a/usr.bin/mandoc/libmdoc.h +++ b/usr.bin/mandoc/libmdoc.h @@ -1,4 +1,4 @@ -/* $Id: libmdoc.h,v 1.20 2009/08/22 22:39:55 schwarze Exp $ */ +/* $Id: libmdoc.h,v 1.21 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -27,7 +27,6 @@ enum mdoc_next { struct mdoc { void *data; struct mdoc_cb cb; - void *htab; int flags; #define MDOC_HALT (1 << 0) /* Error in parse. Halt. */ #define MDOC_LITERAL (1 << 1) /* In a literal scope. */ @@ -139,9 +138,8 @@ int mdoc_tail_alloc(struct mdoc *, int, int, int); int mdoc_body_alloc(struct mdoc *, int, int, int); void mdoc_node_free(struct mdoc_node *); void mdoc_node_freelist(struct mdoc_node *); -void *mdoc_hash_alloc(void); -int mdoc_hash_find(const void *, const char *); -void mdoc_hash_free(void *); +void mdoc_hash_init(void); +int mdoc_hash_find(const char *); int mdoc_iscdelim(char); int mdoc_isdelim(const char *); size_t mdoc_isescape(const char *); diff --git a/usr.bin/mandoc/man.c b/usr.bin/mandoc/man.c index c3888bb684c..d749a73eff3 100644 --- a/usr.bin/mandoc/man.c +++ b/usr.bin/mandoc/man.c @@ -1,4 +1,4 @@ -/* $Id: man.c,v 1.12 2009/09/18 22:46:14 schwarze Exp $ */ +/* $Id: man.c,v 1.13 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -101,9 +101,6 @@ man_free(struct man *man) { man_free1(man); - - if (man->htab) - man_hash_free(man->htab); free(man); } @@ -121,14 +118,11 @@ man_alloc(void *data, int pflags, const struct man_cb *cb) return(NULL); } + man_hash_init(); + p->data = data; p->pflags = pflags; (void)memcpy(&p->cb, cb, sizeof(struct man_cb)); - - if (NULL == (p->htab = man_hash_alloc())) { - free(p); - return(NULL); - } return(p); } @@ -509,7 +503,7 @@ man_pmacro(struct man *m, int ln, char *buf) return(1); } - if (MAN_MAX == (c = man_hash_find(m->htab, mac))) { + if (MAN_MAX == (c = man_hash_find(mac))) { if ( ! (MAN_IGN_MACRO & m->pflags)) { (void)man_perr(m, ln, ppos, WMACRO); goto err; diff --git a/usr.bin/mandoc/man_hash.c b/usr.bin/mandoc/man_hash.c index 2b83f0f56b3..b7d376fa2bf 100644 --- a/usr.bin/mandoc/man_hash.c +++ b/usr.bin/mandoc/man_hash.c @@ -1,4 +1,4 @@ -/* $Id: man_hash.c,v 1.5 2009/08/22 23:17:40 schwarze Exp $ */ +/* $Id: man_hash.c,v 1.6 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -15,39 +15,27 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include +#include #include #include #include "libman.h" +static u_char table[26 * 6]; -/* ARGUSED */ +/* + * XXX - this hash has global scope, so if intended for use as a library + * with multiple callers, it will need re-invocation protection. + */ void -man_hash_free(void *htab) -{ - - free(htab); -} - - -/* ARGUSED */ -void * -man_hash_alloc(void) +man_hash_init(void) { - int *htab; int i, j, x; - /* Initialised to -1. */ - - htab = malloc(26 * 6 * sizeof(int)); - if (NULL == htab) - return(NULL); - for (i = 0; i < 26 * 6; i++) - htab[i] = -1; + memset(table, UCHAR_MAX, sizeof(table)); for (i = 0; i < MAN_MAX; i++) { x = man_macronames[i][0]; - assert((x >= 65 && x <= 90) || (x >= 97 && x <= 122)); @@ -55,25 +43,18 @@ man_hash_alloc(void) x *= 6; for (j = 0; j < 6; j++) - if (-1 == htab[x + j]) { - htab[x + j] = i; + if (UCHAR_MAX == table[x + j]) { + table[x + j] = (u_char)i; break; } - assert(j < 6); } - - return((void *)htab); } - int -man_hash_find(const void *arg, const char *tmp) +man_hash_find(const char *tmp) { int x, i, tok; - const int *htab; - - htab = (const int *)arg; if (0 == (x = tmp[0])) return(MAN_MAX); @@ -84,7 +65,7 @@ man_hash_find(const void *arg, const char *tmp) x *= 6; for (i = 0; i < 6; i++) { - if (-1 == (tok = htab[x + i])) + if (UCHAR_MAX == (tok = table[x + i])) return(MAN_MAX); if (0 == strcmp(tmp, man_macronames[tok])) return(tok); @@ -92,4 +73,3 @@ man_hash_find(const void *arg, const char *tmp) return(MAN_MAX); } - diff --git a/usr.bin/mandoc/mdoc.c b/usr.bin/mandoc/mdoc.c index da3983aca93..f29b4b0e836 100644 --- a/usr.bin/mandoc/mdoc.c +++ b/usr.bin/mandoc/mdoc.c @@ -1,4 +1,4 @@ -/* $Id: mdoc.c,v 1.26 2009/09/18 22:37:05 schwarze Exp $ */ +/* $Id: mdoc.c,v 1.27 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -226,8 +226,6 @@ mdoc_free(struct mdoc *mdoc) { mdoc_free1(mdoc); - if (mdoc->htab) - mdoc_hash_free(mdoc->htab); free(mdoc); } @@ -245,13 +243,12 @@ mdoc_alloc(void *data, int pflags, const struct mdoc_cb *cb) if (cb) (void)memcpy(&p->cb, cb, sizeof(struct mdoc_cb)); + mdoc_hash_init(); + p->data = data; p->pflags = pflags; - if (NULL == (p->htab = mdoc_hash_alloc())) { - free(p); - return(NULL); - } else if (mdoc_alloc1(p)) + if (mdoc_alloc1(p)) return(p); free(p); @@ -721,7 +718,7 @@ parsemacro(struct mdoc *m, int ln, char *buf) return(1); } - if (MDOC_MAX == (c = mdoc_hash_find(m->htab, mac))) { + if (MDOC_MAX == (c = mdoc_hash_find(mac))) { if ( ! macrowarn(m, ln, mac)) goto err; return(1); diff --git a/usr.bin/mandoc/mdoc_action.c b/usr.bin/mandoc/mdoc_action.c index 258b8bb059c..b19180a3936 100644 --- a/usr.bin/mandoc/mdoc_action.c +++ b/usr.bin/mandoc/mdoc_action.c @@ -1,4 +1,4 @@ -/* $Id: mdoc_action.c,v 1.20 2009/08/22 22:50:17 schwarze Exp $ */ +/* $Id: mdoc_action.c,v 1.21 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -53,7 +53,7 @@ static int post_tilde(POST_ARGS); static int pre_bd(PRE_ARGS); static int pre_dl(PRE_ARGS); -const struct actions mdoc_actions[MDOC_MAX] = { +static const struct actions mdoc_actions[MDOC_MAX] = { { NULL, NULL }, /* Ap */ { NULL, post_dd }, /* Dd */ { NULL, post_dt }, /* Dt */ @@ -613,7 +613,7 @@ post_bl_width(POST_ARGS) if (0 == strcmp(p, "Ds")) width = 6; - else if (MDOC_MAX == (tok = mdoc_hash_find(m->htab, p))) + else if (MDOC_MAX == (tok = mdoc_hash_find(p))) return(1); else if (0 == (width = mdoc_macro2len(tok))) return(mdoc_nwarn(m, n, ENOWIDTH)); diff --git a/usr.bin/mandoc/mdoc_hash.c b/usr.bin/mandoc/mdoc_hash.c index b188e340bf7..4af63bea72c 100644 --- a/usr.bin/mandoc/mdoc_hash.c +++ b/usr.bin/mandoc/mdoc_hash.c @@ -1,4 +1,4 @@ -/* $Id: mdoc_hash.c,v 1.5 2009/08/09 18:01:15 schwarze Exp $ */ +/* $Id: mdoc_hash.c,v 1.6 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -18,149 +18,71 @@ #include #include +#include #include #include #include #include "libmdoc.h" -#define ADJUST_MAJOR(x) \ - do if (37 == (x)) \ - (x) = 0; /* % -> 00 */ \ - else if (91 > (x)) \ - (x) -= 64; /* A-Z -> 01 - 26 */ \ - else \ - (x) -= 70; /* a-z -> 27 - 52 */ \ - while (/*CONSTCOND*/0) - -#define ADJUST_MINOR(y) \ - do if (49 == (y)) \ - (y) = 0; /* 1 -> 00 */ \ - else if (91 > (y)) \ - (y) -= 65; /* A-Z -> 00 - 25 */ \ - else \ - (y) -= 97; /* a-z -> 00 - 25 */ \ - while (/*CONSTCOND*/0) - -#define INDEX(maj, min) \ - ((maj) * 26 * 3) + ((min) * 3) - -#define SLOTCMP(slot, val) \ - (mdoc_macronames[(slot)][0] == (val)[0] && \ - mdoc_macronames[(slot)][1] == (val)[1] && \ - (0 == (val)[2] || \ - mdoc_macronames[(slot)][2] == (val)[2])) - +static u_char table[27 * 12]; +/* + * XXX - this hash has global scope, so if intended for use as a library + * with multiple callers, it will need re-invocation protection. + */ void -mdoc_hash_free(void *htab) +mdoc_hash_init(void) { + int i, j, major; + const char *p; - free(htab); -} - - - -void * -mdoc_hash_alloc(void) -{ - int i, major, minor, ind; - const void **htab; - - htab = calloc(26 * 3 * 52, sizeof(struct mdoc_macro *)); - if (NULL == htab) - return(NULL); + memset(table, UCHAR_MAX, sizeof(table)); for (i = 0; i < MDOC_MAX; i++) { - major = mdoc_macronames[i][0]; - assert(isalpha((u_char)major) || 37 == major); - - ADJUST_MAJOR(major); - - minor = mdoc_macronames[i][1]; - assert(isalpha((u_char)minor) || 49 == minor); - - ADJUST_MINOR(minor); + p = mdoc_macronames[i]; - ind = INDEX(major, minor); + if (isalpha((u_char)p[1])) + major = 12 * (tolower((u_char)p[1]) - 97); + else + major = 12 * 26; - if (NULL == htab[ind]) { - htab[ind] = &mdoc_macros[i]; - continue; - } + for (j = 0; j < 12; j++) + if (UCHAR_MAX == table[major + j]) { + table[major + j] = (u_char)i; + break; + } - if (NULL == htab[++ind]) { - htab[ind] = &mdoc_macros[i]; - continue; - } - - assert(NULL == htab[++ind]); - htab[ind] = &mdoc_macros[i]; + assert(j < 12); } - - return((void *)htab); } - int -mdoc_hash_find(const void *arg, const char *tmp) +mdoc_hash_find(const char *p) { - int major, minor, ind, slot; - const void **htab; - - htab = /* LINTED */ - (const void **)arg; + int major, i, j; - if (0 == (major = tmp[0])) + if (0 == p[0]) return(MDOC_MAX); - if (0 == (minor = tmp[1])) + if ( ! isalpha((u_char)p[0]) && '%' != p[0]) return(MDOC_MAX); - if (tmp[2] && tmp[3]) - return(MDOC_MAX); - - if (37 != major && ! isalpha((u_char)major)) - return(MDOC_MAX); - if (49 != minor && ! isalpha((u_char)minor)) + if (isalpha((u_char)p[1])) + major = 12 * (tolower((u_char)p[1]) - 97); + else if ('1' == p[1]) + major = 12 * 26; + else return(MDOC_MAX); - ADJUST_MAJOR(major); - ADJUST_MINOR(minor); - - ind = INDEX(major, minor); - - if (ind < 0 || ind >= 26 * 3 * 52) + if (p[2] && p[3]) return(MDOC_MAX); - if (htab[ind]) { - slot = htab[ind] - /* LINTED */ - (void *)mdoc_macros; - assert(0 == (size_t)slot % sizeof(struct mdoc_macro)); - slot /= sizeof(struct mdoc_macro); - if (SLOTCMP(slot, tmp)) - return(slot); - ind++; - } - - if (htab[ind]) { - slot = htab[ind] - /* LINTED */ - (void *)mdoc_macros; - assert(0 == (size_t)slot % sizeof(struct mdoc_macro)); - slot /= sizeof(struct mdoc_macro); - if (SLOTCMP(slot, tmp)) - return(slot); - ind++; + for (j = 0; j < 12; j++) { + if (UCHAR_MAX == (i = table[major + j])) + break; + if (0 == strcmp(p, mdoc_macronames[i])) + return(i); } - if (NULL == htab[ind]) - return(MDOC_MAX); - slot = htab[ind] - /* LINTED */ - (void *)mdoc_macros; - assert(0 == (size_t)slot % sizeof(struct mdoc_macro)); - slot /= sizeof(struct mdoc_macro); - if (SLOTCMP(slot, tmp)) - return(slot); - return(MDOC_MAX); } - diff --git a/usr.bin/mandoc/mdoc_macro.c b/usr.bin/mandoc/mdoc_macro.c index a3989b9dbde..c0781dca46e 100644 --- a/usr.bin/mandoc/mdoc_macro.c +++ b/usr.bin/mandoc/mdoc_macro.c @@ -1,4 +1,4 @@ -/* $Id: mdoc_macro.c,v 1.23 2009/08/22 22:39:55 schwarze Exp $ */ +/* $Id: mdoc_macro.c,v 1.24 2009/09/21 21:11:37 schwarze Exp $ */ /* * Copyright (c) 2008, 2009 Kristaps Dzonsons * @@ -46,8 +46,8 @@ static int rew_sub(enum mdoc_type, struct mdoc *, static int rew_last(struct mdoc *, const struct mdoc_node *); static int append_delims(struct mdoc *, int, int *, char *); -static int lookup(struct mdoc *, int, const char *); -static int lookup_raw(struct mdoc *, const char *); +static int lookup(int, const char *); +static int lookup_raw(const char *); static int swarn(struct mdoc *, enum mdoc_type, int, int, const struct mdoc_node *); @@ -258,12 +258,13 @@ mdoc_macroend(struct mdoc *m) * Look up a macro from within a subsequent context. */ static int -lookup(struct mdoc *mdoc, int from, const char *p) +lookup(int from, const char *p) { + /* FIXME: make -diag lists be un-PARSED. */ if ( ! (MDOC_PARSED & mdoc_macros[from].flags)) return(MDOC_MAX); - return(lookup_raw(mdoc, p)); + return(lookup_raw(p)); } @@ -271,11 +272,11 @@ lookup(struct mdoc *mdoc, int from, const char *p) * Lookup a macro following the initial line macro. */ static int -lookup_raw(struct mdoc *mdoc, const char *p) +lookup_raw(const char *p) { int res; - if (MDOC_MAX == (res = mdoc_hash_find(mdoc->htab, p))) + if (MDOC_MAX == (res = mdoc_hash_find(p))) return(MDOC_MAX); if (MDOC_CALLABLE & mdoc_macros[res].flags) return(res); @@ -669,7 +670,7 @@ blk_exp_close(MACRO_PROT_ARGS) if (ARGS_EOLN == c) break; - if (MDOC_MAX != (c = lookup(m, tok, p))) { + if (MDOC_MAX != (c = lookup(tok, p))) { if ( ! flushed) { if ( ! rew_sub(MDOC_BLOCK, m, tok, line, ppos)) return(0); @@ -753,7 +754,7 @@ in_line(MACRO_PROT_ARGS) /* Quoted words shouldn't be looked-up. */ - c = ARGS_QWORD == w ? MDOC_MAX : lookup(m, tok, p); + c = ARGS_QWORD == w ? MDOC_MAX : lookup(tok, p); /* * In this case, we've located a submacro and must @@ -932,7 +933,7 @@ blk_full(MACRO_PROT_ARGS) continue; } - if (MDOC_MAX == (c = lookup(m, tok, p))) { + if (MDOC_MAX == (c = lookup(tok, p))) { if ( ! mdoc_word_alloc(m, line, lastarg, p)) return(0); continue; @@ -995,7 +996,7 @@ blk_part_imp(MACRO_PROT_ARGS) if (ARGS_EOLN == c) break; - if (MDOC_MAX == (c = lookup(m, tok, p))) { + if (MDOC_MAX == (c = lookup(tok, p))) { if ( ! mdoc_word_alloc(m, line, la, p)) return(0); continue; @@ -1098,7 +1099,7 @@ blk_part_exp(MACRO_PROT_ARGS) if (ARGS_EOLN == c) break; - if (MDOC_MAX != (c = lookup(m, tok, p))) { + if (MDOC_MAX != (c = lookup(tok, p))) { if ( ! flushed) { if ( ! rew_sub(MDOC_HEAD, m, tok, line, ppos)) return(0); @@ -1209,7 +1210,7 @@ in_line_argn(MACRO_PROT_ARGS) if (ARGS_EOLN == c) break; - if (MDOC_MAX != (c = lookup(m, tok, p))) { + if (MDOC_MAX != (c = lookup(tok, p))) { if ( ! flushed && ! rew_elem(m, tok)) return(0); flushed = 1; @@ -1284,7 +1285,7 @@ in_line_eoln(MACRO_PROT_ARGS) if (ARGS_EOLN == w) break; - c = ARGS_QWORD == w ? MDOC_MAX : lookup(m, tok, p); + c = ARGS_QWORD == w ? MDOC_MAX : lookup(tok, p); if (MDOC_MAX != c) { if ( ! rew_elem(m, tok)) @@ -1333,7 +1334,7 @@ phrase(struct mdoc *m, int line, int ppos, char *buf) if (ARGS_EOLN == w) break; - c = ARGS_QWORD == w ? MDOC_MAX : lookup_raw(m, p); + c = ARGS_QWORD == w ? MDOC_MAX : lookup_raw(p); if (MDOC_MAX != c) { if ( ! mdoc_macro(m, c, line, la, &pos, buf)) -- cgit v1.2.3