1 /* $NetBSD: table.c,v 1.2 1997/01/12 19:12:20 tls 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 afree((void*)otblp, tp->areap); 71 } 72 73 struct tbl * 74 tsearch(tp, n, h) 75 register struct table *tp; /* table */ 76 register const char *n; /* name to enter */ 77 unsigned int h; /* hash(n) */ 78 { 79 register struct tbl **pp, *p; 80 81 if (tp->size == 0) 82 return NULL; 83 84 /* search for name in hashed table */ 85 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) { 86 if (*p->name == *n && strcmp(p->name, n) == 0 87 && (p->flag&DEFINED)) 88 return p; 89 if (pp == tp->tbls) /* wrap */ 90 pp += tp->size; 91 } 92 93 return NULL; 94 } 95 96 struct tbl * 97 tenter(tp, n, h) 98 register struct table *tp; /* table */ 99 register const char *n; /* name to enter */ 100 unsigned int h; /* hash(n) */ 101 { 102 register struct tbl **pp, *p; 103 register int len; 104 105 if (tp->size == 0) 106 texpand(tp, INIT_TBLS); 107 Search: 108 /* search for name in hashed table */ 109 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) { 110 if (*p->name == *n && strcmp(p->name, n) == 0) 111 return p; /* found */ 112 if (pp == tp->tbls) /* wrap */ 113 pp += tp->size; 114 } 115 116 if (tp->nfree <= 0) { /* too full */ 117 texpand(tp, 2*tp->size); 118 goto Search; 119 } 120 121 /* create new tbl entry */ 122 len = strlen(n) + 1; 123 p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len, 124 tp->areap); 125 p->flag = 0; 126 p->type = 0; 127 p->areap = tp->areap; 128 p->u2.field = 0; 129 p->u.array = (struct tbl *)0; 130 memcpy(p->name, n, len); 131 132 /* enter in tp->tbls */ 133 tp->nfree--; 134 *pp = p; 135 return p; 136 } 137 138 void 139 tdelete(p) 140 register struct tbl *p; 141 { 142 p->flag = 0; 143 } 144 145 void 146 twalk(ts, tp) 147 struct tstate *ts; 148 struct table *tp; 149 { 150 ts->left = tp->size; 151 ts->next = tp->tbls; 152 } 153 154 struct tbl * 155 tnext(ts) 156 struct tstate *ts; 157 { 158 while (--ts->left >= 0) { 159 struct tbl *p = *ts->next++; 160 if (p != NULL && (p->flag&DEFINED)) 161 return p; 162 } 163 return NULL; 164 } 165 166 static int 167 tnamecmp(p1, p2) 168 void *p1, *p2; 169 { 170 return strcmp(((struct tbl *)p1)->name, ((struct tbl *)p2)->name); 171 } 172 173 struct tbl ** 174 tsort(tp) 175 register struct table *tp; 176 { 177 register int i; 178 register struct tbl **p, **sp, **dp; 179 180 p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP); 181 sp = tp->tbls; /* source */ 182 dp = p; /* dest */ 183 for (i = 0; i < tp->size; i++) 184 if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) || 185 ((*dp)->flag&ARRAY))) 186 dp++; 187 i = dp - p; 188 qsortp((void**)p, (size_t)i, tnamecmp); 189 p[i] = NULL; 190 return p; 191 } 192 193 #ifdef PERF_DEBUG /* performance debugging */ 194 195 void tprintinfo ARGS((struct table *tp)); 196 197 void 198 tprintinfo(tp) 199 struct table *tp; 200 { 201 struct tbl *te; 202 char *n; 203 unsigned int h; 204 int ncmp; 205 int totncmp = 0, maxncmp = 0; 206 int nentries = 0; 207 struct tstate ts; 208 209 shellf("table size %d, nfree %d\n", tp->size, tp->nfree); 210 shellf(" Ncmp name\n"); 211 twalk(&ts, tp); 212 while ((te = tnext(&ts))) { 213 register struct tbl **pp, *p; 214 215 h = hash(n = te->name); 216 ncmp = 0; 217 218 /* taken from tsearch() and added counter */ 219 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) { 220 ncmp++; 221 if (*p->name == *n && strcmp(p->name, n) == 0 222 && (p->flag&DEFINED)) 223 break; /* return p; */ 224 if (pp == tp->tbls) /* wrap */ 225 pp += tp->size; 226 } 227 shellf(" %4d %s\n", ncmp, n); 228 totncmp += ncmp; 229 nentries++; 230 if (ncmp > maxncmp) 231 maxncmp = ncmp; 232 } 233 if (nentries) 234 shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n", 235 nentries, maxncmp, 236 totncmp / nentries, 237 (totncmp % nentries) * 100 / nentries); 238 } 239 #endif /* PERF_DEBUG */ 240