diff options
| -rw-r--r-- | Makefile | 14 | ||||
| -rw-r--r-- | include/container.h (renamed from include/dynarray.h) | 212 | ||||
| -rw-r--r-- | include/utility.h | 87 | ||||
| -rw-r--r-- | tests/dynarray.c | 11 | ||||
| -rw-r--r-- | tests/dynarray_struct.c | 40 |
5 files changed, 236 insertions, 128 deletions
@@ -6,15 +6,17 @@ CFLAGS := -g -Wall -Wextra -Wpedantic -Werror -Wno-language-extension-token tests: dynarray -dynarray: tests/dynarray.c - $(CC) $(CFLAGS) -o $@ $^ -DTT_CHAR +dynarray: tests/dynarray.c tests/dynarray_struct.c + $(CC) $(CFLAGS) -o $@ $< -DTT_CHAR ./dynarray - $(CC) $(CFLAGS) -o $@ $^ -DTT_SHORT + $(CC) $(CFLAGS) -o $@ $< -DTT_SHORT ./dynarray - $(CC) $(CFLAGS) -o $@ $^ -DTT_INT + $(CC) $(CFLAGS) -o $@ $< -DTT_INT ./dynarray - $(CC) $(CFLAGS) -o $@ $^ -DTT_LONG + $(CC) $(CFLAGS) -o $@ $< -DTT_LONG + ./dynarray + $(CC) $(CFLAGS) -o $@ tests/dynarray_struct.c ./dynarray - rm dynarray + rm $@ diff --git a/include/dynarray.h b/include/container.h index 79b548e..775ffc2 100644 --- a/include/dynarray.h +++ b/include/container.h @@ -1,22 +1,65 @@ -#ifndef JUSTANOTHERCATGIRL_HEADERS_DYNARRAY -#define JUSTANOTHERCATGIRL_HEADERS_DYNARRAY - -//! A dynamic array implementation -//! As this is a header-only library, you have to define `DYNARRAY_IMPLEMENTATION` macro the first time you include this -//! header. This implementation uses the idea of storing metadata to the left of the array data, so that the user can -//! think of it (and use it) as normal array. Most of the API functions are defined as macros that either do some work -//! or call the implementation. They are not all-caps because they are more like functions. -//! As source is the best documentation, you should check yourself what is macro and what is not. generally, everything -//! prefixed with `array_` is a macro. Some of the macros evaluate their arguments more than once (the multiline ones), -//! so as a rule of thumb, you should only ever pass evaluated identifiers or expressions with no side-effects (like `ptr+2`) -//! to all of the macros in this library. - -#include "utility.h" +#ifndef JUSTANOTHERCATGIRL_HEADERS_CONTAINER +#define JUSTANOTHERCATGIRL_HEADERS_CONTAINER + #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <string.h> + + +/* ----------------------------------------------------------------- */ +/* -----------------UTILITY HEADER---------------------------------- */ +/* ----------------------------------------------------------------- */ +#define stringify(val) _stringify_helper(val) +#define _stringify_helper(val) #val +#define string_concat_separator(first, ...) stringify(first) ";" string_concat_separator(__VA_ARGS__) + +#define struct_member_size(type, member) sizeof(( (type*)0 )->member) +typedef unsigned char byte; + +#ifdef __GNUC__ + #define upper_2_power_32(number) (32 - __builtin_clz(number)) + #define upper_2_power_64(number) (64 - __builtin_clzl(number)) +#else + #include <intrin.h> + #include <stdint.h> + #define upper_2_power_32(number) __bit_scan_32(number) + #define upper_2_power_64(number) __bit_scan_64(number) + unsigned long __bit_scan_32(int32_t number); + unsigned long __bit_scan_64(int64_t number); +#endif + +typedef int(*qsort_cmp_t)(const void*, const void*); +#define get_qsort_cmp(type) __qsort_cmps[sizeof(type)] +extern const qsort_cmp_t __qsort_cmps[64]; + +#ifdef CONTAINER_EXPOSE_HELPERS + #define _CONTAINER_STATIC + int __default_char_cmp(const void* a, const void* b); + int __default_short_cmp(const void* a, const void* b); + int __default_int_cmp(const void* a, const void* b); + int __default_long_cmp(const void* a, const void* b); + int __default_long_long_cmp(const void* a, const void* b); +#else + #define _CONTAINER_STATIC static +#endif // CONTAINER_EXPOSE_HELPERS + + +/* ----------------------------------------------------------------- */ +/* -------------------------ARRAY HEADER---------------------------- */ +/* ----------------------------------------------------------------- */ +/* A dynamic array implementation + * As this is a header-only library, you have to define `CONTAINER_IMPLEMENTATION` macro the first time you include this + * header. This implementation uses the idea of storing metadata to the left of the array data, so that the user can + * think of it (and use it) as normal array. Most of the API functions are defined as macros that either do some work + * or call the implementation. They are not all-caps because they are more like functions. + * As source is the best documentation, you should check yourself what is macro and what is not. generally, everything + * prefixed with `array_` is a macro. Some of the macros evaluate their arguments more than once (the multiline ones), + * so as a rule of thumb, you should only ever pass evaluated identifiers or expressions with no side-effects (like `ptr+2`) + * to all of the macros in this library. + */ + /// size of the array header. should not be used directly, unless you know what you are doing #define DYNARRAY_HEADER_SIZE sizeof(struct _dynarray_header) @@ -49,36 +92,47 @@ /// Note: `element` HAS to be of same type as the array during initialization. The expression has to be of the same type. /// That means calling `array_insert(arr, 0, 5)`, where array is of type `long`, WILL lead to errors. because typeof(0) is /// int, and it will put it in an `int` variable and copy 8 bytes from there, which will be some random stack garbage. -#define array_insert(array, element, idx) \ - do { \ - typeof(element) __tmp_el_var = (element); \ - array = _insert_to_index_dynarray(array, &__tmp_el_var, idx); \ +#define array_insert(array, element, idx) \ + do { \ + typeof(element) __tmp_el_var = (element); \ + array = _insert_to_index_dynarray(array, &__tmp_el_var, sizeof(__tmp_el_var), idx); \ } while(0) /// removes last element from the array #define array_pop(array) --array_header(array)->size -/// reserve length elements so that subsequent (length - current_size) operations require no reallocation +/// reserve length elements so that subsequent (length - current_size) pushes require no reallocation #define array_reserve(array, length) if (typeof(array) __tmp; (__tmp = _memreserve_dynarray(array, length)) != NULL) array = __tmp -/// change size of an array. the capacity is set to lowest possible power of 2 that is greater than length +/// change size of an array. the capacity is set to lowest power of 2 that is greater than length #define array_resize(array, length) array = _force_resize_dynarray(array, length); /// set capacity to minimum possible value #define array_shrink(array) array = _memshrink_array(array) /// bound-checks and returns a pointer to that element. on error returns NULL -#define array_at(array, idx) (idx < array_size(array) ? (typeof(array))((byte*)array + idx*array_size(array)) : NULL) +#define array_at(array, idx) (idx < array_size(array) ? (void*)((byte*)array + idx*array_element_size(array)) : NULL) /// sorts the array using compare_func for comparison #define array_qsort(array, compare_func) qsort(array, array_size(array), array_element_size(array), compare_func) /// sorts the array using pre-defined compariton functions for signed integers based on size (1, 2, 4, 8) #define array_qsort_integral(array) array_qsort(array, __qsort_cmps[array_element_size(array)]) /// Placed here because is not a macro. compares 2 arrays and returns the same way as `strcmp` int array_compare(const void *const a1, const void *const a2, qsort_cmp_t comp); +/// Exact copy of the array. you have to free the pointer as well. +void* array_copy(void* old); + +/* ----------------------------------------------------------------- */ +/* ----------------------LINKED LIST HEADER------------------------- */ +/* ----------------------------------------------------------------- */ +// TODO! +/* ------------------------------------------------------------------------- */ +/* ------From now on, the rest of the header is implementation details------ */ +/* -------------------The API and documentation end here-------------------- */ +/* ------------------------------------------------------------------------- */ -/// for internal use +// for internal use enum _dynarray_header_idx { _dah_idx_member_size = 0, _dah_idx_capacity = 1, _dah_idx_size = 2, }; -/// basically for structurization +// for structurization struct _dynarray_header { size_t memb_size; size_t capacity; @@ -92,10 +146,104 @@ void *_alloc_dynarray_buffer(size_t el_size, size_t alen, void *buffer, size_t b void *_force_resize_dynarray(void *dynarray, size_t new_size); void *_memreserve_dynarray(void *dynarray, size_t reserved); void *_memshrink_array(void *dynarray); -void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t index); +void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t el_size, size_t index); + + +// uncomment in dev mode so that LSP highlights the code +/*#define CONTAINER_IMPLEMENTATION*/ +#ifdef CONTAINER_IMPLEMENTATION + +/* ----------------------------------------------------------------- */ +/* ---------------------UTILITY IMPLEMENTATION---------------------- */ +/* ----------------------------------------------------------------- */ +#ifndef __GNUC__ +unsigned long __bit_scan_32(int32_t number) { + #ifdef _MSC_VER + unsigned long index; + if (_BitScanReverse(&index, number)) { + return index + 1; + } else { + return 1; + } + #else // _MSC_VER + unsigned long count; + for (count = 0; number; number >>= 1) { ++count; } + return count; + #endif // _MSC_VER +} +unsigned long __bit_scan_64(int64_t number) { + #ifdef _MSC_VER + unsigned long index; + if (_BitScanReverse64(&index, number)) { + return index + 1; + } else { + return 1; + } + #else // _MSC_VER + unsigned long count; + for (count = 0; number; number >>= 1) { ++count; } + return count; + #endif // _MSC_VER +} +#endif // __GNUC__ -#ifdef DYNARRAY_IMPLEMENTATION + +_CONTAINER_STATIC int __default_char_cmp(const void* a, const void* b) { + char x = *(char*)a, y = *(char*)b; + if (x < y) return -1; + if (x > y) return 1; + return 0; +} +_CONTAINER_STATIC int __default_short_cmp(const void* a, const void* b) { + short x = *(short*)a, y = *(short*)b; + if (x < y) return -1; + if (x > y) return 1; + return 0; +} +_CONTAINER_STATIC int __default_int_cmp(const void* a, const void* b) { + int x = *(int*)a, y = *(int*)b; + if (x < y) return -1; + if (x > y) return 1; + return 0; +} +_CONTAINER_STATIC int __default_long_long_cmp(const void* a, const void* b) { + long long x = *(long long*)a, y = *(long long*)b; + if (x < y) return -1; + if (x > y) return 1; + return 0; +} +_CONTAINER_STATIC int __default_long_cmp(const void* a, const void* b) { + long x = *(long*)a, y = *(long*)b; + if (x < y) return -1; + if (x > y) return 1; + return 0; +} + +#ifdef __GNUC__ +// cope +#pragma GCC diagnostic ignored "-Woverride-init" // Is is meant to override it on different platforms +const qsort_cmp_t __qsort_cmps[64] = { + [sizeof(char)] = __default_char_cmp, + [sizeof(short)] = __default_short_cmp, + [sizeof(int)] = __default_int_cmp, + [sizeof(long)] = __default_long_cmp, + [sizeof(long long)] = __default_long_long_cmp, + [63] = 0, +}; +#pragma GCC diagnostic warning "-Woverride-init" +#else // not __GNUC__ +const qsort_cmp_t __qsort_cmps[64] = { + 0, + __default_char_cmp, __default_short_cmp, 0, __default_int_cmp, + 0, 0, 0, __default_long_long_cmp, +}; +#endif // __GNUC__ + + +/* ----------------------------------------------------------------- */ +/* ----------------------ARRAY IMPLEMENTATION----------------------- */ +/* ----------------------------------------------------------------- */ void *_alloc_dynarray(size_t el_size, size_t len) { @@ -158,13 +306,14 @@ void *_force_resize_dynarray(void * const dynarray, size_t new_size) } } -void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t index) { +void *_insert_to_index_dynarray(void *const dynarray, const void *const element, size_t el_size, size_t index) { struct _dynarray_header* hdr = array_header(dynarray); byte* array = (byte*) _memreserve_dynarray(dynarray, 1 << upper_2_power_64(hdr->size + 1)); hdr = array_header(array); ++hdr->size; memmove(array + hdr->memb_size * (index+1), array + hdr->memb_size * (index), hdr->memb_size * (hdr->size - 1 - index)); - memcpy(array + hdr->memb_size * index, element, hdr->memb_size); + if (el_size != hdr->memb_size) { /* TODO: warning? */ } + memcpy(array + hdr->memb_size * index, element, el_size); return array; } @@ -187,6 +336,11 @@ int array_compare(const void *const a1, const void *const a2, qsort_cmp_t comp) #undef NDEBUG } -#endif // DYNARRAY_IMPLEMENTATION +/*void* array_copy(void* old) {*/ +/* //TODO!*/ +/*}*/ + + +#endif // CONTAINER_IMPLEMENTATION -#endif // JUSTANOTHERCATGIRL_HEADERS_DYNARRAY +#endif // JUSTANOTHERCATGIRL_HEADERS_CONTAINER diff --git a/include/utility.h b/include/utility.h deleted file mode 100644 index 85948cf..0000000 --- a/include/utility.h +++ /dev/null @@ -1,87 +0,0 @@ -#ifndef JUSTANOTHERCATGIRL_HEADERS_UTILITY -#define JUSTANOTHERCATGIRL_HEADERS_UTILITY - -#define stringify(val) _stringify_helper(val) -#define _stringify_helper(val) #val - -#define string_concat_separator(first, ...) stringify(first) ";" string_concat_separator(__VA_ARGS__) - -#define struct_member_size(type, member) sizeof(( (type*)0 )->member) -typedef unsigned char byte; -#define upper_2_power_32(number) (32 - __builtin_clz(number)) -#define upper_2_power_64(number) (64 - __builtin_clzl(number)) - -typedef int(*qsort_cmp_t)(const void*, const void*); -#define get_qsort_cmp(type) __qsort_cmps[sizeof(type)] -extern const qsort_cmp_t __qsort_cmps[64]; - -#ifdef UTILITY_EXPOSE_HELPERS - #define _UTILITY_STATIC - int __default_char_cmp(const void* a, const void* b); - int __default_short_cmp(const void* a, const void* b); - int __default_int_cmp(const void* a, const void* b); - int __default_long_cmp(const void* a, const void* b); - int __default_long_long_cmp(const void* a, const void* b); -#else - #define _UTILITY_STATIC static -#endif // UTILITY_EXPOSE_HELPERS - - -#ifdef UTILITY_IMPLEMENTATION - -_UTILITY_STATIC int __default_char_cmp(const void* a, const void* b) { - char x = *(char*)a, y = *(char*)b; - if (x < y) return -1; - if (x > y) return 1; - return 0; -} -_UTILITY_STATIC int __default_short_cmp(const void* a, const void* b) { - short x = *(short*)a, y = *(short*)b; - if (x < y) return -1; - if (x > y) return 1; - return 0; -} -_UTILITY_STATIC int __default_int_cmp(const void* a, const void* b) { - int x = *(int*)a, y = *(int*)b; - if (x < y) return -1; - if (x > y) return 1; - return 0; -} -_UTILITY_STATIC int __default_long_long_cmp(const void* a, const void* b) { - long long x = *(long long*)a, y = *(long long*)b; - if (x < y) return -1; - if (x > y) return 1; - return 0; -} -_UTILITY_STATIC int __default_long_cmp(const void* a, const void* b) { - long x = *(long*)a, y = *(long*)b; - if (x < y) return -1; - if (x > y) return 1; - return 0; -} - -#ifdef __GNUC__ -// cope -#pragma GCC diagnostic ignored "-Woverride-init" // Is is meant to override it on different platforms -const qsort_cmp_t __qsort_cmps[64] = { - [sizeof(char)] = __default_char_cmp, - [sizeof(short)] = __default_short_cmp, - [sizeof(int)] = __default_int_cmp, - [sizeof(long)] = __default_long_cmp, - [sizeof(long long)] = __default_long_long_cmp, - [63] = 0, -}; -#pragma GCC diagnostic warning "-Woverride-init" -#else // not __GNUC__ -const qsort_cmp_t __qsort_cmps[64] = { - 0, - __default_char_cmp, __default_short_cmp, 0, __default_int_cmp, - 0, 0, 0, __default_long_long_cmp, -}; -#endif // __GNUC__ - - -#endif // UTILITY_IMPLEMENTATION - - -#endif //JUSTANOTHERCATGIRL_HEADERS_UTILITY diff --git a/tests/dynarray.c b/tests/dynarray.c index d7a79d7..2d9ea61 100644 --- a/tests/dynarray.c +++ b/tests/dynarray.c @@ -1,8 +1,6 @@ -#define DYNARRAY_IMPLEMENTATION -#define UTILITY_IMPLEMENTATION +#define CONTAINER_IMPLEMENTATION #define UTILTY_EXPOSE_HELPERS -#include "../include/dynarray.h" -#include "../include/utility.h" +#include "../include/container.h" #include <stdio.h> #include <stdlib.h> @@ -56,7 +54,8 @@ int main(void) array_qsort_integral(arr); // size: 5, cap: 5 /* qsort(arr, array_size(arr), array_element_size(arr), __default_int_cmp); */ print_arr(arr, __LINE__, "qsort"); - array_insert(arr, 20, 1); // size: 6, cap: 8 + TEST_TYPE __inserted = 20; + array_insert(arr, __inserted, 1); // size: 6, cap: 8 print_arr(arr, __LINE__, "1 insert"); for (size_t i = 0; i <= array_size(arr); i += 2) { @@ -74,7 +73,7 @@ int main(void) puts("\x1b[32mTest for \"" stringify(TEST_TYPE)"\" passed\x1b[0m"); } TEST_TYPE* elem; - if ((elem = array_at(arr, 2)) != NULL) { + if ((elem = array_at(arr, 1)) != NULL) { if (*elem == 42) { puts("array_at(1) = 42"); } diff --git a/tests/dynarray_struct.c b/tests/dynarray_struct.c new file mode 100644 index 0000000..6cce97c --- /dev/null +++ b/tests/dynarray_struct.c @@ -0,0 +1,40 @@ + +#define CONTAINER_IMPLEMENTATION +#include "../include/container.h" + +#include <stdio.h> + +struct point { + float x, y, z, w; +}; + +void print_point(struct point* p) { + printf("{ .x=%.2f, .y=%.2f, .z=%.2f, .w=%.2f };\n", p->x, p->y, p->z, p->w); +} + +void print_array(struct point* p) { + for (size_t i = 0; i < array_size(p); ++i) { + printf("%zu: ", i); + print_point(p+i); + } +} + +int point_abs(const void* a, const void* b) { + struct point* c = (struct point*) a; + struct point* d = (struct point*) b; + float absa = c->x * c->x + c->y * c->y + c->z * c->z + c->w * c->w; + float absb = d->x * d->x + d->y * d->y + d->z * d->z + d->w * d->w; + return absa-absb; +} + +int main() +{ + struct point *points = array_new(struct point, 4); + for (size_t i = 0; i < array_size(points); ++i) points[i] = (struct point){.x = i, .y = 2 * i, .z = 4 * i, .w = 8 * i}; + array_push(points, ((struct point){.0f, 2.5f, 3.0, 4.0}) ); + array_insert(points, ((struct point){0}), 3); + array_qsort(points, point_abs); + print_array(points); + array_free(points); + return 0; +} |