Return to 1.hash.c CVS log

Up to [CSRG BSD Unix] / 42BSD / usr.bin / struct

Annotation of 42BSD/usr.bin/struct/1.hash.c, revision 1.1

1.1     ! root        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:        }
        !           241: 
        !           242: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.