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