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 }