4.3BSD - /usr/src/usr.bin/struct/1.hash.c

   1: #ifndef lint
   2: static char sccsid[] = "@(#)1.hash.c	4.1	(Berkeley)	2/11/83";
   3: #endif not lint
   4: 
   5: #include <stdio.h>
   6: #include "1.incl.h"
   7: #include "1.defs.h"
   8: #include"def.h"
   9: 
  10: extern int match[], symclass[],  action[], newstate[];
  11: extern char symbol[];
  12: long *hashtab;
  13: int *value, *chain;
  14: 
  15: extern FILE *infd;
  16: 
  17: 
  18: parse()
  19:     {int i,j,found,current, someread;
  20:     char c;
  21: 
  22:     hash_init();
  23:     routinit();
  24:     line_init();
  25: 
  26:     someread = 0;           /* indicates haven't read part of a routine */
  27: 
  28:     empseek(0);
  29:     endbuf = getline(&endline, &endchar, &endcom, & comchar);
  30:     if (progress && endbuf != -1) fprintf(stderr,"parsing\n");
  31:     while(endbuf != -1)         /* getline returns -1 when no more input */
  32:         {
  33:         someread = 1;
  34:         if (progress > 0)
  35:             {
  36:             for (i = begline; i <= endline; i++)
  37:                 if (!(i % progress)) fprintf(stderr,"parsing line %d\n",i);
  38:             }
  39:         current = 0;
  40:         for (i = 0; i < endbuf; i++)
  41:             {
  42: 
  43:             c = buffer[i];
  44:             if(c != '~')
  45:                 {
  46:                 found = 0;
  47:                 if ( (current < 0 || current >= snum) && current != ABORT)
  48:                     {
  49:                     strerr("in parsing:","","");
  50:                     fprintf(stderr,"line %d of file, parser in invalid state", begline,current);
  51:                     fprintf(stderr,"treating it as straight line code\n");
  52:                     current = ABORT;
  53:                     }
  54:                 else
  55:                     for (j = match[current];  j < match[current + 1]; j++)
  56:                         {
  57:                         if ((symclass[j] == 0 && c == symbol[j]) ||
  58:                             (symclass[j] != 0 && classmatch(c,symclass[j]) ))
  59:                             {found = 1;  break;
  60:                             }
  61:                         }
  62:                 if (!found)
  63:                     {
  64:                     error("in syntax:","","");
  65:                     fprintf(stderr,"between lines %d and %d of file\n",begline, endline);
  66:                     if (debug)
  67:                     fprintf(stderr,"symbol '%c' does not match entries for state %d\n",c,current);
  68:                     fprintf(stderr,"treating it as straight line code\n");
  69:                     current = ABORT;
  70:                     }
  71:                 else if (!action[j])
  72:                     current = newstate[j];
  73:                 else
  74:                     {
  75:                     current = act(action[j],c,i);
  76:                     if (current == nulls)  current = newstate[j];
  77:                     }
  78:                 if (current == ABORT)  break;
  79:                 if (current == endrt)
  80:                     {
  81:                     return(1);
  82:                     }
  83:                 }
  84:             }
  85:         line_init();
  86:         endbuf = getline(&endline, &endchar, &endcom,&comchar);
  87:         }
  88:     if (someread) return(1);
  89:     else return(0);
  90:     }
  91: 
  92: 
  93: hash_init()
  94:     {
  95:     int i;
  96:     hashtab = challoc(sizeof(*hashtab) * maxhash);
  97:     chain = challoc(sizeof(*chain) * maxhash);
  98:     value = challoc(sizeof(*value) * maxhash);
  99:     for (i = 0; i < maxhash; i++)
 100:         {
 101:         hashtab[i] = -1L;
 102:         value[i] = -2;
 103:         chain[i] = 0;
 104:         }
 105:     }
 106: 
 107: 
 108: hash_check()
 109:     {
 110:     int i;
 111:     for (i = 0; i < maxhash; ++i)
 112:         if (value[i] == -2 && hashtab[i] != -1L)
 113:             {
 114:             error("in syntax; label used but does not appear as statement label:","","");
 115:             fprintf(stderr,"%D\n",hashtab[i]);
 116:             routerr = 1;
 117:             }
 118:     }
 119: 
 120: hash_free()
 121:     {
 122:     chfree(hashtab,sizeof(*hashtab) * maxhash);
 123:     hashtab = 0;
 124:     chfree(chain,sizeof(*chain) * maxhash);
 125:     chain = 0;
 126:     chfree(value,sizeof(*value) * maxhash);
 127:     value = 0;
 128:     }
 129: hash(x)
 130: long x;
 131:     {
 132:     int quo, rem, hcount, temp;
 133: 
 134:     ASSERT(x >= 0L, hash);
 135:     quo = x/maxhash;
 136:     rem = x - (quo * maxhash);
 137:     if (quo == 0)  quo = 1;
 138: 
 139:     temp = rem;
 140:     for (hcount=0; (hashtab[temp] != -1L) && (hashtab[temp] != x) && (hcount<maxhash); hcount++)
 141:         temp = (temp + quo)%maxhash;
 142:     if(hcount>=maxhash) faterr("hash table overflow - too many labels","","");
 143:     hashtab[temp] = x;
 144:     return(temp);
 145:     }
 146: 
 147: addref(x,ptr)               /* put ptr in chain for x or assign value of x to *ptr */
 148: long x;
 149: int *ptr;
 150:     {
 151:     int index;
 152:     index = hash(x);
 153: 
 154:     if (value[index]  == -1)
 155:         {           /* x already assigned value */
 156:         *ptr = chain[index];
 157:         return;
 158:         }
 159: 
 160:     /* add ptr to chain */
 161: 
 162:     if (chain[index] == 0)
 163:         *ptr = 0;
 164:     else
 165:         *ptr = chain[index];
 166:     chain[index] = ptr;
 167:     }
 168: 
 169: fixvalue (x,ptr)
 170: long x;
 171: int ptr;
 172:     {
 173:     int *temp1, *temp2, index, temp0;
 174:     index = hash(x);
 175: 
 176:     while (index != -2)
 177:         {           /* trace chain of linked labels */
 178: 
 179:         if (value[index]  == -1)
 180:             {
 181:             error("in syntax:  ","","");
 182:             fprintf(stderr,"attempt to redefine value of label %D between lines %d and %d\n",
 183:                 x,begline,endline);
 184:             routerr = 1;
 185:             return;
 186:             }
 187: 
 188:         temp1 = &chain[index];      /* trace chain for each label */
 189:         while (temp1 != 0)
 190:             {
 191:             temp2 = *temp1;
 192:             *temp1 = ptr;
 193:             temp1 = temp2;
 194:             }
 195:         temp0 = index;
 196:         index = value[index];
 197:         value[temp0] = -1;
 198:         }
 199:     }
 200: 
 201: connect(x,y)
 202: long x,y;
 203:     {
 204:     int *temp, index, temp2;
 205:     index = hash(x);
 206: 
 207:     if (value[index] == -1)
 208:         fixvalue(y, chain[index]);
 209:     else
 210:         {
 211:         if (y == implicit)
 212:         {       /* attach implicit chain to x chain */
 213:         temp = &chain[index];
 214: 
 215:         while (*temp != 0)
 216:             temp = *temp;
 217: 
 218:         *temp = chain[hash(y)];
 219:         }
 220:         temp2 = index;      /* attach y linked labels to x linked labels */
 221:         while (value[temp2] >= 0)
 222:             temp2 = value[temp2];
 223:         if (y == implicit)
 224:             value[temp2] = value[hash(y)];
 225:         else
 226:             value[temp2] = hash(y);
 227:         }
 228:     if (y == implicit)  clear(y);
 229:     }
 230: 
 231: 
 232: clear(x)
 233: long x;
 234:     {
 235:     int index;
 236:     index = hash(x);
 237:     value[index] = -2;
 238:     chain[index] = 0;
 239:     hashtab[index] = -1L;
 240:     }

Defined functions

Defined variables