Mercurial > lbo > hg > ylisp
view src/value.c @ 151:fe5d01fa28ee
value, expr: Test "==" methods and enable freeing all symbols
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Tue, 03 Sep 2019 12:57:53 +0200 |
parents | df0e17d18c80 |
children | 800a02381024 |
line wrap: on
line source
#include "value.h" #include <search.h> #include <string.h> /// An invalid value ID. const yvalue_id_t YVALUE_INVALID_ID = UINT64_MAX - 1; /// Use YVALUE_INSERT in `yvalue_set()` to insert a new value. const yref_t YVALUE_INSERT = {.ref.id = (0xff00000000000000 | UINT64_MAX) - 2}; // TODO: Adjust when programs are bigger. static const size_t YVALUE_INITIAL_VALUES = 256, YVALUE_MAX_VALUES = 1024; // ff marks IDs as such. static const yvalue_id_t YVALUE_COUNTER_OFFSET = 0xff10101010101010; // ylisp keeps tables containing all named values. Unnamed values are // represented as yexpr_t, whereas named values are referenced by their name // (symbol) or ID (numerical ID corresponding to it). // For best performance, symbols should be translated to IDs once and then used // as IDs later. // // The tables are: // 1. Name (char*, heap, owned by hashtable) -> ID (yvalue_id_t) (Hashtable - // slow) // 2. ID (yvalue_id_t) -> Value (yvalue_t) (yvec_t - fast) // // Invariants: // 1. Every symbol has a corresponding place in the value table once it has // been created. static bool yvalue_table_initialized = false; static struct hsearch_data yvalue_name_table; static yvec_t yvalue_table; // vector of yvalue_t static yvec_t yvalue_names; // vector of char* // TODO: Enable garbage collection/reuse instead of monotonic counter. (e.g. // reference-counting in different table) static yvalue_id_t yvalue_counter = YVALUE_COUNTER_OFFSET; // Marker bytes to distinguish yref_t without an extra field. static const yvalue_id_t YVALUE_ID_MARKER = 0xff00000000000000; static const uint64_t YVALUE_CIX_MARKER = 0xfe00000000000000; static inline void yvalue_init_tables(void) { if (yvalue_table_initialized) return; yvalue_table_initialized = true; hcreate_r(YVALUE_MAX_VALUES, &yvalue_name_table); YVEC_INIT(&yvalue_table, YVALUE_INITIAL_VALUES, yvalue_t); YVEC_INIT(&yvalue_names, YVALUE_INITIAL_VALUES, char*); } bool yvalue_is_valid(yvalue_id_t id) { return (id & YVALUE_ID_MARKER) == YVALUE_ID_MARKER && id < yvalue_counter; } YREF_TYPE yref_type(yref_t* ref) { if ((ref->ref.id & YVALUE_ID_MARKER) == YVALUE_ID_MARKER) { return YREF_ID; } if ((ref->ref.id & YVALUE_CIX_MARKER) == YVALUE_CIX_MARKER) { return YREF_STACK; } return YREF_SYM; } yvalue_id_t yvalue_create(void); yref_t yref_new(void) { yref_t ref = {.ref.id = yvalue_create()}; return ref; } yref_t yref_new_id(yvalue_id_t id) { assert(yvalue_is_valid(id)); yref_t ref = {.ref.id = id}; return ref; } yref_t yref_new_str(ystr_t* sym) { yref_t ref = {.ref.sym = *sym}; return ref; } yref_t yref_new_c(const char* sym) { yref_t ref = {.ref.sym = ystr_new(sym)}; return ref; } yref_t yref_new_cix(size_t ix) { yref_t ref = {.ref.cix = ix | YVALUE_CIX_MARKER}; return ref; } bool yref_eq(yref_t* a, yref_t* b) { if (yref_type(a) != yref_type(b)) return false; YREF_TYPE t = yref_type(a); switch (t) { case YREF_SYM: return 0 == ystr_cmp(&a->ref.sym, &b->ref.sym); case YREF_ID: return a->ref.id == b->ref.id; case YREF_STACK: return a->ref.cix == b->ref.cix; default: return false; } } uint64_t yref_cix(yref_t* ref) { return ref->ref.cix ^ YVALUE_CIX_MARKER; } yref_t yref_clone(yref_t* ref) { switch (yref_type(ref)) { case YREF_SYM: // Copy string. return yref_new_c(ystr_str(&ref->ref.sym)); case YREF_ID: case YREF_STACK: return *ref; default: assert(yref_type(ref) == YREF_SYM || yref_type(ref) == YREF_ID || yref_type(ref) == YREF_STACK); return yref_new(); } } yref_t yvalue_clone(yref_t* ref) { yvalue_t* orig = yvalue_get(*ref); assert(orig->typ == YVALUE_EXPR || orig->typ == YVALUE_FUNC); if (orig->typ == YVALUE_FUNC) { // Functions are immutable for now. return *ref; } else if (orig->typ == YVALUE_EXPR) { yvalue_t new = {.typ = YVALUE_EXPR, .value.expr = yexpr_copy(&orig->value.expr)}; return yvalue_set(YVALUE_INSERT, &new); } return yref_new_id(YVALUE_INVALID_ID); } ystr_t yref_debug(yref_t* ref) { YREF_TYPE typ = yref_type(ref); if (typ == YREF_ID) { ystr_t s = ystr_new(NULL); ystr_build(&s, "id:<%llu>", ref->ref.id); return s; } else if (typ == YREF_SYM) { ystr_t s = ystr_new(NULL); ystr_build(&s, "id:<\"%s\">", ystr_str(&ref->ref.sym)); return s; } else if (typ == YREF_STACK) { ystr_t s = ystr_new(NULL); ystr_build(&s, "id:<stackrel:%lld>", -(int64_t)yref_cix(ref)); return s; } return ystr_new("id:INVALID"); } void yref_destroy(yref_t* ref) { if (ref == NULL) return; if (yref_type(ref) == YREF_SYM) { ystr_destroy(&ref->ref.sym); } } void yvalue_destroy(yvalue_t* val) { switch (val->typ) { case YVALUE_EXPR: yexpr_destroy(&val->value.expr); break; default: break; } memset(val, 0, sizeof(yvalue_t)); } yvalue_id_t yvalue_resolve_symbol(ystr_t* sym) { if (ystr_len(sym) == 0) return YVALUE_INVALID_ID; yvalue_init_tables(); const char* sym_s = ystr_str(sym); ENTRY want = {NULL, NULL}; ENTRY* result; want.key = (char*)sym_s; // Valid, key is not modified. hsearch_r(want, FIND, &result, &yvalue_name_table); if (result == NULL) return YVALUE_INVALID_ID; return (yvalue_id_t)result->data; } yvalue_id_t yvalue_create(void) { yvalue_init_tables(); // Create new value entry. yvalue_t empty; memset(&empty, 0, sizeof(yvalue_t)); YVEC_PUSH(&yvalue_table, &empty); return yvalue_counter++; } yvalue_id_t yvalue_resolve_or_create_symbol(ystr_t* sym) { yvalue_init_tables(); yvalue_id_t id = yvalue_resolve_symbol(sym); if (id != YVALUE_INVALID_ID) return id; yvalue_id_t new_id = yvalue_counter++; // Create new value entry. yvalue_t empty; memset(&empty, 0, sizeof(yvalue_t)); YVEC_PUSH(&yvalue_table, &empty); ENTRY new = {.key = strdup(ystr_str(sym)), .data = (void*)new_id}; ENTRY* result; hsearch_r(new, ENTER, &result, &yvalue_name_table); YVEC_PUSH(&yvalue_names, &new.key); return new_id; } void yvalue_resolve_or_create_ref(yref_t* ref) { yvalue_init_tables(); YREF_TYPE typ = yref_type(ref); if (typ == YREF_ID) return; if (typ == YREF_SYM) { yvalue_id_t id = yvalue_resolve_or_create_symbol(&ref->ref.sym); // CAREFUL: This may cause double-frees if `ref` is copied from another // ref. ystr_destroy(&ref->ref.sym); ref->ref.id = id; } } yref_t yvalue_set(yref_t ref, yvalue_t* val) { yvalue_init_tables(); YREF_TYPE typ = yref_type(&ref); // ref == YVALUE_INSERT if (typ == YREF_ID && ref.ref.id == YVALUE_INSERT.ref.id) { // Unnamed value. ref = yref_new(); yvalue_t* valp = yvalue_get(ref); assert(valp != NULL); *valp = *val; return ref; } else { // Resolve reference. yvalue_id_t id; if (typ == YREF_ID) { id = ref.ref.id; } else { id = yvalue_resolve_or_create_symbol(&ref.ref.sym); assert(yvalue_is_valid(id)); ref = yref_new_id(id); } yvalue_t* valp = yvalue_get(ref); assert(valp != NULL); if (valp->typ == YVALUE_EXPR) yexpr_destroy(&valp->value.expr); *valp = *val; return ref; } } yvalue_t* yvalue_get(yref_t ref) { yvalue_init_tables(); YREF_TYPE typ = yref_type(&ref); if (typ == YREF_ID) { assert(ref.ref.id <= yvalue_counter); yvalue_t* vp = YVEC_AT(&yvalue_table, ref.ref.id - YVALUE_COUNTER_OFFSET, yvalue_t); assert(vp != NULL); return vp; } else if (typ == YREF_SYM) { yvalue_id_t id = yvalue_resolve_symbol(&ref.ref.sym); if (id == YVALUE_INVALID_ID) { return NULL; } ref.ref.id = id; return yvalue_get(ref); } else { return NULL; } } void yvalue_free_all(void) { size_t freed = 0; for (yvalue_id_t i = 0; i < yvalue_counter - YVALUE_COUNTER_OFFSET; i++) { yvalue_t* val = YVEC_AT(&yvalue_table, i, yvalue_t); if (val->typ == YVALUE_EXPR) yexpr_destroy(&val->value.expr); if (val->typ == YVALUE_FUNC) yfunc_destroy(&val->value.func); freed += 1; } for (size_t i = 0; i < yvalue_names.len; i++) { free(*YVEC_AT(&yvalue_names, i, char*)); } yvec_destroy(&yvalue_names); hdestroy_r(&yvalue_name_table); yvec_destroy(&yvalue_table); }