# HG changeset patch # User Mike Becker # Date 1401717851 -7200 # Node ID 7084e8e8433ca8e2424c266bd14418c266074d10 # Parent 49cebb8eceff43f419b36c681bb7913c93d331b8 refactoring of list tests + some bug fixes diff -r 49cebb8eceff -r 7084e8e8433c test/list_tests.c --- a/test/list_tests.c Tue May 06 14:35:29 2014 +0200 +++ b/test/list_tests.c Mon Jun 02 16:04:11 2014 +0200 @@ -30,7 +30,8 @@ #include "ucx/utils.h" UCX_TEST(test_ucx_list_append) { - UcxList *list = ucx_list_append(NULL, (void*)"Hello"); + UcxList *list, *first; + list = first = ucx_list_append(NULL, (void*)"Hello"); UCX_TEST_BEGIN UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, @@ -38,8 +39,10 @@ list = ucx_list_append(list, (void*)" World!"); + UCX_TEST_ASSERT(list == first, "does not return first element"); UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, "failed"); + UCX_TEST_ASSERT(list->next->prev == list, "failed"); UCX_TEST_ASSERT(list->next->next == NULL, "failed"); UCX_TEST_END @@ -47,7 +50,8 @@ } UCX_TEST(test_ucx_list_prepend) { - UcxList *list = ucx_list_prepend(NULL, (void*)" World!"); + UcxList *list, *last; + list = last = ucx_list_prepend(NULL, (void*)" World!"); UCX_TEST_BEGIN list = ucx_list_prepend(list, (void*)"Hello"); @@ -56,25 +60,33 @@ "failed"); UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, "failed"); + UCX_TEST_ASSERT(list == last->prev, "does not return first element"); UCX_TEST_ASSERT(list->next->next == NULL, "failed"); + UCX_TEST_ASSERT(list->prev == NULL, "failed"); UCX_TEST_END ucx_list_free(list); } UCX_TEST(test_ucx_list_equals) { - UcxList *list = ucx_list_append(NULL, (void*)"Hello"); - list = ucx_list_append(list, (void*)" World!"); - UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!"); - list2 = ucx_list_prepend(list2, (void*)"Hello"); + const char *hello = "Hello"; + const char *world = " World!"; + UcxList *list = ucx_list_append(NULL, (void*)hello); + list = ucx_list_append(list, (void*)world); + UcxList *list2 = ucx_list_prepend(NULL, (void*)world); + list2 = ucx_list_prepend(list2, (void*)hello); UcxList *list3 = ucx_list_prepend(NULL, (void*)" Welt!"); list3 = ucx_list_prepend(list3, (void*)"Hallo"); + UcxList *list4 = ucx_list_prepend(NULL, (void*)" World!"); + list4 = ucx_list_prepend(list4, (void*)"Hello"); UCX_TEST_BEGIN - UCX_TEST_ASSERT(ucx_list_equals(list, list2, ucx_strcmp, NULL), "failed"); + UCX_TEST_ASSERT(ucx_list_equals(list, list4, ucx_strcmp, NULL), "failed"); UCX_TEST_ASSERT(!ucx_list_equals(list, list3, ucx_strcmp, NULL), "failed"); + UCX_TEST_ASSERT(ucx_list_equals(list, list2, NULL, NULL), "failed"); UCX_TEST_END + ucx_list_free(list4); ucx_list_free(list3); ucx_list_free(list2); ucx_list_free(list); @@ -82,18 +94,28 @@ UCX_TEST(test_ucx_list_concat) { UcxList *list = ucx_list_append(NULL, (void*)"Hello"); + list = ucx_list_append(list, (void*)" my "); UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!"); + list2 = ucx_list_prepend(list2, (void*)" sweet "); UCX_TEST_BEGIN list = ucx_list_concat(list, list2); + list = ucx_list_concat(list, NULL); + list = ucx_list_concat(NULL, list); - UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0, + UCX_TEST_ASSERT(!strncmp((const char*)list->data, "Hello", 5), + "failed"); + UCX_TEST_ASSERT(!strncmp((const char*)list->next->data, " my ", 4), "failed"); - UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0, + UCX_TEST_ASSERT(!strncmp((const char*)list->next->next->data, " sweet ", 7), "failed"); - UCX_TEST_ASSERT(list->next->next == NULL, "failed"); + UCX_TEST_ASSERT(!strncmp((const char*)ucx_list_last(list)->data, + " World!", 7), "failed"); + + UCX_TEST_ASSERT(list->prev == NULL, "failed"); UCX_TEST_END + // don't free list2, as it is freed by freeing list; ucx_list_free(list); } @@ -107,6 +129,8 @@ UCX_TEST_BEGIN UCX_TEST_ASSERT(ucx_list_size(list) == 5, "failed"); + list = ucx_list_remove(list, ucx_list_get(list, 2)); + UCX_TEST_ASSERT(ucx_list_size(list) == 4, "failed after removal"); UCX_TEST_END ucx_list_free(list); @@ -122,6 +146,9 @@ const char* first = (const char*) (ucx_list_first(list)->data); UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed"); + UCX_TEST_ASSERT(ucx_list_first(list->next->next) == list, "failed"); + UCX_TEST_ASSERT(!ucx_list_first(NULL), + "does not return NULL on an empty list"); UCX_TEST_END ucx_list_free(list); @@ -134,9 +161,12 @@ UCX_TEST_BEGIN - const char* last = (const char*) (ucx_list_last(list)->data); + const char* last = (const char*) (ucx_list_last(list->next->next)->data); UCX_TEST_ASSERT(strncmp(last, "last!", 5) == 0, "failed"); + UCX_TEST_ASSERT(ucx_list_last(list) == list->next->next, "failed"); + UCX_TEST_ASSERT(!ucx_list_last(NULL), + "does not return NULL on an empty list"); UCX_TEST_END ucx_list_free(list); @@ -149,9 +179,16 @@ UCX_TEST_BEGIN + const char* first = (const char*) (ucx_list_get(list, 0)->data); const char* mid = (const char*) (ucx_list_get(list, 1)->data); + const char* last = (const char*) (ucx_list_get(list, 2)->data); + UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed"); UCX_TEST_ASSERT(strncmp(mid, "the ", 4) == 0, "failed"); + UCX_TEST_ASSERT(strncmp(last, "mid!", 4) == 0, "failed"); + UCX_TEST_ASSERT(!ucx_list_get(list, -1), "out of bounds (neg)"); + UCX_TEST_ASSERT(!ucx_list_get(list, 3), "out of bounds"); + UCX_TEST_ASSERT(!ucx_list_get(NULL, 0), "empty list"); UCX_TEST_END ucx_list_free(list); @@ -169,8 +206,10 @@ UCX_TEST_ASSERT(ucx_list_indexof(list, ucx_list_get(list, 2)) == 2, "failed"); - UcxList *otherlist = ucx_list_append(NULL, (void*) "foobar"); + UcxList *otherlist = ucx_list_append(NULL, (void*) "the "); UCX_TEST_ASSERT(ucx_list_indexof(list, otherlist) == -1, "failed"); + UCX_TEST_ASSERT(ucx_list_indexof(NULL, otherlist) == -1, "empty list"); + ucx_list_free(otherlist); UCX_TEST_END @@ -178,9 +217,10 @@ } UCX_TEST(test_ucx_list_find) { + const char* teststr = "string!"; UcxList *l = ucx_list_append(NULL, (void*)"find "); l = ucx_list_append(l, (void*)"some "); - l = ucx_list_append(l, (void*)"string!"); + l = ucx_list_append(l, (void*)teststr); UCX_TEST_BEGIN @@ -189,6 +229,12 @@ UCX_TEST_ASSERT(ucx_list_find(l,(void*)"a",ucx_strcmp,NULL) == -1, "finds non-existing string"); + UCX_TEST_ASSERT(ucx_list_find(l,(void*)teststr,NULL,NULL) == 2, + "doesn't find integer without cmp_func"); + + UCX_TEST_ASSERT(ucx_list_find(NULL, (void*)"some ",ucx_strcmp,NULL) == -1, + "empty list"); + UCX_TEST_END ucx_list_free(l); } @@ -311,13 +357,31 @@ list = ucx_list_append(list, (void*)"for"); list = ucx_list_append(list, (void*)"partial"); list = ucx_list_append(list, (void*)"correctness"); + list = ucx_list_append(list, (void*)"of"); + list = ucx_list_append(list, (void*)"the"); + list = ucx_list_append(list, (void*)"sort"); + list = ucx_list_append(list, (void*)"function"); + list = ucx_list_append(list, (void*)"that"); + list = ucx_list_append(list, (void*)"shall"); + list = ucx_list_append(list, (void*)"pass"); + list = ucx_list_append(list, (void*)"this"); + list = ucx_list_append(list, (void*)"test"); UcxList *expected = ucx_list_append(NULL, (void*)"a"); expected = ucx_list_append(expected, (void*)"correctness"); expected = ucx_list_append(expected, (void*)"for"); + expected = ucx_list_append(expected, (void*)"function"); expected = ucx_list_append(expected, (void*)"is"); + expected = ucx_list_append(expected, (void*)"of"); expected = ucx_list_append(expected, (void*)"partial"); + expected = ucx_list_append(expected, (void*)"pass"); + expected = ucx_list_append(expected, (void*)"shall"); + expected = ucx_list_append(expected, (void*)"sort"); expected = ucx_list_append(expected, (void*)"test"); + expected = ucx_list_append(expected, (void*)"test"); + expected = ucx_list_append(expected, (void*)"that"); + expected = ucx_list_append(expected, (void*)"the"); + expected = ucx_list_append(expected, (void*)"this"); expected = ucx_list_append(expected, (void*)"this"); list = ucx_list_sort(list, ucx_strcmp, NULL); @@ -325,12 +389,15 @@ UCX_TEST_BEGIN UCX_TEST_ASSERT( ucx_list_equals(list, expected, ucx_strcmp, NULL), "failed"); + UCX_TEST_ASSERT(ucx_list_size(list) == 16, "list has now a wrong size"); UcxList *l = list; UCX_TEST_ASSERT(l->prev == NULL, "prev field of first entry is not null"); while (l->next != NULL) { - UCX_TEST_ASSERT(l->next->prev == l, "prev pointer corrupted"); + UCX_TEST_ASSERT(l->next->prev == l, "next or prev pointer corrupted"); l = l->next; } + UCX_TEST_ASSERT(!ucx_list_sort(NULL, ucx_strcmp, NULL), + "failed to sort empty list"); UCX_TEST_END ucx_list_free(expected); diff -r 49cebb8eceff -r 7084e8e8433c ucx/list.c --- a/ucx/list.c Tue May 06 14:35:29 2014 +0200 +++ b/ucx/list.c Mon Jun 02 16:04:11 2014 +0200 @@ -121,7 +121,9 @@ if (l1) { UcxList *last = ucx_list_last(l1); last->next = l2; - l2->prev = last; + if (l2) { + l2->prev = last; + } return l1; } else { return l2; @@ -150,7 +152,7 @@ return -1; } -UcxList *ucx_list_get(const UcxList *l, int index) { +UcxList *ucx_list_get(const UcxList *l, size_t index) { if (l == NULL) return NULL; const UcxList *e = l; @@ -196,7 +198,7 @@ return s; } -UcxList *ucx_list_sort_merge(int length, +static UcxList *ucx_list_sort_merge(int length, UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, cmp_func fnc, void* data) { @@ -248,6 +250,8 @@ int ln = 1; UcxList *restrict ls = l, *restrict le, *restrict re; + + // check how many elements are already sorted lc = ls; while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { lc = lc->next; @@ -261,27 +265,30 @@ UcxList *rc; int rn = 1; rc = le; + // skip already sorted elements while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { rc = rc->next; rn++; } re = rc->next; - // Something left? Sort it! - UcxList *remainder = re; - size_t remainder_length = ucx_list_size(remainder); - if (remainder != NULL) { - remainder = ucx_list_sort(remainder, fnc, data); - } - // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them UcxList *sorted = ucx_list_sort_merge(ln+rn, ls, le, re, fnc, data); + + // Something left? Sort it! + size_t remainder_length = ucx_list_size(re); + if (remainder_length > 0) { + UcxList *remainder = ucx_list_sort(re, fnc, data); - // merge sorted list with (also sorted) remainder - l = ucx_list_sort_merge(ln+rn+remainder_length, - sorted, remainder, NULL, fnc, data); + // merge sorted list with (also sorted) remainder + l = ucx_list_sort_merge(ln+rn+remainder_length, + sorted, remainder, NULL, fnc, data); + } else { + // no remainder - we've got our sorted list + l = sorted; + } return l; } diff -r 49cebb8eceff -r 7084e8e8433c ucx/list.h --- a/ucx/list.h Tue May 06 14:35:29 2014 +0200 +++ b/ucx/list.h Mon Jun 02 16:04:11 2014 +0200 @@ -169,7 +169,7 @@ /** * Inserts an element at the end of the list. * - * This is generally an O(n) operation, as the end of the list is seeked with + * This is generally an O(n) operation, as the end of the list is retrieved with * ucx_list_last(). * * @param list the list where to append the data, or NULL to @@ -273,7 +273,7 @@ * @return the element at the specified index or NULL, if the * index is greater than the list size */ -UcxList *ucx_list_get(const UcxList *list, int index); +UcxList *ucx_list_get(const UcxList *list, size_t index); /** * Returns the index of an element. @@ -350,7 +350,7 @@ * mylist = ucx_list_remove(mylist, myelem);. * * @param list the list from which the element shall be removed - * @param element the element to removed + * @param element the element to remove * @return returns the updated list pointer or NULL, if the list * is now empty */ @@ -363,7 +363,7 @@ * * @param allocator the allocator to use * @param list the list from which the element shall be removed - * @param element the element to removed + * @param element the element to remove * @return returns the updated list pointer or NULL, if the list * @see ucx_list_remove() */