Annotation of mandoc/hash.c, Revision 1.11
1.11 ! kristaps 1: /* $Id: hash.c,v 1.10 2009/03/11 00:39:58 kristaps Exp $ */
1.1 kristaps 2: /*
1.11 ! kristaps 3: * Copyright (c) 2008, 2009 Kristaps Dzonsons <kristaps@openbsd.org>
1.1 kristaps 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:
1.5 kristaps 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
1.6 kristaps 31: * allocation penalty for this is 27 * 26 * sizeof(ptr).
1.5 kristaps 32: */
33:
1.1 kristaps 34: void
1.3 kristaps 35: mdoc_tokhash_free(void *htab)
1.1 kristaps 36: {
37:
38: free(htab);
39: }
40:
41:
42: void *
1.3 kristaps 43: mdoc_tokhash_alloc(void)
1.1 kristaps 44: {
1.2 kristaps 45: int i, major, minor, ind;
1.1 kristaps 46: const void **htab;
47:
1.10 kristaps 48: htab = calloc(27 * 26 * 3, sizeof(struct mdoc_macro *));
1.1 kristaps 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:
1.10 kristaps 77: ind = (major * 27 * 3) + (minor * 3);
1.1 kristaps 78:
1.10 kristaps 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]);
1.2 kristaps 90: htab[ind] = &mdoc_macros[i];
1.1 kristaps 91: }
92:
93: return((void *)htab);
94: }
95:
96:
97: int
1.3 kristaps 98: mdoc_tokhash_find(const void *arg, const char *tmp)
1.1 kristaps 99: {
1.2 kristaps 100: int major, minor, ind, slot;
1.1 kristaps 101: const void **htab;
102:
1.2 kristaps 103: htab = /* LINTED */
104: (const void **)arg;
1.1 kristaps 105:
106: if (0 == tmp[0] || 0 == tmp[1])
107: return(MDOC_MAX);
1.8 kristaps 108: if (tmp[2] && tmp[3])
109: return(MDOC_MAX);
1.1 kristaps 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:
1.10 kristaps 131: ind = (major * 27 * 3) + (minor * 3);
132: if (ind < 0 || ind >= (27 * 26 * 3))
1.4 kristaps 133: return(MDOC_MAX);
1.1 kristaps 134:
1.10 kristaps 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])
1.1 kristaps 162: return(MDOC_MAX);
1.2 kristaps 163: slot = htab[ind] - /* LINTED */
164: (void *)mdoc_macros;
165: assert(0 == (size_t)slot % sizeof(struct mdoc_macro));
1.1 kristaps 166: slot /= sizeof(struct mdoc_macro);
1.10 kristaps 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);
1.1 kristaps 172:
1.10 kristaps 173: return(MDOC_MAX);
1.1 kristaps 174: }
175:
CVSweb