![[BACK]](/icons/back.gif){kind=icon}
Return to mdoc_hash.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / mandoc|
Return to mdoc_hash.c CVS log | Up to [local] / src / usr.bin / mandoc |
1.1 ! kristaps 1: /* $Id: mdoc_hash.c,v 1.2 2009/04/02 06:51:44 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 <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
! 34: mdoc_hash_free(void *htab)
! 35: {
! 36:
! 37: free(htab);
! 38: }
! 39:
! 40:
! 41: void *
! 42: mdoc_hash_alloc(void)
! 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)
! 49: return(NULL);
! 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
! 97: mdoc_hash_find(const void *arg, const char *tmp)
! 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: