chars.c

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