From ed62db5344e1fb39f17883c69bd398d18758f29b Mon Sep 17 00:00:00 2001 From: Leo Tenenbaum Date: Sun, 29 Sep 2019 18:09:41 -0400 Subject: continued allocator --- allocator.c | 44 ++++++-------------------------------------- arr.c | 22 ++++++++++++++++++++-- build.sh | 6 ++++-- main.c | 4 +++- parse.c | 33 +++++++++++++++++++++------------ tests.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++ toc.c | 2 ++ 7 files changed, 109 insertions(+), 55 deletions(-) create mode 100644 tests.c diff --git a/allocator.c b/allocator.c index 7d1c6a7..f10c703 100644 --- a/allocator.c +++ b/allocator.c @@ -7,6 +7,9 @@ typedef struct Page { typedef struct { Page *first; Page *last; + void **dyn; /* array of void*s for dynamic memory */ + size_t dyn_len; + size_t dyn_cap; } Allocator; /* number of bytes a page hold, not including the header */ @@ -47,21 +50,7 @@ static void *allocr_calloc(Allocator *a, size_t bytes) { /* IMPORTANT: this can only be called with data which was originally allocated with allocr_realloc(a, NULL, x) */ static void *allocr_realloc(Allocator *a, void *data, size_t new_size) { - if (!data) { - Page *page = err_malloc(sizeof *page + new_size); - page->used = PAGE_SIZE; /* pretend we used all of this page */ - page->next = NULL; - if (a->last) - a->last->next = page; - else - a->first = page; - a->last = page; - return page->data; - } else { - Page *page = (Page *)((char *)data - offsetof(Page, data)); - page = err_realloc(page, sizeof *page + new_size); - return page->data; - } + return NULL; } static void allocr_free_all(Allocator *a) { @@ -70,28 +59,7 @@ static void allocr_free_all(Allocator *a) { free(page); page = next; } -} - -static void allocr_test(void) { - Allocator a; - allocr_create(&a); - for (int x = 1000; x <= 8000; x += 1000) { - size_t nfoos = x; - int *foos = allocr_malloc(&a, nfoos * sizeof(int)); - - for (size_t i = 0; i < nfoos; i++) - foos[i] = (int)i; - for (size_t i = 0; i < nfoos; i++) - assert(foos[i] == (int)i); - size_t nbars = x; - int *bars = allocr_calloc(&a, nbars * sizeof(int)); - for (size_t i = 0; i < nbars; i++) - assert(bars[i] == 0); - for (size_t i = 0; i < nbars; i++) - bars[i] = (int)i; - for (size_t i = 0; i < nbars; i++) - assert(bars[i] == (int)i); + for (size_t i = 0; i < a->dyn_len; i++) { + free(a->dyn[i]); } - - allocr_free_all(&a); } diff --git a/arr.c b/arr.c index 2555d72..fa337e8 100644 --- a/arr.c +++ b/arr.c @@ -16,10 +16,20 @@ static inline void arr_reserve(Array *arr, size_t n) { arr->data = err_realloc(arr->data, arr->item_sz * arr->cap); } +static inline void arr_reservea(Array *arr, size_t n, Allocator *a) { + arr->cap = n; + arr->data = allocr_realloc(a, arr->data, n); +} + /* like arr_reserve, but sets the length of the array too */ static inline void arr_set_len(Array *arr, size_t n) { - arr->len = arr->cap = n; - arr->data = err_realloc(arr->data, arr->item_sz * arr->cap); + arr_reserve(arr, n); + arr->len = n; +} + +static inline void arr_set_lena(Array *arr, size_t n, Allocator *a) { + arr_reservea(arr, n, a); + arr->len = n; } static inline void *arr_last(Array *arr) { @@ -37,6 +47,14 @@ static void *arr_add(Array *arr) { return (void*)((char*)arr->data + arr->item_sz * (arr->len - 1)); } +static void *arr_adda(Array *arr, Allocator *a) { + if (arr->len >= arr->cap) { + arr_reservea(arr, (arr->cap + 1) * 2, a); + } + arr->len++; + return (void*)((char*)arr->data + arr->item_sz * (arr->len - 1)); +} + static void arr_clear(Array *arr) { free(arr->data); arr->len = arr->cap = 0; diff --git a/build.sh b/build.sh index e256f9f..0a7e7ce 100755 --- a/build.sh +++ b/build.sh @@ -10,7 +10,9 @@ CC=clang ADDITIONAL_FLAGS='-Wno-unused-function -Wno-unneeded-internal-declaration' WARNINGS='-Wall -Wextra -Wpedantic -Wconversion -Wshadow' -DEBUG_FLAGS="-O0 -g3 $WARNINGS -std=c11" +DEBUG_FLAGS="-O0 -g3 $WARNINGS -std=c11 -DTOC_DEBUG" RELEASE_FLAGS="-O3 -DNDEBUG $WARNINGS -std=c11" -$CC $DEBUG_FLAGS $ADDITIONAL_FLAGS -o toc main.c || exit 1 +COMMAND="$CC $DEBUG_FLAGS $ADDITIONAL_FLAGS -o toc main.c" +echo $COMMAND +$COMMAND || exit 1 diff --git a/main.c b/main.c index 5c2f1f1..b55b70c 100644 --- a/main.c +++ b/main.c @@ -11,7 +11,9 @@ any odd number of "s for a string #include "toc.c" int main(int argc, char **argv) { - allocr_test(); +#ifdef TOC_DEBUG + test_all(); +#endif return 0; if (argc < 2) { fprintf(stderr, "Please specify an input file.\n"); diff --git a/parse.c b/parse.c index 9f7b401..be46485 100644 --- a/parse.c +++ b/parse.c @@ -230,7 +230,7 @@ typedef struct { typedef struct { Tokenizer *tokr; - BlockArr exprs; /* a dynamic array of expressions, so that we don't need to call malloc every time we make an expression */ + Allocator allocr; Block *block; /* which block are we in? NULL = file scope */ } Parser; @@ -432,7 +432,11 @@ static char *type_to_str(Type *t) { allocate a new expression. */ static Expression *parser_new_expr(Parser *p) { - return block_arr_add(&p->exprs); + return allocr_malloc(&p->allocr, sizeof(Expression)); +} + +static void *parser_arr_add(Parser *p, Array *a) { + return arr_adda(a, &p->allocr); } @@ -543,11 +547,11 @@ static bool parse_type(Parser *p, Type *type) { tokr_err(t, "Expected ( for function type."); return false; } - arr_add(&type->fn.types); /* add return type */ + parser_arr_add(p, &type->fn.types); /* add return type */ t->token++; if (!token_is_kw(t->token, KW_RPAREN)) { while (1) { - Type *param_type = arr_add(&type->fn.types); + Type *param_type = parser_arr_add(p, &type->fn.types); if (!parse_type(p, param_type)) return false; if (token_is_kw(t->token, KW_RPAREN)) break; @@ -594,7 +598,7 @@ static bool parse_type(Parser *p, Type *type) { arr_create(&type->tuple, sizeof(Type)); t->token++; /* move past ( */ while (1) { - Type *child = arr_add(&type->tuple); + Type *child = parser_arr_add(p, &type->tuple); if (!parse_type(p, child)) return false; if (token_is_kw(t->token, KW_RPAREN)) { /* we're done with the tuple */ t->token++; /* move past ) */ @@ -649,7 +653,7 @@ static bool parse_block(Parser *p, Block *b) { if (!token_is_kw(t->token, KW_RBRACE)) { /* non-empty block */ while (1) { - Statement *stmt = arr_add(&b->stmts); + Statement *stmt = parser_arr_add(p, &b->stmts); bool success = parse_stmt(p, stmt); if (!success) { ret = false; @@ -700,7 +704,7 @@ static bool parse_decl_list(Parser *p, Array *decls, DeclEndKind decl_end) { !token_is_kw(t->token - 1, KW_RPAREN) && !token_is_kw(t->token - 1, KW_LBRACE)))) { first = false; - Declaration *decl = arr_add(decls); + Declaration *decl = parser_arr_add(p, decls); if (!parse_decl(p, decl, decl_end, PARSE_DECL_ALLOW_CONST_WITH_NO_EXPR)) { ret = false; /* skip to end of param list */ @@ -754,7 +758,7 @@ static bool parse_fn_expr(Parser *p, FnExpr *f) { arr_create(&f->ret_type.tuple, sizeof(Type)); arr_foreach(&f->ret_decls, Declaration, decl) { for (size_t i = 0; i < decl->idents.len; i++) { - Type *tuple_type = arr_add(&f->ret_type.tuple); + Type *tuple_type = parser_arr_add(p, &f->ret_type.tuple); *tuple_type = decl->type; } } @@ -787,7 +791,7 @@ static bool parse_args(Parser *p, Array *args) { info_print(start->where, "This is where the argument list starts."); return false; } - Argument *arg = arr_add(args); + Argument *arg = parser_arr_add(p, args); arg->where = t->token->where; /* named arguments */ if (t->token->kind == TOKEN_IDENT && token_is_kw(t->token + 1, KW_EQ)) { @@ -1367,7 +1371,7 @@ static bool parse_decl(Parser *p, Declaration *d, DeclEndKind ends_with, uint16_ /* OPTIM: Maybe don't use a dynamic array or use parser allocator. */ while (1) { - Identifier *ident = arr_add(&d->idents); + Identifier *ident = parser_arr_add(p, &d->idents); if (t->token->kind != TOKEN_IDENT) { tokr_err(t, "Cannot declare non-identifier (%s).", token_kind_to_str(t->token->kind)); goto ret_false; @@ -1538,7 +1542,7 @@ static bool parse_stmt(Parser *p, Statement *s) { static void parser_from_tokenizer(Parser *p, Tokenizer *t) { p->tokr = t; p->block = NULL; - block_arr_create(&p->exprs, 10, sizeof(Expression)); /* block size = 1024 */ + allocr_create(&p->allocr); } static bool parse_file(Parser *p, ParsedFile *f) { @@ -1546,7 +1550,7 @@ static bool parse_file(Parser *p, ParsedFile *f) { arr_create(&f->stmts, sizeof(Statement)); bool ret = true; while (t->token->kind != TOKEN_EOF) { - Statement *stmt = arr_add(&f->stmts); + Statement *stmt = parser_arr_add(p, &f->stmts); if (!parse_stmt(p, stmt)) ret = false; if (token_is_kw(t->token, KW_RBRACE)) { @@ -1557,6 +1561,11 @@ static bool parse_file(Parser *p, ParsedFile *f) { return ret; } +static void parser_free(Parser *p) { + allocr_free_all(&p->allocr); +} + + #define PARSE_PRINT_LOCATION(l) //fprintf(out, "[l%lu]", (unsigned long)(l).line); /* in theory, this shouldn't be global, but these functions are mostly for debugging anyways */ diff --git a/tests.c b/tests.c new file mode 100644 index 0000000..6b22cd1 --- /dev/null +++ b/tests.c @@ -0,0 +1,53 @@ + +static void allocr_test(void) { + Allocator a; + allocr_create(&a); + for (int x = 1000; x <= 8000; x += 1000) { + int nfoos = x; + int *foos = allocr_malloc(&a, (size_t)nfoos * sizeof(int)); + + for (int i = 0; i < nfoos; i++) + foos[i] = i; + for (int i = 0; i < nfoos; i++) + assert(foos[i] == i); + int nbars = x; + int *bars = allocr_calloc(&a, (size_t)nbars * sizeof(int)); + for (int i = 0; i < nbars; i++) + assert(bars[i] == 0); + for (int i = 0; i < nbars; i++) + bars[i] = i; + for (int i = 0; i < nbars; i++) + assert(bars[i] == i); + } + + int nfoos1 = 5; + int *foos = allocr_realloc(&a, NULL, (size_t)nfoos1 * sizeof(int)); + for (int i = 0; i < nfoos1; i++) + foos[i] = i; + for (int i = 0; i < nfoos1; i++) + assert(foos[i] == i); + + int nfoos2 = 10; + foos = allocr_realloc(&a, foos, (size_t)nfoos2 * sizeof(int)); + for (int i = nfoos1; i < nfoos2; i++) + foos[i] = i; + for (int i = 0; i < nfoos2; i++) + assert(foos[i] == i); + + Array arr; + arr_create(&arr, sizeof(int)); + int n = 1000; + for (int i = 0; i < n; i++) { + *(int *)arr_adda(&arr, &a) = i; + } + int *arr_data = arr.data; + for (int i = 0; i < n; i++) { + assert(arr_data[i] == i); + } + + allocr_free_all(&a); +} + +static void test_all(void) { + allocr_test(); +} diff --git a/toc.c b/toc.c index ac5db05..a4b6ce3 100644 --- a/toc.c +++ b/toc.c @@ -28,3 +28,5 @@ typedef long double Floating; /* OPTIM: Switch to double */ #include "parse.c" #include "eval.c" #include "types.c" + +#include "tests.c" -- cgit v1.2.3