gnu/abc-shell/table.c

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