| /* | |
| Copyright 2002-2003 John Plevyak, All Rights Reserved | |
| */ | |
| #include "d.h" | |
| #define INITIAL_SYMHASH_SIZE 3137 | |
| typedef struct D_SymHash { | |
| int index; | |
| int grow; | |
| Vec(D_Sym*) syms; | |
| } D_SymHash; | |
| /* | |
| How this works. In a normal symbol table there is simply | |
| a stack of scopes representing the scoping structure of | |
| the program. Because of speculative parsing, this symbol table | |
| also has a tree of all 'updates' representing different | |
| views of the state of scoped variables by each speculative | |
| parse state. Periodically, when the parse state collapses | |
| to a single state (we are nolonger speculating), these changes | |
| are can be 'committed' and the changes pushed into the top | |
| level hash table. | |
| All D_Scope's except the top level just have a 'll' of symbols, the | |
| top level has a 'hash'. | |
| 'updates' is a list of changes to symbols in other scopes. It is | |
| searched to find the current version of a symbol with respect to the | |
| speculative parse path represented by D_Scope. | |
| 'up' points to the enclosing scope, it isn't used much. | |
| 'up_updates' is the prior scope in speculative parsing, it is used find | |
| the next D_Scope to look in for 'updates' after the current one has been | |
| searched. | |
| 'down' and 'down_next' are used to hold enclosing scopes, or in the | |
| case of the top level, sibling scopes (created by commmit). | |
| */ | |
| static void | |
| symhash_add(D_SymHash *sh, D_Sym *s) { | |
| uint i, h = s->hash % sh->syms.n, n; | |
| D_Sym **v = sh->syms.v, *x; | |
| Vec(D_Sym*) vv, tv; | |
| sh->index++; | |
| s->next = v[h]; | |
| v[h] = s; | |
| if (sh->index > sh->grow) { | |
| vv.v = sh->syms.v; | |
| vv.n = sh->syms.n; | |
| sh->syms.n = sh->grow; | |
| sh->grow = sh->grow * 2 + 1; | |
| sh->syms.v = MALLOC(sh->syms.n * sizeof(void *)); | |
| memset(sh->syms.v, 0, sh->syms.n * sizeof(void *)); | |
| v = sh->syms.v; | |
| n = sh->syms.n; | |
| vec_clear(&tv); | |
| for (i = 0; i < vv.n; i++) | |
| /* use temporary to preserve order */ | |
| while (vv.v[i]) { | |
| x = vv.v[i]; | |
| vv.v[i] = x->next; | |
| vec_add(&tv, x); | |
| } | |
| while (tv.v[i]) { | |
| x = tv.v[i]; | |
| tv.v[i] = x->next; | |
| h = x->hash % n; | |
| x->next = v[h]; | |
| v[h] = x; | |
| } | |
| FREE(vv.v); | |
| } | |
| } | |
| static D_SymHash * | |
| new_D_SymHash() { | |
| D_SymHash *sh = MALLOC(sizeof(D_SymHash)); | |
| memset(sh, 0, sizeof(D_SymHash)); | |
| sh->grow = INITIAL_SYMHASH_SIZE * 2 + 1; | |
| sh->syms.n = INITIAL_SYMHASH_SIZE; | |
| sh->syms.v = MALLOC(sh->syms.n * sizeof(void *)); | |
| memset(sh->syms.v, 0, sh->syms.n * sizeof(void *)); | |
| return sh; | |
| } | |
| static void | |
| free_D_SymHash(D_SymHash *sh) { | |
| int i; | |
| D_Sym *sym; | |
| for (i = 0; i < sh->syms.n; i++) | |
| for (; sh->syms.v[i]; sh->syms.v[i] = sym) { | |
| sym = sh->syms.v[i]->next; | |
| free_D_Sym(sh->syms.v[i]); | |
| } | |
| FREE(sh->syms.v); | |
| FREE(sh); | |
| } | |
| D_Scope * | |
| new_D_Scope(D_Scope *parent) { | |
| D_Scope *st = MALLOC(sizeof(D_Scope)); | |
| memset(st, 0, sizeof(D_Scope)); | |
| if (parent) { | |
| st->kind = parent->kind; | |
| st->search = parent; | |
| st->up = parent; | |
| st->up_updates = parent; | |
| st->down_next = parent->down; | |
| parent->down = st; | |
| } else | |
| st->hash = new_D_SymHash(); | |
| return st; | |
| } | |
| D_Scope * | |
| enter_D_Scope(D_Scope *current, D_Scope *scope) { | |
| D_Scope *st = MALLOC(sizeof(D_Scope)), *parent = scope->up; | |
| memset(st, 0, sizeof(D_Scope)); | |
| st->up = parent; | |
| st->kind = scope->kind; | |
| st->search = scope; | |
| st->up_updates = current; | |
| st->down_next = current->down; | |
| current->down = st; | |
| return st; | |
| } | |
| void | |
| free_D_Scope(D_Scope *st, int force) { | |
| D_Scope *s; | |
| D_Sym *sym; | |
| for (; st->down; st->down = s) { | |
| s = st->down->down_next; | |
| free_D_Scope(st->down, 0); | |
| } | |
| if (st->owned_by_user && !force) | |
| return; | |
| if (st->hash) | |
| free_D_SymHash(st->hash); | |
| else | |
| for (; st->ll; st->ll = sym) { | |
| sym = st->ll->next; | |
| free_D_Sym(st->ll); | |
| } | |
| for (; st->updates; st->updates = sym) { | |
| sym = st->updates->next; | |
| free_D_Sym(st->updates); | |
| } | |
| FREE(st); | |
| } | |
| static void | |
| commit_ll(D_Scope *st, D_SymHash *sh) { | |
| D_Sym *sym; | |
| if (st->search) { | |
| commit_ll(st->search, sh); | |
| for (; st->ll; st->ll = sym) { | |
| sym = st->ll->next; | |
| symhash_add(sh, st->ll); | |
| } | |
| } | |
| } | |
| /* make direct links to the latest update */ | |
| static void | |
| commit_update(D_Scope *st, D_SymHash *sh) { | |
| int i; | |
| D_Sym *s; | |
| for (i = 0; i < sh->syms.n; i++) | |
| for (s = sh->syms.v[i]; s; s = s->next) | |
| s->update_of = current_D_Sym(st, s); | |
| } | |
| /* currently only commit the top level scope */ | |
| D_Scope * | |
| commit_D_Scope(D_Scope *st) { | |
| D_Scope *x = st; | |
| if (st->up) | |
| return st; | |
| while (x->search) x = x->search; | |
| commit_ll(st, x->hash); | |
| commit_update(st, x->hash); | |
| return x; | |
| } | |
| D_Sym * | |
| new_D_Sym(D_Scope *st, char *name, char *end, int sizeof_D_Sym) { | |
| int len = end - name; | |
| D_Sym *s = MALLOC(sizeof_D_Sym); | |
| memset(s, 0, sizeof_D_Sym); | |
| s->name = name; | |
| s->len = len; | |
| s->hash = strhashl(name, len); | |
| if (st->hash) { | |
| symhash_add(st->hash, s); | |
| } else { | |
| s->next = st->ll; | |
| st->ll = s; | |
| } | |
| return s; | |
| } | |
| void | |
| free_D_Sym(D_Sym *s) { | |
| FREE(s); | |
| } | |
| D_Sym * | |
| current_D_Sym(D_Scope *st, D_Sym *sym) { | |
| D_Scope *sc; | |
| D_Sym *uu; | |
| if (sym->update_of) sym = sym->update_of; | |
| /* return the last update */ | |
| for (sc = st; sc; sc = sc->up_updates) { | |
| for (uu = sc->updates; uu; uu = uu->next) | |
| if (uu->update_of == sym) | |
| return uu; | |
| } | |
| return sym; | |
| } | |
| D_Sym * | |
| find_sym_internal(D_Scope *top, D_Scope *cur, char *name, int len, uint h) { | |
| D_Sym *ll; | |
| if (!cur) | |
| return NULL; | |
| if (cur->hash) | |
| ll = cur->hash->syms.v[h % cur->hash->syms.n]; | |
| else | |
| ll = cur->ll; | |
| while (ll) { | |
| if (ll->hash == h && ll->len == len && !strncmp(ll->name, name, len)) | |
| break; | |
| ll = ll->next; | |
| } | |
| if (!ll) { | |
| if (cur->search) | |
| return find_sym_internal(top, cur->search, name, len, h); | |
| return ll; | |
| } | |
| return current_D_Sym(top, ll); | |
| } | |
| D_Sym * | |
| find_D_Sym(D_Scope *st, char *name, char *end) { | |
| int len = end - name; | |
| uint h = strhashl(name, len); | |
| return find_sym_internal(st, st, name, len, h); | |
| } | |
| D_Sym * | |
| find_D_Sym_in_Scope(D_Scope *st, char *name, char *end) { | |
| D_Sym *ll; | |
| int len = end - name; | |
| uint h = strhashl(name, len); | |
| for (;st ; st = st->search) { | |
| if (st->hash) | |
| ll = st->hash->syms.v[h % st->hash->syms.n]; | |
| else | |
| ll = st->ll; | |
| while (ll) { | |
| if (ll->hash == h && ll->len == len && !strncmp(ll->name, name, len)) | |
| return ll; | |
| ll = ll->next; | |
| } | |
| if (!st->search || st->search->up != st->up) | |
| break; | |
| } | |
| return NULL; | |
| } | |
| D_Sym * | |
| update_D_Sym(D_Scope *st, D_Sym *sym, int sizeof_D_Sym) { | |
| D_Sym *s; | |
| sym = current_D_Sym(st, sym); | |
| s = MALLOC(sizeof_D_Sym); | |
| memcpy(s, sym, sizeof(D_Sym)); | |
| if (sym->update_of) sym = sym->update_of; | |
| s->update_of = sym; | |
| s->next = st->updates; | |
| st->updates = s; | |
| return s; | |
| } | |
| void | |
| print_sym(D_Sym *s) { | |
| char *c = (char*)MALLOC(s->len + 1); | |
| memcpy(c, s->name, s->len); | |
| s->name[s->len] = 0; | |
| printf("%s, ", c); | |
| FREE(c); | |
| } | |
| void | |
| print_scope(D_Scope *st) { | |
| printf("SCOPE %X: ", (long)st); | |
| printf(" owned: %d, kind: %d, ", st->owned_by_user, st->kind); | |
| if (st->ll) printf(" LL\n"); | |
| if (st->hash) printf(" HASH\n"); | |
| if (st->hash) { | |
| int i; | |
| for (i = 0; i < st->hash->syms.n; i++) | |
| if (st->hash->syms.v[i]) | |
| print_sym(st->hash->syms.v[i]); | |
| } else { | |
| D_Sym *ll = st->ll; | |
| while (ll) { | |
| print_sym(ll); | |
| ll = ll->next; | |
| } | |
| } | |
| printf("\n\n"); | |
| if (st->search) print_scope(st->search); | |
| } |