1 /* $Id: chars.c,v 1.6 2010/03/26 01:22:05 schwarze 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 369 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 for (prev = NULL; pp; pp = pp->next) { 166 if ( ! match(pp, p, sz, type)) { 167 prev = pp; 168 continue; 169 } 170 171 if (prev) { 172 prev->next = pp->next; 173 pp->next = htab[hash]; 174 htab[hash] = pp; 175 } 176 177 if (CHARS_HTML == tab->type) { 178 *rsz = pp->htmlsz; 179 return(pp->html); 180 } 181 *rsz = pp->asciisz; 182 return(pp->ascii); 183 } 184 185 return(NULL); 186 } 187 188 189 static inline int 190 match(const struct ln *ln, const char *p, size_t sz, int type) 191 { 192 193 if ( ! (ln->type & type)) 194 return(0); 195 if (ln->codesz != sz) 196 return(0); 197 return(0 == strncmp(ln->code, p, sz)); 198 } 199