1241675Suqs/* $Id: man_hash.c,v 1.25 2011/07/24 18:15:14 kristaps Exp $ */ 2241675Suqs/* 3241675Suqs * Copyright (c) 2008, 2009, 2010 Kristaps Dzonsons <kristaps@bsd.lv> 4241675Suqs * 5241675Suqs * Permission to use, copy, modify, and distribute this software for any 6241675Suqs * purpose with or without fee is hereby granted, provided that the above 7241675Suqs * copyright notice and this permission notice appear in all copies. 8241675Suqs * 9241675Suqs * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10241675Suqs * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11241675Suqs * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12241675Suqs * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13241675Suqs * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14241675Suqs * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15241675Suqs * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16241675Suqs */ 17241675Suqs#ifdef HAVE_CONFIG_H 18241675Suqs#include "config.h" 19241675Suqs#endif 20241675Suqs 21241675Suqs#include <sys/types.h> 22241675Suqs 23241675Suqs#include <assert.h> 24241675Suqs#include <ctype.h> 25241675Suqs#include <limits.h> 26241675Suqs#include <stdlib.h> 27241675Suqs#include <string.h> 28241675Suqs 29241675Suqs#include "man.h" 30241675Suqs#include "mandoc.h" 31241675Suqs#include "libman.h" 32241675Suqs 33241675Suqs#define HASH_DEPTH 6 34241675Suqs 35241675Suqs#define HASH_ROW(x) do { \ 36241675Suqs if (isupper((unsigned char)(x))) \ 37241675Suqs (x) -= 65; \ 38241675Suqs else \ 39241675Suqs (x) -= 97; \ 40241675Suqs (x) *= HASH_DEPTH; \ 41241675Suqs } while (/* CONSTCOND */ 0) 42241675Suqs 43241675Suqs/* 44241675Suqs * Lookup table is indexed first by lower-case first letter (plus one 45241675Suqs * for the period, which is stored in the last row), then by lower or 46241675Suqs * uppercase second letter. Buckets correspond to the index of the 47241675Suqs * macro (the integer value of the enum stored as a char to save a bit 48241675Suqs * of space). 49241675Suqs */ 50241675Suqsstatic unsigned char table[26 * HASH_DEPTH]; 51241675Suqs 52241675Suqs/* 53241675Suqs * XXX - this hash has global scope, so if intended for use as a library 54241675Suqs * with multiple callers, it will need re-invocation protection. 55241675Suqs */ 56241675Suqsvoid 57241675Suqsman_hash_init(void) 58241675Suqs{ 59241675Suqs int i, j, x; 60241675Suqs 61241675Suqs memset(table, UCHAR_MAX, sizeof(table)); 62241675Suqs 63241675Suqs assert(/* LINTED */ 64241675Suqs MAN_MAX < UCHAR_MAX); 65241675Suqs 66241675Suqs for (i = 0; i < (int)MAN_MAX; i++) { 67241675Suqs x = man_macronames[i][0]; 68241675Suqs 69241675Suqs assert(isalpha((unsigned char)x)); 70241675Suqs 71241675Suqs HASH_ROW(x); 72241675Suqs 73241675Suqs for (j = 0; j < HASH_DEPTH; j++) 74241675Suqs if (UCHAR_MAX == table[x + j]) { 75241675Suqs table[x + j] = (unsigned char)i; 76241675Suqs break; 77241675Suqs } 78241675Suqs 79241675Suqs assert(j < HASH_DEPTH); 80241675Suqs } 81241675Suqs} 82241675Suqs 83241675Suqs 84241675Suqsenum mant 85241675Suqsman_hash_find(const char *tmp) 86241675Suqs{ 87241675Suqs int x, y, i; 88241675Suqs enum mant tok; 89241675Suqs 90241675Suqs if ('\0' == (x = tmp[0])) 91241675Suqs return(MAN_MAX); 92241675Suqs if ( ! (isalpha((unsigned char)x))) 93241675Suqs return(MAN_MAX); 94241675Suqs 95241675Suqs HASH_ROW(x); 96241675Suqs 97241675Suqs for (i = 0; i < HASH_DEPTH; i++) { 98241675Suqs if (UCHAR_MAX == (y = table[x + i])) 99241675Suqs return(MAN_MAX); 100241675Suqs 101241675Suqs tok = (enum mant)y; 102241675Suqs if (0 == strcmp(tmp, man_macronames[tok])) 103241675Suqs return(tok); 104241675Suqs } 105241675Suqs 106241675Suqs return(MAN_MAX); 107241675Suqs} 108