From 541bd6a040566da752999c8826c6a637a8bb7d7c Mon Sep 17 00:00:00 2001 From: realtradam Date: Mon, 1 Aug 2022 13:54:20 -0400 Subject: change to single header --- Makefile | 3 +- Readme.mdown | 16 +++++- arraylist.c | 136 ----------------------------------------------- arraylist.h | 20 ------- src/arraylist.h | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ test.c | 128 --------------------------------------------- test/test.c | 130 +++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 306 insertions(+), 287 deletions(-) delete mode 100644 arraylist.c delete mode 100644 arraylist.h create mode 100644 src/arraylist.h delete mode 100644 test.c create mode 100644 test/test.c diff --git a/Makefile b/Makefile index 587a191..aa97c8a 100644 --- a/Makefile +++ b/Makefile @@ -1,3 +1,2 @@ build: - gcc -c arraylist.c -std=c99 -o arraylist.o -Wall - gcc test.c arraylist.o -std=c99 -o apptest -Wall + gcc test/test.c -Isrc -std=c99 -o apptest -Wall diff --git a/Readme.mdown b/Readme.mdown index f5019b3..fbde033 100644 --- a/Readme.mdown +++ b/Readme.mdown @@ -1,3 +1,17 @@ # Arraylist -Generic arraylist implementation in C. WIP. +Generic arraylist single header implementation in C. + +## How to use +Define it in your main file like so: +``` +#define ARRAYLIST_IMPLEMENTATION +#include "arraylist.h" +#undef ARRAYLIST_IMPLEMENTATION +``` +and for any other files you would also like to use it in simply do +``` +#include "arraylist.h" +``` +--- +Define `ARRAYLIST_DEFAULT_SIZE` to a value of your choice to change the default initialized size(number of elements) of an arraylist. diff --git a/arraylist.c b/arraylist.c deleted file mode 100644 index 048299f..0000000 --- a/arraylist.c +++ /dev/null @@ -1,136 +0,0 @@ - -#include -#include -#include -#include "arraylist.h" - -#define PUBLIC /* nothing */ -#define PRIVATE static - -// size doubles whenever it is exceeded -#define ARRAYLIST_DEFAULT_SIZE 4 -//#define ARRAYLIST_DEBUG - -struct array_list_type { - void* data; // the arraylist data - int element_size; - int max_num_elements; - int num_elements; -}; - -PRIVATE bool al_grow(Arraylist* al) { - void* result = realloc( - al->data, - al->max_num_elements * al->element_size * 2 - ); - if(result != NULL) { - al->data = result; - al->max_num_elements *= 2; - return true; - } else { - return false; - } -} - -void al_delete_last(Arraylist *al) { - if(al->num_elements > 0) - al->num_elements -= 1; -} - -bool al_delete_at(Arraylist *al, int position) { - if(position == (al->num_elements - 1)) { - al_delete_last(al); - return true; - } - else if((position >= 0) && (position < al->num_elements)) { - memcpy( - al->data + (position * al->element_size), - al->data + ((position + 1) * al->element_size), - al->element_size * (al->num_elements - position) - ); - al->num_elements -= 1; - return true; - } - printf("Error: deletion out of bounds\n"); - return false; -} - -int al_len(Arraylist* al) { - return al->num_elements; -} - -bool al_allocate_at_least(Arraylist* al, int size) { - if(al->max_num_elements >= size) return true; - void* result = realloc( - al->data, - size * al->element_size - ); - if(result != NULL) { - al->data = result; - al->max_num_elements = size; -#ifdef ARRAYLIST_DEBUG - printf("Grew arraylist to %i\n", al->max_num_elements); -#endif - return true; - } else { - return false; - } -} - - -Arraylist* al_create(int type_size) { - Arraylist* al = malloc(sizeof(Arraylist)); - - al->data = malloc(sizeof(type_size) * ARRAYLIST_DEFAULT_SIZE); - al->element_size = type_size; - al->num_elements = 0; - al->max_num_elements = ARRAYLIST_DEFAULT_SIZE; - - return al; -} - -void al_free(Arraylist* al) { - free(al->data); - free(al); -} - -bool al_push(Arraylist* al, void* item) { - if(al->num_elements >= al->max_num_elements) { - if(!al_grow(al)) { - printf("Error: Failed to grow arraylist to %i\n", al->max_num_elements); - return false; - } -#ifdef ARRAYLIST_DEBUG - printf("Grew arraylist to %i\n", al->max_num_elements); -#endif - } - memcpy( - al->data + (al->num_elements * al->element_size), - item, - al->element_size - ); - al->num_elements += 1; - return true; -} - -void* al_access(Arraylist* al, int position) { - if((position >= al->num_elements) || (position < 0)) - return NULL; - return al->data + (al->element_size * position); -} - -bool al_overwrite_and_delete(Arraylist* al, int source, int target) { - if(source == target) return true; - else if((source >= al->num_elements) || (target >= al->num_elements) || (source < 0) || (target < 0)) { - printf("Error, out of bounds"); - return false; - } - memcpy( - al->data + (target * al->element_size), - al->data + (source * al->element_size), - al->element_size - ); - return al_delete_at(al, source); -} - - diff --git a/arraylist.h b/arraylist.h deleted file mode 100644 index 7a1f08e..0000000 --- a/arraylist.h +++ /dev/null @@ -1,20 +0,0 @@ -#ifndef ARRAYLIST_H -#define ARRAYLIST_H - -#include - -typedef struct array_list_type Arraylist; - -Arraylist* al_create(int type_size); -void al_free(Arraylist* al); -void* al_access(Arraylist* al, int position); -bool al_push(Arraylist* al, void* item); -void al_delete_last(Arraylist* al); -bool al_delete_at(Arraylist *al, int position); -bool al_allocate_at_least(Arraylist* al, int size); -int al_len(Arraylist* al); - -// give 2 indexes, moves source to overwrite the target -bool al_overwrite_and_delete(Arraylist* al, int source, int target); - -#endif diff --git a/src/arraylist.h b/src/arraylist.h new file mode 100644 index 0000000..b7b33ad --- /dev/null +++ b/src/arraylist.h @@ -0,0 +1,160 @@ +#ifndef ARRAYLIST_H +#define ARRAYLIST_H + +#include +#include +#include +#include + +#define PUBLIC /* nothing */ +#define PRIVATE static + +// size doubles whenever it is exceeded +#ifndef ARRAYLIST_DEFAULT_SIZE +#define ARRAYLIST_DEFAULT_SIZE 4 +#endif + +//#define ARRAYLIST_DEBUG + + +typedef struct array_list_type Arraylist; + +Arraylist* al_create(int type_size); +void al_free(Arraylist* al); +void* al_access(Arraylist* al, int position); +bool al_push(Arraylist* al, void* item); +void al_delete_last(Arraylist* al); +bool al_delete_at(Arraylist *al, int position); +bool al_allocate_at_least(Arraylist* al, int size); +int al_len(Arraylist* al); + +// give 2 indexes, moves source to overwrite the target +bool al_overwrite_and_delete(Arraylist* al, int source, int target); + +#ifdef ARRAYLIST_IMPLEMENTATION + +struct array_list_type { + void* data; // the arraylist data + int element_size; + int max_num_elements; + int num_elements; +}; + +PRIVATE bool al_grow(Arraylist* al) { + void* result = realloc( + al->data, + al->max_num_elements * al->element_size * 2 + ); + if(result != NULL) { + al->data = result; + al->max_num_elements *= 2; + return true; + } else { + return false; + } +} + +void al_delete_last(Arraylist *al) { + if(al->num_elements > 0) + al->num_elements -= 1; +} + +bool al_delete_at(Arraylist *al, int position) { + if(position == (al->num_elements - 1)) { + al_delete_last(al); + return true; + } + else if((position >= 0) && (position < al->num_elements)) { + memcpy( + (char*)al->data + (position * al->element_size), + (char*)al->data + ((position + 1) * al->element_size), + al->element_size * (al->num_elements - position) + ); + al->num_elements -= 1; + return true; + } + printf("Error: deletion out of bounds\n"); + return false; +} + +int al_len(Arraylist* al) { + return al->num_elements; +} + +bool al_allocate_at_least(Arraylist* al, int size) { + if(al->max_num_elements >= size) return true; + void* result = realloc( + al->data, + size * al->element_size + ); + if(result != NULL) { + al->data = result; + al->max_num_elements = size; +#ifdef ARRAYLIST_DEBUG + printf("Grew arraylist to %i\n", al->max_num_elements); +#endif + return true; + } else { + return false; + } +} + + +Arraylist* al_create(int type_size) { + Arraylist* al = (Arraylist*)malloc(sizeof(Arraylist)); + + al->data = malloc(sizeof(type_size) * ARRAYLIST_DEFAULT_SIZE); + al->element_size = type_size; + al->num_elements = 0; + al->max_num_elements = ARRAYLIST_DEFAULT_SIZE; + + return al; +} + +void al_free(Arraylist* al) { + free(al->data); + free(al); +} + +bool al_push(Arraylist* al, void* item) { + if(al->num_elements >= al->max_num_elements) { + if(!al_grow(al)) { + printf("Error: Failed to grow arraylist to %i\n", al->max_num_elements); + return false; + } +#ifdef ARRAYLIST_DEBUG + printf("Grew arraylist to %i\n", al->max_num_elements); +#endif + } + memcpy( + (char*)al->data + (al->num_elements * al->element_size), + item, + al->element_size + ); + al->num_elements += 1; + return true; +} + +void* al_access(Arraylist* al, int position) { + if((position >= al->num_elements) || (position < 0)) + return NULL; + return (char*)al->data + (al->element_size * position); +} + +bool al_overwrite_and_delete(Arraylist* al, int source, int target) { + if(source == target) return true; + else if((source >= al->num_elements) || (target >= al->num_elements) || (source < 0) || (target < 0)) { + printf("Error, out of bounds"); + return false; + } + memcpy( + (char*)al->data + (target * al->element_size), + (char*)al->data + (source * al->element_size), + al->element_size + ); + return al_delete_at(al, source); +} + + +#endif +#endif diff --git a/test.c b/test.c deleted file mode 100644 index 6216586..0000000 --- a/test.c +++ /dev/null @@ -1,128 +0,0 @@ -#include - -#include "arraylist.h" - -bool test_match(Arraylist* al, int answer_key[], int answer_key_size) { - if(al_len(al) != answer_key_size) { - printf("test failed\n"); - printf("unexpected array size\n"); - printf("Expected: %d\n", answer_key_size); - printf("Got: %d\n", al_len(al)); - - return false; - } - for(int i = 0; i < al_len(al); i += 1) { - printf("%d == %d\n", answer_key[i], *(int*)al_access(al, i)); - if(answer_key[i] != *(int*)al_access(al, i)){ - printf("test failed\n"); - printf("Expected: %d\n", answer_key[i]); - printf("Got: %d\n", *(int*)al_access(al, i)); - return false; - } - } - return true; -} - -int main() { - Arraylist* test_list = al_create(sizeof(int)); - - int a = 0; - - printf("testing 1025 integer elements\n"); - for(int i = 0; i < 1025; i += 1) { - a += 3; - al_push(test_list, &a); - /*printf("pushed element %i\n", a); - printf( - "read element %i\n", - *(int*)al_access(test_list,i) - );*/ - } - a = 0; - for(int i = 0; i < 1025; i += 1) { - a += 3; - if(a != *(int*)al_access(test_list, i)){ - printf("failed\n"); - return 1; - } - } - printf("test passed\n"); - - printf("testing resizing arraylist\n"); - al_allocate_at_least(test_list, 4096); - printf("test passed\n"); - - printf("testing deallocating arraylist\n"); - al_free(test_list); - printf("test passed\n"); - - printf("testing deletion\n"); - test_list = al_create(sizeof(int)); - a = 0; - for(int i = 0; i < 5; i += 1) { - a += 1; - al_push(test_list, &a); - } - printf("delete middle element:\n"); - al_delete_at(test_list, 2); - { - int answer_key[] = { 1, 2, 4, 5 }; - if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) - return false; - } - printf("passed\n"); - printf("delete first element:\n"); - al_delete_at(test_list, 0); - { - int answer_key[] = { 2, 4, 5 }; - if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) - return false; - } - printf("passed\n"); - printf("delete last element:\n"); - al_delete_at(test_list, 2); - { - int answer_key[] = { 2, 4 }; - if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) - return false; - } - printf("passed\n"); - printf("try to delete out of bounds\n"); - if(al_delete_at(test_list, 64)){ - printf("Should of errored but did not\n"); - } - printf("passed\n"); - - a = 3; - al_push(test_list, &a); - printf("test editing existing element\n"); - *(int*)al_access(test_list, 1) = 7; - { - int answer_key[] = { 2, 7, 3 }; - if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) - return false; - } - - a = 20; - al_push(test_list, &a); - printf("test overwrite and delete\n"); - al_overwrite_and_delete(test_list, al_len(test_list)-1, 1); - { - int answer_key[] = { 2, 20, 3 }; - if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) - return false; - } - al_overwrite_and_delete(test_list, 1, 0); - { - int answer_key[] = { 20, 3 }; - if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) - return false; - } - - - - printf("test passed\n"); - - printf("all tests passed\n"); - return 0; -} diff --git a/test/test.c b/test/test.c new file mode 100644 index 0000000..9399409 --- /dev/null +++ b/test/test.c @@ -0,0 +1,130 @@ +#include + +#define ARRAYLIST_IMPLEMENTATION +#include "arraylist.h" +#undef ARRAYLIST_IMPLEMENTATION + +bool test_match(Arraylist* al, int answer_key[], int answer_key_size) { + if(al_len(al) != answer_key_size) { + printf("test failed\n"); + printf("unexpected array size\n"); + printf("Expected: %d\n", answer_key_size); + printf("Got: %d\n", al_len(al)); + + return false; + } + for(int i = 0; i < al_len(al); i += 1) { + printf("%d == %d\n", answer_key[i], *(int*)al_access(al, i)); + if(answer_key[i] != *(int*)al_access(al, i)){ + printf("test failed\n"); + printf("Expected: %d\n", answer_key[i]); + printf("Got: %d\n", *(int*)al_access(al, i)); + return false; + } + } + return true; +} + +int main() { + Arraylist* test_list = al_create(sizeof(int)); + + int a = 0; + + printf("testing 1025 integer elements\n"); + for(int i = 0; i < 1025; i += 1) { + a += 3; + al_push(test_list, &a); + /*printf("pushed element %i\n", a); + printf( + "read element %i\n", + *(int*)al_access(test_list,i) + );*/ + } + a = 0; + for(int i = 0; i < 1025; i += 1) { + a += 3; + if(a != *(int*)al_access(test_list, i)){ + printf("failed\n"); + return 1; + } + } + printf("test passed\n"); + + printf("testing resizing arraylist\n"); + al_allocate_at_least(test_list, 4096); + printf("test passed\n"); + + printf("testing deallocating arraylist\n"); + al_free(test_list); + printf("test passed\n"); + + printf("testing deletion\n"); + test_list = al_create(sizeof(int)); + a = 0; + for(int i = 0; i < 5; i += 1) { + a += 1; + al_push(test_list, &a); + } + printf("delete middle element:\n"); + al_delete_at(test_list, 2); + { + int answer_key[] = { 1, 2, 4, 5 }; + if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) + return false; + } + printf("passed\n"); + printf("delete first element:\n"); + al_delete_at(test_list, 0); + { + int answer_key[] = { 2, 4, 5 }; + if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) + return false; + } + printf("passed\n"); + printf("delete last element:\n"); + al_delete_at(test_list, 2); + { + int answer_key[] = { 2, 4 }; + if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) + return false; + } + printf("passed\n"); + printf("try to delete out of bounds\n"); + if(al_delete_at(test_list, 64)){ + printf("Should of errored but did not\n"); + } + printf("passed\n"); + + a = 3; + al_push(test_list, &a); + printf("test editing existing element\n"); + *(int*)al_access(test_list, 1) = 7; + { + int answer_key[] = { 2, 7, 3 }; + if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) + return false; + } + + a = 20; + al_push(test_list, &a); + printf("test overwrite and delete\n"); + al_overwrite_and_delete(test_list, al_len(test_list)-1, 1); + { + int answer_key[] = { 2, 20, 3 }; + if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) + return false; + } + al_overwrite_and_delete(test_list, 1, 0); + { + int answer_key[] = { 20, 3 }; + if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key))) + return false; + } + + + + printf("test passed\n"); + + printf("all tests passed\n"); + return 0; +} -- cgit v1.2.3