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