chars.c revision 1.1.1.3 
1/*	$Vendor-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
27struct	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
55struct	tbl {
56	enum chars	  type;
57	struct ln	**htab;
58};
59
60static	inline int	  match(const struct ln *,
61				const char *, size_t, int);
62static	const char	 *find(struct tbl *, const char *,
63				size_t, size_t *, int);
64
65
66void
67chars_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
78void *
79chars_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
124const char *
125chars_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
132const char *
133chars_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
140static const char *
141find(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
201static inline int
202match(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}
211