chars.c

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