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 15struct table taliases; /* tracked aliases */ 16struct table builtins; /* built-in commands */ 17struct table aliases; /* aliases */ 18struct table keywords; /* keywords */ 19struct table homedirs; /* homedir() cache */ 20 21char *search_path; /* copy of either PATH or def_path */ 22const char *def_path; /* path to use if PATH not set */ 23char *tmpdir; /* TMPDIR value */ 24const char *prompt; 25int cur_prompt; /* PS1 or PS2 */ 26int current_lineno; /* LINENO value */ 27 28static void texpand(struct table *, int); 29static int tnamecmp(const void *, const void *); 30 31 32unsigned int 33hash(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 42void 43ktinit(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 52static void 53texpand(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) */ 87struct tbl * 88ktsearch(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) */ 110struct tbl * 111ktenter(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 152void 153ktdelete(struct tbl *p) 154{ 155 p->flag = 0; 156} 157 158void 159ktwalk(struct tstate *ts, struct table *tp) 160{ 161 ts->left = tp->size; 162 ts->next = tp->tbls; 163} 164 165struct tbl * 166ktnext(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 176static int 177tnamecmp(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 184struct tbl ** 185ktsort(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 206void tprintinfo(struct table *tp); 207 208void 209tprintinfo(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