Mercurial > hg > ucx / changeset

     1.1 --- a/test/list_tests.c	Tue May 06 14:35:29 2014 +0200
     1.2 +++ b/test/list_tests.c	Mon Jun 02 16:04:11 2014 +0200
     1.3 @@ -30,7 +30,8 @@
     1.4  #include "ucx/utils.h"
     1.5  
     1.6  UCX_TEST(test_ucx_list_append) {
     1.7 -    UcxList *list = ucx_list_append(NULL, (void*)"Hello");
     1.8 +    UcxList *list, *first;
     1.9 +    list = first = ucx_list_append(NULL, (void*)"Hello");
    1.10      UCX_TEST_BEGIN
    1.11      
    1.12      UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0,
    1.13 @@ -38,8 +39,10 @@
    1.14      
    1.15      list = ucx_list_append(list, (void*)" World!");
    1.16      
    1.17 +    UCX_TEST_ASSERT(list == first, "does not return first element");
    1.18      UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0,
    1.19              "failed");
    1.20 +    UCX_TEST_ASSERT(list->next->prev == list, "failed");
    1.21      UCX_TEST_ASSERT(list->next->next == NULL, "failed");
    1.22      UCX_TEST_END
    1.23      
    1.24 @@ -47,7 +50,8 @@
    1.25  }
    1.26  
    1.27  UCX_TEST(test_ucx_list_prepend) {
    1.28 -    UcxList *list = ucx_list_prepend(NULL, (void*)" World!");
    1.29 +    UcxList *list, *last;
    1.30 +    list = last = ucx_list_prepend(NULL, (void*)" World!");
    1.31      UCX_TEST_BEGIN
    1.32  
    1.33      list = ucx_list_prepend(list, (void*)"Hello");
    1.34 @@ -56,25 +60,33 @@
    1.35              "failed");
    1.36      UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0,
    1.37              "failed");
    1.38 +    UCX_TEST_ASSERT(list == last->prev, "does not return first element");
    1.39      UCX_TEST_ASSERT(list->next->next == NULL, "failed");
    1.40 +    UCX_TEST_ASSERT(list->prev == NULL, "failed");
    1.41      
    1.42      UCX_TEST_END
    1.43      ucx_list_free(list);
    1.44  }
    1.45  
    1.46  UCX_TEST(test_ucx_list_equals) {
    1.47 -    UcxList *list = ucx_list_append(NULL, (void*)"Hello");
    1.48 -    list = ucx_list_append(list, (void*)" World!");
    1.49 -    UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!");
    1.50 -    list2 = ucx_list_prepend(list2, (void*)"Hello");
    1.51 +    const char *hello = "Hello";
    1.52 +    const char *world = " World!";
    1.53 +    UcxList *list = ucx_list_append(NULL, (void*)hello);
    1.54 +    list = ucx_list_append(list, (void*)world);
    1.55 +    UcxList *list2 = ucx_list_prepend(NULL, (void*)world);
    1.56 +    list2 = ucx_list_prepend(list2, (void*)hello);
    1.57      UcxList *list3 = ucx_list_prepend(NULL, (void*)" Welt!");
    1.58      list3 = ucx_list_prepend(list3, (void*)"Hallo");
    1.59 +    UcxList *list4 = ucx_list_prepend(NULL, (void*)" World!");
    1.60 +    list4 = ucx_list_prepend(list4, (void*)"Hello");
    1.61      UCX_TEST_BEGIN
    1.62      
    1.63 -    UCX_TEST_ASSERT(ucx_list_equals(list, list2, ucx_strcmp, NULL), "failed");
    1.64 +    UCX_TEST_ASSERT(ucx_list_equals(list, list4, ucx_strcmp, NULL), "failed");
    1.65      UCX_TEST_ASSERT(!ucx_list_equals(list, list3, ucx_strcmp, NULL), "failed");
    1.66 +    UCX_TEST_ASSERT(ucx_list_equals(list, list2, NULL, NULL), "failed");
    1.67      
    1.68      UCX_TEST_END
    1.69 +    ucx_list_free(list4);
    1.70      ucx_list_free(list3);
    1.71      ucx_list_free(list2);
    1.72      ucx_list_free(list);
    1.73 @@ -82,18 +94,28 @@
    1.74  
    1.75  UCX_TEST(test_ucx_list_concat) {
    1.76      UcxList *list = ucx_list_append(NULL, (void*)"Hello");
    1.77 +    list = ucx_list_append(list, (void*)" my ");
    1.78      UcxList *list2 = ucx_list_prepend(NULL, (void*)" World!");
    1.79 +    list2 = ucx_list_prepend(list2, (void*)" sweet ");
    1.80      UCX_TEST_BEGIN
    1.81      
    1.82      list = ucx_list_concat(list, list2);
    1.83 +    list = ucx_list_concat(list, NULL);
    1.84 +    list = ucx_list_concat(NULL, list);
    1.85      
    1.86 -    UCX_TEST_ASSERT(strncmp((const char*)list->data, "Hello", 5) == 0,
    1.87 +    UCX_TEST_ASSERT(!strncmp((const char*)list->data, "Hello", 5),
    1.88              "failed");
    1.89 -    UCX_TEST_ASSERT(strncmp((const char*)list->next->data, " World!", 7) == 0,
    1.90 +    UCX_TEST_ASSERT(!strncmp((const char*)list->next->data, " my ", 4),
    1.91              "failed");
    1.92 -    UCX_TEST_ASSERT(list->next->next == NULL, "failed");
    1.93 +    UCX_TEST_ASSERT(!strncmp((const char*)list->next->next->data, " sweet ", 7),
    1.94 +            "failed");
    1.95 +    UCX_TEST_ASSERT(!strncmp((const char*)ucx_list_last(list)->data,
    1.96 +            " World!", 7), "failed");
    1.97 +
    1.98 +    UCX_TEST_ASSERT(list->prev == NULL, "failed");
    1.99      
   1.100      UCX_TEST_END
   1.101 +    // don't free list2, as it is freed by freeing list;
   1.102      ucx_list_free(list);
   1.103  }
   1.104  
   1.105 @@ -107,6 +129,8 @@
   1.106      UCX_TEST_BEGIN
   1.107      
   1.108      UCX_TEST_ASSERT(ucx_list_size(list) == 5, "failed");
   1.109 +    list = ucx_list_remove(list, ucx_list_get(list, 2));
   1.110 +    UCX_TEST_ASSERT(ucx_list_size(list) == 4, "failed after removal");
   1.111      
   1.112      UCX_TEST_END
   1.113      ucx_list_free(list);
   1.114 @@ -122,6 +146,9 @@
   1.115      const char* first = (const char*) (ucx_list_first(list)->data);
   1.116      
   1.117      UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed");
   1.118 +    UCX_TEST_ASSERT(ucx_list_first(list->next->next) == list, "failed");
   1.119 +    UCX_TEST_ASSERT(!ucx_list_first(NULL),
   1.120 +        "does not return NULL on an empty list");
   1.121      
   1.122      UCX_TEST_END
   1.123      ucx_list_free(list);
   1.124 @@ -134,9 +161,12 @@
   1.125      
   1.126      UCX_TEST_BEGIN
   1.127      
   1.128 -    const char* last = (const char*) (ucx_list_last(list)->data);
   1.129 +    const char* last = (const char*) (ucx_list_last(list->next->next)->data);
   1.130      
   1.131      UCX_TEST_ASSERT(strncmp(last, "last!", 5) == 0, "failed");
   1.132 +    UCX_TEST_ASSERT(ucx_list_last(list) == list->next->next, "failed");
   1.133 +    UCX_TEST_ASSERT(!ucx_list_last(NULL),
   1.134 +        "does not return NULL on an empty list");
   1.135      
   1.136      UCX_TEST_END
   1.137      ucx_list_free(list);
   1.138 @@ -149,9 +179,16 @@
   1.139      
   1.140      UCX_TEST_BEGIN
   1.141      
   1.142 +    const char* first = (const char*) (ucx_list_get(list, 0)->data);
   1.143      const char* mid = (const char*) (ucx_list_get(list, 1)->data);
   1.144 +    const char* last = (const char*) (ucx_list_get(list, 2)->data);
   1.145      
   1.146 +    UCX_TEST_ASSERT(strncmp(first, "Find ", 5) == 0, "failed");
   1.147      UCX_TEST_ASSERT(strncmp(mid, "the ", 4) == 0, "failed");
   1.148 +    UCX_TEST_ASSERT(strncmp(last, "mid!", 4) == 0, "failed");
   1.149 +    UCX_TEST_ASSERT(!ucx_list_get(list, -1), "out of bounds (neg)");
   1.150 +    UCX_TEST_ASSERT(!ucx_list_get(list, 3), "out of bounds");
   1.151 +    UCX_TEST_ASSERT(!ucx_list_get(NULL, 0), "empty list");
   1.152      
   1.153      UCX_TEST_END
   1.154      ucx_list_free(list);
   1.155 @@ -169,8 +206,10 @@
   1.156      UCX_TEST_ASSERT(ucx_list_indexof(list, ucx_list_get(list, 2)) == 2,
   1.157          "failed");
   1.158      
   1.159 -    UcxList *otherlist = ucx_list_append(NULL, (void*) "foobar");
   1.160 +    UcxList *otherlist = ucx_list_append(NULL, (void*) "the ");
   1.161      UCX_TEST_ASSERT(ucx_list_indexof(list, otherlist) == -1, "failed");
   1.162 +    UCX_TEST_ASSERT(ucx_list_indexof(NULL, otherlist) == -1, "empty list");
   1.163 +
   1.164      ucx_list_free(otherlist);
   1.165      
   1.166      UCX_TEST_END
   1.167 @@ -178,9 +217,10 @@
   1.168  }
   1.169  
   1.170  UCX_TEST(test_ucx_list_find) {
   1.171 +    const char* teststr = "string!";
   1.172      UcxList *l = ucx_list_append(NULL, (void*)"find ");
   1.173      l = ucx_list_append(l, (void*)"some ");
   1.174 -    l = ucx_list_append(l, (void*)"string!");
   1.175 +    l = ucx_list_append(l, (void*)teststr);
   1.176      
   1.177      UCX_TEST_BEGIN
   1.178      
   1.179 @@ -189,6 +229,12 @@
   1.180      UCX_TEST_ASSERT(ucx_list_find(l,(void*)"a",ucx_strcmp,NULL) == -1,
   1.181          "finds non-existing string");
   1.182      
   1.183 +    UCX_TEST_ASSERT(ucx_list_find(l,(void*)teststr,NULL,NULL) == 2,
   1.184 +        "doesn't find integer without cmp_func");
   1.185 +    
   1.186 +    UCX_TEST_ASSERT(ucx_list_find(NULL, (void*)"some ",ucx_strcmp,NULL) == -1,
   1.187 +        "empty list");
   1.188 +    
   1.189      UCX_TEST_END
   1.190      ucx_list_free(l);
   1.191  }
   1.192 @@ -311,13 +357,31 @@
   1.193      list = ucx_list_append(list, (void*)"for");
   1.194      list = ucx_list_append(list, (void*)"partial");
   1.195      list = ucx_list_append(list, (void*)"correctness");
   1.196 +    list = ucx_list_append(list, (void*)"of");
   1.197 +    list = ucx_list_append(list, (void*)"the");
   1.198 +    list = ucx_list_append(list, (void*)"sort");
   1.199 +    list = ucx_list_append(list, (void*)"function");
   1.200 +    list = ucx_list_append(list, (void*)"that");
   1.201 +    list = ucx_list_append(list, (void*)"shall");
   1.202 +    list = ucx_list_append(list, (void*)"pass");
   1.203 +    list = ucx_list_append(list, (void*)"this");
   1.204 +    list = ucx_list_append(list, (void*)"test");
   1.205  
   1.206      UcxList *expected = ucx_list_append(NULL, (void*)"a");
   1.207      expected = ucx_list_append(expected, (void*)"correctness");
   1.208      expected = ucx_list_append(expected, (void*)"for");
   1.209 +    expected = ucx_list_append(expected, (void*)"function");
   1.210      expected = ucx_list_append(expected, (void*)"is");
   1.211 +    expected = ucx_list_append(expected, (void*)"of");
   1.212      expected = ucx_list_append(expected, (void*)"partial");
   1.213 +    expected = ucx_list_append(expected, (void*)"pass");
   1.214 +    expected = ucx_list_append(expected, (void*)"shall");
   1.215 +    expected = ucx_list_append(expected, (void*)"sort");
   1.216      expected = ucx_list_append(expected, (void*)"test");
   1.217 +    expected = ucx_list_append(expected, (void*)"test");
   1.218 +    expected = ucx_list_append(expected, (void*)"that");
   1.219 +    expected = ucx_list_append(expected, (void*)"the");
   1.220 +    expected = ucx_list_append(expected, (void*)"this");
   1.221      expected = ucx_list_append(expected, (void*)"this");
   1.222  
   1.223      list = ucx_list_sort(list, ucx_strcmp, NULL);
   1.224 @@ -325,12 +389,15 @@
   1.225      UCX_TEST_BEGIN
   1.226      UCX_TEST_ASSERT(
   1.227              ucx_list_equals(list, expected, ucx_strcmp, NULL), "failed");
   1.228 +    UCX_TEST_ASSERT(ucx_list_size(list) == 16, "list has now a wrong size");
   1.229      UcxList *l = list;
   1.230      UCX_TEST_ASSERT(l->prev == NULL, "prev field of first entry is not null");
   1.231      while (l->next != NULL) {
   1.232 -        UCX_TEST_ASSERT(l->next->prev == l, "prev pointer corrupted");
   1.233 +        UCX_TEST_ASSERT(l->next->prev == l, "next or prev pointer corrupted");
   1.234          l = l->next;
   1.235      }
   1.236 +    UCX_TEST_ASSERT(!ucx_list_sort(NULL, ucx_strcmp, NULL),
   1.237 +        "failed to sort empty list");
   1.238      UCX_TEST_END
   1.239  
   1.240      ucx_list_free(expected);

     2.1 --- a/ucx/list.c	Tue May 06 14:35:29 2014 +0200
     2.2 +++ b/ucx/list.c	Mon Jun 02 16:04:11 2014 +0200
     2.3 @@ -121,7 +121,9 @@
     2.4      if (l1) {
     2.5          UcxList *last = ucx_list_last(l1);
     2.6          last->next = l2;
     2.7 -        l2->prev = last;
     2.8 +        if (l2) {
     2.9 +            l2->prev = last;
    2.10 +        }
    2.11          return l1;
    2.12      } else {
    2.13          return l2;
    2.14 @@ -150,7 +152,7 @@
    2.15      return -1;
    2.16  }
    2.17  
    2.18 -UcxList *ucx_list_get(const UcxList *l, int index) {
    2.19 +UcxList *ucx_list_get(const UcxList *l, size_t index) {
    2.20      if (l == NULL) return NULL;
    2.21  
    2.22      const UcxList *e = l;
    2.23 @@ -196,7 +198,7 @@
    2.24      return s;
    2.25  }
    2.26  
    2.27 -UcxList *ucx_list_sort_merge(int length,
    2.28 +static UcxList *ucx_list_sort_merge(int length,
    2.29          UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
    2.30          cmp_func fnc, void* data) {
    2.31  
    2.32 @@ -248,6 +250,8 @@
    2.33      int ln = 1;
    2.34  
    2.35      UcxList *restrict ls = l, *restrict le, *restrict re;
    2.36 +    
    2.37 +    // check how many elements are already sorted
    2.38      lc = ls;
    2.39      while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
    2.40          lc = lc->next;
    2.41 @@ -261,27 +265,30 @@
    2.42          UcxList *rc;
    2.43          int rn = 1;
    2.44          rc = le;
    2.45 +        // skip already sorted elements
    2.46          while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
    2.47              rc = rc->next;
    2.48              rn++;
    2.49          }
    2.50          re = rc->next;
    2.51  
    2.52 -        // Something left? Sort it!
    2.53 -        UcxList *remainder = re;
    2.54 -        size_t remainder_length = ucx_list_size(remainder);
    2.55 -        if (remainder != NULL) {
    2.56 -            remainder = ucx_list_sort(remainder, fnc, data);
    2.57 -        }
    2.58 -
    2.59          // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
    2.60          UcxList *sorted = ucx_list_sort_merge(ln+rn,
    2.61                  ls, le, re,
    2.62                  fnc, data);
    2.63 +        
    2.64 +        // Something left? Sort it!
    2.65 +        size_t remainder_length = ucx_list_size(re);
    2.66 +        if (remainder_length > 0) {
    2.67 +            UcxList *remainder = ucx_list_sort(re, fnc, data);
    2.68  
    2.69 -        // merge sorted list with (also sorted) remainder
    2.70 -        l = ucx_list_sort_merge(ln+rn+remainder_length,
    2.71 -                sorted, remainder, NULL, fnc, data);
    2.72 +            // merge sorted list with (also sorted) remainder
    2.73 +            l = ucx_list_sort_merge(ln+rn+remainder_length,
    2.74 +                    sorted, remainder, NULL, fnc, data);
    2.75 +        } else {
    2.76 +            // no remainder - we've got our sorted list
    2.77 +            l = sorted;
    2.78 +        }
    2.79  
    2.80          return l;
    2.81      }

     3.1 --- a/ucx/list.h	Tue May 06 14:35:29 2014 +0200
     3.2 +++ b/ucx/list.h	Mon Jun 02 16:04:11 2014 +0200
     3.3 @@ -169,7 +169,7 @@
     3.4  /**
     3.5   * Inserts an element at the end of the list.
     3.6   * 
     3.7 - * This is generally an O(n) operation, as the end of the list is seeked with
     3.8 + * This is generally an O(n) operation, as the end of the list is retrieved with
     3.9   * ucx_list_last().
    3.10   * 
    3.11   * @param list the list where to append the data, or <code>NULL</code> to
    3.12 @@ -273,7 +273,7 @@
    3.13   * @return the element at the specified index or <code>NULL</code>, if the
    3.14   * index is greater than the list size
    3.15   */
    3.16 -UcxList *ucx_list_get(const UcxList *list, int index);
    3.17 +UcxList *ucx_list_get(const UcxList *list, size_t index);
    3.18  
    3.19  /**
    3.20   * Returns the index of an element.
    3.21 @@ -350,7 +350,7 @@
    3.22   * <code>mylist = ucx_list_remove(mylist, myelem);</code>.
    3.23   * 
    3.24   * @param list the list from which the element shall be removed
    3.25 - * @param element the element to removed
    3.26 + * @param element the element to remove
    3.27   * @return returns the updated list pointer or <code>NULL</code>, if the list
    3.28   * is now empty
    3.29   */
    3.30 @@ -363,7 +363,7 @@
    3.31   * 
    3.32   * @param allocator the allocator to use
    3.33   * @param list the list from which the element shall be removed
    3.34 - * @param element the element to removed
    3.35 + * @param element the element to remove
    3.36   * @return returns the updated list pointer or <code>NULL</code>, if the list
    3.37   * @see ucx_list_remove()
    3.38   */