ascii.c

   1 /* $Id: ascii.c,v 1.1 2009/03/16 22:19:19 kristaps Exp $ */
   2 /*
   3  * Copyright (c) 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 <err.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #include "term.h"
  25
  26 #define ASCII_PRINT_HI   126
  27 #define ASCII_PRINT_LO   32
  28
  29 /*
  30  * Lookup and hashing routines for constructing the ASCII symbol table,
  31  * which should contain a significant portion of mdoc(7)'s special
  32  * symbols.
  33  */
  34
  35 struct  line {
  36         const char      *code;
  37         const char      *out;
  38         /* 32- and 64-bit alignment safe. */
  39         size_t           codesz;
  40         size_t           outsz;
  41 };
  42
  43 struct  linep {
  44         const struct line *line;
  45         struct linep    *next;
  46 };
  47
  48 #define LINE(w, x, y, z) \
  49         { (w), (y), (x), (z) },
  50 static  const struct line lines[] = {
  51 #include "ascii.in"
  52 };
  53
  54
  55 static  inline int       match(const struct line *,
  56                                 const char *, size_t);
  57
  58
  59 void *
  60 ascii2htab(void)
  61 {
  62         void            **htab;
  63         struct linep     *pp, *p;
  64         int               i, len, hash;
  65
  66         /*
  67          * Constructs a very basic chaining hashtable.  The hash routine
  68          * is simply the integral value of the first character.
  69          * Subsequent entries are chained in the order they're processed
  70          * (they're in-line re-ordered during lookup).
  71          */
  72
  73         assert(0 == sizeof(lines) % sizeof(struct line));
  74         len = sizeof(lines) / sizeof(struct line);
  75
  76         if (NULL == (p = calloc((size_t)len, sizeof(struct linep))))
  77                 err(1, "malloc");
  78
  79         htab = calloc(ASCII_PRINT_HI - ASCII_PRINT_LO + 1,
  80                         sizeof(struct linep **));
  81
  82         if (NULL == htab)
  83                 err(1, "malloc");
  84
  85         for (i = 0; i < len; i++) {
  86                 assert(lines[i].codesz > 0);
  87                 assert(lines[i].code);
  88                 assert(lines[i].out);
  89
  90                 p[i].line = &lines[i];
  91
  92                 hash = (int)lines[i].code[0] - ASCII_PRINT_LO;
  93
  94                 if (NULL == (pp = ((struct linep **)htab)[hash])) {
  95                         htab[hash] = &p[i];
  96                         continue;
  97                 }
  98
  99                 for ( ; pp->next; pp = pp->next)
 100                         /* Scan ahead. */ ;
 101
 102                 pp->next = &p[i];
 103         }
 104
 105         return((void *)htab);
 106 }
 107
 108
 109 const char *
 110 a2ascii(void *htabp, const char *p, size_t sz, size_t *rsz)
 111 {
 112         struct linep     *pp, *prev;
 113         void            **htab;
 114         int               hash;
 115
 116         htab = (void **)htabp;
 117
 118         assert(p);
 119         assert(sz > 0);
 120         assert(p[0] >= ASCII_PRINT_LO && p[0] <= ASCII_PRINT_HI);
 121
 122         /*
 123          * Lookup the symbol in the symbol hash.  See ascii2htab for the
 124          * hashtable specs.  This dynamically re-orders the hash chain
 125          * to optimise for repeat hits.
 126          */
 127
 128         hash = (int)p[0] - ASCII_PRINT_LO;
 129
 130         if (NULL == (pp = ((struct linep **)htab)[hash]))
 131                 return(NULL);
 132
 133         if (NULL == pp->next) {
 134                 if ( ! match(pp->line, p, sz))
 135                         return(NULL);
 136                 *rsz = pp->line->outsz;
 137                 return(pp->line->out);
 138         }
 139
 140         for (prev = NULL; pp; pp = pp->next) {
 141                 if ( ! match(pp->line, p, sz)) {
 142                         prev = pp;
 143                         continue;
 144                 }
 145
 146                 /* Re-order the hash chain. */
 147
 148                 if (prev) {
 149                         prev->next = pp->next;
 150                         pp->next = ((struct linep **)htab)[hash];
 151                         htab[hash] = pp;
 152                 }
 153
 154                 *rsz = pp->line->outsz;
 155                 return(pp->line->out);
 156         }
 157
 158         return(NULL);
 159 }
 160
 161
 162 static inline int
 163 match(const struct line *line, const char *p, size_t sz)
 164 {
 165
 166         if (line->codesz != sz)
 167                 return(0);
 168         return(0 == strncmp(line->code, p, sz));
 169 }