bin/ksh/table.c

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