Fix PagedArray.merge_unordered() dropping pages

1 files changed, 51 insertions, 0 deletions

diff --git a/tests/core/templates/test_paged_array.h b/tests/core/templates/test_paged_array.h
index 37be3080e8..10dc4473ca 100644
--- a/tests/core/templates/test_paged_array.h
+++ b/tests/core/templates/test_paged_array.h
@@ -148,6 +148,57 @@ TEST_CASE("[PagedArray] Shared pool fill, including merging") {
 	array2.reset(); //reset so pagepool can be reset
 	pool.reset();
 }
+
+TEST_CASE("[PagedArray] Extensive merge_unordered() test") {
+	for (int page_size = 1; page_size <= 128; page_size *= 2) {
+		PagedArrayPool<uint32_t> pool(page_size);
+		PagedArray<uint32_t> array1;
+		PagedArray<uint32_t> array2;
+		array1.set_page_pool(&pool);
+		array2.set_page_pool(&pool);
+
+		const int max_count = 123;
+		// Test merging arrays of lengths 0+123, 1+122, 2+121, ..., 123+0
+		for (uint32_t j = 0; j < max_count; j++) {
+			CHECK(array1.size() == 0);
+			CHECK(array2.size() == 0);
+
+			uint32_t sum = 12345;
+			for (uint32_t i = 0; i < j; i++) {
+				// Hashing the addend makes it extremely unlikely for any values
+				// other than the original inputs to produce a matching sum
+				uint32_t addend = hash_murmur3_one_32(i) + i;
+				array1.push_back(addend);
+				sum += addend;
+			}
+			for (uint32_t i = j; i < max_count; i++) {
+				// See above
+				uint32_t addend = hash_murmur3_one_32(i) + i;
+				array2.push_back(addend);
+				sum += addend;
+			}
+
+			CHECK(array1.size() == j);
+			CHECK(array2.size() == max_count - j);
+
+			array1.merge_unordered(array2);
+			CHECK_MESSAGE(array1.size() == max_count, "merge_unordered() added/dropped elements while merging");
+
+			// If any elements were altered during merging, the sum will not match up.
+			for (uint32_t i = 0; i < array1.size(); i++) {
+				sum -= array1[i];
+			}
+			CHECK_MESSAGE(sum == 12345, "merge_unordered() altered elements while merging");
+
+			array1.clear();
+		}
+
+		array1.reset();
+		array2.reset();
+		pool.reset();
+	}
+}
+
 } // namespace TestPagedArray
 
 #endif // TEST_PAGED_ARRAY_H