utils/Burg/map.c

   1 char rcsid_map[] = "$Id$";
   2
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include "b.h"
   6 #include "fe.h"
   7
   8 Mapping globalMap;
   9
  10 static void growMapping ARGS((Mapping));
  11 static int hash ARGS((Item_Set, int));
  12
  13 Mapping
  14 newMapping(size) int size;
  15 {
  16         Mapping m;
  17
  18         m = (Mapping) zalloc(sizeof(struct mapping));
  19         assert(m);
  20
  21         m->count = 0;
  22         m->hash = (List*) zalloc(size * sizeof(List));
  23         m->hash_size = size;
  24         m->max_size = STATES_INCR;
  25         m->set = (Item_Set*) zalloc(m->max_size * sizeof(Item_Set));
  26         assert(m->set);
  27
  28         return m;
  29 }
  30
  31 static void
  32 growMapping(m) Mapping m;
  33 {
  34         Item_Set *tmp;
  35
  36         m->max_size += STATES_INCR;
  37         tmp = (Item_Set*) zalloc(m->max_size * sizeof(Item_Set));
  38         memcpy(tmp, m->set, m->count * sizeof(Item_Set));
  39         zfree(m->set);
  40         m->set = tmp;
  41 }
  42
  43 static int
  44 hash(ts, mod) Item_Set ts; int mod;
  45 {
  46         register Item *p = ts->virgin;
  47         register int v;
  48         register Relevant r = ts->relevant;
  49         register int nt;
  50
  51         if (!ts->op) {
  52                 return 0;
  53         }
  54
  55         v = 0;
  56         for (; (nt = *r) != 0; r++) {
  57                 v ^= ((long)p[nt].rule) + (PRINCIPLECOST(p[nt].delta)<<4);
  58         }
  59         v >>= 4;
  60         v &= (mod-1);
  61         return v;
  62 }
  63
  64 Item_Set
  65 encode(m, ts, new) Mapping m; Item_Set ts; int *new;
  66 {
  67         int h;
  68         List l;
  69
  70         assert(m);
  71         assert(ts);
  72         assert(m->count <= m->max_size);
  73
  74         if (grammarNts && errorState && m == globalMap) {
  75                 List l;
  76                 int found;
  77
  78                 found = 0;
  79                 for (l = grammarNts; l; l = l->next) {
  80                         Symbol s;
  81                         s = (Symbol) l->x;
  82
  83                         if (ts->virgin[s->u.nt->num].rule) {
  84                                 found = 1;
  85                                 break;
  86                         }
  87                 }
  88                 if (!found) {
  89                         *new = 0;
  90                         return errorState;
  91                 }
  92         }
  93
  94         *new = 0;
  95         h = hash(ts, m->hash_size);
  96         for (l = m->hash[h]; l; l = l->next) {
  97                 Item_Set s = (Item_Set) l->x;
  98                 if (ts->op == s->op && equivSet(ts, s)) {
  99                         ts->num = s->num;
 100                         return s;
 101                 }
 102         }
 103         if (m->count >= m->max_size) {
 104                 growMapping(m);
 105         }
 106         assert(m->count < m->max_size);
 107         m->set[m->count] = ts;
 108         ts->num = m->count++;
 109         *new = 1;
 110         m->hash[h] = newList(ts, m->hash[h]);
 111         return ts;
 112 }
 113
 114 Item_Set
 115 decode(m, t) Mapping m; ItemSetNum t;
 116 {
 117         assert(m);
 118         assert(t);
 119         assert(m->count < m->max_size);
 120         assert(t < m->count);
 121
 122         return m->set[t];
 123 }
 124
 125 void
 126 dumpMapping(m) Mapping m;
 127 {
 128         int i;
 129
 130         printf("BEGIN Mapping: Size=%d\n", m->count);
 131         for (i = 0; i < m->count; i++) {
 132                 dumpItem_Set(m->set[i]);
 133         }
 134         printf("END Mapping\n");
 135 }