![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mdoc_hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [cvsweb.bsd.lv] / mandoc|
Return to mdoc_hash.c CVS log | Up to [cvsweb.bsd.lv] / mandoc |
1.1 ! kristaps 1: /* $Id: hash.c,v 1.11 2009/03/16 23:37:28 kristaps Exp $ */
! 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 <err.h>
! 22: #include <stdlib.h>
! 23: #include <stdio.h>
! 24: #include <string.h>
! 25:
! 26: #include "libmdoc.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: