From 8483f582afac052919c83a23fbb33839a836c67d Mon Sep 17 00:00:00 2001 From: glenrendes Date: Thu, 18 Apr 2019 22:54:38 +0200 Subject: [PATCH] da_exists and da_all with tests --- module/da/src/#da.lib.c# | 311 ------------------------------- module/da/src/da.lib.c | 30 +-- module/da/src/da.lib.h | 4 + module/da/test/src/test_da.cli.c | 8 +- module/da/test/src/test_da.lib.c | 70 ++++++- 5 files changed, 89 insertions(+), 334 deletions(-) delete mode 100644 module/da/src/#da.lib.c# diff --git a/module/da/src/#da.lib.c# b/module/da/src/#da.lib.c# deleted file mode 100644 index f370cd2..0000000 --- a/module/da/src/#da.lib.c# +++ /dev/null @@ -1,311 +0,0 @@ -/* -Dynamic Array - -Cannot expand an empty array. - -*/ -#include "da.lib.h" - -#include -#include -#include - -//-------------------------------------------------------------------------------- -// allocation - -void da_alloc(Da *dap, size_t element_size){ - dap->element_size = element_size; - dap->size = 4 * element_size; - dap->base = malloc(dap->size); - dap->end = dap->base; -} -void da_free(Da *dap){ - free(dap->base); - dap->size = 0; -} -void da_rewind(Da *dap){ - dap->end = dap->base; -} - -bool da_emptyq(Da *dap){ - return dap->end == dap->base; -} - -size_t da_length(Da *dap){ - return (dap->end - dap->base)/dap->element_size; -} - -void da_rebase(Da *dap, char *old_base, void *pta){ - char **pt = (char **)pta; - size_t offset = *pt - old_base; - *pt = dap->base + offset; -} - -// Doubles size of of da. Returns old base, so that existing pointers into the -// array can be moved to the new array -char *da_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; -} - -// true when end has run off the allocated area -bool da_boundq(Da *dap){ - return dap->end > (dap->base + dap->size); -} - -//-------------------------------------------------------------------------------- -// putting/taking items - -char *da_index(Da *dap, size_t i){ - size_t offset = i * dap->element_size; - char *pt = dap->base + offset; - return pt; -} - -// allocate space for a new element at the end of the array -char *da_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_expand(dap); - return dap->base + element_off; -} - -char *da_push(Da *dap, void *element){ - char *element_pt = da_push_alloc(dap); - memcpy(element_pt, element, dap->element_size); - return element_pt; -} - -bool da_pop(Da *dap, void *element){ - bool flag = dap->end >= dap->base + dap->element_size; - if( flag ){ - dap->end -= dap->element_size; - if(element) memcpy(element, dap->end, dap->element_size); - } - return flag; -} - -//-------------------------------------------------------------------------------- -// iteration - -// true when pt has run off the end -bool da_endq(Da *dap, void *pt){ - return (char *)pt >= dap->end; -} - -// passed in f(element_pt, arg_pt) -// We have no language support closures, so we pass in an argument for it. -// The closure may be set to NULL if it is not needed. -void da_map(Da *dap, void f(void *, void *), void *closure){ - char *pt = dap->base; - while( pt != dap->end ){ - f(pt, closure); - pt += dap->element_size; - } -} - - -//-------------------------------------------------------------------------------- -// da being used as a resource manager - - -// elements were malloced, now they will all be freed -static void da_free_element(void *pt, void *closure){ - free(*(char **)pt); // free does not care about the pointer type -} - -void da_free_elements(Da *dap){ - da_map(dap, da_free_element, NULL); - da_rewind(dap); -} - -//-------------------------------------------------------------------------------- -// da is an array of integers - -// would like to pass in the printf format to make a general print -// but can't get *pt on the stack for the printf call .. hmmm -void da_ints_print(Da *dap, char *sep){ - char *pt = dap->base; // char * because it points to a byte in the array - if( pt < dap->end ){ - printf("%u", *(int *)pt); - pt += dap->element_size; - while( pt < dap->end ){ - printf("%s%u", sep, *(int *)pt); - pt += dap->element_size; - }}} - - -//-------------------------------------------------------------------------------- -// da is an array of strings - -// for the case of an array of strings -void da_strings_print(Da *dap, char *sep){ - char *pt = dap->base; // char * because it points to a byte in the array - if( pt < dap->end ){ - fputs(*(char **)pt, stdout); - pt += dap->element_size; - while( pt < dap->end ){ - fputs(sep,stdout); - fputs(*(char **)pt,stdout); - pt += dap->element_size; - }}} - -// da is an array of strings, true if the test string is in the array -// might be better to iterate instead of using a map ... -typedef struct { - char *string; - bool found; -} da_strings_exists_closure; -static void string_equal(void *sp, void *closure){ - char *string_element = *(char **)sp; - da_strings_exists_closure *ss = (da_strings_exists_closure *)closure; - if( ss->found ) return; - ss->found = !strcmp(string_element, ss->string); - return; -} - -bool da_strings_exists(Da *string_arrp, char *test_string){ - da_strings_exists_closure sec; - sec.string = test_string; - sec.found = false; - da_map(string_arrp, string_equal, &sec); - return sec.found; -} - -void da_strings_set_insert(Da *string_arrp, char *proffered_string, void destruct(void *)){ - if( da_strings_exists( string_arrp, proffered_string)){ // then throw it away, we don't need it - if(destruct)destruct(proffered_string); - return; - } - da_push(string_arrp, &proffered_string); -} - -// union -void da_strings_set_union(Da *string_arrp, Da *proffered_string_arrp, void destruct(void *)){ - char *pt = proffered_string_arrp->base; - while( pt < proffered_string_arrp->end ){ - da_strings_set_insert(string_arrp, *(char **)pt, destruct); - pt += proffered_string_arrp->element_size; - } - return; -} - - -//-------------------------------------------------------------------------------- -// the da itself is a string - -// Puts text from a line into buffer *dap. Does not push EOF or '\n' into the -// buffer. Returns the old_base so that external pointers can be rebased. -// It is possible that the the base hasn't changed. Use feof(FILE *stream) to -// test for EOF; -char *da_string_input(Da *dap, FILE *file){ - char *old_base = dap->base; - int c = fgetc(file); - while( c != EOF && c != '\n' ){ - da_push(dap, &c); - c = fgetc(file); - } - int terminator = 0; - da_push(dap, &terminator); - return old_base; -} - -void da_string_push(Da *dap0, char *string){ - if(!*string) return; - size_t dap0_size = dap0->end - dap0->base; - size_t string_size = strlen(string); - dap0->end += string_size; - while( dap0->end >= dap0->base + dap0->size ) da_expand(dap0); - memcpy(dap0->base + dap0_size, string, string_size); -} - - -//-------------------------------------------------------------------------------- -// list operations - -// If dap0 has had a terminatating zero added, that must be popped off before -// the call. Similarly if a terminating zero is desired, it should be pushed -// after the call. - -// appends contents of dap1 onto dap0 -void da_cat(Da *dap0, Da *dap1){ - if(dap1->base == dap1->end) return; - size_t dap0_size = dap0->end - dap0->base; - size_t dap1_size = dap1->end - dap1->base; // size of the active portion - dap0->end += dap1_size; - while( dap0->end >= dap0->base + dap0->size ) da_expand(dap0); - memcpy(dap0->base + dap0_size, dap1->base, dap1_size); -} - -//array of Das - -//∃, OR map -//checks that some Da is present in Da of Das - -typedef struct{ - Da *da; - bool found; -} da_present_closure; - -void da_present(Da **dar, int dar_size, void *closure){ - Da **pt = dar; - da_present_closure *dpc = (da_present_closure *)closure; - Da *test_element = dpc->da; - int i = 0; - while (!dpc->found && i < dar_size){ - dpc->found = da_equal(*pt, test_element); - pt++; - i++; - } - return; -} - -bool da_equal(Da *da_el, Da *test_el){ - bool f1 = da_el->base == test_el->base; - bool f2 = da_el->end == test_el->end; - bool f3 = da_el->size == test_el->size; - bool f4 = da_el->element_size == test_el->element_size; - return f1 && f2 && f3 && f4; -}//may need to be static? - - - -void da_matrix_map(Da **dar, int dar_size, void f(void *, void *), void *closure){ - Da **pt = dar; - int i = 0; - while( i < dar_size ){ - f(*pt, closure); - pt++; - i++; - } - return; -} - -//∀, AND map -//checks that all Das are present in Da of Das - - - - -/*bool da_all (Da **dar, int dar_size, Da **dap){ - Da **tdar = dap; - Da *test_da = *tdar; - bool result = true; - int i = 0; - while(result && (i < dar_size)){ - result = da_exists(dar, dar_size, test_da); - tdar++; - test_da = *tdar; - i++; - } - return result; -} -*/ diff --git a/module/da/src/da.lib.c b/module/da/src/da.lib.c index f370cd2..d00b9e1 100644 --- a/module/da/src/da.lib.c +++ b/module/da/src/da.lib.c @@ -289,23 +289,25 @@ void da_matrix_map(Da **dar, int dar_size, void f(void *, void *), void *closure return; } -//∀, AND map -//checks that all Das are present in Da of Das - - +//∃, OR map +bool da_exists(Da *dap, bool f(void *, void*), void *closure){ + char *pt = dap->base; + bool result = false; + while( !result && (pt != dap->end) ){ + result = f(pt, closure); + pt += dap->element_size; + } + return result; +} -/*bool da_all (Da **dar, int dar_size, Da **dap){ - Da **tdar = dap; - Da *test_da = *tdar; +//∀, AND map +bool da_all(Da *dap, bool f(void *, void*), void *closure){ + char *pt = dap->base; bool result = true; - int i = 0; - while(result && (i < dar_size)){ - result = da_exists(dar, dar_size, test_da); - tdar++; - test_da = *tdar; - i++; + while( result && (pt != dap->end) ){ + result = f(pt, closure); + pt += dap->element_size; } return result; } -*/ diff --git a/module/da/src/da.lib.h b/module/da/src/da.lib.h index a721f14..d38194c 100644 --- a/module/da/src/da.lib.h +++ b/module/da/src/da.lib.h @@ -51,6 +51,10 @@ 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); + /* bool da_exists(Da **dar, int dar_size, Da *dap); bool da_all(Da **dar, int dar_size, int dap_size, Da **dap); diff --git a/module/da/test/src/test_da.cli.c b/module/da/test/src/test_da.cli.c index 786931c..92a26a3 100644 --- a/module/da/test/src/test_da.cli.c +++ b/module/da/test/src/test_da.cli.c @@ -27,8 +27,8 @@ int main(){ test_da_boundq_0, test_da_map_0, test_da_present_0, - //test_da_exists_0, - //test_da_all_0, + test_da_exists_0, + test_da_all_0, NULL}; char *test_names[] = { @@ -46,8 +46,8 @@ int main(){ "test_da_boundq_0", "test_da_map_0", "test_da_present_0", - //"test_da_exists_0", - //"test_da_all_0", + "test_da_exists_0", + "test_da_all_0", NULL}; // call tests diff --git a/module/da/test/src/test_da.lib.c b/module/da/test/src/test_da.lib.c index b540878..d13979b 100644 --- a/module/da/test/src/test_da.lib.c +++ b/module/da/test/src/test_da.lib.c @@ -474,8 +474,67 @@ bool test_da_present_0(){ return result; } +bool test_exists(void *pt, void *closure){ + bool result = *(int*)pt == *(int *)closure; + return result; +} + +//test da_exists +bool test_da_exists_0(){ + Da dar; + Da *dar_pt = &dar; + da_alloc(dar_pt, sizeof(int)); + + int i[5] = {5,6,7,8,9}; + + {//pushes ints 5-8 onto dar + int j = 0; + while (j < 4){ + int *i_pt = &i[j]; + da_push(dar_pt, i_pt); + j++; + } + } + + bool f[5]; + {//tests da_exists + int j = 0; + while(j < 5){ + int *i_pt = &i[j]; + f[j] = da_exists(dar_pt, test_exists, i_pt); + j++; + } + } + + bool result = f[0] && f[1] && f[2] && f[3] && !f[4]; + + return result; +} + +//test da_all +bool test_da_all_0(){ +Da dar; + Da *dar_pt = &dar; + da_alloc(dar_pt, sizeof(int)); + int i = 5; + int *i_pt = &i; + //push 5 onto dar 4 times + da_push(dar_pt, i_pt); + da_push(dar_pt, i_pt); + da_push(dar_pt, i_pt); + da_push(dar_pt, i_pt); + + //tests da_all is true + bool f1 = da_all(dar_pt, test_exists, i_pt); + da_pop(dar_pt, NULL); + i = 6; + //tests da_all is false + bool f2 = !da_all(dar_pt, test_exists, i_pt); + + return f1 && f2; +} /* Functions @@ -493,18 +552,18 @@ da_push_alloc -da_push -da_pop da_endq --da_map Had to put da_test_map function in da src code... +-da_map da_free_elements da_ints_print da_strings_print -da_strings_exists +-da_strings_exists da_strings_set_insert da_strings_set_union -da_string_input da_string_push -da_cat -da_exists -da_all +-da_exists +-da_all */ @@ -524,5 +583,6 @@ test_da_rebase_0 test_da_boundq_0 test_da_map_0 test_da_present_0 - +test_da_exists_0 +test_da_all_0 */ -- 2.20.1