1 char rcsid_table[] = "$Id$";
7 static void growIndex_Map ARGS((Index_Map *));
8 static Relevant newRelevant ARGS((void));
9 static Dimension newDimension ARGS((Operator, int));
10 static void GT_1 ARGS((Table));
11 static void GT_2_0 ARGS((Table));
12 static void GT_2_1 ARGS((Table));
13 static void growTransition ARGS((Table, int));
14 static Item_Set restrict ARGS((Dimension, Item_Set));
15 static void addHP_1 ARGS((Table, Item_Set));
16 static void addHP_2_0 ARGS((Table, Item_Set));
17 static void addHP_2_1 ARGS((Table, Item_Set));
18 static void addHyperPlane ARGS((Table, int, Item_Set));
21 growIndex_Map(r) Index_Map *r;
25 new.max_size = r->max_size + STATES_INCR;
26 new.class = (Item_Set*) zalloc(new.max_size * sizeof(Item_Set));
28 memcpy(new.class, r->class, r->max_size * sizeof(Item_Set));
36 Relevant r = (Relevant) zalloc(max_nonterminal * sizeof(*r));
41 addRelevant(r, nt) Relevant r; NonTerminalNum nt;
45 for (i = 0; r[i]; i++) {
56 newDimension(op, index) Operator op; ArityNum index;
63 assert(index >= 0 && index < op->arity);
64 d = (Dimension) zalloc(sizeof(struct dimension));
67 r = d->relevant = newRelevant();
68 for (pl = rules; pl; pl = pl->next) {
69 Rule pr = (Rule) pl->x;
70 if (pr->pat->op == op) {
71 addRelevant(r, pr->pat->children[index]->num);
75 d->index_map.max_size = STATES_INCR;
76 d->index_map.class = (Item_Set*)
77 zalloc(d->index_map.max_size * sizeof(Item_Set));
78 d->map = newMapping(DIM_MAP_SIZE);
79 d->max_size = TABLE_INCR;
85 newTable(op) Operator op;
92 t = (Table) zalloc(sizeof(struct table));
97 for (i = 0; i < op->arity; i++) {
98 t->dimen[i] = newDimension(op, i);
102 for (i = 0; i < op->arity; i++) {
103 size *= t->dimen[i]->max_size;
105 t->transition = (Item_Set*) zalloc(size * sizeof(Item_Set));
106 t->relevant = newRelevant();
107 assert(t->transition);
116 ItemSetNum oldsize = t->dimen[0]->max_size;
117 ItemSetNum newsize = t->dimen[0]->max_size + TABLE_INCR;
119 t->dimen[0]->max_size = newsize;
121 ts = (Item_Set*) zalloc(newsize * sizeof(Item_Set));
123 memcpy(ts, t->transition, oldsize * sizeof(Item_Set));
124 zfree(t->transition);
132 ItemSetNum oldsize = t->dimen[0]->max_size;
133 ItemSetNum newsize = t->dimen[0]->max_size + TABLE_INCR;
136 t->dimen[0]->max_size = newsize;
138 size = newsize * t->dimen[1]->max_size;
140 ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
142 memcpy(ts, t->transition, oldsize*t->dimen[1]->max_size * sizeof(Item_Set));
143 zfree(t->transition);
151 ItemSetNum oldsize = t->dimen[1]->max_size;
152 ItemSetNum newsize = t->dimen[1]->max_size + TABLE_INCR;
158 t->dimen[1]->max_size = newsize;
160 size = newsize * t->dimen[0]->max_size;
162 ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
165 from = t->transition;
167 for (i1 = 0; i1 < t->dimen[0]->max_size; i1++) {
168 for (i2 = 0; i2 < oldsize; i2++) {
174 zfree(t->transition);
179 growTransition(t, dim) Table t; ArityNum dim;
184 assert(dim < t->op->arity);
186 switch (t->op->arity) {
209 restrict(d, ts) Dimension d; Item_Set ts;
214 register Relevant r_ptr = d->relevant;
215 register Item *ts_current = ts->closed;
216 register Item *r_current;
222 r = newItem_Set(d->relevant);
223 r_current = r->virgin;
224 for (i = 0; (nt = r_ptr[i]) != 0; i++) {
225 if (ts_current[nt].rule) {
226 r_current[nt].rule = &stub_rule;
229 ASSIGNCOST(base, ts_current[nt].delta);
231 if (LESSCOST(ts_current[nt].delta, base)) {
232 ASSIGNCOST(base, ts_current[nt].delta);
239 for (i = 0; (nt = r_ptr[i]) != 0; i++) {
240 if (r_current[nt].rule) {
241 ASSIGNCOST(r_current[nt].delta, ts_current[nt].delta);
242 MINUSCOST(r_current[nt].delta, base);
246 r->representative = ts;
251 addHP_1(t, ts) Table t; Item_Set ts;
258 e = newItem_Set(t->relevant);
260 e->kids[0] = ts->representative;
261 for (pl = t->rules; pl; pl = pl->next) {
262 Rule p = (Rule) pl->x;
263 if (t->op == p->pat->op && ts->virgin[p->pat->children[0]->num].rule) {
265 ASSIGNCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
266 ADDCOST(dc, p->delta);
267 if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
268 e->virgin[p->lhs->num].rule = p;
269 ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
276 tmp = encode(globalMap, e, &new);
277 assert(ts->num < t->dimen[0]->map->max_size);
278 t->transition[ts->num] = tmp;
288 addHP_2_0(t, ts) Table t; Item_Set ts;
296 assert(t->dimen[1]->map->count <= t->dimen[1]->map->max_size);
297 for (i2 = 0; i2 < t->dimen[1]->map->count; i2++) {
298 e = newItem_Set(t->relevant);
300 e->kids[0] = ts->representative;
301 e->kids[1] = t->dimen[1]->map->set[i2]->representative;
302 for (pl = t->rules; pl; pl = pl->next) {
303 register Rule p = (Rule) pl->x;
305 if (t->op == p->pat->op
306 && ts->virgin[p->pat->children[0]->num].rule
307 && t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].rule){
309 ASSIGNCOST(dc, p->delta);
310 ADDCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
311 ADDCOST(dc, t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].delta);
313 if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
314 e->virgin[p->lhs->num].rule = p;
315 ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
322 tmp = encode(globalMap, e, &new);
323 assert(ts->num < t->dimen[0]->map->max_size);
324 t->transition[ts->num * t->dimen[1]->max_size + i2] = tmp;
335 addHP_2_1(t, ts) Table t; Item_Set ts;
343 assert(t->dimen[0]->map->count <= t->dimen[0]->map->max_size);
344 for (i1 = 0; i1 < t->dimen[0]->map->count; i1++) {
345 e = newItem_Set(t->relevant);
347 e->kids[0] = t->dimen[0]->map->set[i1]->representative;
348 e->kids[1] = ts->representative;
349 for (pl = t->rules; pl; pl = pl->next) {
350 register Rule p = (Rule) pl->x;
352 if (t->op == p->pat->op
353 && ts->virgin[p->pat->children[1]->num].rule
354 && t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].rule){
356 ASSIGNCOST(dc, p->delta );
357 ADDCOST(dc, ts->virgin[p->pat->children[1]->num].delta);
358 ADDCOST(dc, t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].delta);
359 if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
360 e->virgin[p->lhs->num].rule = p;
361 ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
368 tmp = encode(globalMap, e, &new);
369 assert(ts->num < t->dimen[1]->map->max_size);
370 t->transition[i1 * t->dimen[1]->max_size + ts->num] = tmp;
381 addHyperPlane(t, i, ts) Table t; ArityNum i; Item_Set ts;
383 switch (t->op->arity) {
406 addToTable(t, ts) Table t; Item_Set ts;
414 for (i = 0; i < t->op->arity; i++) {
419 r = restrict(t->dimen[i], ts);
420 tmp = encode(t->dimen[i]->map, r, &new);
421 if (t->dimen[i]->index_map.max_size <= ts->num) {
422 growIndex_Map(&t->dimen[i]->index_map);
424 assert(ts->num < t->dimen[i]->index_map.max_size);
425 t->dimen[i]->index_map.class[ts->num] = tmp;
427 if (t->dimen[i]->max_size <= r->num) {
428 growTransition(t, i);
430 addHyperPlane(t, i, r);
438 transLval(t, row, col) Table t; int row; int col;
440 switch (t->op->arity) {
444 return t->transition;
447 return t->transition + row;
449 return t->transition + row * t->dimen[1]->max_size + col;
457 dumpRelevant(r) Relevant r;
465 dumpIndex_Map(r) Index_Map *r;
469 printf("BEGIN Index_Map: MaxSize (%d)\n", r->max_size);
470 for (i = 0; i < globalMap->count; i++) {
471 printf("\t#%d: -> %d\n", i, r->class[i]->num);
473 printf("END Index_Map:\n");
477 dumpDimension(d) Dimension d;
479 printf("BEGIN Dimension:\n");
480 printf("Relevant: ");
481 dumpRelevant(d->relevant);
483 dumpIndex_Map(&d->index_map);
485 printf("MaxSize of dimension = %d\n", d->max_size);
486 printf("END Dimension\n");
490 dumpTable(t, full) Table t; int full;
495 printf("NO Table yet.\n");
498 printf("BEGIN Table:\n");
500 dumpOperator(t->op, 0);
502 for (i = 0; i < t->op->arity; i++) {
503 printf("BEGIN dimension(%d)\n", i);
504 dumpDimension(t->dimen[i]);
505 printf("END dimension(%d)\n", i);
508 printf("END Table:\n");
512 dumpTransition(t) Table t;
516 switch (t->op->arity) {
518 printf("{ %d }", t->transition[0]->num);
522 for (i = 0; i < t->dimen[0]->map->count; i++) {
526 printf("%5d", t->transition[i]->num);
532 for (i = 0; i < t->dimen[0]->map->count; i++) {
538 for (j = 0; j < t->dimen[1]->map->count; j++) {
539 Item_Set *ts = transLval(t, i, j);
543 printf("%5d", (*ts)->num);