Return to hash.c CVS log

Up to [CSRG BSD Unix] / 43BSD / ucb / pascal / src

Annotation of 43BSD/ucb/pascal/src/hash.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1980 Regents of the University of California.
        !             3:  * All rights reserved.  The Berkeley software License Agreement
        !             4:  * specifies the terms and conditions for redistribution.
        !             5:  */
        !             6: 
        !             7: #ifndef lint
        !             8: static char sccsid[] = "@(#)hash.c     5.1 (Berkeley) 6/5/85";
        !             9: #endif not lint
        !            10: 
        !            11: #include "whoami.h"
        !            12: #include "0.h"
        !            13: #include "tree_ty.h"           /* must be included for yy.h */
        !            14: #include "yy.h"
        !            15: 
        !            16: /*
        !            17:  * The definition for the segmented hash tables.
        !            18:  */
        !            19: struct ht {
        !            20:        int     *ht_low;
        !            21:        int     *ht_high;
        !            22:        int     ht_used;
        !            23: } htab[MAXHASH];
        !            24: 
        !            25: /*
        !            26:  * This is the array of keywords and their
        !            27:  * token values, which are hashed into the table
        !            28:  * by inithash.
        !            29:  */
        !            30: struct kwtab yykey[] = {
        !            31:        "and",          YAND,
        !            32:        "array",        YARRAY,
        !            33:        "begin",        YBEGIN,
        !            34:        "case",         YCASE,
        !            35:        "const",        YCONST,
        !            36:        "div",          YDIV,
        !            37:        "do",           YDO,
        !            38:        "downto",       YDOWNTO,
        !            39:        "else",         YELSE,
        !            40:        "end",          YEND,
        !            41:        "file",         YFILE,
        !            42:        "for",          YFOR,
        !            43:        "forward",      YFORWARD,
        !            44:        "function",     YFUNCTION,
        !            45:        "goto",         YGOTO,
        !            46:        "if",           YIF,
        !            47:        "in",           YIN,
        !            48:        "label",        YLABEL,
        !            49:        "mod",          YMOD,
        !            50:        "nil",          YNIL,
        !            51:        "not",          YNOT,
        !            52:        "of",           YOF,
        !            53:        "or",           YOR,
        !            54:        "packed",       YPACKED,
        !            55:        "procedure",    YPROCEDURE,
        !            56:        "program",      YPROG,
        !            57:        "record",       YRECORD,
        !            58:        "repeat",       YREPEAT,
        !            59:        "set",          YSET,
        !            60:        "then",         YTHEN,
        !            61:        "to",           YTO,
        !            62:        "type",         YTYPE,
        !            63:        "until",        YUNTIL,
        !            64:        "var",          YVAR,
        !            65:        "while",        YWHILE,
        !            66:        "with",         YWITH,
        !            67:        0,              0,       /* the following keywords are non-standard */
        !            68:        "oct",          YOCT,
        !            69:        "hex",          YHEX,
        !            70:        "external",     YEXTERN,
        !            71:        0
        !            72: };
        !            73: 
        !            74: char *lastkey;
        !            75: 
        !            76: /*
        !            77:  * Inithash initializes the hash table routines
        !            78:  * by allocating the first hash table segment using
        !            79:  * an already existing memory slot.
        !            80:  */
        !            81: #ifndef PI0
        !            82: inithash()
        !            83: #else
        !            84: inithash(hshtab)
        !            85:        int *hshtab;
        !            86: #endif
        !            87: {
        !            88:        register int *ip;
        !            89: #ifndef PI0
        !            90:        static int hshtab[HASHINC];
        !            91: #endif
        !            92: 
        !            93:        htab[0].ht_low = hshtab;
        !            94:        htab[0].ht_high = &hshtab[HASHINC];
        !            95:        for (ip = ((int *)yykey); *ip; ip += 2)
        !            96:                hash((char *) ip[0], 0)[0] = ((int) ip);
        !            97:        /*
        !            98:         * If we are not running in "standard-only" mode,
        !            99:         * we load the non-standard keywords.
        !           100:         */
        !           101:        if (!opt('s'))
        !           102:                for (ip += 2; *ip; ip += 2)
        !           103:                        hash((char *) ip[0], 0)[0] = ((int) ip);
        !           104:        lastkey = (char *)ip;
        !           105: }
        !           106: 
        !           107: /*
        !           108:  * Hash looks up the s(ymbol) argument
        !           109:  * in the string table, entering it if
        !           110:  * it is not found. If save is 0, then
        !           111:  * the argument string is already in
        !           112:  * a safe place. Otherwise, if hash is
        !           113:  * entering the symbol for the first time
        !           114:  * it will save the symbol in the string
        !           115:  * table using savestr.
        !           116:  */
        !           117: int *hash(s, save)
        !           118:        char *s;
        !           119:        int save;
        !           120: {
        !           121:        register int *h;
        !           122:        register i;
        !           123:        register char *cp;
        !           124:        int *sym;
        !           125:        struct cstruct *temp;
        !           126:        struct ht *htp;
        !           127:        int sh;
        !           128: 
        !           129:        /*
        !           130:         * The hash function is a modular hash of
        !           131:         * the sum of the characters with the sum
        !           132:         * doubled before each successive character
        !           133:         * is added.
        !           134:         */
        !           135:        cp = s;
        !           136:        if (cp == NIL)
        !           137:                cp = token;     /* default symbol to be hashed */
        !           138:        i = 0;
        !           139:        while (*cp)
        !           140:                i = i*2 + *cp++;
        !           141:        sh = (i&077777) % HASHINC;
        !           142:        cp = s;
        !           143:        if (cp == NIL)
        !           144:                cp = token;
        !           145:        /*
        !           146:         * There are as many as MAXHASH active
        !           147:         * hash tables at any given point in time.
        !           148:         * The search starts with the first table
        !           149:         * and continues through the active tables
        !           150:         * as necessary.
        !           151:         */
        !           152:        for (htp = htab; htp < &htab[MAXHASH]; htp++) {
        !           153:                if (htp->ht_low == NIL) {
        !           154:                        cp = (char *) pcalloc(sizeof ( int * ), HASHINC);
        !           155:                        if (cp == 0) {
        !           156:                                yerror("Ran out of memory (hash)");
        !           157:                                pexit(DIED);
        !           158:                        }
        !           159:                        htp->ht_low = ((int *)cp);
        !           160:                        htp->ht_high = htp->ht_low + HASHINC;
        !           161:                        cp = s;
        !           162:                        if (cp == NIL)
        !           163:                                cp = token;
        !           164:                }
        !           165:                h = htp->ht_low + sh;
        !           166:                /*
        !           167:                 * quadratic rehash increment
        !           168:                 * starts at 1 and incremented
        !           169:                 * by two each rehash.
        !           170:                 */
        !           171:                i = 1;
        !           172:                do {
        !           173:                        if (*h == 0) {
        !           174:                                if (htp->ht_used > (HASHINC * 3)/4)
        !           175:                                        break;
        !           176:                                htp->ht_used++;
        !           177:                                if (save != 0) {
        !           178:                                        *h = (int) savestr(cp);
        !           179:                                } else
        !           180:                                        *h = ((int) s);
        !           181:                                return (h);
        !           182:                        }
        !           183:                        sym = ((int *) *h);
        !           184:                        if (sym < ((int *) lastkey) && sym >= ((int *) yykey))
        !           185:                                sym = ((int *) *sym);
        !           186:                        temp = ((struct cstruct *) sym);
        !           187:                        if (temp->pchar == *cp && pstrcmp((char *) sym, cp) == 0)
        !           188:                                return (h);
        !           189:                        h += i;
        !           190:                        i += 2;
        !           191:                        if (h >= htp->ht_high)
        !           192:                                h -= HASHINC;
        !           193:                } while (i < HASHINC);
        !           194:        }
        !           195:        yerror("Ran out of hash tables");
        !           196:        pexit(DIED);
        !           197:        return (NIL);
        !           198: 
        !           199: }

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