1 /* $Id: mdoc_hash.c,v 1.2 2009/04/02 06:51:44 kristaps Exp $ */
3 * Copyright (c) 2008, 2009 Kristaps Dzonsons <kristaps@openbsd.org>
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
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.
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).
34 mdoc_hash_free(void *htab
)
44 int i
, major
, minor
, ind
;
47 htab
= calloc(27 * 26 * 3, sizeof(struct mdoc_macro
*));
51 for (i
= 1; i
< MDOC_MAX
; i
++) {
52 major
= mdoc_macronames
[i
][0];
53 assert((major
>= 65 && major
<= 90) ||
61 minor
= mdoc_macronames
[i
][1];
62 assert((minor
>= 65 && minor
<= 90) ||
64 (minor
>= 97 && minor
<= 122));
73 assert(major
>= 0 && major
< 27);
74 assert(minor
>= 0 && minor
< 26);
76 ind
= (major
* 27 * 3) + (minor
* 3);
78 if (NULL
== htab
[ind
]) {
79 htab
[ind
] = &mdoc_macros
[i
];
83 if (NULL
== htab
[++ind
]) {
84 htab
[ind
] = &mdoc_macros
[i
];
88 assert(NULL
== htab
[++ind
]);
89 htab
[ind
] = &mdoc_macros
[i
];
97 mdoc_hash_find(const void *arg
, const char *tmp
)
99 int major
, minor
, ind
, slot
;
105 if (0 == tmp
[0] || 0 == tmp
[1])
107 if (tmp
[2] && tmp
[3])
110 if ( ! (tmp
[0] == 37 || (tmp
[0] >= 65 && tmp
[0] <= 90)))
113 if ( ! ((tmp
[1] >= 65 && tmp
[1] <= 90) ||
115 (tmp
[1] >= 97 && tmp
[1] <= 122)))
125 else if (tmp
[1] <= 90)
130 ind
= (major
* 27 * 3) + (minor
* 3);
131 if (ind
< 0 || ind
>= (27 * 26 * 3))
135 slot
= htab
[ind
] - /* LINTED */
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] &&
142 mdoc_macronames
[slot
][2] == tmp
[2]))
148 slot
= htab
[ind
] - /* LINTED */
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] &&
155 mdoc_macronames
[slot
][2] == tmp
[2]))
160 if (NULL
== htab
[ind
])
162 slot
= htab
[ind
] - /* LINTED */
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] &&
169 mdoc_macronames
[slot
][2] == tmp
[2]))