Return to hash.c CVS log

Up to [CSRG BSD Unix] / 41BSD / cmd / pxp

Annotation of 41BSD/cmd/pxp/hash.c, revision 1.1

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

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