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