1.1 --- a/src/list.c Mon Dec 30 09:54:10 2019 +0100
1.2 +++ b/src/list.c Sat Feb 06 19:11:44 2021 +0100
1.3 @@ -1,7 +1,7 @@
1.4 /*
1.5 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 *
1.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
1.8 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
1.9 *
1.10 * Redistribution and use in source and binary forms, with or without
1.11 * modification, are permitted provided that the following conditions are met:
1.12 @@ -26,403 +26,4 @@
1.13 * POSSIBILITY OF SUCH DAMAGE.
1.14 */
1.15
1.16 -#include "ucx/list.h"
1.17 -
1.18 -UcxList *ucx_list_clone(const UcxList *l, copy_func fnc, void *data) {
1.19 - return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
1.20 -}
1.21 -
1.22 -UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l,
1.23 - copy_func fnc, void *data) {
1.24 - UcxList *ret = NULL;
1.25 - while (l) {
1.26 - if (fnc) {
1.27 - ret = ucx_list_append_a(alloc, ret, fnc(l->data, data));
1.28 - } else {
1.29 - ret = ucx_list_append_a(alloc, ret, l->data);
1.30 - }
1.31 - l = l->next;
1.32 - }
1.33 - return ret;
1.34 -}
1.35 -
1.36 -int ucx_list_equals(const UcxList *l1, const UcxList *l2,
1.37 - cmp_func fnc, void* data) {
1.38 - if (l1 == l2) return 1;
1.39 -
1.40 - while (l1 != NULL && l2 != NULL) {
1.41 - if (fnc == NULL) {
1.42 - if (l1->data != l2->data) return 0;
1.43 - } else {
1.44 - if (fnc(l1->data, l2->data, data) != 0) return 0;
1.45 - }
1.46 - l1 = l1->next;
1.47 - l2 = l2->next;
1.48 - }
1.49 -
1.50 - return (l1 == NULL && l2 == NULL);
1.51 -}
1.52 -
1.53 -void ucx_list_free(UcxList *l) {
1.54 - ucx_list_free_a(ucx_default_allocator(), l);
1.55 -}
1.56 -
1.57 -void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) {
1.58 - UcxList *e = l, *f;
1.59 - while (e != NULL) {
1.60 - f = e;
1.61 - e = e->next;
1.62 - alfree(alloc, f);
1.63 - }
1.64 -}
1.65 -
1.66 -void ucx_list_free_content(UcxList* list, ucx_destructor destr) {
1.67 - if (!destr) destr = free;
1.68 - while (list != NULL) {
1.69 - destr(list->data);
1.70 - list = list->next;
1.71 - }
1.72 -}
1.73 -
1.74 -UcxList *ucx_list_append(UcxList *l, void *data) {
1.75 - return ucx_list_append_a(ucx_default_allocator(), l, data);
1.76 -}
1.77 -
1.78 -UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) {
1.79 - UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
1.80 - if (!nl) {
1.81 - return NULL;
1.82 - }
1.83 -
1.84 - nl->data = data;
1.85 - nl->next = NULL;
1.86 - if (l) {
1.87 - UcxList *t = ucx_list_last(l);
1.88 - t->next = nl;
1.89 - nl->prev = t;
1.90 - return l;
1.91 - } else {
1.92 - nl->prev = NULL;
1.93 - return nl;
1.94 - }
1.95 -}
1.96 -
1.97 -UcxList *ucx_list_prepend(UcxList *l, void *data) {
1.98 - return ucx_list_prepend_a(ucx_default_allocator(), l, data);
1.99 -}
1.100 -
1.101 -UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {
1.102 - UcxList *nl = ucx_list_append_a(alloc, NULL, data);
1.103 - if (!nl) {
1.104 - return NULL;
1.105 - }
1.106 - l = ucx_list_first(l);
1.107 -
1.108 - if (l) {
1.109 - nl->next = l;
1.110 - l->prev = nl;
1.111 - }
1.112 - return nl;
1.113 -}
1.114 -
1.115 -UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
1.116 - if (l1) {
1.117 - UcxList *last = ucx_list_last(l1);
1.118 - last->next = l2;
1.119 - if (l2) {
1.120 - l2->prev = last;
1.121 - }
1.122 - return l1;
1.123 - } else {
1.124 - return l2;
1.125 - }
1.126 -}
1.127 -
1.128 -UcxList *ucx_list_last(const UcxList *l) {
1.129 - if (l == NULL) return NULL;
1.130 -
1.131 - const UcxList *e = l;
1.132 - while (e->next != NULL) {
1.133 - e = e->next;
1.134 - }
1.135 - return (UcxList*)e;
1.136 -}
1.137 -
1.138 -ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {
1.139 - ssize_t index = 0;
1.140 - while (list) {
1.141 - if (list == elem) {
1.142 - return index;
1.143 - }
1.144 - list = list->next;
1.145 - index++;
1.146 - }
1.147 - return -1;
1.148 -}
1.149 -
1.150 -UcxList *ucx_list_get(const UcxList *l, size_t index) {
1.151 - if (l == NULL) return NULL;
1.152 -
1.153 - const UcxList *e = l;
1.154 - while (e->next && index > 0) {
1.155 - e = e->next;
1.156 - index--;
1.157 - }
1.158 -
1.159 - return (UcxList*)(index == 0 ? e : NULL);
1.160 -}
1.161 -
1.162 -ssize_t ucx_list_find(const UcxList *l, void *elem,
1.163 - cmp_func fnc, void *cmpdata) {
1.164 - ssize_t index = 0;
1.165 - UCX_FOREACH(e, l) {
1.166 - if (fnc) {
1.167 - if (fnc(elem, e->data, cmpdata) == 0) {
1.168 - return index;
1.169 - }
1.170 - } else {
1.171 - if (elem == e->data) {
1.172 - return index;
1.173 - }
1.174 - }
1.175 - index++;
1.176 - }
1.177 - return -1;
1.178 -}
1.179 -
1.180 -int ucx_list_contains(const UcxList *l, void *elem,
1.181 - cmp_func fnc, void *cmpdata) {
1.182 - return ucx_list_find(l, elem, fnc, cmpdata) > -1;
1.183 -}
1.184 -
1.185 -size_t ucx_list_size(const UcxList *l) {
1.186 - if (l == NULL) return 0;
1.187 -
1.188 - const UcxList *e = l;
1.189 - size_t s = 1;
1.190 - while (e->next != NULL) {
1.191 - e = e->next;
1.192 - s++;
1.193 - }
1.194 -
1.195 - return s;
1.196 -}
1.197 -
1.198 -static UcxList *ucx_list_sort_merge(size_t length,
1.199 - UcxList* ls, UcxList* le, UcxList* re,
1.200 - cmp_func fnc, void* data) {
1.201 -
1.202 - UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
1.203 - UcxList *rc, *lc;
1.204 -
1.205 - lc = ls; rc = le;
1.206 - size_t n = 0;
1.207 - while (lc && lc != le && rc != re) {
1.208 - if (fnc(lc->data, rc->data, data) <= 0) {
1.209 - sorted[n] = lc;
1.210 - lc = lc->next;
1.211 - } else {
1.212 - sorted[n] = rc;
1.213 - rc = rc->next;
1.214 - }
1.215 - n++;
1.216 - }
1.217 - while (lc && lc != le) {
1.218 - sorted[n] = lc;
1.219 - lc = lc->next;
1.220 - n++;
1.221 - }
1.222 - while (rc && rc != re) {
1.223 - sorted[n] = rc;
1.224 - rc = rc->next;
1.225 - n++;
1.226 - }
1.227 -
1.228 - // Update pointer
1.229 - sorted[0]->prev = NULL;
1.230 - for (int i = 0 ; i < length-1 ; i++) {
1.231 - sorted[i]->next = sorted[i+1];
1.232 - sorted[i+1]->prev = sorted[i];
1.233 - }
1.234 - sorted[length-1]->next = NULL;
1.235 -
1.236 - UcxList *ret = sorted[0];
1.237 - free(sorted);
1.238 - return ret;
1.239 -}
1.240 -
1.241 -UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
1.242 - if (l == NULL) {
1.243 - return NULL;
1.244 - }
1.245 -
1.246 - UcxList *lc;
1.247 - size_t ln = 1;
1.248 -
1.249 - UcxList *ls = l, *le, *re;
1.250 -
1.251 - // check how many elements are already sorted
1.252 - lc = ls;
1.253 - while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
1.254 - lc = lc->next;
1.255 - ln++;
1.256 - }
1.257 - le = lc->next;
1.258 -
1.259 - if (le == NULL) {
1.260 - return l; // this list is already sorted :)
1.261 - } else {
1.262 - UcxList *rc;
1.263 - size_t rn = 1;
1.264 - rc = le;
1.265 - // skip already sorted elements
1.266 - while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
1.267 - rc = rc->next;
1.268 - rn++;
1.269 - }
1.270 - re = rc->next;
1.271 -
1.272 - // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
1.273 - UcxList *sorted = ucx_list_sort_merge(ln+rn,
1.274 - ls, le, re,
1.275 - fnc, data);
1.276 -
1.277 - // Something left? Sort it!
1.278 - size_t remainder_length = ucx_list_size(re);
1.279 - if (remainder_length > 0) {
1.280 - UcxList *remainder = ucx_list_sort(re, fnc, data);
1.281 -
1.282 - // merge sorted list with (also sorted) remainder
1.283 - l = ucx_list_sort_merge(ln+rn+remainder_length,
1.284 - sorted, remainder, NULL, fnc, data);
1.285 - } else {
1.286 - // no remainder - we've got our sorted list
1.287 - l = sorted;
1.288 - }
1.289 -
1.290 - return l;
1.291 - }
1.292 -}
1.293 -
1.294 -UcxList *ucx_list_first(const UcxList *l) {
1.295 - if (!l) {
1.296 - return NULL;
1.297 - }
1.298 -
1.299 - const UcxList *e = l;
1.300 - while (e->prev) {
1.301 - e = e->prev;
1.302 - }
1.303 - return (UcxList *)e;
1.304 -}
1.305 -
1.306 -UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
1.307 - return ucx_list_remove_a(ucx_default_allocator(), l, e);
1.308 -}
1.309 -
1.310 -UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
1.311 - if (l == e) {
1.312 - l = e->next;
1.313 - }
1.314 -
1.315 - if (e->next) {
1.316 - e->next->prev = e->prev;
1.317 - }
1.318 -
1.319 - if (e->prev) {
1.320 - e->prev->next = e->next;
1.321 - }
1.322 -
1.323 - alfree(alloc, e);
1.324 - return l;
1.325 -}
1.326 -
1.327 -
1.328 -static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator,
1.329 - UcxList const *left, UcxList const *right,
1.330 - cmp_func cmpfnc, void* cmpdata,
1.331 - copy_func cpfnc, void* cpdata,
1.332 - int op) {
1.333 -
1.334 - UcxList *res = NULL;
1.335 - UcxList *cur = NULL;
1.336 - const UcxList *src = left;
1.337 -
1.338 - do {
1.339 - UCX_FOREACH(node, src) {
1.340 - void* elem = node->data;
1.341 - if (
1.342 - (op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) ||
1.343 - (op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) ||
1.344 - (op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) {
1.345 - UcxList *nl = almalloc(allocator, sizeof(UcxList));
1.346 - nl->prev = cur;
1.347 - nl->next = NULL;
1.348 - if (cpfnc) {
1.349 - nl->data = cpfnc(elem, cpdata);
1.350 - } else {
1.351 - nl->data = elem;
1.352 - }
1.353 - if (cur != NULL)
1.354 - cur->next = nl;
1.355 - cur = nl;
1.356 - if (res == NULL)
1.357 - res = cur;
1.358 - }
1.359 - }
1.360 - if (op == 0 && src == left)
1.361 - src = right;
1.362 - else
1.363 - src = NULL;
1.364 - } while (src != NULL);
1.365 -
1.366 - return res;
1.367 -}
1.368 -
1.369 -UcxList* ucx_list_union(UcxList const *left, UcxList const *right,
1.370 - cmp_func cmpfnc, void* cmpdata,
1.371 - copy_func cpfnc, void* cpdata) {
1.372 - return ucx_list_union_a(ucx_default_allocator(),
1.373 - left, right, cmpfnc, cmpdata, cpfnc, cpdata);
1.374 -}
1.375 -
1.376 -UcxList* ucx_list_union_a(UcxAllocator *allocator,
1.377 - UcxList const *left, UcxList const *right,
1.378 - cmp_func cmpfnc, void* cmpdata,
1.379 - copy_func cpfnc, void* cpdata) {
1.380 -
1.381 - return ucx_list_setoperation_a(allocator, left, right,
1.382 - cmpfnc, cmpdata, cpfnc, cpdata, 0);
1.383 -}
1.384 -
1.385 -UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right,
1.386 - cmp_func cmpfnc, void* cmpdata,
1.387 - copy_func cpfnc, void* cpdata) {
1.388 - return ucx_list_intersection_a(ucx_default_allocator(), left, right,
1.389 - cmpfnc, cmpdata, cpfnc, cpdata);
1.390 -}
1.391 -
1.392 -UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
1.393 - UcxList const *left, UcxList const *right,
1.394 - cmp_func cmpfnc, void* cmpdata,
1.395 - copy_func cpfnc, void* cpdata) {
1.396 -
1.397 - return ucx_list_setoperation_a(allocator, left, right,
1.398 - cmpfnc, cmpdata, cpfnc, cpdata, 1);
1.399 -}
1.400 -
1.401 -UcxList* ucx_list_difference(UcxList const *left, UcxList const *right,
1.402 - cmp_func cmpfnc, void* cmpdata,
1.403 - copy_func cpfnc, void* cpdata) {
1.404 - return ucx_list_difference_a(ucx_default_allocator(), left, right,
1.405 - cmpfnc, cmpdata, cpfnc, cpdata);
1.406 -}
1.407 -
1.408 -UcxList* ucx_list_difference_a(UcxAllocator *allocator,
1.409 - UcxList const *left, UcxList const *right,
1.410 - cmp_func cmpfnc, void* cmpdata,
1.411 - copy_func cpfnc, void* cpdata) {
1.412 -
1.413 - return ucx_list_setoperation_a(allocator, left, right,
1.414 - cmpfnc, cmpdata, cpfnc, cpdata, 2);
1.415 -}
1.416 +#include "cx/list.h"
