/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* 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
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* 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 "ucx/list.h"
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, 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));
} else {
ret = ucx_list_append_a(alloc, ret, l->data);
}
l = l->next;
}
return ret;
}
int ucx_list_equals(const UcxList *l1, const UcxList *l2,
cmp_func fnc, void* data) {
if (l1 == l2) return 1;
while (l1 != NULL && l2 != NULL) {
if (fnc == NULL) {
if (l1->data != l2->data) return 0;
} else {
if (fnc(l1->data, l2->data, data) != 0) return 0;
}
l1 = l1->next;
l2 = l2->next;
}
return (l1 == NULL && l2 == NULL);
}
void ucx_list_free(UcxList *l) {
ucx_list_free_a(ucx_default_allocator(), l);
}
void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) {
UcxList *e = l, *f;
while (e != NULL) {
f = e;
e = e->next;
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;
}
}
UcxList *ucx_list_append(UcxList *l, void *data) {
return ucx_list_append_a(ucx_default_allocator(), l, data);
}
UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) {
UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
if (!nl) {
return NULL;
}
nl->data = data;
nl->next = NULL;
if (l) {
UcxList *t = ucx_list_last(l);
t->next = nl;
nl->prev = t;
return l;
} else {
nl->prev = NULL;
return nl;
}
}
UcxList *ucx_list_prepend(UcxList *l, void *data) {
return ucx_list_prepend_a(ucx_default_allocator(), l, data);
}
UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {
UcxList *nl = ucx_list_append_a(alloc, NULL, data);
if (!nl) {
return NULL;
}
l = ucx_list_first(l);
if (l) {
nl->next = l;
l->prev = nl;
}
return nl;
}
UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
if (l1) {
UcxList *last = ucx_list_last(l1);
last->next = l2;
if (l2) {
l2->prev = last;
}
return l1;
} else {
return l2;
}
}
UcxList *ucx_list_last(const UcxList *l) {
if (l == NULL) return NULL;
const UcxList *e = l;
while (e->next != NULL) {
e = e->next;
}
return (UcxList*)e;
}
ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {
ssize_t index = 0;
while (list) {
if (list == elem) {
return index;
}
list = list->next;
index++;
}
return -1;
}
UcxList *ucx_list_get(const UcxList *l, size_t index) {
if (l == NULL) return NULL;
const UcxList *e = l;
while (e->next && index > 0) {
e = e->next;
index--;
}
return (UcxList*)(index == 0 ? e : NULL);
}
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;
}
} else {
if (elem == e->data) {
return index;
}
}
index++;
}
return -1;
}
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;
const UcxList *e = l;
size_t s = 1;
while (e->next != NULL) {
e = e->next;
s++;
}
return s;
}
static UcxList *ucx_list_sort_merge(size_t length,
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;
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 {
sorted[n] = rc;
rc = rc->next;
}
n++;
}
while (lc && lc != le) {
sorted[n] = lc;
lc = lc->next;
n++;
}
while (rc && rc != re) {
sorted[n] = rc;
rc = rc->next;
n++;
}
// Update pointer
sorted[0]->prev = NULL;
for (int i = 0 ; i < length-1 ; i++) {
sorted[i]->next = sorted[i+1];
sorted[i+1]->prev = sorted[i];
}
sorted[length-1]->next = NULL;
UcxList *ret = sorted[0];
free(sorted);
return ret;
}
UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
if (l == NULL) {
return NULL;
}
UcxList *lc;
size_t ln = 1;
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;
ln++;
}
le = lc->next;
if (le == NULL) {
return l; // this list is already sorted :)
} else {
UcxList *rc;
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++;
}
re = rc->next;
// {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);
} else {
// no remainder - we've got our sorted list
l = sorted;
}
return l;
}
}
UcxList *ucx_list_first(const UcxList *l) {
if (!l) {
return NULL;
}
const UcxList *e = l;
while (e->prev) {
e = e->prev;
}
return (UcxList *)e;
}
UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
return ucx_list_remove_a(ucx_default_allocator(), l, e);
}
UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
if (l == e) {
l = e->next;
}
if (e->next) {
e->next->prev = e->prev;
}
if (e->prev) {
e->prev->next = e->next;
}
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);
}