Return to table.c CVS log

Up to [MW Coherent from dump] / coherent / a / usr / bob / korn

Annotation of coherent/a/usr/bob/korn/table.c, revision 1.1

1.1     ! root        1: static char *RCSid = "$Header: table.c,v 3.1 88/11/03 09:17:53 egisin Exp $";
        !             2: 
        !             3: /*
        !             4:  * dynamic hashed associative table for commands and variables
        !             5:  */
        !             6: 
        !             7: #include <stddef.h>
        !             8: #include <stdlib.h>
        !             9: #include <errno.h>
        !            10: #include <setjmp.h>
        !            11: #include "sh.h"
        !            12: #include "table.h"
        !            13: 
        !            14: #define        INIT_TBLS       8       /* initial table size (power of 2) */
        !            15: 
        !            16: static struct tstate {
        !            17:        int left;
        !            18:        struct tbl **next;
        !            19: } tstate;
        !            20: 
        !            21: static void texpand();
        !            22: 
        !            23: unsigned int
        !            24: hash(n)
        !            25:        register char * n;
        !            26: {
        !            27:        register unsigned int h = 0;
        !            28: 
        !            29:        while (*n != '\0')
        !            30:                h = 2*h + *n++;
        !            31:        return h * (unsigned)32821L;    /* scatter bits */
        !            32: }
        !            33: 
        !            34: #if 0
        !            35: phash(s) char *s; {
        !            36:        printf("%2d: %s\n", hash(s)%32, s);
        !            37: }
        !            38: #endif
        !            39: 
        !            40: void
        !            41: tinit(tp, ap)
        !            42:        register struct table *tp;
        !            43:        register Area *ap;
        !            44: {
        !            45:        tp->areap = ap;
        !            46:        tp->size = tp->free = 0;
        !            47:        tp->tbls = NULL;
        !            48: }
        !            49: 
        !            50: static void
        !            51: texpand(tp, nsize)
        !            52:        register struct table *tp;
        !            53:        int nsize;
        !            54: {
        !            55:        register int i;
        !            56:        register struct tbl *tblp, **p;
        !            57:        register struct tbl **ntblp, **otblp = tp->tbls;
        !            58:        int osize = tp->size;
        !            59: 
        !            60:        ntblp = alloc(sizeofN(struct tbl *, nsize), tp->areap);
        !            61:        for (i = 0; i < nsize; i++)
        !            62:                ntblp[i] = NULL;
        !            63:        tp->size = nsize;
        !            64:        tp->free = 8*nsize/10;  /* table can get 80% full */
        !            65:        tp->tbls = ntblp;
        !            66:        if (otblp == NULL)
        !            67:                return;
        !            68:        for (i = 0; i < osize; i++)
        !            69:                if ((tblp = otblp[i]) != NULL)
        !            70:                        if ((tblp->flag&DEFINED)) {
        !            71:                                for (p = &ntblp[hash(tblp->name) & tp->size-1];
        !            72:                                     *p != NULL; p--)
        !            73:                                        if (p == ntblp) /* wrap */
        !            74:                                                p += tp->size;
        !            75:                                *p = tblp;
        !            76:                                tp->free--;
        !            77:                        } else {
        !            78:                                afree((Void*)tblp, tp->areap);
        !            79:                        }
        !            80:        afree((Void*)otblp, tp->areap);
        !            81: }
        !            82: 
        !            83: struct tbl *
        !            84: tsearch(tp, n, h)
        !            85:        register struct table *tp;      /* table */
        !            86:        register char *n;               /* name to enter */
        !            87:        unsigned int h;                 /* hash(n) */
        !            88: {
        !            89:        register struct tbl **pp, *p;
        !            90: 
        !            91:        if (tp->size == 0)
        !            92:                return NULL;
        !            93: 
        !            94:        /* search for name in hashed table */
        !            95:        for (pp = &tp->tbls[h & tp->size-1]; (p = *pp) != NULL; pp--) {
        !            96:                if (*p->name == *n && strcmp(p->name, n) == 0
        !            97:                    && (p->flag&DEFINED))
        !            98:                        return p;
        !            99:                if (pp == tp->tbls) /* wrap */
        !           100:                        pp += tp->size;
        !           101:        }
        !           102: 
        !           103:        return NULL;
        !           104: }
        !           105: 
        !           106: struct tbl *
        !           107: tenter(tp, n, h)
        !           108:        register struct table *tp;      /* table */
        !           109:        register char *n;               /* name to enter */
        !           110:        unsigned int h;                 /* hash(n) */
        !           111: {
        !           112:        register struct tbl **pp, *p;
        !           113:        register char *cp;
        !           114: 
        !           115:        if (tp->size == 0)
        !           116:                texpand(tp, INIT_TBLS);
        !           117:   Search:
        !           118:        /* search for name in hashed table */
        !           119:        for (pp = &tp->tbls[h & tp->size-1]; (p = *pp) != NULL; pp--) {
        !           120:                if (*p->name == *n && strcmp(p->name, n) == 0)
        !           121:                        return p;       /* found */
        !           122:                if (pp == tp->tbls) /* wrap */
        !           123:                        pp += tp->size;
        !           124:        }
        !           125: 
        !           126:        if (tp->free <= 0) {    /* too full */
        !           127:                texpand(tp, 2*tp->size);
        !           128:                goto Search;
        !           129:        }
        !           130: 
        !           131:        /* create new tbl entry */
        !           132:        for (cp = n; *cp != '\0'; cp++)
        !           133:                ;
        !           134:        p = (struct tbl *) alloc(offsetof(struct tbl, name[(cp-n)+1]), tp->areap);
        !           135:        p->flag = 0;
        !           136:        p->type = 0;
        !           137:        for (cp = p->name; *n != '\0';)
        !           138:                *cp++ = *n++;
        !           139:        *cp = '\0';
        !           140: 
        !           141:        /* enter in tp->tbls */
        !           142:        tp->free--;
        !           143:        *pp = p;
        !           144:        return p;
        !           145: }
        !           146: 
        !           147: void
        !           148: tdelete(p)
        !           149:        register struct tbl *p;
        !           150: {
        !           151:        p->flag = 0;
        !           152: }
        !           153: 
        !           154: void
        !           155: twalk(tp)
        !           156:        register struct table *tp;
        !           157: {
        !           158:        tstate.left = tp->size;
        !           159:        tstate.next = tp->tbls;
        !           160: }
        !           161: 
        !           162: struct tbl *
        !           163: tnext()
        !           164: {
        !           165:        while (--tstate.left >= 0) {
        !           166:                struct tbl *p = *tstate.next++;
        !           167:                if (p != NULL && (p->flag&DEFINED))
        !           168:                        return p;
        !           169:        }
        !           170:        return NULL;
        !           171: }
        !           172: 
        !           173: static int
        !           174: tnamecmp(p1, p2)
        !           175:        Void *p1, *p2;
        !           176: {
        !           177:        return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name);
        !           178: }
        !           179: 
        !           180: struct tbl **
        !           181: tsort(tp)
        !           182:        register struct table *tp;
        !           183: {
        !           184:        register int i;
        !           185:        register struct tbl **p, **sp, **dp;
        !           186: 
        !           187:        p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP);
        !           188:        sp = tp->tbls;          /* source */
        !           189:        dp = p;                 /* dest */
        !           190:        for (i = 0; i < tp->size; i++)
        !           191:                if ((*dp = *sp++) != NULL && ((*dp)->flag&DEFINED))
        !           192:                        dp++;
        !           193:        i = dp - p;
        !           194:        qsortp((Void**)p, (size_t)i, tnamecmp);
        !           195:        p[i] = NULL;
        !           196:        return p;
        !           197: }
        !           198: 

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