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