diff options
Diffstat (limited to 'table.c')
| -rw-r--r-- | table.c | 247 |
1 files changed, 247 insertions, 0 deletions
@@ -0,0 +1,247 @@ +/* $NetBSD: table.c,v 1.8 2018/06/03 12:18:29 kamil Exp $ */ + +/* + * dynamic hashed associative table for commands and variables + */ +#include <sys/cdefs.h> + +#ifndef lint +__RCSID("$NetBSD: table.c,v 1.8 2018/06/03 12:18:29 kamil Exp $"); +#endif + + +#include "sh.h" + +#define INIT_TBLS 8 /* initial table size (power of 2) */ + +static void texpand ARGS((struct table *tp, int nsize)); +static int tnamecmp ARGS((void *p1, void *p2)); + + +unsigned int +hash(n) + const char * n; +{ + unsigned int h = 0; + + while (*n != '\0') + h = 2*h + *n++; + return h * 32821; /* scatter bits */ +} + +void +tinit(tp, ap, tsize) + struct table *tp; + Area *ap; + int tsize; +{ + tp->areap = ap; + tp->tbls = NULL; + tp->size = tp->nfree = 0; + if (tsize) + texpand(tp, tsize); +} + +static void +texpand(tp, nsize) + struct table *tp; + int nsize; +{ + int i; + struct tbl *tblp, **p; + struct tbl **ntblp, **otblp = tp->tbls; + int osize = tp->size; + + ntblp = (struct tbl**) alloc(sizeofN(struct tbl *, nsize), tp->areap); + for (i = 0; i < nsize; i++) + ntblp[i] = NULL; + tp->size = nsize; + tp->nfree = 8*nsize/10; /* table can get 80% full */ + tp->tbls = ntblp; + if (otblp == NULL) + return; + for (i = 0; i < osize; i++) { + if ((tblp = otblp[i]) != NULL) { + if ((tblp->flag&DEFINED)) { + for (p = &ntblp[hash(tblp->name) + & (tp->size-1)]; + *p != NULL; p--) + if (p == ntblp) /* wrap */ + p += tp->size; + *p = tblp; + tp->nfree--; + } else if (!(tblp->flag & FINUSE)) { + afree((void*)tblp, tp->areap); + } + } + } + afree((void*)otblp, tp->areap); +} + +struct tbl * +mytsearch(tp, n, h) + struct table *tp; /* table */ + const char *n; /* name to enter */ + unsigned int h; /* hash(n) */ +{ + struct tbl **pp, *p; + + if (tp->size == 0) + return NULL; + + /* search for name in hashed table */ + for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) { + if (*p->name == *n && strcmp(p->name, n) == 0 + && (p->flag&DEFINED)) + return p; + if (pp == tp->tbls) /* wrap */ + pp += tp->size; + } + + return NULL; +} + +struct tbl * +tenter(tp, n, h) + struct table *tp; /* table */ + const char *n; /* name to enter */ + unsigned int h; /* hash(n) */ +{ + struct tbl **pp, *p; + int len; + + if (tp->size == 0) + texpand(tp, INIT_TBLS); + Search: + /* search for name in hashed table */ + for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) { + if (*p->name == *n && strcmp(p->name, n) == 0) + return p; /* found */ + if (pp == tp->tbls) /* wrap */ + pp += tp->size; + } + + if (tp->nfree <= 0) { /* too full */ + texpand(tp, 2*tp->size); + goto Search; + } + + /* create new tbl entry */ + len = strlen(n) + 1; + p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len, + tp->areap); + p->flag = 0; + p->type = 0; + p->areap = tp->areap; + p->u2.field = 0; + p->u.array = (struct tbl *)0; + memcpy(p->name, n, len); + + /* enter in tp->tbls */ + tp->nfree--; + *pp = p; + return p; +} + +void +mytdelete(p) + struct tbl *p; +{ + p->flag = 0; +} + +void +ksh_twalk(ts, tp) + struct tstate *ts; + struct table *tp; +{ + ts->left = tp->size; + ts->next = tp->tbls; +} + +struct tbl * +tnext(ts) + struct tstate *ts; +{ + while (--ts->left >= 0) { + struct tbl *p = *ts->next++; + if (p != NULL && (p->flag&DEFINED)) + return p; + } + return NULL; +} + +static int +tnamecmp(p1, p2) + void *p1, *p2; +{ + return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name); +} + +struct tbl ** +tsort(tp) + struct table *tp; +{ + int i; + struct tbl **p, **sp, **dp; + + p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP); + sp = tp->tbls; /* source */ + dp = p; /* dest */ + for (i = 0; i < tp->size; i++) + if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) || + ((*dp)->flag&ARRAY))) + dp++; + i = dp - p; + qsortp((void**)p, (size_t)i, tnamecmp); + p[i] = NULL; + return p; +} + +#ifdef PERF_DEBUG /* performance debugging */ + +void tprintinfo ARGS((struct table *tp)); + +void +tprintinfo(tp) + struct table *tp; +{ + struct tbl *te; + char *n; + unsigned int h; + int ncmp; + int totncmp = 0, maxncmp = 0; + int nentries = 0; + struct tstate ts; + + shellf("table size %d, nfree %d\n", tp->size, tp->nfree); + shellf(" Ncmp name\n"); + ksh_twalk(&ts, tp); + while ((te = tnext(&ts))) { + struct tbl **pp, *p; + + h = hash(n = te->name); + ncmp = 0; + + /* taken from mytsearch() and added counter */ + for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) { + ncmp++; + if (*p->name == *n && strcmp(p->name, n) == 0 + && (p->flag&DEFINED)) + break; /* return p; */ + if (pp == tp->tbls) /* wrap */ + pp += tp->size; + } + shellf(" %4d %s\n", ncmp, n); + totncmp += ncmp; + nentries++; + if (ncmp > maxncmp) + maxncmp = ncmp; + } + if (nentries) + shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n", + nentries, maxncmp, + totncmp / nentries, + (totncmp % nentries) * 100 / nentries); +} +#endif /* PERF_DEBUG */ |