utils/Burg/table.c

   1 char rcsid_table[] = "$Id$";
   2
   3 #include "b.h"
   4 #include <string.h>
   5 #include <stdio.h>
   6
   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));
  19
  20 static void
  21 growIndex_Map(r) Index_Map *r;
  22 {
  23   Index_Map new;
  24
  25   new.max_size = r->max_size + STATES_INCR;
  26   new.class = (Item_Set*) zalloc(new.max_size * sizeof(Item_Set));
  27   assert(new.class);
  28   memcpy(new.class, r->class, r->max_size * sizeof(Item_Set));
  29   zfree(r->class);
  30   *r = new;
  31 }
  32
  33 static Relevant
  34 newRelevant()
  35 {
  36   Relevant r = (Relevant) zalloc(max_nonterminal * sizeof(*r));
  37   return r;
  38 }
  39
  40 void
  41 addRelevant(r, nt) Relevant r; NonTerminalNum nt;
  42 {
  43   int i;
  44
  45   for (i = 0; r[i]; i++) {
  46     if (r[i] == nt) {
  47       break;
  48     }
  49   }
  50   if (!r[i]) {
  51     r[i] = nt;
  52   }
  53 }
  54
  55 static Dimension
  56 newDimension(op, index) Operator op; ArityNum index;
  57 {
  58   Dimension d;
  59   List pl;
  60   Relevant r;
  61
  62   assert(op);
  63   assert(index >= 0 && index < op->arity);
  64   d = (Dimension) zalloc(sizeof(struct dimension));
  65   assert(d);
  66
  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);
  72     }
  73   }
  74
  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;
  80
  81   return d;
  82 }
  83
  84 Table
  85 newTable(op) Operator op;
  86 {
  87   Table t;
  88   int i, size;
  89
  90   assert(op);
  91
  92   t = (Table) zalloc(sizeof(struct table));
  93   assert(t);
  94
  95   t->op = op;
  96
  97   for (i = 0; i < op->arity; i++) {
  98     t->dimen[i] = newDimension(op, i);
  99   }
 100
 101   size = 1;
 102   for (i = 0; i < op->arity; i++) {
 103     size *= t->dimen[i]->max_size;
 104   }
 105   t->transition = (Item_Set*) zalloc(size * sizeof(Item_Set));
 106   t->relevant = newRelevant();
 107   assert(t->transition);
 108
 109   return t;
 110 }
 111
 112 static void
 113 GT_1(t) Table t;
 114 {
 115   Item_Set  *ts;
 116   ItemSetNum  oldsize = t->dimen[0]->max_size;
 117   ItemSetNum  newsize = t->dimen[0]->max_size + TABLE_INCR;
 118
 119   t->dimen[0]->max_size = newsize;
 120
 121   ts = (Item_Set*) zalloc(newsize * sizeof(Item_Set));
 122   assert(ts);
 123   memcpy(ts, t->transition, oldsize * sizeof(Item_Set));
 124   zfree(t->transition);
 125   t->transition = ts;
 126 }
 127
 128 static void
 129 GT_2_0(t) Table t;
 130 {
 131   Item_Set  *ts;
 132   ItemSetNum  oldsize = t->dimen[0]->max_size;
 133   ItemSetNum  newsize = t->dimen[0]->max_size + TABLE_INCR;
 134   int   size;
 135
 136   t->dimen[0]->max_size = newsize;
 137
 138   size = newsize * t->dimen[1]->max_size;
 139
 140   ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
 141   assert(ts);
 142   memcpy(ts, t->transition, oldsize*t->dimen[1]->max_size * sizeof(Item_Set));
 143   zfree(t->transition);
 144   t->transition = ts;
 145 }
 146
 147 static void
 148 GT_2_1(t) Table t;
 149 {
 150   Item_Set  *ts;
 151   ItemSetNum  oldsize = t->dimen[1]->max_size;
 152   ItemSetNum  newsize = t->dimen[1]->max_size + TABLE_INCR;
 153   int   size;
 154   Item_Set  *from;
 155   Item_Set  *to;
 156   int     i1, i2;
 157
 158   t->dimen[1]->max_size = newsize;
 159
 160   size = newsize * t->dimen[0]->max_size;
 161
 162   ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
 163   assert(ts);
 164
 165   from = t->transition;
 166   to = ts;
 167   for (i1 = 0; i1 < t->dimen[0]->max_size; i1++) {
 168     for (i2 = 0; i2 < oldsize; i2++) {
 169       to[i2] = from[i2];
 170     }
 171     to += newsize;
 172     from += oldsize;
 173   }
 174   zfree(t->transition);
 175   t->transition = ts;
 176 }
 177
 178 static void
 179 growTransition(t, dim) Table t; ArityNum dim;
 180 {
 181
 182   assert(t);
 183   assert(t->op);
 184   assert(dim < t->op->arity);
 185
 186   switch (t->op->arity) {
 187   default:
 188     assert(0);
 189     break;
 190   case 1:
 191     GT_1(t);
 192     return;
 193   case 2:
 194     switch (dim) {
 195     default:
 196       assert(0);
 197       break;
 198     case 0:
 199       GT_2_0(t);
 200       return;
 201     case 1:
 202       GT_2_1(t);
 203       return;
 204     }
 205   }
 206 }
 207
 208 static Item_Set
 209 restrict(d, ts) Dimension d; Item_Set ts;
 210 {
 211   DeltaCost base;
 212   Item_Set  r;
 213   int found;
 214   register Relevant r_ptr = d->relevant;
 215   register Item *ts_current = ts->closed;
 216   register Item *r_current;
 217   register int i;
 218   register int nt;
 219
 220   ZEROCOST(base);
 221   found = 0;
 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;
 227       if (!found) {
 228         found = 1;
 229         ASSIGNCOST(base, ts_current[nt].delta);
 230       } else {
 231         if (LESSCOST(ts_current[nt].delta, base)) {
 232           ASSIGNCOST(base, ts_current[nt].delta);
 233         }
 234       }
 235     }
 236   }
 237
 238   /* zero align */
 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);
 243     }
 244   }
 245   assert(!r->closed);
 246   r->representative = ts;
 247   return r;
 248 }
 249
 250 static void
 251 addHP_1(t, ts) Table t; Item_Set ts;
 252 {
 253   List pl;
 254   Item_Set e;
 255   Item_Set tmp;
 256   int new;
 257
 258   e = newItem_Set(t->relevant);
 259   assert(e);
 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) {
 264       DeltaCost dc;
 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);
 270         e->op = t->op;
 271       }
 272     }
 273   }
 274   trim(e);
 275   zero(e);
 276   tmp = encode(globalMap, e, &new);
 277   assert(ts->num < t->dimen[0]->map->max_size);
 278   t->transition[ts->num] = tmp;
 279   if (new) {
 280     closure(e);
 281     addQ(globalQ, tmp);
 282   } else {
 283     freeItem_Set(e);
 284   }
 285 }
 286
 287 static void
 288 addHP_2_0(t, ts) Table t; Item_Set ts;
 289 {
 290   List pl;
 291   register Item_Set e;
 292   Item_Set tmp;
 293   int new;
 294   int i2;
 295
 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);
 299     assert(e);
 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;
 304
 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){
 308         DeltaCost dc;
 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);
 312
 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);
 316           e->op = t->op;
 317         }
 318       }
 319     }
 320     trim(e);
 321     zero(e);
 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;
 325     if (new) {
 326       closure(e);
 327       addQ(globalQ, tmp);
 328     } else {
 329       freeItem_Set(e);
 330     }
 331   }
 332 }
 333
 334 static void
 335 addHP_2_1(t, ts) Table t; Item_Set ts;
 336 {
 337   List pl;
 338   register Item_Set e;
 339   Item_Set tmp;
 340   int new;
 341   int i1;
 342
 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);
 346     assert(e);
 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;
 351
 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){
 355         DeltaCost dc;
 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);
 362           e->op = t->op;
 363         }
 364       }
 365     }
 366     trim(e);
 367     zero(e);
 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;
 371     if (new) {
 372       closure(e);
 373       addQ(globalQ, tmp);
 374     } else {
 375       freeItem_Set(e);
 376     }
 377   }
 378 }
 379
 380 static void
 381 addHyperPlane(t, i, ts) Table t; ArityNum i; Item_Set ts;
 382 {
 383   switch (t->op->arity) {
 384   default:
 385     assert(0);
 386     break;
 387   case 1:
 388     addHP_1(t, ts);
 389     return;
 390   case 2:
 391     switch (i) {
 392     default:
 393       assert(0);
 394       break;
 395     case 0:
 396       addHP_2_0(t, ts);
 397       return;
 398     case 1:
 399       addHP_2_1(t, ts);
 400       return;
 401     }
 402   }
 403 }
 404
 405 void
 406 addToTable(t, ts) Table t; Item_Set ts;
 407 {
 408   ArityNum i;
 409
 410   assert(t);
 411   assert(ts);
 412   assert(t->op);
 413
 414   for (i = 0; i < t->op->arity; i++) {
 415     Item_Set r;
 416     Item_Set tmp;
 417     int new;
 418
 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);
 423     }
 424     assert(ts->num < t->dimen[i]->index_map.max_size);
 425     t->dimen[i]->index_map.class[ts->num] = tmp;
 426     if (new) {
 427       if (t->dimen[i]->max_size <= r->num) {
 428         growTransition(t, i);
 429       }
 430       addHyperPlane(t, i, r);
 431     } else {
 432       freeItem_Set(r);
 433     }
 434   }
 435 }
 436
 437 Item_Set *
 438 transLval(t, row, col) Table t; int row; int col;
 439 {
 440   switch (t->op->arity) {
 441   case 0:
 442     assert(row == 0);
 443     assert(col == 0);
 444     return t->transition;
 445   case 1:
 446     assert(col == 0);
 447     return t->transition + row;
 448   case 2:
 449     return t->transition + row * t->dimen[1]->max_size + col;
 450   default:
 451     assert(0);
 452   }
 453   return 0;
 454 }
 455
 456 void
 457 dumpRelevant(r) Relevant r;
 458 {
 459   for (; *r; r++) {
 460     printf("%4d", *r);
 461   }
 462 }
 463
 464 void
 465 dumpIndex_Map(r) Index_Map *r;
 466 {
 467   int i;
 468
 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);
 472   }
 473   printf("END Index_Map:\n");
 474 }
 475
 476 void
 477 dumpDimension(d) Dimension d;
 478 {
 479   printf("BEGIN Dimension:\n");
 480   printf("Relevant: ");
 481   dumpRelevant(d->relevant);
 482   printf("\n");
 483   dumpIndex_Map(&d->index_map);
 484   dumpMapping(d->map);
 485   printf("MaxSize of dimension = %d\n", d->max_size);
 486   printf("END Dimension\n");
 487 }
 488
 489 void
 490 dumpTable(t, full) Table t; int full;
 491 {
 492   int i;
 493
 494   if (!t) {
 495     printf("NO Table yet.\n");
 496     return;
 497   }
 498   printf("BEGIN Table:\n");
 499   if (full) {
 500     dumpOperator(t->op, 0);
 501   }
 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);
 506   }
 507   dumpTransition(t);
 508   printf("END Table:\n");
 509 }
 510
 511 void
 512 dumpTransition(t) Table t;
 513 {
 514   int i,j;
 515
 516   switch (t->op->arity) {
 517   case 0:
 518     printf("{ %d }", t->transition[0]->num);
 519     break;
 520   case 1:
 521     printf("{");
 522     for (i = 0; i < t->dimen[0]->map->count; i++) {
 523       if (i > 0) {
 524         printf(",");
 525       }
 526       printf("%5d", t->transition[i]->num);
 527     }
 528     printf("}");
 529     break;
 530   case 2:
 531     printf("{");
 532     for (i = 0; i < t->dimen[0]->map->count; i++) {
 533       if (i > 0) {
 534         printf(",");
 535       }
 536       printf("\n");
 537       printf("{");
 538       for (j = 0; j < t->dimen[1]->map->count; j++) {
 539         Item_Set *ts = transLval(t, i, j);
 540         if (j > 0) {
 541           printf(",");
 542         }
 543         printf("%5d", (*ts)->num);
 544       }
 545       printf("}");
 546     }
 547     printf("\n}\n");
 548     break;
 549   default:
 550     assert(0);
 551   }
 552 }