diff options
| -rw-r--r-- | core/templates/paged_array.h | 20 | ||||
| -rw-r--r-- | tests/core/templates/test_paged_array.h | 51 |
2 files changed, 60 insertions, 11 deletions
diff --git a/core/templates/paged_array.h b/core/templates/paged_array.h index c447b5af64..45b90869b9 100644 --- a/core/templates/paged_array.h +++ b/core/templates/paged_array.h @@ -278,10 +278,10 @@ public: count -= remainder; - uint32_t src_pages = p_array._get_pages_in_use(); + uint32_t src_page_index = 0; uint32_t page_size = page_size_mask + 1; - for (uint32_t i = 0; i < src_pages; i++) { + while (p_array.count > 0) { uint32_t page_count = _get_pages_in_use(); uint32_t new_page_count = page_count + 1; @@ -289,16 +289,14 @@ public: _grow_page_array(); //keep out of inline } - page_data[page_count] = p_array.page_data[i]; - page_ids[page_count] = p_array.page_ids[i]; - if (i == src_pages - 1) { - //last page, only increment with remainder - count += p_array.count & page_size_mask; - } else { - count += page_size; - } + page_data[page_count] = p_array.page_data[src_page_index]; + page_ids[page_count] = p_array.page_ids[src_page_index]; + + uint32_t take = MIN(p_array.count, page_size); //pages to take away + p_array.count -= take; + count += take; + src_page_index++; } - p_array.count = 0; //take away the other array pages //handle the remainder page if exists if (remainder_page) { 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 |