Annotation of mandoc/chars.c, Revision 1.1
1.1 ! kristaps 1: /* $Id: ascii.c,v 1.9 2009/07/27 12:02:49 kristaps Exp $ */
! 2: /*
! 3: * Copyright (c) 2009 Kristaps Dzonsons <kristaps@kth.se>
! 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 above
! 7: * copyright notice and this permission notice appear in all copies.
! 8: *
! 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.
! 16: */
! 17: #include <assert.h>
! 18: #include <err.h>
! 19: #include <stdlib.h>
! 20: #include <string.h>
! 21:
! 22: #include "chars.h"
! 23:
! 24: #define ASCII_PRINT_HI 126
! 25: #define ASCII_PRINT_LO 32
! 26:
! 27: struct ln {
! 28: struct ln *next;
! 29: const char *code;
! 30: const char *out;
! 31: size_t codesz;
! 32: size_t outsz;
! 33: int type;
! 34: #define CHARS_CHAR (1 << 0)
! 35: #define CHARS_STRING (1 << 1)
! 36: #define CHARS_BOTH (0x03)
! 37: };
! 38:
! 39: #define LINES_MAX 266
! 40:
! 41: #define CHAR(w, x, y, z) \
! 42: { NULL, (w), (y), (x), (z), CHARS_CHAR },
! 43: #define STRING(w, x, y, z) \
! 44: { NULL, (w), (y), (x), (z), CHARS_STRING },
! 45: #define BOTH(w, x, y, z) \
! 46: { NULL, (w), (y), (x), (z), CHARS_BOTH },
! 47:
! 48: static struct ln lines[LINES_MAX] = {
! 49: #include "chars.in"
! 50: };
! 51:
! 52: struct tbl {
! 53: struct ln **htab;
! 54: };
! 55:
! 56: static inline int match(const struct ln *,
! 57: const char *, size_t, int);
! 58: static const char *find(struct tbl *, const char *,
! 59: size_t, size_t *, int);
! 60:
! 61:
! 62: void
! 63: chars_free(void *arg)
! 64: {
! 65: struct tbl *tab;
! 66:
! 67: tab = (struct tbl *)arg;
! 68:
! 69: free(tab->htab);
! 70: free(tab);
! 71: }
! 72:
! 73:
! 74: /* ARGSUSED */
! 75: void *
! 76: chars_init(enum chars type)
! 77: {
! 78: struct tbl *tab;
! 79: struct ln **htab;
! 80: struct ln *pp;
! 81: int i, hash;
! 82:
! 83: /*
! 84: * Constructs a very basic chaining hashtable. The hash routine
! 85: * is simply the integral value of the first character.
! 86: * Subsequent entries are chained in the order they're processed
! 87: * (they're in-line re-ordered during lookup).
! 88: */
! 89:
! 90: if (NULL == (tab = malloc(sizeof(struct tbl))))
! 91: err(1, "malloc");
! 92:
! 93: htab = calloc(ASCII_PRINT_HI - ASCII_PRINT_LO + 1,
! 94: sizeof(struct ln **));
! 95:
! 96: if (NULL == htab)
! 97: err(1, "malloc");
! 98:
! 99: for (i = 0; i < LINES_MAX; i++) {
! 100: assert(lines[i].codesz > 0);
! 101: assert(lines[i].code);
! 102: assert(lines[i].out);
! 103:
! 104: hash = (int)lines[i].code[0] - ASCII_PRINT_LO;
! 105:
! 106: if (NULL == (pp = htab[hash])) {
! 107: htab[hash] = &lines[i];
! 108: continue;
! 109: }
! 110:
! 111: for ( ; pp->next; pp = pp->next)
! 112: /* Scan ahead. */ ;
! 113:
! 114: pp->next = &lines[i];
! 115: }
! 116:
! 117: tab->htab = htab;
! 118: return(tab);
! 119: }
! 120:
! 121:
! 122: const char *
! 123: chars_a2ascii(void *arg, const char *p, size_t sz, size_t *rsz)
! 124: {
! 125:
! 126: return(find((struct tbl *)arg, p, sz, rsz, CHARS_CHAR));
! 127: }
! 128:
! 129:
! 130: const char *
! 131: chars_a2res(void *arg, const char *p, size_t sz, size_t *rsz)
! 132: {
! 133:
! 134: return(find((struct tbl *)arg, p, sz, rsz, CHARS_STRING));
! 135: }
! 136:
! 137:
! 138: static const char *
! 139: find(struct tbl *tab, const char *p, size_t sz, size_t *rsz, int type)
! 140: {
! 141: struct ln *pp, *prev;
! 142: struct ln **htab;
! 143: int hash;
! 144:
! 145: assert(p);
! 146: assert(sz > 0);
! 147:
! 148: if (p[0] < ASCII_PRINT_LO || p[0] > ASCII_PRINT_HI)
! 149: return(NULL);
! 150:
! 151: /*
! 152: * Lookup the symbol in the symbol hash. See ascii2htab for the
! 153: * hashtable specs. This dynamically re-orders the hash chain
! 154: * to optimise for repeat hits.
! 155: */
! 156:
! 157: hash = (int)p[0] - ASCII_PRINT_LO;
! 158: htab = tab->htab;
! 159:
! 160: if (NULL == (pp = htab[hash]))
! 161: return(NULL);
! 162:
! 163: if (NULL == pp->next) {
! 164: if ( ! match(pp, p, sz, type))
! 165: return(NULL);
! 166: *rsz = pp->outsz;
! 167: return(pp->out);
! 168: }
! 169:
! 170: for (prev = NULL; pp; pp = pp->next) {
! 171: if ( ! match(pp, p, sz, type)) {
! 172: prev = pp;
! 173: continue;
! 174: }
! 175:
! 176: /* Re-order the hash chain. */
! 177:
! 178: if (prev) {
! 179: prev->next = pp->next;
! 180: pp->next = htab[hash];
! 181: htab[hash] = pp;
! 182: }
! 183:
! 184: *rsz = pp->outsz;
! 185: return(pp->out);
! 186: }
! 187:
! 188: return(NULL);
! 189: }
! 190:
! 191:
! 192: static inline int
! 193: match(const struct ln *ln, const char *p, size_t sz, int type)
! 194: {
! 195:
! 196: if ( ! (ln->type & type))
! 197: return(0);
! 198: if (ln->codesz != sz)
! 199: return(0);
! 200: return(0 == strncmp(ln->code, p, sz));
! 201: }
CVSweb