1*95c635efSGarrett D'Amore /* $Id: man_hash.c,v 1.25 2011/07/24 18:15:14 kristaps Exp $ */ 2*95c635efSGarrett D'Amore /* 3*95c635efSGarrett D'Amore * Copyright (c) 2008, 2009, 2010 Kristaps Dzonsons <kristaps@bsd.lv> 4*95c635efSGarrett D'Amore * 5*95c635efSGarrett D'Amore * Permission to use, copy, modify, and distribute this software for any 6*95c635efSGarrett D'Amore * purpose with or without fee is hereby granted, provided that the above 7*95c635efSGarrett D'Amore * copyright notice and this permission notice appear in all copies. 8*95c635efSGarrett D'Amore * 9*95c635efSGarrett D'Amore * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10*95c635efSGarrett D'Amore * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11*95c635efSGarrett D'Amore * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12*95c635efSGarrett D'Amore * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13*95c635efSGarrett D'Amore * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14*95c635efSGarrett D'Amore * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15*95c635efSGarrett D'Amore * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16*95c635efSGarrett D'Amore */ 17*95c635efSGarrett D'Amore #ifdef HAVE_CONFIG_H 18*95c635efSGarrett D'Amore #include "config.h" 19*95c635efSGarrett D'Amore #endif 20*95c635efSGarrett D'Amore 21*95c635efSGarrett D'Amore #include <sys/types.h> 22*95c635efSGarrett D'Amore 23*95c635efSGarrett D'Amore #include <assert.h> 24*95c635efSGarrett D'Amore #include <ctype.h> 25*95c635efSGarrett D'Amore #include <limits.h> 26*95c635efSGarrett D'Amore #include <stdlib.h> 27*95c635efSGarrett D'Amore #include <string.h> 28*95c635efSGarrett D'Amore 29*95c635efSGarrett D'Amore #include "man.h" 30*95c635efSGarrett D'Amore #include "mandoc.h" 31*95c635efSGarrett D'Amore #include "libman.h" 32*95c635efSGarrett D'Amore 33*95c635efSGarrett D'Amore #define HASH_DEPTH 6 34*95c635efSGarrett D'Amore 35*95c635efSGarrett D'Amore #define HASH_ROW(x) do { \ 36*95c635efSGarrett D'Amore if (isupper((unsigned char)(x))) \ 37*95c635efSGarrett D'Amore (x) -= 65; \ 38*95c635efSGarrett D'Amore else \ 39*95c635efSGarrett D'Amore (x) -= 97; \ 40*95c635efSGarrett D'Amore (x) *= HASH_DEPTH; \ 41*95c635efSGarrett D'Amore } while (/* CONSTCOND */ 0) 42*95c635efSGarrett D'Amore 43*95c635efSGarrett D'Amore /* 44*95c635efSGarrett D'Amore * Lookup table is indexed first by lower-case first letter (plus one 45*95c635efSGarrett D'Amore * for the period, which is stored in the last row), then by lower or 46*95c635efSGarrett D'Amore * uppercase second letter. Buckets correspond to the index of the 47*95c635efSGarrett D'Amore * macro (the integer value of the enum stored as a char to save a bit 48*95c635efSGarrett D'Amore * of space). 49*95c635efSGarrett D'Amore */ 50*95c635efSGarrett D'Amore static unsigned char table[26 * HASH_DEPTH]; 51*95c635efSGarrett D'Amore 52*95c635efSGarrett D'Amore /* 53*95c635efSGarrett D'Amore * XXX - this hash has global scope, so if intended for use as a library 54*95c635efSGarrett D'Amore * with multiple callers, it will need re-invocation protection. 55*95c635efSGarrett D'Amore */ 56*95c635efSGarrett D'Amore void 57*95c635efSGarrett D'Amore man_hash_init(void) 58*95c635efSGarrett D'Amore { 59*95c635efSGarrett D'Amore int i, j, x; 60*95c635efSGarrett D'Amore 61*95c635efSGarrett D'Amore memset(table, UCHAR_MAX, sizeof(table)); 62*95c635efSGarrett D'Amore 63*95c635efSGarrett D'Amore assert(/* LINTED */ 64*95c635efSGarrett D'Amore MAN_MAX < UCHAR_MAX); 65*95c635efSGarrett D'Amore 66*95c635efSGarrett D'Amore for (i = 0; i < (int)MAN_MAX; i++) { 67*95c635efSGarrett D'Amore x = man_macronames[i][0]; 68*95c635efSGarrett D'Amore 69*95c635efSGarrett D'Amore assert(isalpha((unsigned char)x)); 70*95c635efSGarrett D'Amore 71*95c635efSGarrett D'Amore HASH_ROW(x); 72*95c635efSGarrett D'Amore 73*95c635efSGarrett D'Amore for (j = 0; j < HASH_DEPTH; j++) 74*95c635efSGarrett D'Amore if (UCHAR_MAX == table[x + j]) { 75*95c635efSGarrett D'Amore table[x + j] = (unsigned char)i; 76*95c635efSGarrett D'Amore break; 77*95c635efSGarrett D'Amore } 78*95c635efSGarrett D'Amore 79*95c635efSGarrett D'Amore assert(j < HASH_DEPTH); 80*95c635efSGarrett D'Amore } 81*95c635efSGarrett D'Amore } 82*95c635efSGarrett D'Amore 83*95c635efSGarrett D'Amore 84*95c635efSGarrett D'Amore enum mant 85*95c635efSGarrett D'Amore man_hash_find(const char *tmp) 86*95c635efSGarrett D'Amore { 87*95c635efSGarrett D'Amore int x, y, i; 88*95c635efSGarrett D'Amore enum mant tok; 89*95c635efSGarrett D'Amore 90*95c635efSGarrett D'Amore if ('\0' == (x = tmp[0])) 91*95c635efSGarrett D'Amore return(MAN_MAX); 92*95c635efSGarrett D'Amore if ( ! (isalpha((unsigned char)x))) 93*95c635efSGarrett D'Amore return(MAN_MAX); 94*95c635efSGarrett D'Amore 95*95c635efSGarrett D'Amore HASH_ROW(x); 96*95c635efSGarrett D'Amore 97*95c635efSGarrett D'Amore for (i = 0; i < HASH_DEPTH; i++) { 98*95c635efSGarrett D'Amore if (UCHAR_MAX == (y = table[x + i])) 99*95c635efSGarrett D'Amore return(MAN_MAX); 100*95c635efSGarrett D'Amore 101*95c635efSGarrett D'Amore tok = (enum mant)y; 102*95c635efSGarrett D'Amore if (0 == strcmp(tmp, man_macronames[tok])) 103*95c635efSGarrett D'Amore return(tok); 104*95c635efSGarrett D'Amore } 105*95c635efSGarrett D'Amore 106*95c635efSGarrett D'Amore return(MAN_MAX); 107*95c635efSGarrett D'Amore } 108