ascii.c

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