pkarr: PK_ARR_MOVE_IN_PLACE shift correct byte range

2 files changed, 114 insertions, 4 deletions

diff --git a/pkarr.h b/pkarr.h
index 3d05e77..fa2d88a 100644
--- a/pkarr.h
+++ b/pkarr.h
@@ -80,14 +80,39 @@ pk_arr_move_to_back(struct pk_arr *arr, uint32_t index)
 	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;
+	char *target = (char *)pk_new(arr->stride, arr->alignment, arr->bkt);
+	char *buffer = (char *)arr->data;
+	// copy bytes to temp buffer
 	for (ii = 0, i = arr->stride * index; ii < arr->stride; ++ii, ++i) {
 		target[ii] = buffer[i];
 	}
+	// shift everything forward
+	// arr->stride = 8
+	// arr->next = 2
+	// index = 0
+	//
+	// for (i = 0; i < 8; ++i) {
+	//   b[i] = b[i + 8]
+	// }
+	// b[00] = b[08]
+	// b[01] = b[09]
+	// ...
+	// b[07] = b[15]
 	for (i = arr->stride * index; i < (arr->stride * (arr->next - 1)); ++i) {
 		buffer[i] = buffer[i + arr->stride];
 	}
+	// copy temp buffer back into arr
+	// arr->stride = 8
+	// arr->next = 2
+	// index = 0
+	//
+	// for (ii = 0, i = 8; ii < 8; ++ii, ++i) {
+	//   b[i] = t[ii]
+	// }
+	// b[08] = t[00]
+	// b[09] = t[01]
+	// ...
+	// b[15] = t[07]
 	for (ii = 0, i = arr->stride * (arr->next - 1); ii < arr->stride; ++ii, ++i) {
 		buffer[i] = target[ii];
 	}
@@ -138,8 +163,20 @@ pk_arr_remove_at(struct pk_arr *arr, uint32_t index)
 	}
 #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) {
+	char *buffer = (char *)arr->data;
+	// shift everything forward
+	// arr->stride = 8
+	// arr->next = 3
+	// index = 0
+	//
+	// for (i = 0; i < 16; ++i) {
+	//   b[i] = b[i + 8]
+	// }
+	// b[00] = b[08]
+	// b[01] = b[09]
+	// ...
+	// b[15] = b[23]
+	for (i = arr->stride * index; i < arr->stride * arr->next; ++i) {
 		buffer[i] = buffer[i + arr->stride];
 	}
 #else
diff --git a/test/pkarr.c b/test/pkarr.c
index bbc3411..c8878af 100644
--- a/test/pkarr.c
+++ b/test/pkarr.c
@@ -1,9 +1,19 @@
 
 // NOTE: only intended for performance testing
+// TODO: move flag to compiler and run tests more than once for full coverage
 #define PK_ARR_MOVE_IN_PLACE
 
 #include "../pkarr.h"
 
+/* 2025-01-10 JCB
+ * I was chasing a heisenbug, which only appeared with this override.
+ * When compiling with `-O0`, all tests pass
+ * When compiling with `-O3`, one (or maybe more?) of the tests fails
+ * The issue is resolved now; leaving this for testing purposes.
+ */
+#undef PK_LOGV_INF
+#define PK_LOGV_INF(str, ...) (void)str
+
 struct some_complex_struct {
 	char uhh;
 	union {
@@ -55,6 +65,7 @@ int main(int argc, char *argv[])
 	*/
 
 	// init via append, soft clear
+	PK_LOGV_INF("%s", "[init via append, soft clear] begin\n");
 	{
 		test_spinup(&arr, &bkt);
 		arr.stride = sizeof(uint8_t);
@@ -63,22 +74,32 @@ int main(int argc, char *argv[])
 		uint8_t c = 255;
 		pk_arr_append(&arr, &c);
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 1) exit(1);
 
 		pk_arr_clear(&arr);
 		
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 0) exit(1);
 
 		test_teardown(&arr, &bkt);
 	}
+	PK_LOGV_INF("%s", "[init via append, soft clear] end\n\n");
 
 	// movement
+	PK_LOGV_INF("%s", "[movement] begin\n");
 	{
 		test_spinup(&arr, &bkt);
 		arr.stride = sizeof(uint64_t);
@@ -90,12 +111,19 @@ int main(int argc, char *argv[])
 
 		pk_arr_move_to_back(&arr, 2);
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 5) exit(1);
 
 		uint64_t *vals = (uint64_t *)arr.data;
+		for (i = 0; i < 5; ++i) {
+			PK_LOGV_INF("vals[%lu]: %lu\n", i, vals[i]);
+		}
 		if (0 != vals[0]) exit(1);
 		if (1 != vals[1]) exit(1);
 		if (3 != vals[2]) exit(1);
@@ -104,8 +132,10 @@ int main(int argc, char *argv[])
 
 		test_teardown(&arr, &bkt);
 	}
+	PK_LOGV_INF("%s", "[movement] end\n\n");
 
 	// complex movement
+	PK_LOGV_INF("%s", "[complex movement] begin\n");
 	{
 		test_spinup(&arr, &bkt);
 		arr.stride = sizeof(struct some_complex_struct);
@@ -120,12 +150,19 @@ int main(int argc, char *argv[])
 
 		pk_arr_move_to_back(&arr, 2);
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 5) exit(1);
 
 		struct some_complex_struct *vals = (struct some_complex_struct*)arr.data;
+		for (i = 0; i < 5; ++i) {
+			PK_LOGV_INF("vals[%lu]: %lu\n", i, vals[i].lng);
+		}
 		if (0 != vals[0].lng) exit(1);
 		if (1 != vals[1].lng) exit(1);
 		if (3 != vals[2].lng) exit(1);
@@ -134,8 +171,10 @@ int main(int argc, char *argv[])
 
 		test_teardown(&arr, &bkt);
 	}
+	PK_LOGV_INF("%s", "[complex movement] end\n\n");
 
 	// resize (implicit reserve) + grow
+	PK_LOGV_INF("%s", "[resize (implicit reserve) + grow] begin\n");
 	{
 		test_spinup(&arr, &bkt);
 		arr.stride = sizeof(uint8_t);
@@ -144,9 +183,13 @@ int main(int argc, char *argv[])
 		pk_arr_resize(&arr, 17);
 		uint8_t *typed_buffer = (uint8_t *)arr.data;
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved != 17) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 17) exit(1);
 
 		for (i = 0; i < 17; ++i) {
@@ -156,15 +199,21 @@ int main(int argc, char *argv[])
 		uint8_t v = 17;
 		pk_arr_append(&arr, &v);
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 17) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 18) exit(1);
 
 		test_teardown(&arr, &bkt);
 	}
+	PK_LOGV_INF("%s", "[resize (implicit reserve) + grow] end\n\n");
 
 	// remove_at back, middle, front
+	PK_LOGV_INF("%s", "[remove_at back, middle, front] begin\n");
 	{
 		test_spinup(&arr, &bkt);
 		arr.stride = sizeof(uint64_t);
@@ -176,12 +225,19 @@ int main(int argc, char *argv[])
 
 		pk_arr_remove_at(&arr, 4); // back
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 4) exit(1);
 
 		uint64_t *vals = (uint64_t *)arr.data;
+		for (i = 0; i < 4; ++i) {
+			PK_LOGV_INF("vals[%lu]: %lu\n", i, vals[i]);
+		}
 		if (0 != vals[0]) exit(1);
 		if (1 != vals[1]) exit(1);
 		if (2 != vals[2]) exit(1);
@@ -189,31 +245,47 @@ int main(int argc, char *argv[])
 
 		pk_arr_remove_at(&arr, 2); // middle
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 3) exit(1);
 
 		vals = (uint64_t *)arr.data;
+		for (i = 0; i < 3; ++i) {
+			PK_LOGV_INF("vals[%lu]: %lu\n", i, vals[i]);
+		}
 		if (0 != vals[0]) exit(1);
 		if (1 != vals[1]) exit(1);
 		if (3 != vals[2]) exit(1);
 
 		pk_arr_remove_at(&arr, 0); // front
 
+		PK_LOGV_INF("arr.bkt: %p\n", (void *)arr.bkt);
 		if (arr.bkt == NULL) exit(1);
+		PK_LOGV_INF("arr.data: %p\n",  arr.data);
 		if (arr.data == NULL) exit(1);
+		PK_LOGV_INF("arr.reserved: %i\n", arr.reserved);
 		if (arr.reserved == 0) exit(1);
+		PK_LOGV_INF("arr.next: %i\n", arr.next);
 		if (arr.next != 2) exit(1);
 
 		vals = (uint64_t *)arr.data;
+		for (i = 0; i < 2; ++i) {
+			PK_LOGV_INF("vals[%lu]: %lu\n", i, vals[i]);
+		}
 		if (1 != vals[0]) exit(1);
 		if (3 != vals[1]) exit(1);
 
 		test_teardown(&arr, &bkt);
 	}
+	PK_LOGV_INF("%s", "[remove_at back, middle, front] end\n\n");
 
 	// init via append, soft clear
+	PK_LOGV_INF("%s", "[init via append, soft clear] begin\n");
 	{
 		test_spinup(&arr, &bkt);
 		arr.stride = sizeof(uint8_t);
@@ -231,6 +303,7 @@ int main(int argc, char *argv[])
 
 		test_teardown(&arr, &bkt);
 	}
+	PK_LOGV_INF("%s", "[init via append, soft clear] end\n\n");
 
 	return 0;
 }