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