diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/env.c | 151 | ||||
| -rw-r--r-- | src/env.h | 14 | ||||
| -rw-r--r-- | src/hashtable.c | 171 | ||||
| -rw-r--r-- | src/hashtable.h | 54 | ||||
| -rw-r--r-- | src/main.c | 125 | ||||
| -rw-r--r-- | src/memdebug.h | 15 |
6 files changed, 181 insertions, 349 deletions
@@ -4,102 +4,153 @@ #include "common.h" #include "env.h" -#include "hashtable.h" +#include "list.h" #include "value.h" -struct env { - hashtable_t table; +#define HAS(v, flag) (((v) & (flag)) == (flag)) +struct env { struct env *parent; + struct list_head *head; + size_t refs; + size_t circular_refs; +}; - env_destroy_func destroy_func; +struct env_kv { + char *key; + _value_t value; + struct list_head list; + + int flags; }; #include "mempool.h" -MEMPOOL_GENERATE(env, struct env, 64) - -#define ENV_TABLE_CAP (1 << 3) +MEMPOOL_GENERATE(env, struct env, 256) +MEMPOOL_GENERATE(env_kv, struct env_kv, 1024) -static unsigned long str_hash(char *str) +static int equal(char *key1, char *key2) { - unsigned long hash = 5381; - int c; - - while ((c = *str++)) - hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ - - return hash; + return (strcmp(key1, key2) == 0); } -static size_t hash(void *key) +static struct env_kv *env_kv_create(char *key, value_t value, int flags) { - return str_hash((char*)key); + struct env_kv *pair = env_kv_mempool_allocate(); + + pair->key = key; + pair->value = value; + LIST_EMPTY(&pair->list); + pair->flags = flags; + + return pair; } -static bool equal(void *key1, void *key2) +static void env_kv_destroy(struct env_kv *pair) { - if(strcmp((char *)key1, (char*)key2) == 0) { - return true; - } + if(HAS(pair->flags, ENV_KV_FREE_KEY)) + free(pair->key); - return false; + value_destroy(pair->value); + env_kv_mempool_free(pair); } -env_t env_create(env_t parent, env_destroy_func destroy_func) +env_t env_create(env_t parent) { - // env_t env = malloc(sizeof(*env)); env_t env = env_mempool_allocate(); - env->destroy_func = destroy_func; - env->parent = parent; - env->refs = 1; - - ERR_Z(env->table = hashtable_create(ENV_TABLE_CAP, hash, equal), - env_destroy(env)); + env->parent = env_copy(parent); + env->head = NULL; + env->refs = 0; + env->circular_refs = 0; return env; } void env_destroy(env_t env) { - if(!env) return; + if(env == ENV_EMPTY) return; - env->refs--; - env_destroy(env->parent); + if(env->refs > env->circular_refs) { + env->refs--; + return; + } - if(env->refs > 0) return; + list_for_each_safe(head, env->head) { + struct env_kv *p = list_entry(head, struct env_kv, list); - hashtable_for_each_item(env->table, item, i) { - env->destroy_func((char *)item->key, (value_t)item->data); + if(HAS(p->flags, ENV_KV_CIRCULAR_REF)) env->circular_refs--; + env_kv_destroy(p); } - hashtable_destroy(env->table); - // free(env); + env_destroy(env->parent); env_mempool_free(env); } -int env_insert(env_t env, char *key, value_t data, - char **prevkey, value_t *prevdata) +int env_insert(env_t env, char *key, _value_t value, + _value_t *prevval, int flags) { - return hashtable_insert(env->table, (void *)key, (void *)data, (void **)prevkey, (void **)prevdata); + if(env->head) + list_for_each_entry(struct env_kv, p, list, env->head) { + if(!equal(p->key, key)) continue; + + env->circular_refs += + (HAS(flags, ENV_KV_CIRCULAR_REF) - + HAS(p->flags, ENV_KV_CIRCULAR_REF)); + p->flags = flags; + + if(prevval) *prevval = p->value; + p->value = value; + return 0; + } + + if(HAS(flags, ENV_KV_CIRCULAR_REF)) env->circular_refs++; + + struct env_kv *pair = env_kv_create(key, value, flags); + if(env->head) list_append(&pair->list, env->head); + env->head = &pair->list; + + return 0; } -int env_query(env_t env, char *key, value_t *data) +int env_query(env_t env, char *key, _value_t *data) { - return hashtable_query(env->table, (void *)key, (void **)data); + struct env_kv *pair = NULL; + + for(env_t e = env; e; e = e->parent) { + if(e->head == NULL) continue; + list_for_each_entry(struct env_kv, p, list, e->head) { + if(equal(p->key, key)) pair = p; + } + + if(pair) break; + } + + if(!pair) return 1; + + *data = pair->value; + return 0; } env_t env_copy(env_t env) { - if(env == ENV_EMPTY) return ENV_EMPTY; + if(!env) return env; env->refs++; - env_copy(env->parent); - return env; } -env_t env_parent(env_t env) -{ - return env->parent; -} +// void env_print(env_t env) +// { +// printf("REFS: %d\n", env->refs); +// printf("CREFS: %d\n", env->circular_refs); +// if(!env || !env->head) return; +// list_for_each_entry(struct env_kv, pair, list, env->head) { +// printf("ENTRY: %s %s\n", pair->key, pair->value); +// } + +// if(env->parent) { +// printf("---- PARENT ----\n"); +// env_print(env->parent); +// printf("-- END PARENT --\n"); +// } +// } @@ -1,22 +1,26 @@ #ifndef ENV_H #define ENV_H +#include "list.h" + // #include "value.h" typedef struct value * _value_t; typedef struct env * env_t; #define ENV_EMPTY NULL -typedef void (*env_destroy_func)(char *key, _value_t value); +enum env_kv_flag { + ENV_KV_FREE_KEY = 1, + ENV_KV_CIRCULAR_REF = 2 +}; -env_t env_create(env_t parent, env_destroy_func destroy_func); +env_t env_create(env_t parent); void env_destroy(env_t env); -int env_insert(env_t env, char *key, _value_t data, - char **prevkey, _value_t *prevdata); +int env_insert(env_t env, char *key, _value_t value, + _value_t *prevval, int flags); int env_query(env_t env, char *key, _value_t *data); env_t env_copy(env_t env); -env_t env_parent(env_t env); #endif diff --git a/src/hashtable.c b/src/hashtable.c deleted file mode 100644 index e9845f2..0000000 --- a/src/hashtable.c +++ /dev/null @@ -1,171 +0,0 @@ -#include <stdlib.h> -#include <errno.h> - -#include "common.h" -#include "hashtable.h" - -#include "mempool.h" -MEMPOOL_GENERATE(ht, struct hashtable, 32) -MEMPOOL_GENERATE(hi, struct hashtable_item, 128) - -// TODO: -// - insertion options - -#define HASH(ht, key) (ht->hash_func(key) % ht->cap) - -static int hashtable_grow(hashtable_t ht, size_t cap); -static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev); -static void hashtable_table_append_item(struct hashtable_item ** table, size_t idx, struct hashtable_item *item); - -hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func) -{ - hashtable_t ht; - // ERR_Z(ht = malloc(sizeof(*ht)), goto fail); - ht = ht_mempool_allocate(); - - ht->hash_func = hash_func; - ht->equal_func = equal_func; - ht->cap = 0; - ht->size = 0; - - ERR_ERRNO_SET(hashtable_grow(ht, cap), goto fail); - - return ht; -fail: - hashtable_destroy(ht); - return NULL; -} - -void hashtable_destroy(hashtable_t ht) -{ - if(!ht) return; - - if(ht->table) { - hashtable_for_each_item_safe(ht, item, i) { - // free(item); - hi_mempool_free(item); - } - - free(ht->table); - } - - // free(ht); - ht_mempool_free(ht); -} - -void hashtable_reset(hashtable_t ht) -{ - if(!ht) return; - - if(ht->table) { - hashtable_for_each_item_safe(ht, item, i) { - // free(item); - hi_mempool_free(item); - } - } - - ht->size = 0; -} - -int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void **prevdata) -{ - size_t idx = HASH(ht, key); - - struct hashtable_item *item, *prev; - hashtable_find_item(ht, idx, key, &item, &prev); - - if(item) { - if(prevkey) *prevkey = item->key; - if(prevdata) *prevdata = item->data; - item->key = key; - item->data = data; - return 0; - } - - // ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM); - item = hi_mempool_allocate(); - - item->key = key; - item->data = data; - item->next = NULL; - - hashtable_table_append_item(ht->table, idx, item); - ht->size++; - - if(ht->size > (ht->cap * 3/4)) { - return hashtable_grow(ht, ht->cap << 1); - } - - return 0; -} - -int hashtable_query(hashtable_t ht, void *key, void **data) -{ - size_t idx = HASH(ht, key); - - struct hashtable_item *item; - ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, NULL)); - - *data = item->data; - - return 0; -} - -int hashtable_delete(hashtable_t ht, void *key) -{ - size_t idx = HASH(ht, key); - - struct hashtable_item *item, *prev; - ERR_NZ_RET(hashtable_find_item(ht, idx, key, &item, &prev)); - - if(prev) - prev->next = item->next; - else - ht->table[idx] = item->next; - - free(item); - - return 0; -} - -static int hashtable_grow(hashtable_t ht, size_t cap) -{ - struct hashtable_item **new_table; - ERR_Z(new_table = calloc(cap, sizeof(*new_table)), return -ENOMEM); - if(ht->cap > 0) { - hashtable_for_each_item_safe(ht, item, i) { - // hash but with the new cap - size_t idx = ht->hash_func(item->key) % cap; - hashtable_table_append_item(new_table, idx, item); - } - - free(ht->table); - } - - ht->table = new_table; - ht->cap = cap; - - return 0; -} - -static int hashtable_find_item(hashtable_t ht, size_t idx, void *key, struct hashtable_item **item, struct hashtable_item **prev) -{ - if(item) *item = NULL; - if(prev) *prev = NULL; - - hashtable_for_each_item_on_index(ht, _item, idx) { - if(ht->equal_func(_item->key, key)) { - if(item) *item = _item; - return 0; - } - if(prev) *prev = _item; - } - - return -ENOENT; -} - -static void hashtable_table_append_item(struct hashtable_item **table, size_t idx, struct hashtable_item *item) -{ - item->next = table[idx]; - table[idx] = item; -} diff --git a/src/hashtable.h b/src/hashtable.h deleted file mode 100644 index b9b1b2a..0000000 --- a/src/hashtable.h +++ /dev/null @@ -1,54 +0,0 @@ -#ifndef HASHMAP_H -#define HASHMAP_H - -#include <stdbool.h> - -typedef struct hashtable *hashtable_t; - -typedef size_t (*hashtable_hash_func)(void *key); -typedef bool (*hashtable_equal_func)(void *key1, void *key2); - -struct hashtable { - hashtable_hash_func hash_func; - hashtable_equal_func equal_func; - - struct hashtable_item { - struct hashtable_item *next; - void *key; - void *data; - } **table; - - size_t size; - size_t cap; -}; - -hashtable_t hashtable_create(size_t cap, hashtable_hash_func hash_func, hashtable_equal_func equal_func); -void hashtable_destroy(hashtable_t ht); -void hashtable_reset(hashtable_t ht); - -int hashtable_insert(hashtable_t ht, void *key, void *data, - void **prevkey, void **prevdata); -int hashtable_query(hashtable_t ht, void *key, void **data); -int hashtable_delete(hashtable_t ht, void *key); - -#define hashtable_for_each_item(ht, item, i) \ - for(size_t i = 0; i < ht->cap; i++) \ - for(struct hashtable_item *item = ht->table[i]; \ - item != NULL; \ - item = item->next) - -#define hashtable_for_each_item_on_index(ht, item, idx) \ - for(struct hashtable_item *item = \ - ht->table[idx]; \ - item != NULL; \ - item = item->next) - -#define hashtable_for_each_item_safe(ht, item, i) \ - for(size_t i = 0; i < ht->cap; i++) \ - for(struct hashtable_item \ - *item = ht->table[i], \ - *next = NULL; \ - item != NULL && (next = item->next, 1); \ - item = next) - -#endif @@ -9,7 +9,6 @@ #include "env.h" #ifdef ENABLE_MEMDEBUG -#define MEMDEBUG_OUT_OF_BOUNDS #define MEMDEBUG_IMPLEMENTATION #define MEMDEBUG_OUTPUT_DIR "files" #endif @@ -164,18 +163,6 @@ static struct toklist *cons_to_toklist(value_t value); static env_t global_env = ENV_EMPTY; static value_t global_nil = VALUE_EMPTY; -static void destroy_env(char *key, value_t value) -{ - (void)key; - value_destroy(value); -} - -static void destroy_global_env(char *key, value_t value) -{ - free(key); - value_destroy(value); -} - int main(int argc, char **argv) { int opt, repl_flag = 0; @@ -205,27 +192,25 @@ int main(int argc, char **argv) if(!filename) repl_flag = 1; + FILE *fp = stdin; + if(!repl_flag) { + fp = fopen(filename, "r"); + if(!fp) { + die("fopen: %s", strerror(errno)); + } + } - env_t builtin_env = env_create(ENV_EMPTY, destroy_env); - global_env = env_create(builtin_env, destroy_global_env); + global_env = env_create(NULL); global_nil = value_create(VALUE_NIL, NULL); for(size_t i = 0; i < BUILTIN_PROCEDURES; i++) { value_t proc_value = value_create( VALUE_PROC_BUILTIN, (void *)&builtin_proc_descriptions[i]); - - env_insert(builtin_env, - builtin_proc_name_list[i], - proc_value, NULL, NULL); - } - FILE *fp = stdin; - if(!repl_flag) { - fp = fopen(filename, "r"); - if(!fp) { - die("fopen: %s", strerror(errno)); - } + ERR_NZ(env_insert(global_env, builtin_proc_name_list[i], + proc_value, NULL, 0), r, + return r); } lexer_t lexer = lexer_create(fp); @@ -236,7 +221,7 @@ int main(int argc, char **argv) if(repl_flag) printf("> "); while(next_token(&tctx)) { - value_t val = evaluate_expr(ENV_EMPTY, &tctx); + value_t val = evaluate_expr(global_env, &tctx); if(val == VALUE_EMPTY) { if(!repl_flag) { @@ -261,11 +246,11 @@ int main(int argc, char **argv) value_destroy(val); } - lexer_destroy(lexer); - fclose(fp); - value_destroy(global_nil); env_destroy(global_env); + + lexer_destroy(lexer); + fclose(fp); return 0; } @@ -277,12 +262,17 @@ static char *str_alloc_copy(char *src) return memcpy(malloc(len), src, len); } -#define HAS_ENOUGH_ARGS(proc, type, argc, fail) \ - if(argc != vvalue_##type(proc).argc) { \ - err("Wrong number of arguemnts, expected %zu, but got %zu", \ - vvalue_##type(proc).argc, argc); \ - fail; \ - } +// static char *str_temp_copy(char *src) +// { +// if(!src) return src; + +// static char[256] dest; +// size_t len = strlen(src) + 1; + +// return (sizeof(dest) < len) +// ? NULL +// : memcpy(dest, src, len); +// } static value_t apply_lambda(struct proc *proc, value_t *args) { @@ -290,18 +280,17 @@ static value_t apply_lambda(struct proc *proc, value_t *args) env_t env = ENV_EMPTY; struct tctx tctx = {0}; - ERR_Z(env = env_create(env_copy(proc->parent_env), destroy_env), goto exit); + ERR_Z(env = env_create(proc->parent_env), goto exit); tctx_init_toklist(&tctx, proc->body); for(size_t i = 0; i < proc->argc; i++) { - ERR_NZ(env_insert(env, proc->arg_keys[i]->value.atom, - value_copy(args[i]), NULL, NULL), + ERR_NZ(env_insert(env, vvalue_atom(proc->arg_keys[i]), + value_copy(args[i]), NULL, 0), _r, goto exit); } TOKEN_NEXT(&tctx); ret = evaluate_expr(env, &tctx); - exit: env_destroy(env); return ret; @@ -330,6 +319,13 @@ exit: return ret; } +#define HAS_ENOUGH_ARGS(proc, type, argc, fail) \ + if(argc != vvalue_##type(proc).argc) { \ + err("Wrong number of arguemnts, expected %zu, but got %zu", \ + vvalue_##type(proc).argc, argc); \ + fail; \ + } + value_t apply(env_t env, value_t proc, size_t argc, value_t *argv) { if(proc == VALUE_EMPTY) return value_copy(global_nil); @@ -454,21 +450,13 @@ exit: value_t evaluate_id(env_t env, struct tctx *tctx) { - if(env == ENV_EMPTY) { - return evaluate_id(global_env, tctx); - } - value_t ret = VALUE_EMPTY; ERR_NZ(env_query(env, TOKEN(tctx)->value.id, &ret), _r, goto fail); return value_copy(ret); - fail: - if(env == env_parent(global_env)) { - err("Symbol %s is unbound", TOKEN(tctx)->value.id); - return VALUE_EMPTY; - } - return evaluate_id(env_parent(env), tctx); + err("Symbol %s is unbound", TOKEN(tctx)->value.id); + return VALUE_EMPTY; } value_t evaluate_lambda(env_t env, struct tctx *tctx) @@ -528,12 +516,6 @@ value_t evaluate_define(env_t env, struct tctx *tctx) // TODO: don't alloc when the key is the same char *key = NULL; - // only in the outside environement - if(env != ENV_EMPTY) { - err("define can only be called in the outermost environement"); - goto fail; - } - TOKEN_SKIP(tctx, TOKEN_DEFINE, goto fail); switch(TOKEN(tctx)->type) @@ -556,18 +538,22 @@ value_t evaluate_define(env_t env, struct tctx *tctx) goto fail); value_t prevval = VALUE_EMPTY; - char *prevkey = NULL; + int flags = ENV_KV_FREE_KEY; + flags |= (vvalue_type(val) == VALUE_PROC) ? ENV_KV_CIRCULAR_REF : 0; ERR_NZ( - env_insert(global_env, key, val, &prevkey, &prevval), + env_insert(env, key, val, &prevval, flags), r, { err("Couldn't insert symbol into the environement due to %s", strerror(r)); value_destroy(val); // the copy goto fail; }); - if(prevkey) free(prevkey); - value_destroy(prevval); + if(prevval) { + free(key); + value_destroy(prevval); + } + return value_copy(global_nil); fail: @@ -632,30 +618,31 @@ value_t evaluate_defmacro(env_t env, struct tctx *tctx) } // unsafe and bad - tctx->token->type = TOKEN_LAMBDA; + TOKEN(tctx)->type = TOKEN_LAMBDA; ERR_Z(lambda = evaluate_lambda(env, tctx), goto fail); value_set_type(lambda, VALUE_MACRO); - // TOKEN_MATCH(tctx, TOKEN_RP, goto fail); - value_t prevval = VALUE_EMPTY; - char *prevkey = NULL; + int flags = ENV_KV_FREE_KEY | ENV_KV_CIRCULAR_REF; ERR_NZ( - env_insert(global_env, key, lambda, &prevkey, &prevval), + env_insert(env, key, lambda, &prevval, flags), r, { err("Couldn't insert symbol into the environement due to %s", strerror(r)); + value_destroy(lambda); goto fail; }); - if(prevkey) free(prevkey); - value_destroy(prevval); + if(prevval) { + free(key); + value_destroy(prevval); + } + return value_copy(global_nil); fail: - value_destroy(lambda); - if(key)free(key); + if(key) free(key); return VALUE_EMPTY; } diff --git a/src/memdebug.h b/src/memdebug.h index 7d72a10..c318656 100644 --- a/src/memdebug.h +++ b/src/memdebug.h @@ -22,6 +22,8 @@ void *__memdebug_calloc(size_t nmemb, size_t size, char *file, int line); void *__memdebug_realloc(void *ptr, size_t size, char *file, int line); void __memdebug_free(void *ptr, char *file, int line); +int memdebug_log(char *format, ...); + #ifdef MEMDEBUG_IMPLEMENTATION // Default memory allocation functions @@ -66,6 +68,7 @@ typedef long long int memdebug_suffix; #include <stdlib.h> #include <stdint.h> #include <string.h> +#include <stdarg.h> #include <errno.h> #include <time.h> @@ -95,6 +98,18 @@ static inline void *memdebug_add_out_of_bounds_check(void *addr, size_t size) return (void *)((uintptr_t)addr + sizeof(size)); } +int memdebug_log(char *format, ...) +{ + int ret = 0; + va_list args; + + va_start(args, format); + ret = vfprintf(_memdebug_fp, format, args); + va_end(args); + + return ret; +} + void *__memdebug_malloc(size_t size, char *file, int line) { #ifndef MEMDEBUG_OUT_OF_BOUNDS |