Return to hash.c CVS log

Up to [Research Unix] / researchv9 / cmd / strip

Annotation of researchv9/cmd/strip/hash.c, revision 1.1

1.1     ! root        1: #include "hash.h"
        !             2: 
        !             3: static struct st *curstp;
        !             4: static int nchleft;
        !             5: 
        !             6: hashinit()
        !             7: {
        !             8:        register struct ht *htp;
        !             9:        register struct st *stp;
        !            10:        for (htp = hroot; htp; htp = htp->next)
        !            11:                free(htp);
        !            12:        for (stp = sroot; stp; stp = stp->next)
        !            13:                free(stp);
        !            14:        if ((hroot = Calloc(struct ht, 1)) == 0)
        !            15:                fatal("cannot calloc struct ht", "");
        !            16:        if ((sroot = Calloc(struct st, 1)) == 0)
        !            17:                fatal("cannot calloc struct st", "");
        !            18:        stcount = 1;
        !            19:        curstp = sroot;
        !            20:        nchleft = STRTABSIZE;
        !            21: }
        !            22: 
        !            23: char *
        !            24: savestr(str)   /* Place string into permanent storage. */
        !            25: register char *str;
        !            26: {
        !            27:        char *strcpy();
        !            28:        register int len; register struct st *stp = curstp;
        !            29: 
        !            30:        if ((len = strlen(str)+1) > nchleft) {
        !            31:                int stsize = sizeof(struct st);
        !            32:                if (len > STRTABSIZE) {
        !            33:                        stsize += len-STRTABSIZE;
        !            34:                        nchleft = len;
        !            35:                } else
        !            36:                        nchleft = STRTABSIZE;
        !            37:                stp->next = (struct st *)malloc(stsize);
        !            38:                if ((curstp = stp = stp->next) == 0)
        !            39:                        fatal("malloc failed in savestr", "");
        !            40:                stp->next = 0;
        !            41:                stp->nused = 0;
        !            42:                ++stcount;
        !            43:        }
        !            44:        str = strcpy(&stp->strtab[stp->nused], str);
        !            45:        stp->nused += len; nchleft -= len;
        !            46:        return str;
        !            47: }
        !            48: 
        !            49: char *
        !            50: hash(str)      /* Lookup str in hash tables; if not found, make new entry. */
        !            51: char *str;
        !            52: {
        !            53:        register char *cp, *hstr, **hstrp;
        !            54:        register int h, i;
        !            55:        struct ht *htp;
        !            56:        int sh;
        !            57: 
        !            58:        if (*(cp = str) == '_')
        !            59:                ++cp;
        !            60:        for (h = 0; *cp; )
        !            61:                h = (h << 1) + *cp++;
        !            62:        sh = (h & 077777) % HASHSIZE;
        !            63:        cp = (char *)(*str != '_');
        !            64: 
        !            65:        /* Look through each table for name.  Use quadratic re-hash. */
        !            66:        for (htp = hroot; htp; htp = htp->next) {
        !            67:                for (h=sh, i=1; i<HASHSIZE; h += i, i += 2) {
        !            68:                        if (h >= HASHSIZE)
        !            69:                                h -= HASHSIZE;
        !            70:                        hstrp = &htp->ptable[h];
        !            71:                        if (hstr = *hstrp) {
        !            72:                                if (cp && *hstr == '_')
        !            73:                                        ++hstr;
        !            74:                                if (strcmp(hstr, str))
        !            75:                                        continue;
        !            76:                                return hstr;
        !            77:                        } else {
        !            78:                                if (htp->nused > MAXHUSE)
        !            79:                                        break;
        !            80:                                htp->nused++;
        !            81:                                return (*hstrp = savestr(str));
        !            82:                        }
        !            83:                }
        !            84:                if (htp->next == 0)
        !            85:                        htp->next = Calloc(struct ht, 1);
        !            86:        }
        !            87:        fatal("calloc failed in hash", "");
        !            88: }
        !            89: 
        !            90: prthash()
        !            91: {
        !            92:        register struct ht *htp;
        !            93:        register struct st *stp;
        !            94:        register ntot = 0;
        !            95:        for (htp = hroot; htp; htp = htp->next) {
        !            96:                printf("%s %d", (htp == hroot ? "hash usage:" : " +"),
        !            97:                    htp->nused);
        !            98:                ntot += htp->nused;
        !            99:        }
        !           100:        printf(" = %d\n", ntot);
        !           101:        ntot = 0;
        !           102:        for (stp = sroot; stp; stp = stp->next) {
        !           103:                printf("%s %d", (stp == sroot ? "string usage:" : " +"),
        !           104:                    stp->nused);
        !           105:                ntot += stp->nused;
        !           106:        }
        !           107:        printf(" = %d\n", ntot);
        !           108: }

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