Return to hashing.c CVS log

Up to [Research Unix] / researchv10no / cmd / visi

Annotation of researchv10no/cmd/visi/hashing.c, revision 1.1

1.1     ! root        1: /*
        !             2:  *      hashing.c 1.3
        !             3:  *
        !             4:  *     Hashing Functions for Spreadsheet Program `vis'
        !             5:  *
        !             6:  *      A. F. Gettier
        !             7:  *      Bell Laboratories
        !             8:  *      Update made 11/1/82 11:11:37
        !             9:  *      Retrieved 11/15/82 13:22:21
        !            10:  */
        !            11: #include       <stdio.h>
        !            12: #include       "vis.h"
        !            13: #include       "y.tab.h"
        !            14: 
        !            15: struct hashhdr htbl;
        !            16: 
        !            17: static struct reswd reswd[]={
        !            18:        "PI", PI,
        !            19:        "ABS", ABS,
        !            20:        "ACOS", ACOS,
        !            21:        "ASIN", ASIN,
        !            22:        "AT", AT,
        !            23:        "ATAN", ATAN,
        !            24:        "ATAN2", ATAN2,
        !            25:        "COS", COS,
        !            26:        "EXP", EXP,
        !            27:        "GAMMA", GAMMA,
        !            28:        "HYPOT", HYPOT,
        !            29:        "INT", INT,
        !            30:        "LOG", LOG,
        !            31:        "POW", POW,
        !            32:        "SIN", SIN,
        !            33:        "SQRT", SQRT,
        !            34:        "COL", COL,
        !            35:        "COPY", COPY,
        !            36:        "DEBUG", DEBUG,
        !            37:        "DOWN", DOWN,
        !            38:        "DUP", DUP,
        !            39:        "DUPLICATE", DUPLICATE,
        !            40:        "EDIT", EDIT,
        !            41:        "HELP", HELP,
        !            42:        "LEFT", LEFT,
        !            43:        "LIST", LIST,
        !            44:        "POSITION", POSITION,
        !            45:        "READ", READ,
        !            46:        "REDRAW", REDRAW,
        !            47:        "REFRESH", REFRESH,
        !            48:        "REP", REP,
        !            49:        "REPLICATE", REPLICATE,
        !            50:        "RIGHT", RIGHT,
        !            51:        "ROW", ROW,
        !            52:        "SCALE", SCALE,
        !            53:        "SHIFT", SHIFT,
        !            54:        "SLIDE", SLIDE,
        !            55:        "SHELL", SHELL,
        !            56:        "SH", SH,
        !            57:        "THRU", THRU,
        !            58:        "UP", UP,
        !            59:        "VER", VER,
        !            60:        "WIDTH", WIDTH,
        !            61:        "WRITE", WRITE,
        !            62:        "ZERO", ZERO,
        !            63:        "QUIT", QUIT,
        !            64:        0, 0 };
        !            65: 
        !            66: /*
        !            67:  *     Init a hash table
        !            68:  */
        !            69: void hashinit()
        !            70: {
        !            71:        int     i;
        !            72:        int     size;
        !            73:        struct hashentry        *tbl;
        !            74:        size = 63; /* default hash table size */
        !            75:        htbl.size = size;
        !            76:        tbl = htbl.table = multnode( hashentry, size );
        !            77:        for ( i=0; i<size; i++ ) (tbl++)->symbol = 0;
        !            78:        /*
        !            79:         *      enter all the keywords
        !            80:         */
        !            81:        for( i=0; reswd[i].name!=0; i++ )
        !            82:                hashenter( reswd[i].name, reswd[i].value );
        !            83: }
        !            84: 
        !            85: /*
        !            86:  *     Search a hash table
        !            87:  */
        !            88: hashsearch( symbol )
        !            89: char   *symbol;
        !            90: {
        !            91:        int     key, mkey;
        !            92:        struct hashentry        *tbl, *start;
        !            93:        key = makekey( symbol );
        !            94:        mkey = key%(htbl.size - 1);
        !            95:        start = tbl = htbl.table + mkey;
        !            96:        do {
        !            97:                if ( tbl->symbol == 0 ) return( 0 );
        !            98:                if ( tbl->symbol != (char *)(-1) && tbl->key == key
        !            99:                    && strcmp( symbol, tbl->symbol ) == 0 )
        !           100:                        return(tbl->value);
        !           101:                tbl++;
        !           102:                if ( tbl >= (htbl.table + htbl.size ) )  tbl = htbl.table;
        !           103:        } while ( tbl != start );
        !           104:        return( 0 );
        !           105: }
        !           106: 
        !           107: /*
        !           108:  *     Enter into a hash table
        !           109:  */
        !           110: void hashenter( symbol, value )
        !           111: char   *symbol;
        !           112: int    value;
        !           113: {
        !           114:        int     key, mkey;
        !           115:        float   a, b;
        !           116:        struct hashentry        *tbl;
        !           117:        a = htbl.size;
        !           118:        b = htbl.entry;
        !           119:        /*
        !           120:         *      First try to clean up the table
        !           121:         */
        !           122:        if ( b/a > .65 )        hashclean( );
        !           123:        /*
        !           124:         *      Now expand
        !           125:         */
        !           126:        b = htbl.entry;
        !           127:        if ( b/a > .65 )        hashexpand( );
        !           128:        key = makekey( symbol );
        !           129:        mkey = key%(htbl.size - 1);
        !           130:        tbl = htbl.table;
        !           131:        tbl += mkey;
        !           132:        loop {
        !           133:                if ( tbl->symbol == 0 || tbl->symbol == (char *)(-1)) {
        !           134:                        tbl->key = key;
        !           135:                        tbl->symbol = symbol;
        !           136:                        (htbl.entry)++;
        !           137:                        tbl->value = value;
        !           138:                        return;
        !           139:                }
        !           140:                if ( tbl->key == key && strcmp( symbol, tbl->symbol ) == 0 ) {
        !           141:                        tbl->value = value;
        !           142:                        return;
        !           143:                }
        !           144:                tbl++;
        !           145:                if ( tbl >= (htbl.table + htbl.size ) )  tbl = htbl.table;
        !           146:        }
        !           147: }
        !           148: 
        !           149: /*
        !           150:  *     Make the key
        !           151:  */
        !           152: static makekey( symbol )
        !           153: char   *symbol;
        !           154: {
        !           155:        int     key, i;
        !           156:        key = 0;
        !           157:        i = 8;
        !           158:        while (*symbol != 0) {
        !           159:                key += *symbol + ((*symbol)<<8) + ((*symbol)<<(i++));
        !           160:                symbol++;
        !           161:        }
        !           162:        return( ((key<0)?(-key):(key)) );
        !           163: }
        !           164: 
        !           165: /*
        !           166:  *     Expand the Hash Table
        !           167:  */
        !           168: static hashexpand( )
        !           169:  {
        !           170:        int     i, mkey, size;
        !           171:        struct hashentry        *tbl, *temp, *tbl2;
        !           172:        size = htbl.size * 2 + 1;
        !           173:        tbl = temp = multnode( hashentry, size );
        !           174:        for ( i=0; i<size; i++ ) (temp++)->symbol = 0;
        !           175:        tbl2 = htbl.table;
        !           176:        for ( i=0; i<htbl.size; i++ ) {
        !           177:                if ( tbl2->symbol == 0 || tbl2->symbol == (char *)(-1)) {
        !           178:                        tbl2++;
        !           179:                        continue;
        !           180:                }
        !           181:                mkey = (tbl2->key)%(size - 1);
        !           182:                temp = tbl;
        !           183:                temp += mkey;
        !           184:                loop {
        !           185:                        if ( temp->symbol == 0 ) {
        !           186:                                temp->key = tbl2->key;
        !           187:                                temp->symbol = tbl2->symbol;
        !           188:                                temp->value = tbl2->value;
        !           189:                                tbl2++;
        !           190:                                break;
        !           191:                        }
        !           192:                        temp++;
        !           193:                        if ( temp >= ( tbl+ size ) )  temp = tbl;
        !           194:                }
        !           195:        }
        !           196:        free( (char *)htbl.table );
        !           197:        htbl.size = size;
        !           198:        htbl.table = tbl;
        !           199: }
        !           200: 
        !           201: /*
        !           202:  *     Clean up the Hash Table
        !           203:  */
        !           204: static hashclean( )
        !           205: {
        !           206:        int     i, mkey, size, entry;
        !           207:        struct hashentry        *tbl, *temp, *tbl2;
        !           208:        size = htbl.size;
        !           209:        tbl = temp = multnode( hashentry, size );
        !           210:        for ( i=0; i<size; i++ ) (temp++)->symbol = 0;
        !           211:        entry = 0;
        !           212:        tbl2 = htbl.table;
        !           213:        for ( i=0; i<htbl.size; i++ ) {
        !           214:                if ( tbl2->symbol == 0 || tbl2->symbol == (char *)(-1)) {
        !           215:                        tbl2++;
        !           216:                        continue;
        !           217:                }
        !           218:                mkey = (tbl2->key)%(size - 1);
        !           219:                temp = tbl;
        !           220:                temp += mkey;
        !           221:                loop {
        !           222:                        if ( temp->symbol == 0 ) {
        !           223:                                temp->key = tbl2->key;
        !           224:                                temp->symbol = tbl2->symbol;
        !           225:                                temp->value = tbl2->value;
        !           226:                                tbl2++;
        !           227:                                entry++;
        !           228:                                break;
        !           229:                        }
        !           230:                        temp++;
        !           231:                        if ( temp >= ( tbl+ size ) )  temp = tbl;
        !           232:                }
        !           233:        }
        !           234:        free( (char *)htbl.table );
        !           235:        htbl.entry = entry;
        !           236:        htbl.table = tbl;
        !           237: }

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