hash.c (7898B)
1 /* hash.c: hash table support for functions and variables. */ 2 3 /* 4 Functions and variables are cached in both internal and external 5 form for performance. Thus a variable which is never "dereferenced" 6 with a $ is passed on to rc's children untouched. This is not so 7 important for variables, but is a big win for functions, where a call 8 to yyparse() is involved. 9 */ 10 11 #include "rc.h" 12 #include "sigmsgs.h" 13 14 static bool var_exportable(char *); 15 static bool fn_exportable(char *); 16 static int hash(char *, int); 17 static int find(char *, Htab *, int); 18 static void free_fn(rc_Function *); 19 20 Htab *fp; 21 Htab *vp; 22 static int fused, fsize, vused, vsize; 23 static char **env; 24 static int bozosize; 25 static int envsize; 26 static bool env_dirty = TRUE; 27 static char *dead = ""; 28 29 #define HASHSIZE 64 /* rc was debugged with HASHSIZE == 2; 64 is about right for normal use */ 30 31 extern void inithash() { 32 Htab *fpp, *vpp; 33 int i; 34 fp = ealloc(sizeof(Htab) * HASHSIZE); 35 vp = ealloc(sizeof(Htab) * HASHSIZE); 36 fused = vused = 0; 37 fsize = vsize = HASHSIZE; 38 for (vpp = vp, fpp = fp, i = 0; i < HASHSIZE; i++, vpp++, fpp++) 39 vpp->name = fpp->name = NULL; 40 } 41 42 #define ADV() {if ((c = *s++) == '\0') break;} 43 44 /* hash function courtesy of paul haahr */ 45 46 static int hash(char *s, int size) { 47 int c, n = 0; 48 while (1) { 49 ADV(); 50 n += (c << 17) ^ (c << 11) ^ (c << 5) ^ (c >> 1); 51 ADV(); 52 n ^= (c << 14) + (c << 7) + (c << 4) + c; 53 ADV(); 54 n ^= (~c << 11) | ((c << 3) ^ (c >> 1)); 55 ADV(); 56 n -= (c << 16) | (c << 9) | (c << 2) | (c & 3); 57 } 58 if (n < 0) 59 n = ~n; 60 return n & (size - 1); /* need power of 2 size */ 61 } 62 63 static bool rehash(Htab *ht) { 64 int i, j, size; 65 int newsize, newused; 66 Htab *newhtab; 67 if (ht == fp) { 68 if (fsize > 2 * fused) 69 return FALSE; 70 size = fsize; 71 } else { 72 if (vsize > 2 * vused) 73 return FALSE; 74 size = vsize; 75 } 76 newsize = 2 * size; 77 newhtab = ealloc(newsize * sizeof(Htab)); 78 for (i = 0; i < newsize; i++) 79 newhtab[i].name = NULL; 80 for (i = newused = 0; i < size; i++) 81 if (ht[i].name != NULL && ht[i].name != dead) { 82 newused++; 83 j = hash(ht[i].name, newsize); 84 while (newhtab[j].name != NULL) { 85 j++; 86 j &= (newsize - 1); 87 } 88 newhtab[j].name = ht[i].name; 89 newhtab[j].p = ht[i].p; 90 } 91 if (ht == fp) { 92 fused = newused; 93 fp = newhtab; 94 fsize = newsize; 95 } else { 96 vused = newused; 97 vp = newhtab; 98 vsize = newsize; 99 } 100 efree(ht); 101 return TRUE; 102 } 103 104 #define varfind(s) find(s, vp, vsize) 105 #define fnfind(s) find(s, fp, fsize) 106 107 static int find(char *s, Htab *ht, int size) { 108 int h = hash(s, size); 109 while (ht[h].name != NULL && !streq(ht[h].name, s)) { 110 h++; 111 h &= size - 1; 112 } 113 return h; 114 } 115 116 extern void *lookup(char *s, Htab *ht) { 117 int h = find(s, ht, ht == fp ? fsize : vsize); 118 return (ht[h].name == NULL) ? NULL : ht[h].p; 119 } 120 121 extern rc_Function *get_fn_place(char *s) { 122 int h = fnfind(s); 123 env_dirty = TRUE; 124 if (fp[h].name == NULL) { 125 if (rehash(fp)) 126 h = fnfind(s); 127 fused++; 128 fp[h].name = ecpy(s); 129 fp[h].p = enew(rc_Function); 130 } else 131 free_fn(fp[h].p); 132 return fp[h].p; 133 } 134 135 extern Variable *get_var_place(char *s, bool stack) { 136 Variable *new; 137 int h = varfind(s); 138 139 env_dirty = TRUE; 140 141 if (vp[h].name == NULL) { 142 if (rehash(vp)) 143 h = varfind(s); 144 vused++; 145 vp[h].name = ecpy(s); 146 vp[h].p = enew(Variable); 147 ((Variable *)vp[h].p)->n = NULL; 148 return vp[h].p; 149 } else { 150 if (stack) { /* increase the stack by 1 */ 151 new = enew(Variable); 152 new->n = vp[h].p; 153 return vp[h].p = new; 154 } else { /* trample the top of the stack */ 155 new = vp[h].p; 156 efree(new->extdef); 157 listfree(new->def); 158 return new; 159 } 160 } 161 } 162 163 extern void delete_fn(char *s) { 164 int h = fnfind(s); 165 if (fp[h].name == NULL) 166 return; /* not found */ 167 env_dirty = TRUE; 168 free_fn(fp[h].p); 169 efree(fp[h].p); 170 efree(fp[h].name); 171 if (fp[(h+1)&(fsize-1)].name == NULL) { 172 --fused; 173 fp[h].name = NULL; 174 } else { 175 fp[h].name = dead; 176 } 177 } 178 179 extern void delete_var(char *s, bool stack) { 180 int h = varfind(s); 181 Variable *v; 182 if (vp[h].name == NULL) 183 return; /* not found */ 184 env_dirty = TRUE; 185 v = vp[h].p; 186 efree(v->extdef); 187 listfree(v->def); 188 if (v->n != NULL) { /* This is the top of a stack */ 189 if (stack) { /* pop */ 190 vp[h].p = v->n; 191 efree(v); 192 } else { /* else just empty */ 193 v->extdef = NULL; 194 v->def = NULL; 195 } 196 } else { /* needs to be removed from the hash table */ 197 efree(v); 198 vp[h].p = NULL; 199 efree(vp[h].name); 200 if (vp[(h+1)&(vsize-1)].name == NULL) { 201 --vused; 202 vp[h].name = NULL; 203 } else { 204 vp[h].name = dead; 205 } 206 } 207 } 208 209 static void free_fn(rc_Function *f) { 210 treefree(f->def); 211 efree(f->extdef); 212 } 213 214 extern void initenv(char **envp) { 215 int n; 216 for (n = 0; envp[n] != NULL; n++) 217 ; 218 n++; /* one for the null terminator */ 219 if (n < HASHSIZE) 220 n = HASHSIZE; 221 env = ealloc((envsize = 2 * n) * sizeof (char *)); 222 for (; *envp != NULL; envp++) 223 if (strncmp(*envp, "fn_", conststrlen("fn_")) == 0) { 224 if (!dashpee) 225 fnassign_string(*envp); 226 } else { 227 if (!varassign_string(*envp)) /* add to bozo env */ 228 env[bozosize++] = *envp; 229 } 230 } 231 232 static char *neverexport[] = { 233 "apid", "apids", "bqstatus", "cdpath", "home", 234 "ifs", "path", "pid", "status", "*" 235 }; 236 237 /* for a few variables that have default values, we export them only 238 if they've been explicitly set; maybeexport[n].flag is TRUE if this 239 has occurred. */ 240 struct nameflag { 241 char *name; 242 bool flag; 243 }; 244 static struct nameflag maybeexport[] = { 245 { "prompt", FALSE }, 246 { "version", FALSE } 247 }; 248 249 void set_exportable(char *s, bool b) { 250 int i; 251 for (i = 0; i < arraysize(maybeexport); ++i) 252 if (maybeexport[i].flag != b && streq(s, maybeexport[i].name)) 253 maybeexport[i].flag = b; 254 } 255 256 static bool var_exportable(char *s) { 257 int i; 258 for (i = 0; i < arraysize(neverexport); i++) 259 if (streq(s, neverexport[i])) 260 return FALSE; 261 for (i = 0; i < arraysize(maybeexport); i++) 262 if (maybeexport[i].flag == FALSE && streq(s, maybeexport[i].name)) 263 return FALSE; 264 return TRUE; 265 } 266 267 static bool fn_exportable(char *s) { 268 int i; 269 if (strncmp(s, "sig", conststrlen("sig")) == 0) { /* small speed hack */ 270 for (i = 0; i < NUMOFSIGNALS; i++) 271 if (streq(s, signals[i].name)) 272 return FALSE; 273 if (streq(s, "sigexit")) 274 return FALSE; 275 } 276 return TRUE; 277 } 278 279 extern char **makeenv() { 280 int ep, i; 281 char *v; 282 if (!env_dirty) 283 return env; 284 env_dirty = FALSE; 285 ep = bozosize; 286 if (vsize + fsize + 1 + bozosize > envsize) { 287 envsize = 2 * (bozosize + vsize + fsize + 1); 288 env = erealloc(env, envsize * sizeof(char *)); 289 } 290 for (i = 0; i < vsize; i++) { 291 if (vp[i].name == NULL || vp[i].name == dead || !var_exportable(vp[i].name)) 292 continue; 293 v = varlookup_string(vp[i].name); 294 if (v != NULL) 295 env[ep++] = v; 296 } 297 for (i = 0; i < fsize; i++) { 298 if (fp[i].name == NULL || fp[i].name == dead || !fn_exportable(fp[i].name)) 299 continue; 300 env[ep++] = fnlookup_string(fp[i].name); 301 } 302 env[ep] = NULL; 303 qsort(env, (size_t) ep, sizeof(char *), starstrcmp); 304 return env; 305 } 306 307 extern void whatare_all_vars(bool showfn, bool showvar) { 308 int i; 309 List *s; 310 if (showvar) 311 for (i = 0; i < vsize; i++) 312 if (vp[i].name != NULL && (s = varlookup(vp[i].name)) != NULL) 313 prettyprint_var(1, vp[i].name, s); 314 if (showfn) 315 for (i = 0; i < fsize; i++) 316 if (fp[i].name != NULL && fp[i].name != dead) 317 prettyprint_fn(1, fp[i].name, fnlookup(fp[i].name)); 318 } 319 320 extern char *compl_name(const char *text, int state, char **p, size_t count, ssize_t inc) { 321 static char **n; 322 static size_t i, len; 323 char *name; 324 325 if (!state) { 326 n = p; 327 i = 0; 328 len = strlen(text); 329 } 330 for (name = NULL; name == NULL && i < count; i++, n += inc) 331 if (*n != NULL && strncmp(*n, text, len) == 0) 332 name = strdup(*n); 333 return name; 334 } 335 336 extern char *compl_fn(const char *text, int state) { 337 return compl_name(text, state, &fp[0].name, fsize, &fp[1].name - &fp[0].name); 338 } 339 340 extern char *compl_var(const char *text, int state) { 341 return compl_name(text, state, &vp[0].name, vsize, &vp[1].name - &vp[0].name); 342 }