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

comparison anagram/agcore/tsd.cpp @ 0:13d2b8934445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:13d2b8934445
1 /*
2 * AnaGram, A System for Syntax Directed Programming
3 * Copyright 1993-2002 Parsifal Software. All Rights Reserved.
4 * See the file COPYING for license and usage terms.
5 *
6 * tsd.cpp - tuple set dictionary
7 */
8
9 #include <stdarg.h>
10 #include <string.h>
11 #include "port.h"
12
13 #include "assert.h"
14 #include "myalloc.h"
15 #include "tsd.h"
16
17 //#define INCLUDE_LOGGING
18 #include "log.h"
19
20
21 /*
22 invalid_tsd() checks the internal consistency of a tuple set and
23 returns true if the tuple set is invalid
24 */
25
26 int invalid_tsd(tsd *t) {
27 if (!ptr_ok(t)) return 1;
28 if (t->nt > t->na) return 1;
29 if (t->sb == NULL) return 0;
30 return !ptr_ok(t->sb);
31 }
32
33 void purge_tsd(tsd *r, tsd *k) {
34 LOGSECTION("purge_tsd");
35 int *rp = r->sb;
36 int *wp = rp;
37 int wn = 0;
38 int rn = r->nt;
39 int rw = r->tw;
40 int *kp = k->sb;
41 int kn = k->nt;
42 int kw = k->tw;
43
44 LOGV(r->nt) LCV(k->nt);
45 check_tsd(r);
46 check_tsd(k);
47 assert (kw == rw);
48 while (rn--) {
49 int *sp = kp;
50 int sn = kn;
51
52 #ifdef INCLUDE_LOGGING
53 LOGS("Contains ");
54 for (int k = 0; k < kw; k++) LOGX() LS(rp[k]);
55 #endif
56
57 while (sn--) {
58 int k = rw;
59 while (k--) {
60 if (rp[k] != sp[k]) break;
61 }
62 if (k < 0) break;
63 sp += kw;
64 }
65 if (sn < 0) {
66 if (wp != rp) {
67 int k = rw;
68 while (k--) {
69 wp[k] = rp[k];
70 }
71 }
72 wp += rw;
73 wn++;
74 }
75 #ifdef INCLUDE_LOGGING
76 else {
77 LOGS("Eliminating");
78 for (int k = 0; k < kw; k++) (*Log::theLog) LS(rp[k]);
79 }
80 #endif
81 rp += rw;
82 }
83 r->nt = wn;
84 }
85
86 void p1_tsd(tsd *r, int rc, tsd *k, int kc) {
87 int *rp = r->sb;
88 int *wp = rp;
89 int wn = 0;
90 int rn = r->nt;
91 int rw = r->tw;
92 int *kp = k->sb;
93 int kn = k->nt;
94 int kw = k->tw;
95
96 check_tsd(k);
97 while (rn--) {
98 int *sp = kp;
99 int sn = kn;
100 int tv = rp[rc];
101
102 while (sn--) {
103 if (tv == sp[kc]) break;
104 sp += kw;
105 }
106 if (sn < 0) {
107 if (wp != rp) {
108 int k = rw;
109 while (k--) {
110 wp[k] = rp[k];
111 }
112 }
113 wp += rw;
114 wn++;
115 }
116 rp += rw;
117 }
118 r->nt = wn;
119 }
120
121 /*
122 copy_tuple_set makes a copy of a tuple set, including a copy
123 of the contents
124 */
125
126 tsd *copy_tuple_set(tsd *t) {
127 tsd *c;
128 unsigned n;
129
130 check_tsd(t);
131 c = ZALLOCATE(1,tsd);
132 n = t->na * t->tw;
133 c->sb = ALLOCATE(n, int);
134 if (n) {
135 memmove(c->sb,t->sb, n*sizeof(*t->sb));
136 }
137 c->nt = t->nt;
138 c->tw = t->tw;
139 c->na = t->na;
140 return c;
141 }
142
143 tsd *delete_tsd(tsd *ts) {
144 if (ts == NULL) {
145 return NULL;
146 }
147 assert(ts->nt <= ts->na);
148 if (ts->sb != NULL) {
149 DEALLOCATE(ts->sb);
150 }
151 DEALLOCATE(ts);
152 return NULL;
153 }
154
155 void reset_tsd(tsd *ts) {
156 unsigned na,tw;
157 unsigned k;
158
159 check_tsd(ts);
160 assert(ts->nt <= ts->na);
161 if (ts->nt == 0) {
162 if (ts->sb == NULL) {
163 return;
164 }
165 }
166 tw = ts->tw;
167 na = ts->na;
168 ts->nt = 0;
169 ok_ptr(ts->sb);
170 k = tw*na*sizeof(*ts->sb);
171 size_ok(ts->sb, k, __FILE__, __LINE__);
172 memset(ts->sb, 0, k);
173 }
174
175 tsd *spec_tsd(unsigned size, unsigned n) {
176 tsd *ts;
177
178 ts = ZALLOCATE(1, tsd);
179 ok_ptr(ts);
180 ts->tw = n;
181 if (size == 0) {
182 return ts;
183 }
184 ts->na = size;
185 ts->sb = ZALLOCATE(size*ts->tw, int);
186 return ts;
187 }
188
189 tsd *resize_tsd(tsd *ts, unsigned size) {
190 LOGSECTION("resize_tsd");
191 unsigned lim;
192
193 ok_ptr(ts);
194 if (size == ts->na) {
195 return ts;
196 }
197
198 lim = (unsigned) MAX_BYTES/(ts->tw * sizeof(*ts->sb));
199 if (size > lim) {
200 size = lim;
201 }
202 LOGV(ts->nt) LCV(size);
203
204 assert(ts->nt <= size);
205 ts->sb = reallocate(ts->sb,ts->tw*size, int);
206 ts->na = size;
207 return ts;
208 }
209
210 tsd *init_tsd(unsigned n) {
211 tsd *ts;
212
213 ts = spec_tsd(32,n);
214 return ts;
215 }
216
217 int sit(tsd *t,...) {
218 va_list ap;
219 int *sp,*p;
220 unsigned i,j;
221 unsigned long size;
222 unsigned long lim;
223 unsigned nt,tw,nb;
224 int flag;
225
226 check_stack;
227 check_tsd(t);
228 if (t->nt >= t->na) {
229 if (t->na == 0) {
230 size = 32;
231 }
232 else if (t->na > ((MAX_BYTES/2)/3)) {
233 size = MAX_BYTES;
234 }
235 else {
236 size = 1 + t->na + t->na/2;
237 }
238
239 lim = MAX_BYTES/(t->tw * sizeof(*t->sb));
240 if (size > lim) size = lim;
241 LOGSECTION("sit::resize");
242 LOGV(t->nt) LCV(size);
243 assert(t->nt < size);
244
245 t->sb = reallocate(t->sb,t->tw*(unsigned)size, int);
246 t->na = (unsigned) size;
247 }
248
249 va_start(ap,t);
250 sp = t->sb + t->tw * t->nt;
251 for (i = 0; i < t->tw; i++) {
252 sp[i] = va_arg(ap, int);
253 }
254 va_end(ap);
255 p = t->sb;
256 tw = t->tw;
257 nb = sizeof(*t->sb)*tw;
258 nt = t->nt;
259 for (i = 0; i < nt; i++, p += tw) {
260 for (j = 0; j < tw; j++) {
261 if ((flag = sp[j] - p[j]) < 0) {
262 goto b;
263 }
264 if (flag > 0) {
265 goto c;
266 }
267 }
268 return 1;
269 c:
270 continue;
271 b:
272 break;
273 }
274 memmove(p+tw,p,nb*(nt - i));
275 va_start(ap, t);
276 for (i = 0; i < t->tw; i++) {
277 p[i] = va_arg(ap, int);
278 }
279 t->nt++;
280 va_end(ap);
281 return 0;
282 }
283
284 void at(tsd *t,...) {
285 va_list ap;
286 int *sp;
287 int i;
288 unsigned long size;
289 unsigned long lim;
290
291 check_stack;
292 check_tsd(t);
293 if (t->nt >= t->na) {
294 if (t->na == 0) {
295 size = 32;
296 }
297 else if (t->na > ((MAX_BYTES/2)/3)) {
298 size = MAX_BYTES;
299 }
300 else {
301 size = 1 + t->na + t->na/2;
302 }
303
304 lim = MAX_BYTES/(t->tw * sizeof(*t->sb));
305 if (size > lim) {
306 size = lim;
307 }
308 LOGSECTION("at::resize");
309 LOGV(t->nt) LCV(size);
310 assert(t->nt < size);
311
312 t->sb = reallocate(t->sb, t->tw*(int)size, int);
313 t->na = (unsigned) size;
314 }
315
316 va_start(ap,t);
317 sp = t->sb + t->tw * t->nt;
318 for (i = t->tw; i--; ) {
319 *sp++ = va_arg(ap, int);
320 }
321 t->nt++;
322 va_end(ap);
323 }
324
325 void xtx(tsd *t, unsigned x, ...) {
326 va_list ap;
327 int *sp;
328 unsigned i;
329
330 check_stack;
331 check_tsd(t);
332 assert(x < t->nt);
333 va_start(ap, x);
334 sp = t->sb + t->tw*x;
335 for (i = 0; i<t->tw; i++) {
336 *(va_arg(ap, int*)) = sp[i];
337 }
338 va_end(ap);
339 }
340
341 void xtxf(tsd *t, unsigned x, ...) {
342 va_list ap;
343 int *sp;
344 unsigned i;
345
346 va_start(ap, x);
347 sp = t->sb+t->tw*x;
348 for (i = t->tw; i--; ) {
349 *(va_arg(ap, int*)) = *sp++;
350 }
351 va_end(ap);
352 }
353