BLI_array_utils: add BLI_array_rfindindex

Array search from back to front.

3 files changed, 96 insertions, 8 deletions

diff --git a/source/blender/blenlib/BLI_array_utils.h b/source/blender/blenlib/BLI_array_utils.h
index 5ef8421c003..a46c87cec40 100644
--- a/source/blender/blenlib/BLI_array_utils.h
+++ b/source/blender/blenlib/BLI_array_utils.h
@@ -48,6 +48,10 @@ int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_strid
 #define BLI_array_findindex(arr, arr_len, p) \
 	_bli_array_findindex(arr, arr_len, sizeof(*(arr)), p)
 
+int _bli_array_rfindindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p);
+#define BLI_array_rfindindex(arr, arr_len, p) \
+	_bli_array_rfindindex(arr, arr_len, sizeof(*(arr)), p)
+
 void _bli_array_binary_and(
         void *arr, const void *arr_a, const void *arr_b,
         unsigned int arr_len, size_t arr_stride);
diff --git a/source/blender/blenlib/intern/array_utils.c b/source/blender/blenlib/intern/array_utils.c
index 9c91da4abee..32f0111babd 100644
--- a/source/blender/blenlib/intern/array_utils.c
+++ b/source/blender/blenlib/intern/array_utils.c
@@ -134,8 +134,22 @@ void _bli_array_permute(
 int _bli_array_findindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p)
 {
 	const char *arr_step = (const char *)arr;
-	unsigned int i;
-	for (i = 0; i < arr_len; i++, arr_step += arr_stride) {
+	for (unsigned int i = 0; i < arr_len; i++, arr_step += arr_stride) {
+		if (memcmp(arr_step, p, arr_stride) == 0) {
+			return (int)i;
+		}
+	}
+	return -1;
+}
+
+/**
+ * A version of #BLI_array_findindex that searches from the end of the list.
+ */
+int _bli_array_rfindindex(const void *arr, unsigned int arr_len, size_t arr_stride, const void *p)
+{
+	const char *arr_step = (const char *)arr + (arr_stride * arr_len);
+	for (unsigned int i = arr_len; i-- != 0; ) {
+		arr_step -= arr_stride;
 		if (memcmp(arr_step, p, arr_stride) == 0) {
 			return (int)i;
 		}
diff --git a/tests/gtests/blenlib/BLI_array_utils_test.cc b/tests/gtests/blenlib/BLI_array_utils_test.cc
index e532419691a..eabf5bc72cf 100644
--- a/tests/gtests/blenlib/BLI_array_utils_test.cc
+++ b/tests/gtests/blenlib/BLI_array_utils_test.cc
@@ -5,6 +5,7 @@
 extern "C" {
 #include "BLI_utildefines.h"
 #include "BLI_array_utils.h"
+#include "BLI_stackdefines.h"
 }
 
 /* -------------------------------------------------------------------- */
@@ -44,33 +45,102 @@ TEST(array_utils, ReverseInt4)
 TEST(array_utils, FindIndexStringEmpty)
 {
 	char data[] = "", find = '0';
-	EXPECT_EQ(-1, BLI_array_findindex(data, ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(-1, BLI_array_findindex(data,  ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(-1, BLI_array_rfindindex(data, ARRAY_SIZE(data) - 1, &find));
 }
 
 TEST(array_utils, FindIndexStringSingle)
 {
 	char data[] = "0", find = '0';
-	EXPECT_EQ(0, BLI_array_findindex(data, ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(0, BLI_array_findindex(data,  ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(0, BLI_array_rfindindex(data, ARRAY_SIZE(data) - 1, &find));
 }
 
 TEST(array_utils, FindIndexStringSingleMissing)
 {
 	char data[] = "1", find = '0';
-	EXPECT_EQ(-1, BLI_array_findindex(data, ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(-1, BLI_array_findindex(data,  ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(-1, BLI_array_rfindindex(data, ARRAY_SIZE(data) - 1, &find));
 }
 
 TEST(array_utils, FindIndexString4)
 {
 	char data[] = "0123", find = '3';
-	EXPECT_EQ(3, BLI_array_findindex(data, ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(3, BLI_array_findindex(data,  ARRAY_SIZE(data) - 1, &find));
+	EXPECT_EQ(3, BLI_array_rfindindex(data, ARRAY_SIZE(data) - 1, &find));
 }
 
 TEST(array_utils, FindIndexInt4)
 {
-	int data[] = {0, 1, 2, 3}, find = 2;
-	EXPECT_EQ(2, BLI_array_findindex(data, ARRAY_SIZE(data) - 1, &find));
+	int data[] = {0, 1, 2, 3}, find = 3;
+	EXPECT_EQ(3, BLI_array_findindex(data,  ARRAY_SIZE(data), &find));
+	EXPECT_EQ(3, BLI_array_rfindindex(data, ARRAY_SIZE(data), &find));
 }
 
+TEST(array_utils, FindIndexInt4_DupeEnd)
+{
+	int data[] = {0, 1, 2, 0}, find = 0;
+	EXPECT_EQ(0, BLI_array_findindex(data,  ARRAY_SIZE(data), &find));
+	EXPECT_EQ(3, BLI_array_rfindindex(data, ARRAY_SIZE(data), &find));
+}
+
+TEST(array_utils, FindIndexInt4_DupeMid)
+{
+	int data[] = {1, 0, 0, 3}, find = 0;
+	EXPECT_EQ(1, BLI_array_findindex(data,  ARRAY_SIZE(data), &find));
+	EXPECT_EQ(2, BLI_array_rfindindex(data, ARRAY_SIZE(data), &find));
+}
+
+TEST(array_utils, FindIndexPointer)
+{
+	const char *data[4] = {NULL};
+	STACK_DECLARE(data);
+
+	STACK_INIT(data, ARRAY_SIZE(data));
+
+	const char *a = "a", *b = "b", *c = "c", *d = "d";
+
+#define STACK_PUSH_AND_CHECK_FORWARD(v, i) { \
+	STACK_PUSH(data, v); \
+	EXPECT_EQ(i, BLI_array_findindex(data,  STACK_SIZE(data), &(v))); \
+} ((void)0)
+
+#define STACK_PUSH_AND_CHECK_BACKWARD(v, i) { \
+	STACK_PUSH(data, v); \
+	EXPECT_EQ(i, BLI_array_rfindindex(data, STACK_SIZE(data), &(v))); \
+} ((void)0)
+
+#define STACK_PUSH_AND_CHECK_BOTH(v, i) { \
+	STACK_PUSH(data, v); \
+	EXPECT_EQ(i, BLI_array_findindex(data,  STACK_SIZE(data), &(v))); \
+	EXPECT_EQ(i, BLI_array_rfindindex(data, STACK_SIZE(data), &(v))); \
+} ((void)0)
+
+	STACK_PUSH_AND_CHECK_BOTH(a, 0);
+	STACK_PUSH_AND_CHECK_BOTH(b, 1);
+	STACK_PUSH_AND_CHECK_BOTH(c, 2);
+	STACK_PUSH_AND_CHECK_BOTH(d, 3);
+
+	STACK_POP(data);
+	STACK_PUSH_AND_CHECK_BACKWARD(a, 3);
+
+	STACK_POP(data);
+	STACK_PUSH_AND_CHECK_FORWARD(a, 0);
+
+	STACK_POP(data);
+	STACK_POP(data);
+
+	STACK_PUSH_AND_CHECK_BACKWARD(b, 2);
+	STACK_PUSH_AND_CHECK_BACKWARD(a, 3);
+
+#undef STACK_PUSH_AND_CHECK_FORWARD
+#undef STACK_PUSH_AND_CHECK_BACKWARD
+#undef STACK_PUSH_AND_CHECK_BOTH
+
+}
+
+
+
 /* BLI_array_binary_and */
 #define BINARY_AND_TEST(data_cmp, data_a, data_b, data_combine, length) \
 { \