webserver: comparison src/ucx/list.c

-:21274e5950af
+:a1f4cb076d2f
 /*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
-* Copyright 2016 Olaf Wintermann. All rights reserved.
+* Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
-#include "list.h"
+#include "ucx/list.h"
-UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
+UcxList *ucx_list_clone(const UcxList *l, copy_func fnc, void *data) {
 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
 }
-UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l,
+UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l,
 copy_func fnc, void *data) {
 UcxList *ret = NULL;
 while (l) {
 if (fnc) {
 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data));
 alfree(alloc, f);
 }
 }
 void ucx_list_free_content(UcxList* list, ucx_destructor destr) {
+if (!destr) destr = free;
 while (list != NULL) {
 destr(list->data);
 list = list->next;
 }
 }
 }
 return (UcxList*)(index == 0 ? e : NULL);
 }
-ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
+ssize_t ucx_list_find(const UcxList *l, void *elem,
+cmp_func fnc, void *cmpdata) {
 ssize_t index = 0;
 UCX_FOREACH(e, l) {
 if (fnc) {
 if (fnc(elem, e->data, cmpdata) == 0) {
 return index;
 index++;
 }
 return -1;
 }
-int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
+int ucx_list_contains(const UcxList *l, void *elem,
+cmp_func fnc, void *cmpdata) {
 return ucx_list_find(l, elem, fnc, cmpdata) > -1;
 }
 size_t ucx_list_size(const UcxList *l) {
 if (l == NULL) return 0;
 }
 return s;
 }
-static UcxList *ucx_list_sort_merge(int length,
+static UcxList *ucx_list_sort_merge(size_t length,
-UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
+UcxList* ls, UcxList* le, UcxList* re,
 cmp_func fnc, void* data) {
 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
 UcxList *rc, *lc;
 lc = ls; rc = le;
-int n = 0;
+size_t n = 0;
 while (lc && lc != le && rc != re) {
 if (fnc(lc->data, rc->data, data) <= 0) {
 sorted[n] = lc;
 lc = lc->next;
 } else {
 if (l == NULL) {
 return NULL;
 }
 UcxList *lc;
-int ln = 1;
+size_t ln = 1;
-UcxList *restrict ls = l, *restrict le, *restrict re;
+UcxList *ls = l, *le, *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;
 if (le == NULL) {
 return l; // this list is already sorted :)
 } else {
 UcxList *rc;
-int rn = 1;
+size_t rn = 1;
 rc = le;
 // skip already sorted elements
 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
 rc = rc->next;
 rn++;
 }
 alfree(alloc, e);
 return l;
 }
+static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator,
+UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata,
+int op) {
+UcxList *res = NULL;
+UcxList *cur = NULL;
+const UcxList *src = left;
+do {
+UCX_FOREACH(node, src) {
+void* elem = node->data;
+if (
+(op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) ||
+(op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) ||
+(op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) {
+UcxList *nl = almalloc(allocator, sizeof(UcxList));
+nl->prev = cur;
+nl->next = NULL;
+if (cpfnc) {
+nl->data = cpfnc(elem, cpdata);
+} else {
+nl->data = elem;
+}
+if (cur != NULL)
+cur->next = nl;
+cur = nl;
+if (res == NULL)
+res = cur;
+}
+}
+if (op == 0 && src == left)
+src = right;
+else
+src = NULL;
+} while (src != NULL);
+return res;
+}
+UcxList* ucx_list_union(UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata) {
+return ucx_list_union_a(ucx_default_allocator(),
+left, right, cmpfnc, cmpdata, cpfnc, cpdata);
+}
+UcxList* ucx_list_union_a(UcxAllocator *allocator,
+UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata) {
+return ucx_list_setoperation_a(allocator, left, right,
+cmpfnc, cmpdata, cpfnc, cpdata, 0);
+}
+UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata) {
+return ucx_list_intersection_a(ucx_default_allocator(), left, right,
+cmpfnc, cmpdata, cpfnc, cpdata);
+}
+UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
+UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata) {
+return ucx_list_setoperation_a(allocator, left, right,
+cmpfnc, cmpdata, cpfnc, cpdata, 1);
+}
+UcxList* ucx_list_difference(UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata) {
+return ucx_list_difference_a(ucx_default_allocator(), left, right,
+cmpfnc, cmpdata, cpfnc, cpdata);
+}
+UcxList* ucx_list_difference_a(UcxAllocator *allocator,
+UcxList const *left, UcxList const *right,
+cmp_func cmpfnc, void* cmpdata,
+copy_func cpfnc, void* cpdata) {
+return ucx_list_setoperation_a(allocator, left, right,
+cmpfnc, cmpdata, cpfnc, cpdata, 2);
+}

Mercurial > hg > webserver / file comparison

comparison: src/ucx/list.c

src/ucx/list.c