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 */ 248