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