table.c

   1 /*
   2  * dynamic hashed associative table for commands and variables
   3  */
   4
   5 #include "sh.h"
   6 #include <search.h>
   7
   8 static int tbl_compare(const void *pa, const void *pb) {
   9         return strcmp(((struct tbl *)pa)->name, ((struct tbl *)pb)->name);
  10 }
  11
  12 void
  13 transitional_tinit(struct table *tp, Area *ap)
  14 {
  15         tp->areap = ap;
  16         tp->tbls = NULL;
  17         tp->root = NULL;
  18         tp->size = tp->nfree = 0;
  19 }
  20
  21 struct tbl *
  22 transitional_tsearch(void **tbl_root, const char *n)
  23 {
  24         struct tbl *p, **q;
  25         unsigned int len;
  26
  27         len = strlen(n) + 1;
  28         p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len,
  29                                  ATEMP);
  30         memcpy(p->name, n, len);
  31
  32         q = tfind(p, (void **)tbl_root, tbl_compare);
  33
  34         return q ? *q : NULL;
  35 }
  36
  37 struct tbl *
  38 transitional_tenter(void **tbl_root, const char *n, Area *ap)
  39 {
  40         struct tbl *p, **q;
  41         unsigned int len;
  42
  43         len = strlen(n) + 1;
  44         p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len,
  45                                  ap);
  46         p->flag = 0;
  47         p->type = 0;
  48         p->areap = ap;
  49         p->u2.field = 0;
  50         p->u.array = (struct tbl *)0;
  51         memcpy(p->name, n, len);
  52
  53         q = (struct tbl **)tsearch((void *)p, (void **)tbl_root, tbl_compare);
  54
  55         return *q;
  56 }
  57
  58 void
  59 transitional_tdelete(void **tbl_root, struct tbl *p)
  60 {
  61         tdelete((void *)p, tbl_root, tbl_compare);
  62 }
  63
  64 #ifdef PERF_DEBUG /* performance debugging */
  65
  66 void tprintinfo ARGS((struct table *tp));
  67
  68 void
  69 tprintinfo(tp)
  70         struct table *tp;
  71 {
  72         struct tbl *te;
  73         char *n;
  74         unsigned int h;
  75         int ncmp;
  76         int totncmp = 0, maxncmp = 0;
  77         int nentries = 0;
  78         struct tstate ts;
  79
  80         shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
  81         shellf("    Ncmp name\n");
  82         twalk(&ts, tp);
  83         while ((te = tnext(&ts))) {
  84                 register struct tbl **pp, *p;
  85
  86                 h = hash(n = te->name);
  87                 ncmp = 0;
  88
  89                 /* taken from tsearch() and added counter */
  90                 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
  91                         ncmp++;
  92                         if (*p->name == *n && strcmp(p->name, n) == 0
  93                             && (p->flag&DEFINED))
  94                                 break; /* return p; */
  95                         if (pp == tp->tbls) /* wrap */
  96                                 pp += tp->size;
  97                 }
  98                 shellf("    %4d %s\n", ncmp, n);
  99                 totncmp += ncmp;
 100                 nentries++;
 101                 if (ncmp > maxncmp)
 102                         maxncmp = ncmp;
 103         }
 104         if (nentries)
 105                 shellf("  %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
 106                         nentries, maxncmp,
 107                         totncmp / nentries,
 108                         (totncmp % nentries) * 100 / nentries);
 109 }
 110 #endif /* PERF_DEBUG */