bin/ksh/table.c

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