1 /* $OpenBSD: table.c,v 1.15 2012/02/19 07:52:30 otto 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 = 33*h + (unsigned char)(*n++); 22 return h; 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 = 7*nsize/10; /* table can get 70% 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 if (tp->size <= INT_MAX/2) 112 texpand(tp, 2*tp->size); 113 else 114 internal_errorf(1, "too many vars"); 115 goto Search; 116 } 117 118 /* create new tbl entry */ 119 len = strlen(n) + 1; 120 p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len, 121 tp->areap); 122 p->flag = 0; 123 p->type = 0; 124 p->areap = tp->areap; 125 p->u2.field = 0; 126 p->u.array = (struct tbl *)0; 127 memcpy(p->name, n, len); 128 129 /* enter in tp->tbls */ 130 tp->nfree--; 131 *pp = p; 132 return p; 133 } 134 135 void 136 ktdelete(struct tbl *p) 137 { 138 p->flag = 0; 139 } 140 141 void 142 ktwalk(struct tstate *ts, struct table *tp) 143 { 144 ts->left = tp->size; 145 ts->next = tp->tbls; 146 } 147 148 struct tbl * 149 ktnext(struct tstate *ts) 150 { 151 while (--ts->left >= 0) { 152 struct tbl *p = *ts->next++; 153 if (p != NULL && (p->flag&DEFINED)) 154 return p; 155 } 156 return NULL; 157 } 158 159 static int 160 tnamecmp(const void *p1, const void *p2) 161 { 162 char *name1 = (*(struct tbl **)p1)->name; 163 char *name2 = (*(struct tbl **)p2)->name; 164 return strcmp(name1, name2); 165 } 166 167 struct tbl ** 168 ktsort(struct table *tp) 169 { 170 int i; 171 struct tbl **p, **sp, **dp; 172 173 p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP); 174 sp = tp->tbls; /* source */ 175 dp = p; /* dest */ 176 for (i = 0; i < tp->size; i++) 177 if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) || 178 ((*dp)->flag&ARRAY))) 179 dp++; 180 i = dp - p; 181 qsortp((void**)p, (size_t)i, tnamecmp); 182 p[i] = NULL; 183 return p; 184 } 185 186 #ifdef PERF_DEBUG /* performance debugging */ 187 188 void tprintinfo(struct table *tp); 189 190 void 191 tprintinfo(struct table *tp) 192 { 193 struct tbl *te; 194 char *n; 195 unsigned int h; 196 int ncmp; 197 int totncmp = 0, maxncmp = 0; 198 int nentries = 0; 199 struct tstate ts; 200 201 shellf("table size %d, nfree %d\n", tp->size, tp->nfree); 202 shellf(" Ncmp name\n"); 203 ktwalk(&ts, tp); 204 while ((te = ktnext(&ts))) { 205 struct tbl **pp, *p; 206 207 h = hash(n = te->name); 208 ncmp = 0; 209 210 /* taken from ktsearch() and added counter */ 211 for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) { 212 ncmp++; 213 if (*p->name == *n && strcmp(p->name, n) == 0 && 214 (p->flag&DEFINED)) 215 break; /* return p; */ 216 if (pp == tp->tbls) /* wrap */ 217 pp += tp->size; 218 } 219 shellf(" %4d %s\n", ncmp, n); 220 totncmp += ncmp; 221 nentries++; 222 if (ncmp > maxncmp) 223 maxncmp = ncmp; 224 } 225 if (nentries) 226 shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n", 227 nentries, maxncmp, 228 totncmp / nentries, 229 (totncmp % nentries) * 100 / nentries); 230 } 231 #endif /* PERF_DEBUG */ 232