Mercurial > hg > ucx / changeset

     1.1 --- a/src/list.c	Thu Nov 07 10:43:31 2019 +0100
     1.2 +++ b/src/list.c	Sun Nov 24 17:57:25 2019 +0100
     1.3 @@ -28,11 +28,11 @@
     1.4  
     1.5  #include "ucx/list.h"
     1.6  
     1.7 -UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
     1.8 +UcxList *ucx_list_clone(const UcxList *l, copy_func fnc, void *data) {
     1.9      return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
    1.10  }
    1.11  
    1.12 -UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l,
    1.13 +UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l,
    1.14          copy_func fnc, void *data) {
    1.15      UcxList *ret = NULL;
    1.16      while (l) {
    1.17 @@ -172,7 +172,8 @@
    1.18      return (UcxList*)(index == 0 ? e : NULL);
    1.19  }
    1.20  
    1.21 -ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
    1.22 +ssize_t ucx_list_find(const UcxList *l, void *elem,
    1.23 +        cmp_func fnc, void *cmpdata) {
    1.24      ssize_t index = 0;
    1.25      UCX_FOREACH(e, l) {
    1.26          if (fnc) {
    1.27 @@ -189,7 +190,8 @@
    1.28      return -1;
    1.29  }
    1.30  
    1.31 -int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
    1.32 +int ucx_list_contains(const UcxList *l, void *elem,
    1.33 +        cmp_func fnc, void *cmpdata) {
    1.34      return ucx_list_find(l, elem, fnc, cmpdata) > -1;
    1.35  }
    1.36  
    1.37 @@ -334,3 +336,93 @@
    1.38      alfree(alloc, e);
    1.39      return l;
    1.40  }
    1.41 +
    1.42 +
    1.43 +static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator,
    1.44 +        UcxList const *left, UcxList const *right,
    1.45 +        cmp_func cmpfnc, void* cmpdata,
    1.46 +        copy_func cpfnc, void* cpdata,
    1.47 +        int op) {
    1.48 +    
    1.49 +    UcxList *res = NULL;
    1.50 +    UcxList *cur = NULL;
    1.51 +    const UcxList *src = left;
    1.52 +    
    1.53 +    do {
    1.54 +        UCX_FOREACH(node, src) {
    1.55 +            void* elem = node->data;
    1.56 +            if (
    1.57 +                (op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) ||
    1.58 +                (op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) ||
    1.59 +                (op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) {
    1.60 +                UcxList *nl = almalloc(allocator, sizeof(UcxList));
    1.61 +                nl->prev = cur;
    1.62 +                nl->next = NULL;
    1.63 +                if (cpfnc) {
    1.64 +                    nl->data = cpfnc(elem, cpdata);
    1.65 +                } else {
    1.66 +                    nl->data = elem;
    1.67 +                }
    1.68 +                if (cur != NULL)
    1.69 +                    cur->next = nl;
    1.70 +                cur = nl;
    1.71 +                if (res == NULL)
    1.72 +                    res = cur;
    1.73 +            }
    1.74 +        }
    1.75 +        if (op == 0 && src == left)
    1.76 +            src = right;
    1.77 +        else
    1.78 +            src = NULL;
    1.79 +    } while (src != NULL);
    1.80 +    
    1.81 +    return res;
    1.82 +}
    1.83 +
    1.84 +UcxList* ucx_list_union(UcxList const *left, UcxList const *right,
    1.85 +        cmp_func cmpfnc, void* cmpdata,
    1.86 +        copy_func cpfnc, void* cpdata) {
    1.87 +    return ucx_list_union_a(ucx_default_allocator(),
    1.88 +            left, right, cmpfnc, cmpdata, cpfnc, cpdata);
    1.89 +}
    1.90 +
    1.91 +UcxList* ucx_list_union_a(UcxAllocator *allocator,
    1.92 +        UcxList const *left, UcxList const *right,
    1.93 +        cmp_func cmpfnc, void* cmpdata,
    1.94 +        copy_func cpfnc, void* cpdata) {
    1.95 +    
    1.96 +    return ucx_list_setoperation_a(allocator, left, right,
    1.97 +            cmpfnc, cmpdata, cpfnc, cpdata, 0);
    1.98 +}
    1.99 +
   1.100 +UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right,
   1.101 +        cmp_func cmpfnc, void* cmpdata,
   1.102 +        copy_func cpfnc, void* cpdata) {
   1.103 +    return ucx_list_intersection_a(ucx_default_allocator(), left, right,
   1.104 +            cmpfnc, cmpdata, cpfnc, cpdata);
   1.105 +}
   1.106 +
   1.107 +UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
   1.108 +        UcxList const *left, UcxList const *right,
   1.109 +        cmp_func cmpfnc, void* cmpdata,
   1.110 +        copy_func cpfnc, void* cpdata) {
   1.111 +    
   1.112 +    return ucx_list_setoperation_a(allocator, left, right,
   1.113 +            cmpfnc, cmpdata, cpfnc, cpdata, 1);
   1.114 +}
   1.115 +
   1.116 +UcxList* ucx_list_difference(UcxList const *left, UcxList const *right,
   1.117 +        cmp_func cmpfnc, void* cmpdata,
   1.118 +        copy_func cpfnc, void* cpdata) {
   1.119 +    return ucx_list_difference_a(ucx_default_allocator(), left, right,
   1.120 +            cmpfnc, cmpdata, cpfnc, cpdata);
   1.121 +}
   1.122 +
   1.123 +UcxList* ucx_list_difference_a(UcxAllocator *allocator,
   1.124 +        UcxList const *left, UcxList const *right,
   1.125 +        cmp_func cmpfnc, void* cmpdata,
   1.126 +        copy_func cpfnc, void* cpdata) {
   1.127 +    
   1.128 +    return ucx_list_setoperation_a(allocator, left, right,
   1.129 +            cmpfnc, cmpdata, cpfnc, cpdata, 2);
   1.130 +}

     2.1 --- a/src/ucx/list.h	Thu Nov 07 10:43:31 2019 +0100
     2.2 +++ b/src/ucx/list.h	Sun Nov 24 17:57:25 2019 +0100
     2.3 @@ -57,7 +57,7 @@
     2.4   * @param elem The variable name of the element
     2.5   */
     2.6  #define UCX_FOREACH(elem,list) \
     2.7 -        for (UcxList* elem = list ; elem != NULL ; elem = elem->next)
     2.8 +        for (UcxList* elem = (UcxList*) list ; elem != NULL ; elem = elem->next)
     2.9  
    2.10  /**
    2.11   * UCX list type.
    2.12 @@ -99,7 +99,7 @@
    2.13   * @param data additional data for the copy_func()
    2.14   * @return a pointer to the copy
    2.15   */
    2.16 -UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data);
    2.17 +UcxList *ucx_list_clone(const UcxList *list, copy_func cpyfnc, void* data);
    2.18  
    2.19  /**
    2.20   * Creates an element-wise copy of a list using a UcxAllocator.
    2.21 @@ -117,7 +117,7 @@
    2.22   * @return a pointer to the copy
    2.23   * @see ucx_list_clone()
    2.24   */
    2.25 -UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list,
    2.26 +UcxList *ucx_list_clone_a(UcxAllocator *allocator, const UcxList *list,
    2.27          copy_func cpyfnc, void* data);
    2.28  
    2.29  /**
    2.30 @@ -328,7 +328,8 @@
    2.31   * @return the index of the element containing the specified data or -1 if the
    2.32   * data is not found in this list
    2.33   */
    2.34 -ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
    2.35 +ssize_t ucx_list_find(const UcxList *list, void *elem,
    2.36 +    cmp_func cmpfnc, void *data);
    2.37  
    2.38  /**
    2.39   * Checks, if a list contains a specific element.
    2.40 @@ -342,7 +343,8 @@
    2.41   * @return 1, if and only if the list contains the specified element data
    2.42   * @see ucx_list_find()
    2.43   */
    2.44 -int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
    2.45 +int ucx_list_contains(const UcxList *list, void *elem,
    2.46 +    cmp_func cmpfnc, void *data);
    2.47  
    2.48  /**
    2.49   * Sorts a UcxList with natural merge sort.
    2.50 @@ -388,6 +390,120 @@
    2.51  UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
    2.52          UcxList *element);
    2.53  
    2.54 +/**
    2.55 + * Returns the union of two lists.
    2.56 + * 
    2.57 + * The union is a list of unique elements regarding cmpfnc obtained from
    2.58 + * both source lists.
    2.59 + * 
    2.60 + * @param left the left source list
    2.61 + * @param right the right source list
    2.62 + * @param cmpfnc a function to compare elements
    2.63 + * @param cmpdata additional data for the compare function
    2.64 + * @param cpfnc a function to copy the elements
    2.65 + * @param cpdata additional data for the copy function
    2.66 + * @return a new list containing the union
    2.67 + */
    2.68 +UcxList* ucx_list_union(const UcxList *left, const UcxList *right,
    2.69 +    cmp_func cmpfnc, void* cmpdata,
    2.70 +    copy_func cpfnc, void* cpdata);
    2.71 +
    2.72 +/**
    2.73 + * Returns the union of two lists.
    2.74 + * 
    2.75 + * The union is a list of unique elements regarding cmpfnc obtained from
    2.76 + * both source lists.
    2.77 + * 
    2.78 + * @param allocator allocates the new list elements
    2.79 + * @param left the left source list
    2.80 + * @param right the right source list
    2.81 + * @param cmpfnc a function to compare elements
    2.82 + * @param cmpdata additional data for the compare function
    2.83 + * @param cpfnc a function to copy the elements
    2.84 + * @param cpdata additional data for the copy function
    2.85 + * @return a new list containing the union
    2.86 + */
    2.87 +UcxList* ucx_list_union_a(UcxAllocator *allocator,
    2.88 +    const UcxList *left, const UcxList *right,
    2.89 +    cmp_func cmpfnc, void* cmpdata,
    2.90 +    copy_func cpfnc, void* cpdata);
    2.91 +
    2.92 +/**
    2.93 + * Returns the intersection of two lists.
    2.94 + * 
    2.95 + * The intersection contains all elements of the left list
    2.96 + * (including duplicates) that can be found in the right list.
    2.97 + * 
    2.98 + * @param left the left source list
    2.99 + * @param right the right source list
   2.100 + * @param cmpfnc a function to compare elements
   2.101 + * @param cmpdata additional data for the compare function
   2.102 + * @param cpfnc a function to copy the elements
   2.103 + * @param cpdata additional data for the copy function
   2.104 + * @return a new list containing the intersection
   2.105 + */
   2.106 +UcxList* ucx_list_intersection(const UcxList *left, const UcxList *right,
   2.107 +    cmp_func cmpfnc, void* cmpdata,
   2.108 +    copy_func cpfnc, void* cpdata);
   2.109 +
   2.110 +/**
   2.111 + * Returns the intersection of two lists.
   2.112 + * 
   2.113 + * The intersection contains all elements of the left list
   2.114 + * (including duplicates) that can be found in the right list.
   2.115 + * 
   2.116 + * @param allocator allocates the new list elements
   2.117 + * @param left the left source list
   2.118 + * @param right the right source list
   2.119 + * @param cmpfnc a function to compare elements
   2.120 + * @param cmpdata additional data for the compare function
   2.121 + * @param cpfnc a function to copy the elements
   2.122 + * @param cpdata additional data for the copy function
   2.123 + * @return a new list containing the intersection
   2.124 + */
   2.125 +UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
   2.126 +    const UcxList *left, const UcxList *right,
   2.127 +    cmp_func cmpfnc, void* cmpdata,
   2.128 +    copy_func cpfnc, void* cpdata);
   2.129 +
   2.130 +/**
   2.131 + * Returns the difference of two lists.
   2.132 + * 
   2.133 + * The difference contains all elements of the left list
   2.134 + * (including duplicates) that are not equal to any element of the right list.
   2.135 + * 
   2.136 + * @param left the left source list
   2.137 + * @param right the right source list
   2.138 + * @param cmpfnc a function to compare elements
   2.139 + * @param cmpdata additional data for the compare function
   2.140 + * @param cpfnc a function to copy the elements
   2.141 + * @param cpdata additional data for the copy function
   2.142 + * @return a new list containing the difference
   2.143 + */
   2.144 +UcxList* ucx_list_difference(const UcxList *left, const UcxList *right,
   2.145 +    cmp_func cmpfnc, void* cmpdata,
   2.146 +    copy_func cpfnc, void* cpdata);
   2.147 +
   2.148 +/**
   2.149 + * Returns the difference of two lists.
   2.150 + * 
   2.151 + * The difference contains all elements of the left list
   2.152 + * (including duplicates) that are not equal to any element of the right list.
   2.153 + * 
   2.154 + * @param allocator allocates the new list elements
   2.155 + * @param left the left source list
   2.156 + * @param right the right source list
   2.157 + * @param cmpfnc a function to compare elements
   2.158 + * @param cmpdata additional data for the compare function
   2.159 + * @param cpfnc a function to copy the elements
   2.160 + * @param cpdata additional data for the copy function
   2.161 + * @return a new list containing the difference
   2.162 + */
   2.163 +UcxList* ucx_list_difference_a(UcxAllocator *allocator,
   2.164 +    const UcxList *left, const UcxList *right,
   2.165 +    cmp_func cmpfnc, void* cmpdata,
   2.166 +    copy_func cpfnc, void* cpdata);
   2.167 +
   2.168  #ifdef	__cplusplus
   2.169  }
   2.170  #endif

     3.1 --- a/test/list_tests.c	Thu Nov 07 10:43:31 2019 +0100
     3.2 +++ b/test/list_tests.c	Sun Nov 24 17:57:25 2019 +0100
     3.3 @@ -403,3 +403,94 @@
     3.4      ucx_list_free(expected);
     3.5      ucx_list_free(list);
     3.6  }
     3.7 +
     3.8 +UCX_TEST(test_ucx_list_union) {
     3.9 +    UcxList *left = ucx_list_append(NULL, (void*)"this");
    3.10 +    left = ucx_list_append(left, (void*)"is");
    3.11 +    left = ucx_list_append(left, (void*)"a");
    3.12 +    left = ucx_list_append(left, (void*)"test");
    3.13 +
    3.14 +    UcxList *right = ucx_list_append(NULL, (void*)"to");
    3.15 +    right = ucx_list_append(right, (void*)"test");
    3.16 +    right = ucx_list_append(right, (void*)"set");
    3.17 +    right = ucx_list_append(right, (void*)"operations");
    3.18 +    
    3.19 +    UcxList *expected = ucx_list_append(NULL, (void*)"this");
    3.20 +    expected = ucx_list_append(expected, (void*)"is");
    3.21 +    expected = ucx_list_append(expected, (void*)"a");
    3.22 +    expected = ucx_list_append(expected, (void*)"test");
    3.23 +    expected = ucx_list_append(expected, (void*)"to");
    3.24 +    expected = ucx_list_append(expected, (void*)"set");
    3.25 +    expected = ucx_list_append(expected, (void*)"operations");
    3.26 +
    3.27 +    UcxList* result = ucx_list_union(left, right, ucx_cmp_str,
    3.28 +            NULL, NULL, NULL);
    3.29 +
    3.30 +    UCX_TEST_BEGIN
    3.31 +    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
    3.32 +            ucx_cmp_str, NULL), "failed");
    3.33 +    UCX_TEST_END
    3.34 +
    3.35 +    ucx_list_free(result);
    3.36 +    ucx_list_free(expected);
    3.37 +    ucx_list_free(right);
    3.38 +    ucx_list_free(left);
    3.39 +}
    3.40 +
    3.41 +UCX_TEST(test_ucx_list_intersection) {
    3.42 +    UcxList *left = ucx_list_append(NULL, (void*)"this");
    3.43 +    left = ucx_list_append(left, (void*)"is");
    3.44 +    left = ucx_list_append(left, (void*)"a");
    3.45 +    left = ucx_list_append(left, (void*)"test");
    3.46 +
    3.47 +    UcxList *right = ucx_list_append(NULL, (void*)"to");
    3.48 +    right = ucx_list_append(right, (void*)"test");
    3.49 +    right = ucx_list_append(right, (void*)"a");
    3.50 +    right = ucx_list_append(right, (void*)"set");
    3.51 +    right = ucx_list_append(right, (void*)"operation");
    3.52 +    
    3.53 +    UcxList *expected = ucx_list_append(NULL, (void*)"a");
    3.54 +    expected = ucx_list_append(expected, (void*)"test");
    3.55 +
    3.56 +    UcxList* result = ucx_list_intersection(left, right, ucx_cmp_str,
    3.57 +            NULL, NULL, NULL);
    3.58 +
    3.59 +    UCX_TEST_BEGIN
    3.60 +    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
    3.61 +            ucx_cmp_str, NULL), "failed");
    3.62 +    UCX_TEST_END
    3.63 +
    3.64 +    ucx_list_free(result);
    3.65 +    ucx_list_free(expected);
    3.66 +    ucx_list_free(right);
    3.67 +    ucx_list_free(left);
    3.68 +}
    3.69 +
    3.70 +UCX_TEST(test_ucx_list_difference) {
    3.71 +    UcxList *left = ucx_list_append(NULL, (void*)"this");
    3.72 +    left = ucx_list_append(left, (void*)"is");
    3.73 +    left = ucx_list_append(left, (void*)"a");
    3.74 +    left = ucx_list_append(left, (void*)"test");
    3.75 +
    3.76 +    UcxList *right = ucx_list_append(NULL, (void*)"to");
    3.77 +    right = ucx_list_append(right, (void*)"test");
    3.78 +    right = ucx_list_append(right, (void*)"this");
    3.79 +    right = ucx_list_append(right, (void*)"set");
    3.80 +    right = ucx_list_append(right, (void*)"operations");
    3.81 +    
    3.82 +    UcxList *expected = ucx_list_append(NULL, (void*)"is");
    3.83 +    expected = ucx_list_append(expected, (void*)"a");
    3.84 +    
    3.85 +    UcxList* result = ucx_list_difference(left, right, ucx_cmp_str,
    3.86 +            NULL, NULL, NULL);
    3.87 +
    3.88 +    UCX_TEST_BEGIN
    3.89 +    UCX_TEST_ASSERT(ucx_list_equals(result, expected,
    3.90 +            ucx_cmp_str, NULL), "failed");
    3.91 +    UCX_TEST_END
    3.92 +
    3.93 +    ucx_list_free(result);
    3.94 +    ucx_list_free(expected);
    3.95 +    ucx_list_free(right);
    3.96 +    ucx_list_free(left);
    3.97 +}

     4.1 --- a/test/list_tests.h	Thu Nov 07 10:43:31 2019 +0100
     4.2 +++ b/test/list_tests.h	Sun Nov 24 17:57:25 2019 +0100
     4.3 @@ -55,6 +55,9 @@
     4.4  UCX_TEST(test_ucx_list_remove);
     4.5  UCX_TEST(test_ucx_list_clone);
     4.6  UCX_TEST(test_ucx_list_sort);
     4.7 +UCX_TEST(test_ucx_list_union);
     4.8 +UCX_TEST(test_ucx_list_intersection);
     4.9 +UCX_TEST(test_ucx_list_difference);
    4.10  
    4.11  #ifdef	__cplusplus
    4.12  }

     5.1 --- a/test/main.c	Thu Nov 07 10:43:31 2019 +0100
     5.2 +++ b/test/main.c	Sun Nov 24 17:57:25 2019 +0100
     5.3 @@ -180,6 +180,9 @@
     5.4          ucx_test_register(suite, test_ucx_list_remove);
     5.5          ucx_test_register(suite, test_ucx_list_clone);
     5.6          ucx_test_register(suite, test_ucx_list_sort);
     5.7 +        ucx_test_register(suite, test_ucx_list_union);
     5.8 +        ucx_test_register(suite, test_ucx_list_intersection);
     5.9 +        ucx_test_register(suite, test_ucx_list_difference);
    5.10  
    5.11          /* UcxMemPool Tests */
    5.12          ucx_test_register(suite, test_ucx_mempool_new);