Return to hash.c CVS log

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

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

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

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