bin/ksh/table.c

   1 /*      $OpenBSD: table.c,v 1.25 2018/01/16 22:52:32 jca Exp $  */
   2
   3 /*
   4  * dynamic hashed associative table for commands and variables
   5  */
   6
   7 #include <limits.h>
   8 #include <stddef.h>
   9 #include <string.h>
  10
  11 #include "sh.h"
  12
  13 #define INIT_TBLS       8       /* initial table size (power of 2) */
  14
  15 struct table taliases;  /* tracked aliases */
  16 struct table builtins;  /* built-in commands */
  17 struct table aliases;   /* aliases */
  18 struct table keywords;  /* keywords */
  19 struct table homedirs;  /* homedir() cache */
  20
  21 char *search_path;      /* copy of either PATH or def_path */
  22 const char *def_path;   /* path to use if PATH not set */
  23 char *tmpdir;           /* TMPDIR value */
  24 const char *prompt;
  25 int cur_prompt;         /* PS1 or PS2 */
  26 int current_lineno;     /* LINENO value */
  27
  28 static void     texpand(struct table *, int);
  29 static int      tnamecmp(const void *, const void *);
  30
  31
  32 unsigned int
  33 hash(const char *n)
  34 {
  35         unsigned int h = 0;
  36
  37         while (*n != '\0')
  38                 h = 33*h + (unsigned char)(*n++);
  39         return h;
  40 }
  41
  42 void
  43 ktinit(struct table *tp, Area *ap, int tsize)
  44 {
  45         tp->areap = ap;
  46         tp->tbls = NULL;
  47         tp->size = tp->nfree = 0;
  48         if (tsize)
  49                 texpand(tp, tsize);
  50 }
  51
  52 static void
  53 texpand(struct table *tp, int nsize)
  54 {
  55         int i;
  56         struct tbl *tblp, **p;
  57         struct tbl **ntblp, **otblp = tp->tbls;
  58         int osize = tp->size;
  59
  60         ntblp = areallocarray(NULL, nsize, sizeof(struct tbl *), tp->areap);
  61         for (i = 0; i < nsize; i++)
  62                 ntblp[i] = NULL;
  63         tp->size = nsize;
  64         tp->nfree = 7*nsize/10; /* table can get 70% 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) &
  72                                     (tp->size-1)]; *p != NULL; p--)
  73                                         if (p == ntblp) /* wrap */
  74                                                 p += tp->size;
  75                                 *p = tblp;
  76                                 tp->nfree--;
  77                         } else if (!(tblp->flag & FINUSE)) {
  78                                 afree(tblp, tp->areap);
  79                         }
  80                 }
  81         afree(otblp, tp->areap);
  82 }
  83
  84 /* table */
  85 /* name to enter */
  86 /* hash(n) */
  87 struct tbl *
  88 ktsearch(struct table *tp, const char *n, unsigned int h)
  89 {
  90         struct tbl **pp, *p;
  91
  92         if (tp->size == 0)
  93                 return NULL;
  94
  95         /* search for name in hashed table */
  96         for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
  97                 if (*p->name == *n && strcmp(p->name, n) == 0 &&
  98                     (p->flag&DEFINED))
  99                         return p;
 100                 if (pp == tp->tbls) /* wrap */
 101                         pp += tp->size;
 102         }
 103
 104         return NULL;
 105 }
 106
 107 /* table */
 108 /* name to enter */
 109 /* hash(n) */
 110 struct tbl *
 111 ktenter(struct table *tp, const char *n, unsigned int h)
 112 {
 113         struct tbl **pp, *p;
 114         int len;
 115
 116         if (tp->size == 0)
 117                 texpand(tp, INIT_TBLS);
 118   Search:
 119         /* search for name in hashed table */
 120         for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
 121                 if (*p->name == *n && strcmp(p->name, n) == 0)
 122                         return p;       /* found */
 123                 if (pp == tp->tbls) /* wrap */
 124                         pp += tp->size;
 125         }
 126
 127         if (tp->nfree <= 0) {   /* too full */
 128                 if (tp->size <= INT_MAX/2)
 129                         texpand(tp, 2*tp->size);
 130                 else
 131                         internal_errorf("too many vars");
 132                 goto Search;
 133         }
 134
 135         /* create new tbl entry */
 136         len = strlen(n) + 1;
 137         p = alloc(offsetof(struct tbl, name[0]) + len,
 138                                  tp->areap);
 139         p->flag = 0;
 140         p->type = 0;
 141         p->areap = tp->areap;
 142         p->u2.field = 0;
 143         p->u.array = NULL;
 144         memcpy(p->name, n, len);
 145
 146         /* enter in tp->tbls */
 147         tp->nfree--;
 148         *pp = p;
 149         return p;
 150 }
 151
 152 void
 153 ktdelete(struct tbl *p)
 154 {
 155         p->flag = 0;
 156 }
 157
 158 void
 159 ktwalk(struct tstate *ts, struct table *tp)
 160 {
 161         ts->left = tp->size;
 162         ts->next = tp->tbls;
 163 }
 164
 165 struct tbl *
 166 ktnext(struct tstate *ts)
 167 {
 168         while (--ts->left >= 0) {
 169                 struct tbl *p = *ts->next++;
 170                 if (p != NULL && (p->flag&DEFINED))
 171                         return p;
 172         }
 173         return NULL;
 174 }
 175
 176 static int
 177 tnamecmp(const void *p1, const void *p2)
 178 {
 179         char *name1 = (*(struct tbl **)p1)->name;
 180         char *name2 = (*(struct tbl **)p2)->name;
 181         return strcmp(name1, name2);
 182 }
 183
 184 struct tbl **
 185 ktsort(struct table *tp)
 186 {
 187         int i;
 188         struct tbl **p, **sp, **dp;
 189
 190         p = areallocarray(NULL, tp->size + 1,
 191             sizeof(struct tbl *), ATEMP);
 192         sp = tp->tbls;          /* source */
 193         dp = p;                 /* dest */
 194         for (i = 0; i < tp->size; i++)
 195                 if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
 196                     ((*dp)->flag&ARRAY)))
 197                         dp++;
 198         i = dp - p;
 199         qsortp((void**)p, (size_t)i, tnamecmp);
 200         p[i] = NULL;
 201         return p;
 202 }
 203
 204 #ifdef PERF_DEBUG /* performance debugging */
 205
 206 void tprintinfo(struct table *tp);
 207
 208 void
 209 tprintinfo(struct table *tp)
 210 {
 211         struct tbl *te;
 212         char *n;
 213         unsigned int h;
 214         int ncmp;
 215         int totncmp = 0, maxncmp = 0;
 216         int nentries = 0;
 217         struct tstate ts;
 218
 219         shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
 220         shellf("    Ncmp name\n");
 221         ktwalk(&ts, tp);
 222         while ((te = ktnext(&ts))) {
 223                 struct tbl **pp, *p;
 224
 225                 h = hash(n = te->name);
 226                 ncmp = 0;
 227
 228                 /* taken from ktsearch() and added counter */
 229                 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
 230                         ncmp++;
 231                         if (*p->name == *n && strcmp(p->name, n) == 0 &&
 232                             (p->flag&DEFINED))
 233                                 break; /* return p; */
 234                         if (pp == tp->tbls) /* wrap */
 235                                 pp += tp->size;
 236                 }
 237                 shellf("    %4d %s\n", ncmp, n);
 238                 totncmp += ncmp;
 239                 nentries++;
 240                 if (ncmp > maxncmp)
 241                         maxncmp = ncmp;
 242         }
 243         if (nentries)
 244                 shellf("  %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
 245                     nentries, maxncmp,
 246                     totncmp / nentries,
 247                     (totncmp % nentries) * 100 / nentries);
 248 }
 249 #endif /* PERF_DEBUG */