diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | README.md | 1 | ||||
| -rw-r--r-- | include/moslib/ds/array.h | 120 | ||||
| -rw-r--r-- | include/moslib/tester.h | 6 | ||||
| -rw-r--r-- | src/ds/array.c | 184 | ||||
| -rw-r--r-- | tests/ds/array_tests.c | 33 |
6 files changed, 281 insertions, 67 deletions
@@ -1,6 +1,6 @@ CC=gcc -CFLAGS=-std=c99 -Wall -Wextra -fPIC -I./include -O2 -s -CFLAGS_TEST=-std=c99 -Wall -Wextra -Og -ggdb +CFLAGS=-std=c99 -Wall -Wextra -Wpointer-arith -fPIC -I./include -O2 -s +CFLAGS_TEST=-std=c99 -Wall -Wextra -Wpointer-arith -Og -ggdb AR=ar rcs both: shared static clean @@ -6,3 +6,4 @@ Defnitely not the best implementations ever made, but they're mine, so idc. ## Contains: - memory management helpers - testing framework +- dynamic array implementation diff --git a/include/moslib/ds/array.h b/include/moslib/ds/array.h index 41164c5..ac8b9f9 100644 --- a/include/moslib/ds/array.h +++ b/include/moslib/ds/array.h @@ -47,18 +47,18 @@ // // To put into specific index (and update if value exists) use: // -// size_t zerod = arr_put(array, i, item); +// size_t index = arr_put(array, i, item); // +// It returns the index of the newly put item // If index is greater or equal to array length it will extend the length to the put item and it will // zero all items between previously last item to the new item. -// It returns the count of items that were zerod that way. // // If you want to add more items than 1 at once, you can use these: // // size_t index = arr_append_n(array, items, n_items); // size_t index = arr_push_n(array, items, n_items); // size_t index = arr_insert_n(array, i, items, n_items); -// size_t zerod = arr_put_n(array, i, items, n_items); +// size_t index = arr_put_n(array, i, items, n_items); // // They work the same way as their counterparts without n, but accept an array of items instead. // @@ -70,15 +70,15 @@ // // First array will be the destination. // Returns index of the first item of array2 in array1. +// If array 2 is NULL or has length 0 - returns (size_t)-1. // // ---------------------------------------------------------------------------------------------------- // -// To delete item from an array at specific index and retrieve it you can use: +// To delete and retrieve the last item from an array use: // -// T item = arr_pop_i(array, i); -// T item = arr_pop(array); // same as arr_pop_i(array, arr_len(array)-1) +// T item = arr_pop(array); // -// No bounds checking, so it may return garbage or segfault. +// No bounds checking, so it may return garbage or segfault if the array is empty. // // You can just delete items on given index with: // @@ -165,7 +165,6 @@ #define arr_insert_n mos_arr_insert_n #define arr_put_n mos_arr_put_n #define arr_concat mos_arr_concat -#define arr_pop_i mos_arr_pop_i #define arr_pop mos_arr_pop #define arr_del mos_arr_del #define arr_del_n mos_arr_del_n @@ -195,7 +194,7 @@ // // Returns: // pointer to the item or NULL if i is out of bounds -#define mos_arr_get(arr, i) ((arr) ? (arr) : NULL) +#define mos_arr_get(arr, i) ((size_t)(i) < mos_arr_len(arr) ? (arr) + (size_t)(i) : NULL) // Get a pointer to the first item in the array // @@ -205,7 +204,7 @@ // // Returns: // pointer to the first item or NULL if array is empty -#define mos_arr_first(arr) NULL +#define mos_arr_first(arr) (mos_arr_len(arr) == 0 ? NULL : (arr)) // Get a pointer to the last item in the array // @@ -215,7 +214,9 @@ // // Returns: // pointer to the last item or NULL if array is empty -#define mos_arr_last(arr) NULL +#define mos_arr_last(arr) (mos_arr_len(arr) == 0 ? NULL : (arr) + mos_arr_len(arr) - 1) + +// clang-format off // Append a given item to the array // @@ -229,8 +230,12 @@ // // Returns: // index of the appended item -#define mos_arr_append(arr, ...) (!(arr) ? (arr) = mos_safe_malloc(sizeof(*(arr))) : 0, *(arr) = (__VA_ARGS__)) #define mos_arr_push mos_arr_append +#define mos_arr_append(arr, ...) ( \ + mos_arr_append_fn(&(arr), sizeof(*(arr))), \ + (arr)[mos_arr_len(arr) - 1] = __VA_ARGS__, \ + mos_arr_len(arr) - 1 \ +) // Insert a given item at the specific position in the array // Move everything after it to the right @@ -249,7 +254,15 @@ // // Returns: // index of the inserted item -#define mos_arr_insert(arr, i, ...) 0 +#define mos_arr_insert(arr, i, ...) ( \ + (size_t)(i) >= mos_arr_len(arr) ? ( \ + mos_arr_append(arr, __VA_ARGS__) \ + ) : ( \ + mos_arr_insert_fn(&(arr), i, sizeof(*(arr))), \ + (arr)[(size_t)(i)] = __VA_ARGS__, \ + (size_t)(i) \ + ) \ +) // Put a given item at the specific position in the array // If index is within array bounds - it overwrites the item at given spot @@ -268,8 +281,14 @@ // variadic to make things like (struct T){1,1} work properly // // Returns: -// count of zerod items -#define mos_arr_put(arr, i, ...) 0 +// index of the put item +#define mos_arr_put(arr, i, ...) ( \ + mos_arr_put_fn(&(arr), i, sizeof(*(arr))), \ + (arr)[(size_t)(i)] = __VA_ARGS__, \ + (size_t)(i) \ +) + +// clang-format on // Append n given items to the array // @@ -285,8 +304,8 @@ // // Returns: // index of the first appended item -#define mos_arr_append_n(arr, items, n) (!(arr) ? (arr) = mos_safe_malloc(sizeof(*(arr))) : 0, *(arr) = (items)[0]) #define mos_arr_push_n mos_arr_append_n +#define mos_arr_append_n(arr, items, n) mos_arr_append_n_fn(&(arr), items, n, sizeof(*(arr))) // Insert n given items at the specific position in the array // Move everything after them to the right @@ -307,7 +326,7 @@ // // Returns: // index of the first inserted item -#define mos_arr_insert_n(arr, i, items, n) 0 +#define mos_arr_insert_n(arr, i, items, n) mos_arr_insert_n_fn(&(arr), i, items, n, sizeof(*(arr))) // Put n given items at the specific position in the array // If index is within array bounds - it overwrites the items at given spots @@ -328,8 +347,8 @@ // count of items to put // // Returns: -// count of zerod items -#define mos_arr_put_n(arr, i, items, n) 0 +// index of the first put item +#define mos_arr_put_n(arr, i, items, n) mos_arr_put_n_fn(&(arr), i, items, n, sizeof(*(arr))) // Concatenate two dynamic arrays of the same type // @@ -341,23 +360,8 @@ // array to concatenate (source) // // Returns: -// index of the first new item in arr1 -#define mos_arr_concat(arr1, arr2) 0 - -// Delete and retrieve an item at specific index from the array -// Moves items after deleted one to the left -// No bounds checking -// -// Arguments: -// arr -// array to pop from -// -// i -// index of the item to pop -// -// Returns: -// the popped item -#define mos_arr_pop_i(arr, i) (arr)[0] +// index of the first new item in arr1 or (size_t)-1 if arr2 is NULL or has length 0 +#define mos_arr_concat(arr1, arr2) mos_arr_concat_fn(&(arr1), arr2, sizeof(*(arr1))) // Delete and retrieve the last item from the array // No bounds checking @@ -368,7 +372,7 @@ // // Returns: // the popped item -#define mos_arr_pop(arr) (arr)[0] +#define mos_arr_pop(arr) (mos_arr_del_back(arr, 1), (arr)[mos_arr_len(arr)]) // Delete an item at specific index from the array // Moves items after deleted one to the left @@ -382,7 +386,7 @@ // // Returns: // 1 if item was deleted, 0 if it failed (e.g. out of bounds) -#define mos_arr_del(arr, i) 0 +#define mos_arr_del(arr, i) mos_arr_del_fn(arr, i, sizeof(*(arr))) // Delete n consecutive items at specific index from the array // Moves items after deleted ones to the left @@ -399,7 +403,7 @@ // // Returns: // count of deleted items -#define mos_arr_del_n(arr, i, n) 0 +#define mos_arr_del_n(arr, i, n) mos_arr_del_n_fn(arr, i, n, sizeof(*(arr))) // Delete n first items from the array // Moves items after deleted ones to the left @@ -413,7 +417,7 @@ // // Returns: // count of deleted items -#define mos_arr_del_front(arr, n) 0 +#define mos_arr_del_front(arr, n) mos_arr_del_front_fn(arr, n, sizeof(*(arr))) // Delete n last items from the array // @@ -426,7 +430,7 @@ // // Returns: // count of deleted items -#define mos_arr_del_back(arr, n) 0 +#define mos_arr_del_back(arr, n) mos_arr_del_back_fn(arr, n) // Get the pointer to the previous item in the array from the pointer to the current one // If pointer is NULL - gets the last item from the array @@ -440,7 +444,7 @@ // // Returns: // pointer to the previous item or NULL if there's no more items -#define mos_arr_prev(arr, curr) NULL +#define mos_arr_prev(arr, curr) (mos_arr_len(arr) == 0 ? NULL : (!(curr) ? mos_arr_last(arr) : ((curr) == (arr) ? NULL : (curr) - 1))) // Get the pointer to the next item in the array from the pointer to the current one // If pointer is NULL - gets the first item from the array @@ -454,7 +458,7 @@ // // Returns: // pointer to the next item or NULL if there's no more items -#define mos_arr_next(arr, curr) NULL +#define mos_arr_next(arr, curr) (mos_arr_len(arr) == 0 ? NULL : (!(curr) ? (arr) : ((curr) == mos_arr_last(arr) ? NULL : (curr) + 1))) // Get the length of the array // @@ -464,7 +468,7 @@ // // Returns: // length of the array -#define mos_arr_len(arr) 0 +extern size_t mos_arr_len(void *arr); // Set the length of the array // If it's bigger than current length - it will zero new items @@ -479,7 +483,7 @@ // // Returns: // count of the deleted items -#define mos_arr_set_len(arr, len) 0 +#define mos_arr_set_len(arr, len) mos_arr_set_len_fn(&(arr), len, sizeof(*(arr))) // Get the capacity of the array // @@ -489,7 +493,7 @@ // // Returns: // capacity of the array -#define mos_arr_cap(arr) 0 +extern size_t mos_arr_cap(void *arr); // Set the capacity of the array // If it's lower than current length - it will set the capacity equal to length @@ -503,13 +507,33 @@ // // Returns: // new capacity of the array -#define mos_arr_set_cap(arr, cap) 0 +#define mos_arr_set_cap(arr, cap) mos_arr_set_cap_fn(&(arr), cap, sizeof(*(arr))) // Free the array // // Arguments: // arr // array to free -#define mos_arr_free(arr) void +extern void mos_arr_free(void *arr); + +typedef struct { + size_t len; + size_t cap; +} MosArrHeader; + +// Function prototypes for macros +extern void mos_arr_append_fn(void *p_arr, size_t el_size); +extern void mos_arr_insert_fn(void *p_arr, size_t i, size_t el_size); +extern void mos_arr_put_fn(void *p_arr, size_t i, size_t el_size); +extern size_t mos_arr_append_n_fn(void *p_arr, void *items, size_t n, size_t el_size); +extern size_t mos_arr_insert_n_fn(void *p_arr, size_t i, void *items, size_t n, size_t el_size); +extern size_t mos_arr_put_n_fn(void *p_arr, size_t i, void *items, size_t n, size_t el_size); +extern size_t mos_arr_concat_fn(void *p_arr, void *arr2, size_t el_size); +extern size_t mos_arr_del_fn(void *arr, size_t i, size_t el_size); +extern size_t mos_arr_del_n_fn(void *arr, size_t i, size_t n, size_t el_size); +extern size_t mos_arr_del_front_fn(void *arr, size_t n, size_t el_size); +extern size_t mos_arr_del_back_fn(void *arr, size_t n); +extern size_t mos_arr_set_len_fn(void *p_arr, size_t len, size_t el_size); +extern size_t mos_arr_set_cap_fn(void *p_arr, size_t cap, size_t el_size); #endif // MOSLIB_DS_ARRAY_H diff --git a/include/moslib/tester.h b/include/moslib/tester.h index aa0adb2..ae41629 100644 --- a/include/moslib/tester.h +++ b/include/moslib/tester.h @@ -124,7 +124,7 @@ extern MosTester *mos_new_tester(void); // // Returns: // pointer to the added group -#define mos_add_test_group(tester, group_name) ((!(tester) ? (tester) = mos_new_tester() : 0), mos_add_test_group_fn((tester), (group_name))) +#define mos_add_test_group(tester, group_name) ((!(tester) ? (tester) = mos_new_tester() : 0), mos_add_test_group_fn(tester, group_name)) // Assert that an expression is true // Use in test functions to test correctness @@ -146,7 +146,7 @@ extern void mos_test_assert(int expression, const char *fail_message); // // code // expected exit code -#define mos_test_assert_exit(function, code) mos_test_assert_exit_fn((function), (code), #function); +#define mos_test_assert_exit(function, code) mos_test_assert_exit_fn(function, code, #function); // Suppress given output // @@ -167,7 +167,7 @@ extern void mos_unsuppress_outputs(void); // // test // test to add to the group -#define mos_add_test(group, test) mos_add_test_fn((group), (test), #test); +#define mos_add_test(group, test) mos_add_test_fn(group, test, #test); // Run defined tests // diff --git a/src/ds/array.c b/src/ds/array.c index e69de29..e8dbeec 100644 --- a/src/ds/array.c +++ b/src/ds/array.c @@ -0,0 +1,184 @@ +#define MOSLIB_FORCE_PREFIXES +#include "moslib/ds/array.h" + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "moslib/mem/alloc.h" + +MosArrHeader *arr2hdr(void *arr) { + return (MosArrHeader *)arr - 1; +} + +void *hdr2arr(MosArrHeader *hdr) { + return hdr + 1; +} + +void *init_cap(size_t cap, size_t el_size) { + MosArrHeader *hdr = mos_safe_malloc(sizeof(MosArrHeader) + cap * el_size); + *hdr = (MosArrHeader){.len = 0, .cap = cap}; + return hdr2arr(hdr); +} + +void *init(size_t el_size) { + return init_cap(MOS_ARR_INIT_CAP, el_size); +} + +void *expand(void *arr, size_t min_cap, size_t el_size) { + MosArrHeader *hdr = arr2hdr(arr); + if (hdr->cap >= min_cap) + return arr; + + if (hdr->cap < 1) + hdr->cap = 1; + + while (hdr->cap < min_cap) + hdr->cap *= 2; + + hdr = mos_safe_realloc(hdr, sizeof(MosArrHeader) + hdr->cap * el_size); + return hdr2arr(hdr); +} + +// clang-format off +// init array if it's not, define arr, hdr vars and expand to fit min_cap +#define ini(min_cap) \ + !*(void**)p_arr ? *(void **)p_arr = init(el_size) : 0; \ + MosArrHeader *hdr = arr2hdr(*(void**)p_arr); \ + *(void **)p_arr = expand(*(void**)p_arr, min_cap, el_size); \ + void *arr = *(void **)p_arr +// clang-format on + +void mos_arr_append_fn(void *p_arr, size_t el_size) { + ini(hdr->len + 1); + hdr->len++; + (void)arr; +} + +void mos_arr_insert_fn(void *p_arr, size_t i, size_t el_size) { + ini(hdr->len + 1); + memmove((char *)arr + (i + 1) * el_size, (char *)arr + i * el_size, (hdr->len++ - i) * el_size); +} + +void mos_arr_put_fn(void *p_arr, size_t i, size_t el_size) { + ini(i + 1); + if (i > hdr->len) { + memset((char *)arr + hdr->len * el_size, 0, (i - hdr->len) * el_size); + hdr->len = i + 1; + } +} + +size_t mos_arr_append_n_fn(void *p_arr, void *items, size_t n, size_t el_size) { + ini(hdr->len + n); + size_t i = hdr->len; + + memmove((char *)arr + i * el_size, items, n * el_size); + hdr->len += n; + return i; +} + +size_t mos_arr_insert_n_fn(void *p_arr, size_t i, void *items, size_t n, size_t el_size) { + ini(hdr->len + n); + if (i >= hdr->len) + return mos_arr_append_n_fn(p_arr, items, n, el_size); + + memmove((char *)arr + (i + n) * el_size, (char *)arr + i * el_size, (hdr->len - i) * el_size); + memmove((char *)arr + i * el_size, items, n * el_size); + hdr->len += n; + return i; +} + +size_t mos_arr_put_n_fn(void *p_arr, size_t i, void *items, size_t n, size_t el_size) { + ini(i + n + 1); + if (i > hdr->len) { + memset((char *)arr + hdr->len * el_size, 0, (i - hdr->len) * el_size); + } + + memmove((char *)arr + i * el_size, items, n * el_size); + if (i + n + 1 > hdr->len) + hdr->len = i + n + 1; + return i; +} + +size_t mos_arr_concat_fn(void *p_arr, void *arr2, size_t el_size) { + size_t arr2_len = mos_arr_len(arr2); + if (arr2_len == 0) + return -1; + + return mos_arr_append_n_fn(p_arr, arr2, arr2_len, el_size); +} + +size_t mos_arr_del_fn(void *arr, size_t i, size_t el_size) { + return mos_arr_del_n_fn(arr, i, 1, el_size); +} + +size_t mos_arr_del_n_fn(void *arr, size_t i, size_t n, size_t el_size) { + if (!arr) + return 0; + + MosArrHeader *hdr = arr2hdr(arr); + if (i >= hdr->len) + return 0; + + size_t new_n = n > hdr->len - i ? hdr->len - i : n; + memmove((char *)arr + i * el_size, (char *)arr + (i + new_n) * el_size, (hdr->len - i) * el_size); + hdr->len -= new_n; + return new_n; +} + +size_t mos_arr_del_front_fn(void *arr, size_t n, size_t el_size) { + return mos_arr_del_n_fn(arr, 0, n, el_size); +} + +size_t mos_arr_del_back_fn(void *arr, size_t n) { + if (!arr) + return 0; + + MosArrHeader *hdr = arr2hdr(arr); + size_t new_n = n > hdr->len ? hdr->len : n; + hdr->len -= new_n; + return new_n; +} + +size_t mos_arr_len(void *arr) { + if (!arr) + return 0; + return arr2hdr(arr)->len; +} + +size_t mos_arr_set_len_fn(void *p_arr, size_t len, size_t el_size) { + ini(len); + + size_t del = hdr->len > len ? hdr->len - len : 0; + if (len > hdr->len) + memset((char *)arr + hdr->len, 0, (len - hdr->len) * el_size); + + hdr->len = len; + return del; +} + +size_t mos_arr_cap(void *arr) { + if (!arr) + return 0; + return arr2hdr(arr)->cap; +} + +size_t mos_arr_set_cap_fn(void *p_arr, size_t cap, size_t el_size) { + void *arr = *(void **)p_arr; + if (!arr) { + *(void **)p_arr = init_cap(cap, el_size); + return cap; + } + + MosArrHeader *hdr = arr2hdr(arr); + hdr->cap = hdr->len > cap ? hdr->len : cap; + hdr = mos_safe_realloc(hdr, sizeof(MosArrHeader) + hdr->cap * el_size); + *(void **)p_arr = hdr2arr(hdr); + return hdr->cap; +} + +void mos_arr_free(void *arr) { + if (!arr) + return; + free(arr2hdr(arr)); +} diff --git a/tests/ds/array_tests.c b/tests/ds/array_tests.c index 0cefb78..1a9234d 100644 --- a/tests/ds/array_tests.c +++ b/tests/ds/array_tests.c @@ -50,8 +50,8 @@ Test adding_items() { test_assert(index == 1, "item inserted at index <= arr_len didn't return same index"); // {3, 1, 8, 0, 0, 7} - size_t zerod = arr_put(arr, 5, 7); - test_assert(zerod == 2, "item put at index > arr_len didn't return proper zerod count"); + index = arr_put(arr, 5, 7); + test_assert(index == 5, "item put at index > arr_len didn't return proper index"); // {3, 1, 8, 0, 0, 7, 1, 2} int items[] = {1, 2, 3, 4, 5, 6, 7}; @@ -67,8 +67,8 @@ Test adding_items() { test_assert(index == 0, "insert_n returned wrong index"); // {4, 5, 3, 1, 8, 6, 7, 7, 1, 2, 3} - zerod = arr_put_n(arr, 5, items + 5, 2); - test_assert(zerod == 0, "put_n returned wrong zerod value"); + index = arr_put_n(arr, 5, items + 5, 2); + test_assert(index == 5, "put_n returned wrong index"); size_t len = arr_len(arr); test_assert(len == 11, "arr_len after adding all items was incorrect"); @@ -94,8 +94,8 @@ Test getting_items() { test_assert(arr_first(arr) != arr_last(arr), "first and last are the same for array of length >1"); struct test *next_first = arr_next(arr, NULL); - struct test *next_last = arr_next(arr, next_last); - struct test *next_null = arr_next(arr, next_null); + struct test *next_last = arr_next(arr, next_first); + struct test *next_null = arr_next(arr, next_last); struct test *prev_last = arr_prev(arr, NULL); struct test *prev_first = arr_prev(arr, prev_last); struct test *prev_null = arr_prev(arr, prev_first); @@ -105,7 +105,7 @@ Test getting_items() { test_assert(!next_null, "next didn't give NULL after running out of items"); test_assert(!prev_null, "prev didn't give NULL after running out of items"); - test_assert(!arr_get(arr, (size_t)-1) && !arr_get(arr, 2), "arr_get didn't give NULL when out of bounds"); + test_assert(arr_get(arr, -1) == NULL && arr_get(arr, 2) == NULL, "arr_get didn't give NULL when out of bounds"); struct test i0 = *arr_get(arr, 0); struct test i1 = *arr_get(arr, 1); @@ -119,17 +119,15 @@ Test deleting_items() { // {1, 2, 3, 4, 5, 6, 7, 8} int i1 = arr_pop(arr); - // {1, 2, 3, 4, 6, 7, 8} - int i2 = arr_pop_i(arr, 4); - test_assert(i1 == 9 && i2 == 5, "arr_pop returned wrong values"); + test_assert(i1 == 9, "arr_pop returned wrong value"); - // {1, 2, 3, 6, 7, 8} + // {1, 2, 3, 5, 6, 7, 8} size_t deleted = arr_del(arr, 3); test_assert(deleted == 1, "failed to delete item in bounds"); // {1, 8} - deleted = arr_del_n(arr, 1, 4); - test_assert(deleted == 4, "del_n deleted wrong number of items"); + deleted = arr_del_n(arr, 1, 5); + test_assert(deleted == 5, "del_n deleted wrong number of items"); test_assert(arr_len(arr) == 2 && arr[0] == 1 && arr[1] == 8, "deleted wrong items"); deleted = arr_del_front(arr, 10); @@ -147,11 +145,18 @@ Test arr_concat_test() { unsigned long *arr1 = NULL; unsigned long *arr2 = NULL; + size_t index = arr_concat(arr1, arr2); + test_assert(index == (size_t)-1, "arr_concat with arr2 as NULL didn't return -1"); + + arr_set_len(arr2, 0); + index = arr_concat(arr1, arr2); + test_assert(index == (size_t)-1, "arr_concat with 0 length arr2 didn't return -1"); + unsigned long items[] = {1, 2, 3, 4, 5}; arr_append_n(arr1, items, 3); arr_append_n(arr2, items + 3, 2); - size_t index = arr_concat(arr1, arr2); + index = arr_concat(arr1, arr2); test_assert(index == 3, "arr_concat returned wrong index"); test_assert(arr_len(arr1) == 5, "arr_concat produced array of wrong length"); test_assert(!memcmp(arr1, items, 5 * sizeof(unsigned long)), "arr_concat produced wrong array"); |