ascii.c

   1 /* $Id: ascii.c,v 1.4 2009/03/20 21:58:38 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 struct  asciitab {
  55         struct linep     *lines;
  56         void            **htab;
  57 };
  58
  59
  60 static  inline int        match(const struct line *,
  61                                 const char *, size_t);
  62
  63
  64 void
  65 term_asciifree(void *arg)
  66 {
  67         struct asciitab *tab;
  68
  69         tab = (struct asciitab *)arg;
  70
  71         free(tab->lines);
  72         free(tab->htab);
  73         free(tab);
  74 }
  75
  76
  77 void *
  78 term_ascii2htab(void)
  79 {
  80         struct asciitab  *tab;
  81         void            **htab;
  82         struct linep     *pp, *p;
  83         int               i, len, hash;
  84
  85         /*
  86          * Constructs a very basic chaining hashtable.  The hash routine
  87          * is simply the integral value of the first character.
  88          * Subsequent entries are chained in the order they're processed
  89          * (they're in-line re-ordered during lookup).
  90          */
  91
  92         if (NULL == (tab = malloc(sizeof(struct asciitab))))
  93                 err(1, "malloc");
  94
  95         len = sizeof(lines) / sizeof(struct line);
  96
  97         if (NULL == (p = calloc((size_t)len, sizeof(struct linep))))
  98                 err(1, "malloc");
  99
 100         htab = calloc(ASCII_PRINT_HI - ASCII_PRINT_LO + 1,
 101                         sizeof(struct linep **));
 102
 103         if (NULL == htab)
 104                 err(1, "malloc");
 105
 106         for (i = 0; i < len; i++) {
 107                 assert(lines[i].codesz > 0);
 108                 assert(lines[i].code);
 109                 assert(lines[i].out);
 110
 111                 p[i].line = &lines[i];
 112
 113                 hash = (int)lines[i].code[0] - ASCII_PRINT_LO;
 114
 115                 if (NULL == (pp = ((struct linep **)htab)[hash])) {
 116                         htab[hash] = &p[i];
 117                         continue;
 118                 }
 119
 120                 for ( ; pp->next; pp = pp->next)
 121                         /* Scan ahead. */ ;
 122
 123                 pp->next = &p[i];
 124         }
 125
 126         tab->htab = htab;
 127         tab->lines = p;
 128
 129         return(tab);
 130 }
 131
 132
 133 const char *
 134 term_a2ascii(void *arg, const char *p, size_t sz, size_t *rsz)
 135 {
 136         struct asciitab  *tab;
 137         struct linep     *pp, *prev;
 138         void            **htab;
 139         int               hash;
 140
 141         tab = (struct asciitab *)arg;
 142         htab = tab->htab;
 143
 144         assert(p);
 145         assert(sz > 0);
 146         assert(p[0] >= ASCII_PRINT_LO && p[0] <= ASCII_PRINT_HI);
 147
 148         /*
 149          * Lookup the symbol in the symbol hash.  See ascii2htab for the
 150          * hashtable specs.  This dynamically re-orders the hash chain
 151          * to optimise for repeat hits.
 152          */
 153
 154         hash = (int)p[0] - ASCII_PRINT_LO;
 155
 156         if (NULL == (pp = ((struct linep **)htab)[hash]))
 157                 return(NULL);
 158
 159         if (NULL == pp->next) {
 160                 if ( ! match(pp->line, p, sz))
 161                         return(NULL);
 162                 *rsz = pp->line->outsz;
 163                 return(pp->line->out);
 164         }
 165
 166         for (prev = NULL; pp; pp = pp->next) {
 167                 if ( ! match(pp->line, p, sz)) {
 168                         prev = pp;
 169                         continue;
 170                 }
 171
 172                 /* Re-order the hash chain. */
 173
 174                 if (prev) {
 175                         prev->next = pp->next;
 176                         pp->next = ((struct linep **)htab)[hash];
 177                         htab[hash] = pp;
 178                 }
 179
 180                 *rsz = pp->line->outsz;
 181                 return(pp->line->out);
 182         }
 183
 184         return(NULL);
 185 }
 186
 187
 188 static inline int
 189 match(const struct line *line, const char *p, size_t sz)
 190 {
 191
 192         if (line->codesz != sz)
 193                 return(0);
 194         return(0 == strncmp(line->code, p, sz));
 195 }