Merge branch 'master' into temp-ghash-setopstemp-ghash-setops

1 files changed, 218 insertions, 0 deletions

diff --git a/tests/gtests/blenlib/BLI_listbase_test.cc b/tests/gtests/blenlib/BLI_listbase_test.cc
index 4b4d5d80a43..994b8f74541 100644
--- a/tests/gtests/blenlib/BLI_listbase_test.cc
+++ b/tests/gtests/blenlib/BLI_listbase_test.cc
@@ -3,10 +3,69 @@
 #include "testing/testing.h"
 
 extern "C" {
+#include "BLI_array_utils.h"
 #include "BLI_listbase.h"
 #include "MEM_guardedalloc.h"
+
+#include "BLI_string.h"
+#include "BLI_path_util.h"
+#include "BLI_ressource_strings.h"
+}
+
+
+/* local validation function */
+static bool listbase_is_valid(const ListBase *listbase)
+{
+#define TESTFAIL(test) \
+	if (!(test)) goto fail;
+
+	if (listbase->first) {
+		const Link *prev, *link;
+		link = (Link *)listbase->first;
+		TESTFAIL(link->prev == NULL);
+
+		link = (Link *)listbase->last;
+		TESTFAIL(link->next == NULL);
+
+		prev = NULL;
+		link = (Link *)listbase->first;
+		do {
+			TESTFAIL(link->prev == prev);
+		} while ((prev = link), (link = link->next));
+		TESTFAIL(prev == listbase->last);
+
+		prev = NULL;
+		link = (Link *)listbase->last;
+		do {
+			TESTFAIL(link->next == prev);
+		} while ((prev = link), (link = link->prev));
+		TESTFAIL(prev == listbase->first);
+	}
+	else {
+		TESTFAIL(listbase->last == NULL);
+	}
+#undef TESTFAIL
+
+	return true;
+
+fail:
+	return false;
+}
+
+static int char_switch(char *string, char ch_src, char ch_dst)
+{
+	int tot = 0;
+	while (*string != 0) {
+		if (*string == ch_src) {
+			*string = ch_dst;
+			tot++;
+		}
+		string++;
+	}
+	return tot;
 }
 
+
 TEST(listbase, FindLinkOrIndex)
 {
 	ListBase lb;
@@ -37,3 +96,162 @@ TEST(listbase, FindLinkOrIndex)
 
 	BLI_freelistN(&lb);
 }
+
+
+/* -------------------------------------------------------------------- */
+/* Sort utilities & test */
+
+static int testsort_array_str_cmp(const void *a, const void *b)
+{
+	int i = strcmp(*(const char **)a, *(const char **)b);
+	return (i > 0) ? 1 : (i < 0) ? -1 : 0;
+}
+
+static int testsort_listbase_str_cmp(const void *a, const void *b)
+{
+	const LinkData *link_a = (LinkData *)a;
+	const LinkData *link_b = (LinkData *)b;
+	int i = strcmp((const char *)link_a->data, (const char *)link_b->data);
+	return (i > 0) ? 1 : (i < 0) ? -1 : 0;
+}
+
+static int testsort_array_str_cmp_reverse(const void *a, const void *b)
+{
+	return -testsort_array_str_cmp(a, b);
+}
+
+static int testsort_listbase_str_cmp_reverse(const void *a, const void *b)
+{
+	return -testsort_listbase_str_cmp(a, b);
+}
+
+/* check array and listbase compare */
+static bool testsort_listbase_array_str_cmp(ListBase *lb, char **arr, int arr_tot)
+{
+	LinkData *link_step;
+	int i;
+
+	link_step = (LinkData *)lb->first;
+	for (i = 0; i < arr_tot; i++) {
+		if (strcmp(arr[i], (char *)link_step->data) != 0) {
+			return false;
+		}
+		link_step = link_step->next;
+	}
+	if (link_step) {
+		return false;
+	}
+
+	return true;
+}
+
+/* assumes nodes are allocated in-order */
+static bool testsort_listbase_sort_is_stable(ListBase *lb, bool forward)
+{
+	LinkData *link_step;
+
+	link_step = (LinkData *)lb->first;
+	while (link_step && link_step->next) {
+		if (strcmp((const char *)link_step->data, (const char *)link_step->next->data) == 0) {
+			if ((link_step < link_step->next) != forward) {
+				return false;
+			}
+		}
+		link_step = link_step->next;
+	}
+	return true;
+}
+
+TEST(listbase, Sort)
+{
+	const int words_len = sizeof(words10k) - 1;
+	char     *words = BLI_strdupn(words10k, words_len);
+	int       words_tot;
+	char    **words_arr;  /* qsort for comparison */
+	int i;
+	char *w_step;
+	ListBase words_lb;
+	LinkData *words_linkdata_arr;
+
+	/* delimit words */
+	words_tot = 1 + char_switch(words, ' ', '\0');
+
+	words_arr = (char **)MEM_mallocN(sizeof(*words_arr) * words_tot, __func__);
+
+	words_linkdata_arr = (LinkData *)MEM_mallocN(sizeof(*words_linkdata_arr) * words_tot, __func__);
+
+	/* create array */
+	w_step = words;
+	for (i = 0; i < words_tot; i++) {
+		words_arr[i] = w_step;
+		w_step += strlen(w_step) + 1;
+	}
+
+	/* sort empty list */
+	{
+		BLI_listbase_clear(&words_lb);
+		BLI_listbase_sort(&words_lb, testsort_listbase_str_cmp);
+		EXPECT_TRUE(listbase_is_valid(&words_lb));
+	}
+
+	/* sort single single */
+	{
+		LinkData link;
+		link.data = words;
+		BLI_addtail(&words_lb, &link);
+		BLI_listbase_sort(&words_lb, testsort_listbase_str_cmp);
+		EXPECT_TRUE(listbase_is_valid(&words_lb));
+		BLI_listbase_clear(&words_lb);
+	}
+
+	/* create listbase */
+	BLI_listbase_clear(&words_lb);
+	w_step = words;
+	for (i = 0; i < words_tot; i++) {
+		LinkData *link = &words_linkdata_arr[i];
+		link->data = w_step;
+		BLI_addtail(&words_lb, link);
+		w_step += strlen(w_step) + 1;
+	}
+	EXPECT_TRUE(listbase_is_valid(&words_lb));
+
+	/* sort (forward) */
+	{
+		qsort(words_arr, words_tot, sizeof(*words_arr), testsort_array_str_cmp);
+
+		BLI_listbase_sort(&words_lb, testsort_listbase_str_cmp);
+		EXPECT_TRUE(listbase_is_valid(&words_lb));
+		EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_tot));
+		EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, true));
+	}
+
+	/* sort (reverse) */
+	{
+		qsort(words_arr, words_tot, sizeof(*words_arr), testsort_array_str_cmp_reverse);
+
+		BLI_listbase_sort(&words_lb, testsort_listbase_str_cmp_reverse);
+		EXPECT_TRUE(listbase_is_valid(&words_lb));
+		EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_tot));
+		EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, true));
+	}
+
+	/* sort (forward but after reversing, test stability in alternate direction) */
+	{
+		BLI_array_reverse(words_arr, words_tot);
+		BLI_listbase_reverse(&words_lb);
+
+		EXPECT_TRUE(listbase_is_valid(&words_lb));
+		EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_tot));
+		EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, false));
+
+		/* and again */
+		BLI_array_reverse(words_arr, words_tot);
+		BLI_listbase_sort(&words_lb, testsort_listbase_str_cmp_reverse);
+		EXPECT_TRUE(testsort_listbase_array_str_cmp(&words_lb, words_arr, words_tot));
+		EXPECT_TRUE(testsort_listbase_sort_is_stable(&words_lb, false));
+	}
+
+	MEM_freeN(words);
+	MEM_freeN(words_arr);
+	MEM_freeN(words_linkdata_arr);
+}