aboutsummaryrefslogtreecommitdiff
path: root/bin/ksh/table.c
diff options
context:
space:
mode:
Diffstat (limited to 'bin/ksh/table.c')
-rw-r--r--bin/ksh/table.c249
1 files changed, 249 insertions, 0 deletions
diff --git a/bin/ksh/table.c b/bin/ksh/table.c
new file mode 100644
index 0000000..074fc13
--- /dev/null
+++ b/bin/ksh/table.c
@@ -0,0 +1,249 @@
+/* $OpenBSD: table.c,v 1.23 2015/11/01 15:38:53 mmcc Exp $ */
+
+/*
+ * dynamic hashed associative table for commands and variables
+ */
+
+#include <limits.h>
+#include <stddef.h>
+#include <string.h>
+
+#include "sh.h"
+
+#define INIT_TBLS 8 /* initial table size (power of 2) */
+
+struct table taliases; /* tracked aliases */
+struct table builtins; /* built-in commands */
+struct table aliases; /* aliases */
+struct table keywords; /* keywords */
+struct table homedirs; /* homedir() cache */
+
+char *path; /* copy of either PATH or def_path */
+const char *def_path; /* path to use if PATH not set */
+char *tmpdir; /* TMPDIR value */
+const char *prompt;
+int cur_prompt; /* PS1 or PS2 */
+int current_lineno; /* LINENO value */
+
+static void texpand(struct table *, int);
+static int tnamecmp(const void *, const void *);
+
+
+unsigned int
+hash(const char *n)
+{
+ unsigned int h = 0;
+
+ while (*n != '\0')
+ h = 33*h + (unsigned char)(*n++);
+ return h;
+}
+
+void
+ktinit(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(struct table *tp, int nsize)
+{
+ int i;
+ struct tbl *tblp, **p;
+ struct tbl **ntblp, **otblp = tp->tbls;
+ int osize = tp->size;
+
+ ntblp = areallocarray(NULL, nsize, sizeof(struct tbl *), tp->areap);
+ for (i = 0; i < nsize; i++)
+ ntblp[i] = NULL;
+ tp->size = nsize;
+ tp->nfree = 7*nsize/10; /* table can get 70% 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(tblp, tp->areap);
+ }
+ }
+ afree(otblp, tp->areap);
+}
+
+/* table */
+/* name to enter */
+/* hash(n) */
+struct tbl *
+ktsearch(struct table *tp, const char *n, unsigned int h)
+{
+ 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;
+}
+
+/* table */
+/* name to enter */
+/* hash(n) */
+struct tbl *
+ktenter(struct table *tp, const char *n, unsigned int h)
+{
+ 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 */
+ if (tp->size <= INT_MAX/2)
+ texpand(tp, 2*tp->size);
+ else
+ internal_errorf(1, "too many vars");
+ goto Search;
+ }
+
+ /* create new tbl entry */
+ len = strlen(n) + 1;
+ p = 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 = NULL;
+ memcpy(p->name, n, len);
+
+ /* enter in tp->tbls */
+ tp->nfree--;
+ *pp = p;
+ return p;
+}
+
+void
+ktdelete(struct tbl *p)
+{
+ p->flag = 0;
+}
+
+void
+ktwalk(struct tstate *ts, struct table *tp)
+{
+ ts->left = tp->size;
+ ts->next = tp->tbls;
+}
+
+struct tbl *
+ktnext(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(const void *p1, const void *p2)
+{
+ char *name1 = (*(struct tbl **)p1)->name;
+ char *name2 = (*(struct tbl **)p2)->name;
+ return strcmp(name1, name2);
+}
+
+struct tbl **
+ktsort(struct table *tp)
+{
+ int i;
+ struct tbl **p, **sp, **dp;
+
+ p = areallocarray(NULL, tp->size + 1,
+ sizeof(struct tbl *), 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(struct table *tp);
+
+void
+tprintinfo(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");
+ ktwalk(&ts, tp);
+ while ((te = ktnext(&ts))) {
+ struct tbl **pp, *p;
+
+ h = hash(n = te->name);
+ ncmp = 0;
+
+ /* taken from ktsearch() 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 */