From 64ca7b514abf3f6e1ceb88d96107d87586d7bce0 Mon Sep 17 00:00:00 2001 From: glenrendes Date: Thu, 2 May 2019 15:57:54 +0200 Subject: [PATCH] not done with accounting stuff but better safe than sorry --- module/da/makefile | 1 + module/da/src/#da.lib.h# | 116 +++++++++++++++++++++++++++++++ module/da/src/da.lib.c | 55 +-------------- module/da/src/da.lib.h | 39 ++++++++--- module/da/src/da_na.lib.c | 80 +++++++++++++++++++++ module/da/src/da_na.lib.h | 30 ++++++++ module/da/test/src/test_da.cli.c | 10 +-- module/da/test/src/test_da.lib.c | 12 ++-- module/da/test/src/test_da.lib.h | 2 +- 9 files changed, 269 insertions(+), 76 deletions(-) create mode 100644 module/da/src/#da.lib.h# create mode 100644 module/da/src/da_na.lib.c create mode 100644 module/da/src/da_na.lib.h diff --git a/module/da/makefile b/module/da/makefile index b8832c6..a744187 100644 --- a/module/da/makefile +++ b/module/da/makefile @@ -18,6 +18,7 @@ dep: .PHONY: lib lib: cp $(SRCDIR)/da.lib.h $(INCDIR)/da.h +# cat $(SRCDIR)/da.lib.h $(SRCDIR)/da_na.lib.h > $(INCDIR)/da.h $(MAKE) $@ .PHONY: exec diff --git a/module/da/src/#da.lib.h# b/module/da/src/#da.lib.h# new file mode 100644 index 0000000..7b354e0 --- /dev/null +++ b/module/da/src/#da.lib.h# @@ -0,0 +1,116 @@ +#ifndef DA_LIB_H +#define DA_LIB_H +#include +#include +#include + +typedef struct { + char *base; + char *end; // one byte/one element off the end of the array + size_t size; // size >= (end - base) + 1; + size_t element_size; +} Da; + +//#include "da_na.lib.h" + +#define RETURN(dap, r) \ + { da_free_elements(dap); return r; } + + +void da_alloc(Da *dap, size_t element_size); +void da_free(Da *dap); +void da_rewind(Da *dap); +bool da_empty(Da *dap); +size_t da_length(Da *dap); +void da_rebase(Da *dap, char *old_base, void *pta); +char *da_expand(Da *dap); +bool da_boundq(Da *dap); + +char *da_index(Da *dap, size_t i); +char *da_push_alloc(Da *dap); +char *da_push(Da *dap, void *element); +bool da_pop(Da *dap, void *element); + +bool da_endq(Da *dap, void *pt); +void da_map(Da *dap, void f(void *, void *), void *closure); + +void da_free_elements(Da *dap); + +void da_ints_print(Da *dap, char *sep); +bool da_integer_repeats(Da *dap); +int da_integer_sum(Da *dap); + + +void da_strings_print(Da *dap, char *sep); + +bool da_strings_exists(Da *string_arrp, char *test_string); +void da_strings_set_insert(Da *string_arrp, char *proffered_string, void destruct(void *)); +void da_strings_set_union(Da *string_arrp, Da *proffered_string_arrp, void destruct(void *)); + + +char *da_string_input(Da *dap, FILE *file); +void da_string_push(Da *dap0, char *string); + +void da_cat(Da *dap_base, Da *dap_cat); + +void da_present(Da **dar, int dar_size, void *closure); +bool da_equal(Da *da_el, Da *test_el); +void da_matrix_map(Da **dar, int dar_size, void f(void *,void*), void *closure); + +bool da_exists(Da *dap, bool f(void *, void*), void *closure); +bool da_all(Da *dap, bool f(void *, void*), void *closure); + +//matrix functions +void da_erase(Da *damp); +Da *da_push_row_alloc(Da *damp); +Da *da_push_row(Da *damp, Da *dap); +void da_push_column(Da *damp, Da *dap, void *fill); + +void da_every_row(Da *damp, void f(void *, void *), void *closure); +Da *da_longer(Da *dap0, Da *dap1); +Da *da_longest(Da *damp); +void da_every_column(Da *damp, void f(void *, void *), void *closure); + +Da *da_matrix_transpose(Da *damp, void *fill); + +bool da_length_equal(Da *dap0, Da *dap1); +bool da_all_rows_same_length(Da *damp); +bool da_integer_all_rows_repeat(Da *damp); +bool da_integer_all_columns_repeat(Da *damp); +bool da_integer_repeats_matrix(Da *damp); + +Da *da_integer_transpose(Da *damp, int *fill); +int *da_integer_to_raw_image_matrix(Da *damp, int fill); +int *da_integer_to_raw_image_transpose(Da *damp, int fill); + + +/* +Accounting for all the pointers for which we allocated memory on the heap. + +Replacement for malloc and free that allows us to check if all the memory we allocated was freed, and if all the memory we tried to free was actually allocated by keeping registers of pointers in Da structs. + */ + +#define MALLOC da_malloc_counted +#define FREE da_free_counted +#define ACCOUNT Da heap_acc; \ + Da extra_frees; \ + bool accounting = false; \ + da_start_accounting(heap_acc, extra_frees, accounting); + +#define BALANCE da_result_accounting() +#define CLOSE_ACC da_na_free(&heap_acc); da_na_free(&extra_frees); + +Da heap_acc; Da extra_frees; +void da_start_accounting(Da heap_acc, Da extra_frees, bool acc); +void *da_malloc_counted(size_t mem_size); +void da_free_counted(void *pt); +bool da_result_accounting(void); + +char *da_na_expand(Da *dap); +char *da_na_push_alloc(Da *dap); +char *da_na_push(Da *dap, void *element); +void da_na_free(Da *dap); + + +#endif + diff --git a/module/da/src/da.lib.c b/module/da/src/da.lib.c index e8ec21b..bea8cfb 100644 --- a/module/da/src/da.lib.c +++ b/module/da/src/da.lib.c @@ -10,59 +10,6 @@ Cannot expand an empty array. #include #include - -//------------------------------------------------------------------ -//FREE and MALLOC - -static bool counting = false; -void da_start_heap_counter(){//assigns properties of heap_counter, must be called before other code to be used - heap_count.element_size = sizeof(void *); - heap_count.size = 4*sizeof(void *); - heap_count.base = malloc(heap_count.size); - heap_count.end = heap_count.base; - counting = true; -} -static char *da_count_expand(Da *dap){//these are redefined with malloc instead of MALLOC becuase da_malloc_counted will not make it past the push once heap_count needs to expand - char *old_base = dap->base; - size_t end_offset = dap->end - old_base; - size_t new_size = dap->size << 1; - char *new_base = malloc( new_size ); - memcpy( new_base, old_base, end_offset + dap->element_size); - free(old_base); - dap->base = new_base; - dap->end = new_base + end_offset; - dap->size = new_size; - return old_base; -} -static char *da_count_push_alloc(Da *dap){ - size_t element_off = dap->end - dap->base; - dap->end += dap->element_size; - if( dap->end > dap->base + dap->size ) da_count_expand(dap); - return dap->base + element_off; -} -static char *da_count_push(Da *dap, void *element){ - char *element_pt = da_count_push_alloc(dap); - memcpy(element_pt, element, dap->element_size); - return element_pt; -} -void *da_malloc_counted(size_t mem_size){//pushed pointer onto heap_count - void *temp = malloc(mem_size); - if( counting == true ) da_count_push(&heap_count, temp); - return (void *)temp; -} -void da_free_counted(void *pt){//pops pointer from heap_count - bool flag1 = false;//put here for debugging purposes - if( counting == true ) {flag1 = da_pop(&heap_count, NULL);} - free(pt); -} -//returns false if heap_count is not empty or if it was not being used -bool da_result_heap_counter(){ - if ( counting == true ){ - return heap_count.base == heap_count.end; - } else return false; -} - - //-------------------------------------------------------------------------------- // allocation @@ -80,7 +27,7 @@ void da_rewind(Da *dap){ dap->end = dap->base; } -bool da_emptyq(Da *dap){ +bool da_empty(Da *dap){ return dap->end == dap->base; } diff --git a/module/da/src/da.lib.h b/module/da/src/da.lib.h index 7091565..c82c497 100644 --- a/module/da/src/da.lib.h +++ b/module/da/src/da.lib.h @@ -3,8 +3,6 @@ #include #include #include -#define MALLOC da_malloc_counted -#define FREE da_free_counted typedef struct { char *base; @@ -13,21 +11,16 @@ typedef struct { size_t element_size; } Da; +//#include "da_na.lib.h" + #define RETURN(dap, r) \ { da_free_elements(dap); return r; } -// assuring we freed everything we allocated - -Da heap_count; -void da_start_heap_counter(void); -void *da_malloc_counted(size_t mem_size); -void da_free_counted(void *pt); -bool da_result_heap_counter(void); void da_alloc(Da *dap, size_t element_size); void da_free(Da *dap); void da_rewind(Da *dap); -bool da_emptyq(Da *dap); +bool da_empty(Da *dap); size_t da_length(Da *dap); void da_rebase(Da *dap, char *old_base, void *pta); char *da_expand(Da *dap); @@ -91,6 +84,32 @@ int *da_integer_to_raw_image_matrix(Da *damp, int fill); int *da_integer_to_raw_image_transpose(Da *damp, int fill); +/* +Accounting for all the pointers for which we allocated memory on the heap. + +Replacement for malloc and free that allows us to check if all the memory we allocated was freed, and if all the memory we tried to free was actually allocated by keeping registers of pointers in Da structs. + */ + +#define MALLOC da_malloc_counted +#define FREE da_free_counted +#define ACCOUNT Da heap_acc; \ + Da extra_frees; \ + bool accounting = false; \ + da_start_accounting(heap_acc, extra_frees, accounting); +#define BALANCE da_result_accounting() +#define CLOSE_ACC da_na_free(&heap_acc); da_na_free(&extra_frees); + +Da heap_acc; Da extra_frees; +void da_start_accounting(Da heap_acc, Da extra_frees, bool acc); +void *da_malloc_counted(size_t mem_size); +void da_free_counted(void *pt); +bool da_result_accounting(void); + +char *da_na_expand(Da *dap); +char *da_na_push_alloc(Da *dap); +char *da_na_push(Da *dap, void *element); +void da_na_free(Da *dap); + #endif diff --git a/module/da/src/da_na.lib.c b/module/da/src/da_na.lib.c new file mode 100644 index 0000000..4a3cb53 --- /dev/null +++ b/module/da/src/da_na.lib.c @@ -0,0 +1,80 @@ +#include "da.lib.h" + +#include +#include +#include + +//------------------------------------------------------------------ +//FREE and MALLOC replacement + +static bool accounting = false; +void da_start_accounting(Da heap_acc, Da extra_frees, bool acc){//assigns properties of heap_acc and extra_frees, must be called before other code to be used + heap_acc.element_size = sizeof(void *); + heap_acc.size = 4*sizeof(void *); + heap_acc.base = malloc(heap_acc.size); + heap_acc.end = heap_acc.base; + extra_frees.element_size = sizeof(void *); + extra_frees.size = 4*sizeof(void *); + extra_frees.base = malloc(extra_frees.size); + extra_frees.end = extra_frees.base; + acc = true; +} +void *da_malloc_counted(size_t mem_size){//pushed pointer onto heap_acc + void *temp = malloc(mem_size); + if( accounting == true ) da_na_push(&heap_acc, &temp); + return (void *)temp; +} +void da_free_counted(void *pt){ + if( accounting == true ) { + void *i = heap_acc.base; + bool present = false; + while( i < (void *)heap_acc.end ){ + if( pt == *(void **)i ){//matches and zeroes out pointer from heap_acc + *(int *)i = 0; + present = true; + if( (i + heap_acc.element_size) == heap_acc.end )//pops excess 0s from end + da_pop(&heap_acc, NULL); + } + i++; + } + if( present == false ) da_push(&extra_frees, &pt);//stores pointer in extra_frees if tried to free one that we didn't count + } + free(pt); +} +//returns false if accounting wasn't being used or heap_acc is not empty or if we tried to free more pointers than we malloced for +bool da_result_accounting(){ + if ( accounting == true ){ + bool flag1 = da_empty(&heap_acc); + bool flag2 = da_empty(&extra_frees); + return flag1 && flag2; + } else return false; +} + +//these are redefined with malloc instead of MALLOC because da_malloc_counted will not make it past the push once heap_acc needs to expand +char *da_na_expand(Da *dap){ + char *old_base = dap->base; + size_t end_offset = dap->end - old_base; + size_t new_size = dap->size << 1; + char *new_base = malloc( new_size ); + memcpy( new_base, old_base, end_offset + dap->element_size); + free(old_base); + dap->base = new_base; + dap->end = new_base + end_offset; + dap->size = new_size; + return old_base; +} +char *da_na_push_alloc(Da *dap){ + size_t element_off = dap->end - dap->base; + dap->end += dap->element_size; + if( dap->end > dap->base + dap->size ) da_na_expand(dap); + return dap->base + element_off; +} +char *da_na_push(Da *dap, void *element){ + char *element_pt = da_na_push_alloc(dap); + memcpy(element_pt, element, dap->element_size); + return element_pt; +} +void da_na_free(Da *dap){ + free(dap->base); + dap->size = 0; +} diff --git a/module/da/src/da_na.lib.h b/module/da/src/da_na.lib.h new file mode 100644 index 0000000..426c2fe --- /dev/null +++ b/module/da/src/da_na.lib.h @@ -0,0 +1,30 @@ +/* +Accounting for all the pointers for which we allocated memory on the heap. + +Replacement for malloc and free that allows us to check if all the memory we allocated was freed, and if all the memory we tried to free was actually allocated by keeping registers of pointers in Da structs. + */ + +#ifndef DA_NA_LIB_H +#define DA_NA_LIB_H + +#define MALLOC da_malloc_counted +#define FREE da_free_counted +#define ACCOUNT Da heap_acc; \ + Da extra_frees; \ + bool accounting = false; \ + da_start_accounting(heap_acc, extra_frees, accounting); +#define BALANCE da_result_accounting() +#define CLOSE_ACC da_na_free(&heap_acc); da_na_free(&extra_frees); + +Da heap_acc; Da extra_frees; +void da_start_accounting(Da heap_acc, Da extra_frees, bool acc); +void *da_malloc_counted(size_t mem_size); +void da_free_counted(void *pt); +bool da_result_accounting(void); + +char *da_na_expand(Da *dap); +char *da_na_push_alloc(Da *dap); +char *da_na_push(Da *dap, void *element); +void da_na_free(Da *dap); + +#endif diff --git a/module/da/test/src/test_da.cli.c b/module/da/test/src/test_da.cli.c index 10d0652..515ba55 100644 --- a/module/da/test/src/test_da.cli.c +++ b/module/da/test/src/test_da.cli.c @@ -8,7 +8,6 @@ int main(){ // enumeration of tests typedef bool (*test_fun)(); - da_start_heap_counter(); test_fun tests[] = { test_da_push_0, @@ -30,13 +29,13 @@ int main(){ test_da_all_0, test_da_alloc_0, test_da_free_0, - test_da_emptyq_0, + test_da_empty_0, test_da_length_0, test_da_push_row_0, test_da_erase_0, test_da_longer_0, test_da_longest_0, - da_result_heap_counter, + da_result_accounting, NULL}; char *test_names[] = { @@ -59,16 +58,17 @@ int main(){ "test_da_all_0", "test_da_alloc_0", "test_da_free_0", - "test_da_emptyq_0", + "test_da_empty_0", "test_da_length_0", "test_da_push_row_0", "test_da_erase_0", "test_da_longer_0", "test_da_longest_0", - "da_result_heap_counter", + "da_result_accounting", NULL}; // call tests + ACCOUNT bool da_0_passed = true; unsigned int passed = 0; unsigned int failed = 0; diff --git a/module/da/test/src/test_da.lib.c b/module/da/test/src/test_da.lib.c index f118196..6e9bad6 100644 --- a/module/da/test/src/test_da.lib.c +++ b/module/da/test/src/test_da.lib.c @@ -678,8 +678,8 @@ bool test_da_free_0(){ return flag1 && flag2; } -//tests da_emptyq -bool test_da_emptyq_0(){ +//tests da_empty +bool test_da_empty_0(){ int i = 6; Da da; Da *da_pt = &da; @@ -688,9 +688,9 @@ bool test_da_emptyq_0(){ da_push(da_pt, &i); ++i; } - bool flag1 = !da_emptyq(da_pt); + bool flag1 = !da_empty(da_pt); da_rewind(da_pt); - bool flag2 = da_emptyq(da_pt); + bool flag2 = da_empty(da_pt); da_free(da_pt); return flag1 && flag2; } @@ -873,7 +873,7 @@ bool test_da_longest_0(){ -da_alloc -da_free -da_rewind --da_emptyq +-da_empty -da_length -da_rebase -da_expand @@ -943,7 +943,7 @@ test_da_exists_1 test_da_all_0 test_da_alloc_0 test_da_free_0 -test_da_emptyq_0 +test_da_empty_0 test_da_length_0 //matrix diff --git a/module/da/test/src/test_da.lib.h b/module/da/test/src/test_da.lib.h index 9c9cd32..9a7c33a 100644 --- a/module/da/test/src/test_da.lib.h +++ b/module/da/test/src/test_da.lib.h @@ -20,7 +20,7 @@ bool test_da_exists_1(); bool test_da_all_0(); bool test_da_alloc_0(); bool test_da_free_0(); -bool test_da_emptyq_0(); +bool test_da_empty_0(); bool test_da_length_0(); bool test_da_push_row_0(); bool test_da_erase_0(); -- 2.20.1