diff options
| -rw-r--r-- | README.md | 3 | ||||
| -rw-r--r-- | src/env.c | 14 | ||||
| -rw-r--r-- | src/hashtable.c | 28 | ||||
| -rw-r--r-- | src/mempool.h | 75 | ||||
| -rw-r--r-- | src/value.c | 12 |
5 files changed, 118 insertions, 14 deletions
@@ -4,6 +4,7 @@ A simple lisp/scheme interpreter #### TODO +* reduce allocations +* overhaul environement/closures * improve errors -* macros * FFI @@ -5,7 +5,13 @@ #include "env.h" #include "value.h" -#define ENV_TABLE_CAP (1 << 8) +#include "mempool.h" + +#define MEMPOOL_OBJ_TYPE struct symbol_table +#define MEMPOOL_CAP 64 +MEMPOOL_GENERATE(env) + +#define ENV_TABLE_CAP (1 << 3) static unsigned long str_hash(char *str) { @@ -34,7 +40,8 @@ static bool equal(void *key1, void *key2) env_t env_create(env_t parent, env_destroy_func destroy_func) { - env_t env = malloc(sizeof(*env)); + // env_t env = malloc(sizeof(*env)); + env_t env = env_mempool_allocate(); env->destroy_func = destroy_func; env->parent = parent; env->refs = 1; @@ -59,7 +66,8 @@ void env_destroy(env_t env) } hashtable_destroy(env->table); - free(env); + // free(env); + env_mempool_free(env); } env_t env_copy(env_t env) diff --git a/src/hashtable.c b/src/hashtable.c index 9f5d2e1..955a3bf 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -4,8 +4,16 @@ #include "common.h" #include "hashtable.h" +#include "mempool.h" + +#define MEMPOOL_CAP 32 +#define MEMPOOL_OBJ_TYPE struct hashtable +MEMPOOL_GENERATE(ht) +#define MEMPOOL_CAP 128 +#define MEMPOOL_OBJ_TYPE struct hashtable_item +MEMPOOL_GENERATE(hi) + // TODO: -// - automatic growing // - insertion options #define HASH(ht, key) (ht->hash_func(key) % ht->cap) @@ -17,7 +25,8 @@ static void hashtable_table_append_item(struct hashtable_item ** table, size_t i 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); + // ERR_Z(ht = malloc(sizeof(*ht)), goto fail); + ht = ht_mempool_allocate(); ht->hash_func = hash_func; ht->equal_func = equal_func; @@ -38,13 +47,15 @@ void hashtable_destroy(hashtable_t ht) if(ht->table) { hashtable_for_each_item_safe(ht, item, i) { - free(item); + // free(item); + hi_mempool_free(item); } free(ht->table); } - free(ht); + // free(ht); + ht_mempool_free(ht); } void hashtable_reset(hashtable_t ht) @@ -53,7 +64,8 @@ void hashtable_reset(hashtable_t ht) if(ht->table) { hashtable_for_each_item_safe(ht, item, i) { - free(item); + // free(item); + hi_mempool_free(item); } } @@ -75,7 +87,8 @@ int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void return 0; } - ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM); + // ERR_Z(item = malloc(sizeof(*item)), return -ENOMEM); + item = hi_mempool_allocate(); item->key = key; item->data = data; @@ -85,7 +98,7 @@ int hashtable_insert(hashtable_t ht, void *key, void *data, void **prevkey, void ht->size++; if(ht->size > (ht->cap * 3/4)) { - return hashtable_grow(ht, 1 << ht->cap); + return hashtable_grow(ht, ht->cap << 1); } return 0; @@ -124,7 +137,6 @@ 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 diff --git a/src/mempool.h b/src/mempool.h new file mode 100644 index 0000000..6c25ac9 --- /dev/null +++ b/src/mempool.h @@ -0,0 +1,75 @@ +#ifndef MEMPOOL_H +#define MEMPOOL_H + +#ifndef MEMPOOL_OBJ_TYPE +#define MEMPOOL_OBJ_TYPE int +#endif + +#ifndef MEMPOOL_CAP +#define MEMPOOL_CAP (1 << 16) +#endif + +#define for_each_block(id, b, head) \ + for(struct id##_block *b = (head), *next = NULL; \ + b && (next = b->next, 1); b = next) +#define get_last_block(b) \ + while((b)->next != NULL) (b) = (b)->next + +#define MEMPOOL_GENERATE(id) \ + \ + struct id##_block { \ + union id##_chunk { \ + MEMPOOL_OBJ_TYPE obj; \ + union id##_chunk *next; \ + } chunks[MEMPOOL_CAP]; \ + \ + struct id##_block *next; \ + }; \ + \ + static union id##_chunk *id##_ap = NULL; \ + static struct id##_block id##_block; \ + static size_t id##_allocations = 0; \ + \ + static inline void *_##id##_mempool_init_block(struct id##_block *b) \ + { \ + b->next = NULL; \ + for(size_t i = 0; i < MEMPOOL_CAP; i++) \ + b->chunks[i].next = &b->chunks[i+1]; \ + b->chunks[MEMPOOL_CAP-1].next = NULL; \ + \ + return b->chunks; \ + } \ + \ + static inline void *id##_mempool_allocate(void) \ + { \ + if(!id##_ap) { \ + struct id##_block *new_block = &(id##_block); \ + if((id##_allocations) > 0) { \ + new_block = malloc(sizeof(*new_block)); \ + struct id##_block *last_block = &(id##_block); \ + get_last_block(last_block); \ + last_block->next = new_block; \ + } \ + id##_ap = _##id##_mempool_init_block(new_block); \ + } \ + \ + id##_allocations++; \ + \ + void *ptr = &(id##_ap)->obj; \ + id##_ap = (id##_ap)->next; \ + return ptr; \ + } \ + \ + static inline void id##_mempool_free(void *ptr) \ + { \ + ((union id##_chunk *)ptr)->next = id##_ap; \ + id##_ap = (union id##_chunk *)ptr; \ + \ + if(--id##_allocations == 0) { \ + for_each_block(id, b, (id##_block).next) \ + free(b); \ + id##_ap = id##_block.chunks; \ + } \ + } \ + +#endif diff --git a/src/value.c b/src/value.c index 9a7f9b6..0d263d7 100644 --- a/src/value.c +++ b/src/value.c @@ -5,6 +5,12 @@ #include "value.h" #include "lexer.h" +#include "mempool.h" + +#define MEMPOOL_OBJ_TYPE struct value +#define MEMPOOL_CAP 64 +MEMPOOL_GENERATE(value) + #define NOT_IMPLEMENTED() die("Not Implemented. ABORTING") const char * const value_type_string[] = { @@ -76,7 +82,8 @@ static void proc_destroy(struct proc *proc); value_t value_create(enum value_type type, void *value) { - value_t _value = malloc(sizeof(*_value)); + // value_t _value = malloc(sizeof(*_value)); + value_t _value = value_mempool_allocate(); _value->type = type; switch(type) { @@ -98,7 +105,8 @@ void value_destroy(value_t value) } if(value->refs == 0) - free(value); + value_mempool_free(value); + // free(value); } value_t value_from_token(struct token *token) |