diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-06-10 13:23:34 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-06-10 13:26:56 +0300 |
commit | 6e844da9dad5bcbc1fb747879fa2a11715223d84 (patch) | |
tree | c93e5adc6e51eb92b8c4c6105467587aac622473 /tests | |
parent | 0446c73c4a368d8393f434fbe745ada54e4225d3 (diff) |
GTest: add test for listbase sorting
Check for correct sort and stable order for matching values.
Diffstat (limited to 'tests')
-rw-r--r-- | tests/gtests/blenlib/BLI_listbase_test.cc | 218 | ||||
-rw-r--r-- | tests/gtests/blenlib/BLI_ressource_strings.h | 2 |
2 files changed, 219 insertions, 1 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); +} diff --git a/tests/gtests/blenlib/BLI_ressource_strings.h b/tests/gtests/blenlib/BLI_ressource_strings.h index b823f14af53..d7002d748c9 100644 --- a/tests/gtests/blenlib/BLI_ressource_strings.h +++ b/tests/gtests/blenlib/BLI_ressource_strings.h @@ -3,7 +3,7 @@ #ifndef __BLENDER_TESTING_BLI_RESSOURCE_STRING_H__ #define __BLENDER_TESTING_BLI_RESSOURCE_STRING_H__ -const char *words10k = +const char words10k[] = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nullam auctor ultrices purus tincidunt mollis. Vestibulum " "tincidunt imperdiet molestie. Vivamus posuere, risus ut mollis rutrum, lacus nulla mollis velit, consectetur auctor " "erat est in odio. Proin quis lobortis ex. Ut id quam lacus. Morbi ultrices orci quis sem suscipit tincidunt. Nullam " |