pkarr: PK_ARR_MOVE_IN_PLACE

3 files changed, 66 insertions, 7 deletions

diff --git a/pk.h.in b/pk.h.in
index 6ae6b89..0ca132b 100644
--- a/pk.h.in
+++ b/pk.h.in
@@ -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] = ...;
+* ```
 *
 *******************************************************************************/
 
diff --git a/pkarr.h b/pkarr.h
index 0ddb1af..19ab53a 100644
--- a/pkarr.h
+++ b/pkarr.h
@@ -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);