Return to hash.c CVS log

Up to [CSRG BSD Unix] / 40BSD / cmd / pi

Annotation of 40BSD/cmd/pi/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.1 8/27/80";
        !             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:        "assert",       YASSERT,
        !            27:        "begin",        YBEGIN,
        !            28:        "case",         YCASE,
        !            29:        "const",        YCONST,
        !            30:        "div",          YDIV,
        !            31:        "do",           YDO,
        !            32:        "downto",       YDOWNTO,
        !            33:        "else",         YELSE,
        !            34:        "end",          YEND,
        !            35:        "file",         YFILE,
        !            36:        "for",          YFOR,
        !            37:        "forward",      YFORWARD,
        !            38:        "function",     YFUNCTION,
        !            39:        "goto",         YGOTO,
        !            40:        "if",           YIF,
        !            41:        "in",           YIN,
        !            42:        "label",        YLABEL,
        !            43:        "mod",          YMOD,
        !            44:        "nil",          YNIL,
        !            45:        "not",          YNOT,
        !            46:        "of",           YOF,
        !            47:        "or",           YOR,
        !            48:        "packed",       YPACKED,
        !            49:        "procedure",    YPROCEDURE,
        !            50:        "program",      YPROG,
        !            51:        "record",       YRECORD,
        !            52:        "repeat",       YREPEAT,
        !            53:        "set",          YSET,
        !            54:        "then",         YTHEN,
        !            55:        "to",           YTO,
        !            56:        "type",         YTYPE,
        !            57:        "until",        YUNTIL,
        !            58:        "var",          YVAR,
        !            59:        "while",        YWHILE,
        !            60:        "with",         YWITH,
        !            61:        "oct",          YOCT,    /* non-standard Pascal */
        !            62:        "hex",          YHEX,    /* non-standard Pascal */
        !            63:        "external",     YEXTERN, /* non-standard Pascal */
        !            64:        0
        !            65: };
        !            66: 
        !            67: char   *lastkey        = &yykey[sizeof yykey/sizeof yykey[0]];
        !            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: 
        !            92: /*
        !            93:  * Hash looks up the s(ymbol) argument
        !            94:  * in the string table, entering it if
        !            95:  * it is not found. If save is 0, then
        !            96:  * the argument string is already in
        !            97:  * a safe place. Otherwise, if hash is
        !            98:  * entering the symbol for the first time
        !            99:  * it will save the symbol in the string
        !           100:  * table using savestr.
        !           101:  */
        !           102: int *hash(s, save)
        !           103:        char *s;
        !           104:        int save;
        !           105: {
        !           106:        register int *h;
        !           107:        register i;
        !           108:        register char *cp;
        !           109:        int *sym;
        !           110:        struct ht *htp;
        !           111:        int sh;
        !           112: 
        !           113:        /*
        !           114:         * The hash function is a modular hash of
        !           115:         * the sum of the characters with the sum
        !           116:         * doubled before each successive character
        !           117:         * is added.
        !           118:         */
        !           119:        cp = s;
        !           120:        if (cp == NIL)
        !           121:                cp = token;     /* default symbol to be hashed */
        !           122:        i = 0;
        !           123:        while (*cp)
        !           124:                i = i*2 + *cp++;
        !           125:        sh = (i&077777) % HASHINC;
        !           126:        cp = s;
        !           127:        if (cp == NIL)
        !           128:                cp = token;
        !           129:        /*
        !           130:         * There are as many as MAXHASH active
        !           131:         * hash tables at any given point in time.
        !           132:         * The search starts with the first table
        !           133:         * and continues through the active tables
        !           134:         * as necessary.
        !           135:         */
        !           136:        for (htp = htab; htp < &htab[MAXHASH]; htp++) {
        !           137:                if (htp->ht_low == NIL) {
        !           138:                        cp = (char *) calloc(sizeof ( int * ), HASHINC);
        !           139:                        if (cp == -1) {
        !           140:                                yerror("Ran out of memory (hash)");
        !           141:                                pexit(DIED);
        !           142:                        }
        !           143:                        htp->ht_low = cp;
        !           144:                        htp->ht_high = htp->ht_low + HASHINC;
        !           145:                        cp = s;
        !           146:                        if (cp == NIL)
        !           147:                                cp = token;
        !           148:                }
        !           149:                h = htp->ht_low + sh;
        !           150:                /*
        !           151:                 * quadratic rehash increment
        !           152:                 * starts at 1 and incremented
        !           153:                 * by two each rehash.
        !           154:                 */
        !           155:                i = 1;
        !           156:                do {
        !           157:                        if (*h == 0) {
        !           158:                                if (htp->ht_used > (HASHINC * 3)/4)
        !           159:                                        break;
        !           160:                                htp->ht_used++;
        !           161:                                if (save != 0) {
        !           162:                                        *h = (int) savestr(cp);
        !           163:                                } else
        !           164:                                        *h = s;
        !           165:                                return (h);
        !           166:                        }
        !           167:                        sym = *h;
        !           168:                        if (sym < lastkey && sym >= yykey)
        !           169:                                sym = *sym;
        !           170:                        if (sym->pchar == *cp && strcmp(sym, cp) == 0)
        !           171:                                return (h);
        !           172:                        h += i;
        !           173:                        i += 2;
        !           174:                        if (h >= htp->ht_high)
        !           175:                                h -= HASHINC;
        !           176:                } while (i < HASHINC);
        !           177:        }
        !           178:        yerror("Ran out of hash tables");
        !           179:        pexit(DIED);
        !           180: }

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