env is just linked list now, uses much less memory

6 files changed, 181 insertions, 349 deletions

diff --git a/src/env.c b/src/env.c
index b78b095..ee2e65e 100644
--- a/src/env.c
+++ b/src/env.c
@@ -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");
+//     }
+// }
diff --git a/src/env.h b/src/env.h
index a233a09..3415410 100644
--- a/src/env.h
+++ b/src/env.h
@@ -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
diff --git a/src/main.c b/src/main.c
index 1986f1f..70dd906 100644
--- a/src/main.c
+++ b/src/main.c
@@ -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