mdoc_tokhash -> hash
[mandoc.git] / mdoc_hash.c
1 /* $Id: mdoc_hash.c,v 1.2 2009/04/02 06:51:44 kristaps Exp $ */
2 /*
3 * Copyright (c) 2008, 2009 Kristaps Dzonsons <kristaps@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the
7 * above copyright notice and this permission notice appear in all
8 * copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
11 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
12 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
13 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
15 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
16 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19 #include <assert.h>
20 #include <ctype.h>
21 #include <stdlib.h>
22 #include <stdio.h>
23 #include <string.h>
24
25 #include "libmdoc.h"
26
27 /*
28 * Routines for the perfect-hash hashtable used by the parser to look up
29 * tokens by their string-ified names (`.Fl' -> MDOC_Fl). The
30 * allocation penalty for this is 27 * 26 * sizeof(ptr).
31 */
32
33 void
34 mdoc_hash_free(void *htab)
35 {
36
37 free(htab);
38 }
39
40
41 void *
42 mdoc_hash_alloc(void)
43 {
44 int i, major, minor, ind;
45 const void **htab;
46
47 htab = calloc(27 * 26 * 3, sizeof(struct mdoc_macro *));
48 if (NULL == htab)
49 return(NULL);
50
51 for (i = 1; i < MDOC_MAX; i++) {
52 major = mdoc_macronames[i][0];
53 assert((major >= 65 && major <= 90) ||
54 major == 37);
55
56 if (major == 37)
57 major = 0;
58 else
59 major -= 64;
60
61 minor = mdoc_macronames[i][1];
62 assert((minor >= 65 && minor <= 90) ||
63 (minor == 49) ||
64 (minor >= 97 && minor <= 122));
65
66 if (minor == 49)
67 minor = 0;
68 else if (minor <= 90)
69 minor -= 65;
70 else
71 minor -= 97;
72
73 assert(major >= 0 && major < 27);
74 assert(minor >= 0 && minor < 26);
75
76 ind = (major * 27 * 3) + (minor * 3);
77
78 if (NULL == htab[ind]) {
79 htab[ind] = &mdoc_macros[i];
80 continue;
81 }
82
83 if (NULL == htab[++ind]) {
84 htab[ind] = &mdoc_macros[i];
85 continue;
86 }
87
88 assert(NULL == htab[++ind]);
89 htab[ind] = &mdoc_macros[i];
90 }
91
92 return((void *)htab);
93 }
94
95
96 int
97 mdoc_hash_find(const void *arg, const char *tmp)
98 {
99 int major, minor, ind, slot;
100 const void **htab;
101
102 htab = /* LINTED */
103 (const void **)arg;
104
105 if (0 == tmp[0] || 0 == tmp[1])
106 return(MDOC_MAX);
107 if (tmp[2] && tmp[3])
108 return(MDOC_MAX);
109
110 if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
111 return(MDOC_MAX);
112
113 if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
114 (tmp[1] == 49) ||
115 (tmp[1] >= 97 && tmp[1] <= 122)))
116 return(MDOC_MAX);
117
118 if (tmp[0] == 37)
119 major = 0;
120 else
121 major = tmp[0] - 64;
122
123 if (tmp[1] == 49)
124 minor = 0;
125 else if (tmp[1] <= 90)
126 minor = tmp[1] - 65;
127 else
128 minor = tmp[1] - 97;
129
130 ind = (major * 27 * 3) + (minor * 3);
131 if (ind < 0 || ind >= (27 * 26 * 3))
132 return(MDOC_MAX);
133
134 if (htab[ind]) {
135 slot = htab[ind] - /* LINTED */
136 (void *)mdoc_macros;
137 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
138 slot /= sizeof(struct mdoc_macro);
139 if (mdoc_macronames[slot][0] == tmp[0] &&
140 mdoc_macronames[slot][1] == tmp[1] &&
141 (0 == tmp[2] ||
142 mdoc_macronames[slot][2] == tmp[2]))
143 return(slot);
144 ind++;
145 }
146
147 if (htab[ind]) {
148 slot = htab[ind] - /* LINTED */
149 (void *)mdoc_macros;
150 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
151 slot /= sizeof(struct mdoc_macro);
152 if (mdoc_macronames[slot][0] == tmp[0] &&
153 mdoc_macronames[slot][1] == tmp[1] &&
154 (0 == tmp[2] ||
155 mdoc_macronames[slot][2] == tmp[2]))
156 return(slot);
157 ind++;
158 }
159
160 if (NULL == htab[ind])
161 return(MDOC_MAX);
162 slot = htab[ind] - /* LINTED */
163 (void *)mdoc_macros;
164 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
165 slot /= sizeof(struct mdoc_macro);
166 if (mdoc_macronames[slot][0] == tmp[0] &&
167 mdoc_macronames[slot][1] == tmp[1] &&
168 (0 == tmp[2] ||
169 mdoc_macronames[slot][2] == tmp[2]))
170 return(slot);
171
172 return(MDOC_MAX);
173 }
174