Annotation of mandoc/mdoc_hash.c, Revision 1.2
1.2 ! kristaps 1: /* $Id: mdoc_hash.c,v 1.1 2009/03/23 14:22:11 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
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
1.2 ! kristaps 34: mdoc_hash_free(void *htab)
1.1 kristaps 35: {
36:
37: free(htab);
38: }
39:
40:
41: void *
1.2 ! kristaps 42: mdoc_hash_alloc(void)
1.1 kristaps 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)
1.2 ! kristaps 49: return(NULL);
1.1 kristaps 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
1.2 ! kristaps 97: mdoc_hash_find(const void *arg, const char *tmp)
1.1 kristaps 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:
CVSweb