]> git.cameronkatri.com Git - mandoc.git/blob - hash.c
Expanded perfect htab to use 27 * 26 * 3 space.
[mandoc.git] / hash.c
1 /* $Id: hash.c,v 1.10 2009/03/11 00:39:58 kristaps Exp $ */
2 /*
3 * Copyright (c) 2008 Kristaps Dzonsons <kristaps@kth.se>
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 <err.h>
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include <string.h>
25
26 #include "private.h"
27
28 /*
29 * Routines for the perfect-hash hashtable used by the parser to look up
30 * tokens by their string-ified names (`.Fl' -> MDOC_Fl). The
31 * allocation penalty for this is 27 * 26 * sizeof(ptr).
32 */
33
34 void
35 mdoc_tokhash_free(void *htab)
36 {
37
38 free(htab);
39 }
40
41
42 void *
43 mdoc_tokhash_alloc(void)
44 {
45 int i, major, minor, ind;
46 const void **htab;
47
48 htab = calloc(27 * 26 * 3, sizeof(struct mdoc_macro *));
49 if (NULL == htab)
50 err(1, "calloc");
51
52 for (i = 1; i < MDOC_MAX; i++) {
53 major = mdoc_macronames[i][0];
54 assert((major >= 65 && major <= 90) ||
55 major == 37);
56
57 if (major == 37)
58 major = 0;
59 else
60 major -= 64;
61
62 minor = mdoc_macronames[i][1];
63 assert((minor >= 65 && minor <= 90) ||
64 (minor == 49) ||
65 (minor >= 97 && minor <= 122));
66
67 if (minor == 49)
68 minor = 0;
69 else if (minor <= 90)
70 minor -= 65;
71 else
72 minor -= 97;
73
74 assert(major >= 0 && major < 27);
75 assert(minor >= 0 && minor < 26);
76
77 ind = (major * 27 * 3) + (minor * 3);
78
79 if (NULL == htab[ind]) {
80 htab[ind] = &mdoc_macros[i];
81 continue;
82 }
83
84 if (NULL == htab[++ind]) {
85 htab[ind] = &mdoc_macros[i];
86 continue;
87 }
88
89 assert(NULL == htab[++ind]);
90 htab[ind] = &mdoc_macros[i];
91 }
92
93 return((void *)htab);
94 }
95
96
97 int
98 mdoc_tokhash_find(const void *arg, const char *tmp)
99 {
100 int major, minor, ind, slot;
101 const void **htab;
102
103 htab = /* LINTED */
104 (const void **)arg;
105
106 if (0 == tmp[0] || 0 == tmp[1])
107 return(MDOC_MAX);
108 if (tmp[2] && tmp[3])
109 return(MDOC_MAX);
110
111 if ( ! (tmp[0] == 37 || (tmp[0] >= 65 && tmp[0] <= 90)))
112 return(MDOC_MAX);
113
114 if ( ! ((tmp[1] >= 65 && tmp[1] <= 90) ||
115 (tmp[1] == 49) ||
116 (tmp[1] >= 97 && tmp[1] <= 122)))
117 return(MDOC_MAX);
118
119 if (tmp[0] == 37)
120 major = 0;
121 else
122 major = tmp[0] - 64;
123
124 if (tmp[1] == 49)
125 minor = 0;
126 else if (tmp[1] <= 90)
127 minor = tmp[1] - 65;
128 else
129 minor = tmp[1] - 97;
130
131 ind = (major * 27 * 3) + (minor * 3);
132 if (ind < 0 || ind >= (27 * 26 * 3))
133 return(MDOC_MAX);
134
135 if (htab[ind]) {
136 slot = htab[ind] - /* LINTED */
137 (void *)mdoc_macros;
138 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
139 slot /= sizeof(struct mdoc_macro);
140 if (mdoc_macronames[slot][0] == tmp[0] &&
141 mdoc_macronames[slot][1] == tmp[1] &&
142 (0 == tmp[2] ||
143 mdoc_macronames[slot][2] == tmp[2]))
144 return(slot);
145 ind++;
146 }
147
148 if (htab[ind]) {
149 slot = htab[ind] - /* LINTED */
150 (void *)mdoc_macros;
151 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
152 slot /= sizeof(struct mdoc_macro);
153 if (mdoc_macronames[slot][0] == tmp[0] &&
154 mdoc_macronames[slot][1] == tmp[1] &&
155 (0 == tmp[2] ||
156 mdoc_macronames[slot][2] == tmp[2]))
157 return(slot);
158 ind++;
159 }
160
161 if (NULL == htab[ind])
162 return(MDOC_MAX);
163 slot = htab[ind] - /* LINTED */
164 (void *)mdoc_macros;
165 assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
166 slot /= sizeof(struct mdoc_macro);
167 if (mdoc_macronames[slot][0] == tmp[0] &&
168 mdoc_macronames[slot][1] == tmp[1] &&
169 (0 == tmp[2] ||
170 mdoc_macronames[slot][2] == tmp[2]))
171 return(slot);
172
173 return(MDOC_MAX);
174 }
175