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