diff options
author | Campbell Barton <ideasman42@gmail.com> | 2021-07-09 06:33:36 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2021-07-09 06:35:54 +0300 |
commit | 7592a5097c8b997b308f5414434bca8e66376af1 (patch) | |
tree | 129b78c2943eea24421d2a87c7700f8bace71c0b | |
parent | ab70133db0ba3b92d0f10837e5c615a6460910ef (diff) |
BLI_array: add BLI_array_deduplicate_ordered utility & tests
-rw-r--r-- | source/blender/blenlib/BLI_array_utils.h | 4 | ||||
-rw-r--r-- | source/blender/blenlib/intern/array_utils.c | 29 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_array_utils_test.cc | 50 |
3 files changed, 83 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_array_utils.h b/source/blender/blenlib/BLI_array_utils.h index 2847bc960ad..dc85d619e91 100644 --- a/source/blender/blenlib/BLI_array_utils.h +++ b/source/blender/blenlib/BLI_array_utils.h @@ -44,6 +44,10 @@ void _bli_array_permute(void *arr, #define BLI_array_permute_ex(arr, arr_len, order, arr_temp) \ _bli_array_permute(arr, arr_len, sizeof(*(arr)), order, arr_temp) +unsigned int _bli_array_deduplicate_ordered(void *arr, unsigned int arr_len, size_t arr_stride); +#define BLI_array_deduplicate_ordered(arr, arr_len) \ + _bli_array_deduplicate_ordered(arr, arr_len, sizeof(*(arr))) + int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p); #define BLI_array_findindex(arr, arr_len, p) _bli_array_findindex(arr, arr_len, sizeof(*(arr)), p) diff --git a/source/blender/blenlib/intern/array_utils.c b/source/blender/blenlib/intern/array_utils.c index 25261e82cc9..085f51ac451 100644 --- a/source/blender/blenlib/intern/array_utils.c +++ b/source/blender/blenlib/intern/array_utils.c @@ -121,6 +121,35 @@ void _bli_array_permute(void *arr, } /** + * In-place array de-duplication of an ordered array. + * + * \return The new length of the array. + * + * Access via #BLI_array_deduplicate_ordered + */ +unsigned int _bli_array_deduplicate_ordered(void *arr, unsigned int arr_len, size_t arr_stride) +{ + if (UNLIKELY(arr_len <= 1)) { + return arr_len; + } + + const unsigned int arr_stride_uint = (unsigned int)arr_stride; + uint j = 0; + for (uint i = 0; i < arr_len; i++) { + if ((i == j) || (memcmp(POINTER_OFFSET(arr, arr_stride_uint * i), + POINTER_OFFSET(arr, arr_stride_uint * j), + arr_stride) == 0)) { + continue; + } + j += 1; + memcpy(POINTER_OFFSET(arr, arr_stride_uint * j), + POINTER_OFFSET(arr, arr_stride_uint * i), + arr_stride); + } + return j + 1; +} + +/** * Find the first index of an item in an array. * * Access via #BLI_array_findindex diff --git a/source/blender/blenlib/tests/BLI_array_utils_test.cc b/source/blender/blenlib/tests/BLI_array_utils_test.cc index 5d12b8fbd4d..1bf221c5335 100644 --- a/source/blender/blenlib/tests/BLI_array_utils_test.cc +++ b/source/blender/blenlib/tests/BLI_array_utils_test.cc @@ -189,3 +189,53 @@ TEST(array_utils, BinaryOrInt4Mix) BINARY_OR_TEST(data_cmp, data_a, data_b, data_combine, ARRAY_SIZE(data_cmp)); } #undef BINARY_OR_TEST + +/* BLI_array_deduplicate_ordered */ +#define DEDUPLICATE_ORDERED_TEST(data, data_cmp) \ + { \ + const uint data_len_new = BLI_array_deduplicate_ordered(data, ARRAY_SIZE(data)); \ + EXPECT_EQ(data_len_new, ARRAY_SIZE(data_cmp)); \ + EXPECT_EQ_ARRAY(data, data_cmp, data_len_new); \ + /* Ensure running a second time does nothing. */ \ + const uint data_len_test = BLI_array_deduplicate_ordered(data, data_len_new); \ + EXPECT_EQ(data_len_test, ARRAY_SIZE(data_cmp)); \ + EXPECT_EQ_ARRAY(data, data_cmp, data_len_new); \ + } \ + ((void)0) + +TEST(array_utils, DeduplicateOrdered1) +{ + int data[] = {0}; + const int data_cmp[] = {0}; + DEDUPLICATE_ORDERED_TEST(data, data_cmp); +} + +TEST(array_utils, DeduplicateOrdered2) +{ + int data[] = {1, 2}; + const int data_cmp[] = {1, 2}; + DEDUPLICATE_ORDERED_TEST(data, data_cmp); +} + +TEST(array_utils, DeduplicateOrdered2Same) +{ + int data[] = {1, 1}; + const int data_cmp[] = {1}; + DEDUPLICATE_ORDERED_TEST(data, data_cmp); +} + +TEST(array_utils, DeduplicateOrdered3Same) +{ + int data[] = {1, 1, 1}; + const int data_cmp[] = {1}; + DEDUPLICATE_ORDERED_TEST(data, data_cmp); +} + +TEST(array_utils, DeduplicateOrdered3) +{ + int data[] = {3, 3, 2, 2, 1, 1}; + const int data_cmp[] = {3, 2, 1}; + DEDUPLICATE_ORDERED_TEST(data, data_cmp); +} + +#undef DEDUPLICATE_ORDERED_TEST |