diff options
| -rw-r--r-- | pk.h.in | 31 | ||||
| -rw-r--r-- | pkarr.h | 34 | ||||
| -rw-r--r-- | test/pkarr.c | 8 |
3 files changed, 66 insertions, 7 deletions
@@ -128,17 +128,40 @@ * The following definitions (shown with defaults) can be overridden: * PK_ARR_INITIAL_COUNT 16 * PK_ARR_GROW_RATIO 1.5 -* -* Initialize `stride`, `alignment` (optional), and `bkt` (optional) members +* PK_ARR_MOVE_IN_PLACE (not defined) +* +* The macro `PK_ARR_MOVE_IN_PLACE` ensures that when possible, the pointer value +* of `arr->data` is preserved. +* It is used in the following methods: +* `pk_arr_move_to_back` +* `pk_arr_remove_at` +* This has two additinal benefits: +* 1. Minimizing the number and `sz` of calls to `pk_new` +* 2. Ensuring `data[0]` to `data[(N - 1) * stride]` is not copied extraneously +* to a new buffer. +* The speed of this will vary depending on usage, platform, and compiler. +* +* Initialize `stride`, `alignment`, and `bkt` (optional) members * *before* calling any `pk_arr_*` methods. +* +* Examples: * ``` c * struct pk_arr arr = {0}; -* arr.stride = sizeof(obj); -* arr.alignment = alignof(obj); // optional +* arr.stride = sizeof(obj); // required +* arr.alignment = alignof(obj); // required * arr.bkt = bkt; // optional * pk_arr_reserve(&arr, 10); // optional * pk_arr_append(&arr, &obj); * ``` +* ``` c +* struct pk_arr arr = {0}; +* arr.stride = sizeof(obj); // required +* arr.alignment = alignof(obj); // required +* arr.bkt = bkt; // optional +* pk_arr_resize(&arr, 10); +* obj* d = (obj*)arr->data; +* d[0] = ...; +* ``` * *******************************************************************************/ @@ -22,7 +22,9 @@ void pk_arr_append(struct pk_arr *arr, void *data); void pk_arr_remove_at(struct pk_arr *arr, uint32_t index); #endif /* PK_PKARR_H */ -#ifdef PK_IMPL_ARR +#ifdef PK_IMPL_ARR + +#include "./pkmacros.h" /* deleteme */ #ifndef PK_ARR_GROW_RATIO #define PK_ARR_GROW_RATIO 1.5 @@ -52,7 +54,9 @@ pk_arr_reserve(struct pk_arr *arr, uint32_t count) if (arr->reserved >= count) return; void *new_data = pk_new(arr->stride * count, arr->alignment, arr->bkt); if (arr->data != NULL) { - memcpy(new_data, arr->data, arr->stride * arr->reserved); + if (arr->next != 0) { + memcpy(new_data, arr->data, arr->stride * arr->reserved); + } pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt); } arr->reserved = count; @@ -71,6 +75,21 @@ pk_arr_move_to_back(struct pk_arr *arr, uint32_t index) { if (arr->reserved == 0) return; if (arr->next <= 1) return; +#ifdef PK_ARR_MOVE_IN_PLACE + uint32_t i, ii; + uint8_t *target = (uint8_t *)pk_new(arr->stride, arr->alignment, arr->bkt); + uint8_t *buffer = (uint8_t *)arr->data; + for (ii = 0, i = arr->stride * index; ii < arr->stride; ++ii, ++i) { + target[ii] = buffer[i]; + } + for (i = arr->stride * index; i < (arr->stride * (arr->next - 1)); ++i) { + buffer[i] = buffer[i + arr->stride]; + } + for (ii = 0, i = arr->stride * (arr->next - 1); ii < arr->stride; ++ii, ++i) { + buffer[i] = target[ii]; + } + pk_delete(target, arr->stride, arr->bkt); +#else char *new_data = (char *)pk_new(arr->stride * arr->reserved, arr->alignment, arr->bkt); if (index > 0) { memcpy(new_data, arr->data, arr->stride * index); @@ -85,13 +104,14 @@ pk_arr_move_to_back(struct pk_arr *arr, uint32_t index) arr->stride * (arr->next - index - 1)); pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt); arr->data = (void *)new_data; +#endif } void pk_arr_append(struct pk_arr *arr, void *data) { if (arr->reserved == arr->next) { - uint32_t new_count = arr->reserved == 0 ? PK_ARR_INITIAL_COUNT : arr->reserved * PK_ARR_GROW_RATIO; + uint32_t new_count = PK_MAX(arr->reserved == 0 ? PK_ARR_INITIAL_COUNT : arr->reserved * PK_ARR_GROW_RATIO, arr->reserved + 1); void *new_data = pk_new(arr->stride * new_count, arr->alignment, arr->bkt); if (arr->data != NULL) { memcpy(new_data, arr->data, arr->stride * arr->reserved); @@ -113,6 +133,13 @@ pk_arr_remove_at(struct pk_arr *arr, uint32_t index) arr->next -=1; return; } +#ifdef PK_ARR_MOVE_IN_PLACE + uint32_t i; + uint8_t *buffer = (uint8_t *)arr->data; + for (i = arr->stride * index; i < (arr->stride * (arr->next - 1)); ++i) { + buffer[i] = buffer[i + arr->stride]; + } +#else char *new_data = (char *)pk_new(arr->stride * arr->reserved, arr->alignment, arr->bkt); if (index > 0) { memcpy(new_data, arr->data, arr->stride * index); @@ -123,6 +150,7 @@ pk_arr_remove_at(struct pk_arr *arr, uint32_t index) arr->stride * (arr->next - index - 1)); pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt); arr->data = (void *)new_data; +#endif arr->next -= 1; } diff --git a/test/pkarr.c b/test/pkarr.c index deac974..97757dc 100644 --- a/test/pkarr.c +++ b/test/pkarr.c @@ -1,4 +1,7 @@ +// NOTE: only intended for performance testing +#define PK_ARR_MOVE_IN_PLACE + #include "../pkarr.h" struct some_complex_struct { @@ -49,6 +52,7 @@ int main(int argc, char *argv[]) { test_spinup(&arr, &bkt); arr.stride = sizeof(uint8_t); + arr.alignment = alignof(uint8_t); uint8_t c = 255; pk_arr_append(&arr, &c); @@ -72,6 +76,7 @@ int main(int argc, char *argv[]) { test_spinup(&arr, &bkt); arr.stride = sizeof(uint64_t); + arr.alignment = alignof(uint64_t); for (i = 0; i < 5; ++i) { pk_arr_append(&arr, &i); @@ -98,6 +103,7 @@ int main(int argc, char *argv[]) { test_spinup(&arr, &bkt); arr.stride = sizeof(struct some_complex_struct); + arr.alignment = alignof(struct some_complex_struct); for (i = 0; i < 5; ++i) { cmplx_strct.uhh = (char)i; @@ -127,6 +133,7 @@ int main(int argc, char *argv[]) { test_spinup(&arr, &bkt); arr.stride = sizeof(uint8_t); + arr.alignment = alignof(uint8_t); pk_arr_resize(&arr, 17); uint8_t *typed_buffer = (uint8_t *)arr.data; @@ -155,6 +162,7 @@ int main(int argc, char *argv[]) { test_spinup(&arr, &bkt); arr.stride = sizeof(uint64_t); + arr.alignment = alignof(uint64_t); for (i = 0; i < 5; ++i) { pk_arr_append(&arr, &i); |