Mercurial > ~dholland > hg > tradcpp > index.cgi

comparison macro.c @ 17:76da41da923f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added macro table
author David A. Holland
date Mon, 20 Dec 2010 01:15:43 -0500
parents
children c08a947d8f30
comparison
equal deleted inserted replaced
16:9dda765ee85c 17:76da41da923f
1 #include <stdlib.h>
2 #include <string.h>
3
4 #include "array.h"
5 #include "mode.h"
6 #include "place.h"
7 #include "macro.h"
8
9 struct macro {
10 struct place defplace;
11 struct place expansionplace;
12 unsigned hash;
13 char *name;
14 char *expansion;
15 };
16 DECLARRAY(macro);
17 DEFARRAY(macro, );
18 DECLARRAY(macroarray);
19 DEFARRAY(macroarray, );
20
21 static struct macroarrayarray macros;
22 static unsigned total_macros;
23 static unsigned hashmask;
24
25 ////////////////////////////////////////////////////////////
26 // macro structure ops
27
28 static
29 struct macro *
30 macro_create(struct place *p1, struct place *p2, unsigned hash,
31 const char *name, const char *expansion)
32 {
33 struct macro *m;
34
35 m = domalloc(sizeof(*m));
36 m->defplace = *p1;
37 m->expansionplace = *p2;
38 m->hash = hash;
39 m->name = dostrdup(name);
40 m->expansion = dostrdup(expansion);
41 return m;
42 }
43
44 static
45 void
46 macro_destroy(struct macro *m)
47 {
48 free(m->name);
49 free(m->expansion);
50 free(m);
51 }
52
53 ////////////////////////////////////////////////////////////
54 // macro table
55
56 /*
57 * Unless I've screwed up, this is something called Fletcher's Checksum
58 * that showed up in Dr. Dobbs in, according to my notes, May 1992. The
59 * implementation is new.
60 */
61 static
62 unsigned
63 hashfunc(const char *s)
64 {
65 uint16_t x1, x2, a;
66 size_t i, len;
67
68 len = strlen(s);
69
70 x1 = (uint16_t) (len >> 16);
71 x2 = (uint16_t) (len);
72 if (x1==0) {
73 x1++;
74 }
75 if (x2==0) {
76 x2++;
77 }
78
79 for (i=0; i<len; i+=2) {
80 if (i==len-1) {
81 a = (unsigned char)s[i];
82 /* don't run off the end of the array */
83 }
84 else {
85 a = (unsigned char)s[i] +
86 ((uint16_t)(unsigned char)s[i+1] << 8);
87 }
88 x1 += a;
89 if (x1 < a) {
90 x1++;
91 }
92 x2 += x1;
93 if (x2 < x1) {
94 x2++;
95 }
96 }
97
98 x1 ^= 0xffff;
99 x2 ^= 0xffff;
100 return ((uint32_t)x2)*65535U + x1;
101 }
102
103 static
104 void
105 macrotable_init(void)
106 {
107 unsigned i;
108
109 macroarrayarray_init(&macros);
110 macroarrayarray_setsize(&macros, 4);
111 for (i=0; i<4; i++) {
112 macroarrayarray_set(&macros, i, NULL);
113 }
114 total_macros = 0;
115 hashmask = 0x3;
116 }
117
118 DESTROYALL_ARRAY(macro, );
119
120 static
121 void
122 macrotable_cleanup(void)
123 {
124 struct macroarray *bucket;
125 unsigned numbuckets, i;
126
127 numbuckets = macroarrayarray_num(&macros);
128 for (i=0; i<numbuckets; i++) {
129 bucket = macroarrayarray_get(&macros, i);
130 macroarray_destroyall(bucket);
131 macroarray_destroy(bucket);
132 }
133 macroarrayarray_setsize(&macros, 0);
134 macroarrayarray_cleanup(&macros);
135 }
136
137 static
138 struct macro *
139 macrotable_find(const char *name, bool remove)
140 {
141 unsigned hash;
142 struct macroarray *bucket;
143 struct macro *m, *m2;
144 unsigned i, num;
145
146 hash = hashfunc(name);
147 bucket = macroarrayarray_get(&macros, hash & hashmask);
148 if (bucket == NULL) {
149 return NULL;
150 }
151 num = macroarray_num(bucket);
152 for (i=0; i<num; i++) {
153 m = macroarray_get(bucket, i);
154 if (hash != m->hash) {
155 continue;
156 }
157 if (!strcmp(name, m->name)) {
158 if (remove) {
159 if (i < num-1) {
160 m2 = macroarray_get(bucket, num-1);
161 macroarray_set(bucket, i, m2);
162 }
163 macroarray_setsize(bucket, num-1);
164 total_macros--;
165 }
166 return m;
167 }
168 }
169 return NULL;
170 }
171
172 static
173 void
174 macrotable_rehash(void)
175 {
176 struct macroarray *newbucket, *oldbucket;
177 struct macro *m;
178 unsigned newmask, tossbit;
179 unsigned numbuckets, i;
180 unsigned oldnum, j, k;
181
182 numbuckets = macroarrayarray_num(&macros);
183 macroarrayarray_setsize(&macros, numbuckets*2);
184
185 assert(hashmask == numbuckets - 1);
186 newmask = (hashmask << 1) | 1U;
187 tossbit = newmask && ~hashmask;
188 hashmask = newmask;
189
190 for (i=0; i<numbuckets; i++) {
191 newbucket = NULL;
192 oldbucket = macroarrayarray_get(&macros, i);
193 oldnum = macroarray_num(oldbucket);
194 for (j=0; j<oldnum; j++) {
195 m = macroarray_get(oldbucket, j);
196 if (m->hash & tossbit) {
197 if (newbucket == NULL) {
198 newbucket = macroarray_create();
199 }
200 macroarray_set(oldbucket, j, NULL);
201 macroarray_add(newbucket, m, NULL);
202 }
203 }
204 for (j=k=0; j<oldnum; j++) {
205 m = macroarray_get(oldbucket, j);
206 if (m != NULL && k < j) {
207 macroarray_set(oldbucket, k++, m);
208 }
209 }
210 macroarray_setsize(oldbucket, k);
211 macroarrayarray_set(&macros, numbuckets + i, newbucket);
212 }
213 }
214
215 static
216 void
217 macrotable_add(struct macro *m)
218 {
219 unsigned hash;
220 struct macroarray *bucket;
221 unsigned numbuckets;
222
223 numbuckets = macroarrayarray_num(&macros);
224 if (total_macros > 0 && total_macros / numbuckets > 9) {
225 macrotable_rehash();
226 }
227
228 hash = hashfunc(m->name);
229 bucket = macroarrayarray_get(&macros, hash & hashmask);
230 if (bucket == NULL) {
231 bucket = macroarray_create();
232 macroarrayarray_set(&macros, hash & hashmask, bucket);
233 }
234 macroarray_add(bucket, m, NULL);
235 total_macros++;
236 }
237
238 ////////////////////////////////////////////////////////////
239 // external macro definition interface
240
241 void
242 macro_define(struct place *p1, const char *macro,
243 struct place *p2, const char *expansion)
244 {
245 struct macro *m;
246
247 m = macrotable_find(macro, false);
248 if (m != NULL) {
249 if (!strcmp(expansion, m->expansion)) {
250 complain(p1, "Warning: redefinition of %s", macro);
251 if (mode.werror) {
252 complain_fail();
253 }
254 return;
255 }
256 complain(p1, "Redefinition of %s is not identical", macro);
257 complain_fail();
258 return;
259 }
260
261 m = macro_create(p1, p2, hashfunc(macro), macro, expansion);
262 macrotable_add(m);
263 }
264
265 void
266 macro_undef(const char *macro)
267 {
268 struct macro *m;
269
270 m = macrotable_find(macro, true);
271 if (m) {
272 macro_destroy(m);
273 }
274 }
275
276 bool
277 macro_isdefined(const char *macro)
278 {
279 struct macro *m;
280
281 m = macrotable_find(macro, false);
282 return m != NULL;
283 }
284
285 ////////////////////////////////////////////////////////////
286 // macro expansion
287
288 char *macroexpand(struct place *, char *buf, size_t len, bool honordefined);
289
290 void macro_sendline(struct place *, char *buf, size_t len);
291 void macro_sendeof(struct place *);
292
293 ////////////////////////////////////////////////////////////
294 // module initialization
295
296 void
297 macros_init(void)
298 {
299 macrotable_init();
300 }
301
302 void
303 macros_cleanup(void)
304 {
305 macrotable_cleanup();
306 }