[Bf-blender-cvs] [7592a5097c8] master: BLI_array: add BLI_array_deduplicate_ordered utility & tests

[Campbell Barton]

Commit: 7592a5097c8b997b308f5414434bca8e66376af1
Author: Campbell Barton
Date:   Fri Jul 9 13:33:36 2021 +1000
Branches: master
https://developer.blender.org/rB7592a5097c8b997b308f5414434bca8e66376af1

BLI_array: add BLI_array_deduplicate_ordered utility & tests

===================================================================

M	source/blender/blenlib/BLI_array_utils.h
M	source/blender/blenlib/intern/array_utils.c
M	source/blender/blenlib/tests/BLI_array_utils_test.cc

===================================================================

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
@@ -120,6 +120,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.
  *
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