BLI_array: add BLI_array_deduplicate_ordered utility & tests

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)
 

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.
  *

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