1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/list.c Tue Oct 17 16:15:41 2017 +0200
1.3 @@ -0,0 +1,370 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2017 Olaf Wintermann. All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#include "ucx/list.h"
1.33 +
1.34 +UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) {
1.35 + return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data);
1.36 +}
1.37 +
1.38 +UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l,
1.39 + copy_func fnc, void *data) {
1.40 + UcxList *ret = NULL;
1.41 + while (l) {
1.42 + if (fnc) {
1.43 + ret = ucx_list_append_a(alloc, ret, fnc(l->data, data));
1.44 + } else {
1.45 + ret = ucx_list_append_a(alloc, ret, l->data);
1.46 + }
1.47 + l = l->next;
1.48 + }
1.49 + return ret;
1.50 +}
1.51 +
1.52 +int ucx_list_equals(const UcxList *l1, const UcxList *l2,
1.53 + cmp_func fnc, void* data) {
1.54 + if (l1 == l2) return 1;
1.55 +
1.56 + while (l1 != NULL && l2 != NULL) {
1.57 + if (fnc == NULL) {
1.58 + if (l1->data != l2->data) return 0;
1.59 + } else {
1.60 + if (fnc(l1->data, l2->data, data) != 0) return 0;
1.61 + }
1.62 + l1 = l1->next;
1.63 + l2 = l2->next;
1.64 + }
1.65 +
1.66 + return (l1 == NULL && l2 == NULL);
1.67 +}
1.68 +
1.69 +void ucx_list_free(UcxList *l) {
1.70 + ucx_list_free_a(ucx_default_allocator(), l);
1.71 +}
1.72 +
1.73 +void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) {
1.74 + UcxList *e = l, *f;
1.75 + while (e != NULL) {
1.76 + f = e;
1.77 + e = e->next;
1.78 + alfree(alloc, f);
1.79 + }
1.80 +}
1.81 +
1.82 +void ucx_list_free_content(UcxList* list, ucx_destructor destr) {
1.83 + while (list != NULL) {
1.84 + destr(list->data);
1.85 + list = list->next;
1.86 + }
1.87 +}
1.88 +
1.89 +UcxList *ucx_list_append(UcxList *l, void *data) {
1.90 + return ucx_list_append_a(ucx_default_allocator(), l, data);
1.91 +}
1.92 +
1.93 +UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) {
1.94 + UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
1.95 + if (!nl) {
1.96 + return NULL;
1.97 + }
1.98 +
1.99 + nl->data = data;
1.100 + nl->next = NULL;
1.101 + if (l) {
1.102 + UcxList *t = ucx_list_last(l);
1.103 + t->next = nl;
1.104 + nl->prev = t;
1.105 + return l;
1.106 + } else {
1.107 + nl->prev = NULL;
1.108 + return nl;
1.109 + }
1.110 +}
1.111 +
1.112 +UcxList *ucx_list_append_once(UcxList *l, void *data,
1.113 + cmp_func cmpfnc, void *cmpdata) {
1.114 + return ucx_list_append_once_a(ucx_default_allocator(), l,
1.115 + data, cmpfnc, cmpdata);
1.116 +}
1.117 +
1.118 +UcxList *ucx_list_append_once_a(UcxAllocator *alloc, UcxList *l, void *data,
1.119 + cmp_func cmpfnc, void *cmpdata) {
1.120 +
1.121 + UcxList *last = NULL;
1.122 + {
1.123 + UcxList *e = l;
1.124 + while (e) {
1.125 + if (cmpfnc(e->data, data, cmpdata) == 0) {
1.126 + return l;
1.127 + }
1.128 + last = e;
1.129 + e = e->next;
1.130 + }
1.131 + }
1.132 +
1.133 + UcxList *nl = ucx_list_append_a(alloc, NULL, data);
1.134 + if (!nl) {
1.135 + return NULL;
1.136 + }
1.137 +
1.138 + if (last == NULL) {
1.139 + return nl;
1.140 + } else {
1.141 + nl->prev = last;
1.142 + last->next = nl;
1.143 + return l;
1.144 + }
1.145 +}
1.146 +
1.147 +UcxList *ucx_list_prepend(UcxList *l, void *data) {
1.148 + return ucx_list_prepend_a(ucx_default_allocator(), l, data);
1.149 +}
1.150 +
1.151 +UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {
1.152 + UcxList *nl = ucx_list_append_a(alloc, NULL, data);
1.153 + if (!nl) {
1.154 + return NULL;
1.155 + }
1.156 + l = ucx_list_first(l);
1.157 +
1.158 + if (l) {
1.159 + nl->next = l;
1.160 + l->prev = nl;
1.161 + }
1.162 + return nl;
1.163 +}
1.164 +
1.165 +UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
1.166 + if (l1) {
1.167 + UcxList *last = ucx_list_last(l1);
1.168 + last->next = l2;
1.169 + if (l2) {
1.170 + l2->prev = last;
1.171 + }
1.172 + return l1;
1.173 + } else {
1.174 + return l2;
1.175 + }
1.176 +}
1.177 +
1.178 +UcxList *ucx_list_last(const UcxList *l) {
1.179 + if (l == NULL) return NULL;
1.180 +
1.181 + const UcxList *e = l;
1.182 + while (e->next != NULL) {
1.183 + e = e->next;
1.184 + }
1.185 + return (UcxList*)e;
1.186 +}
1.187 +
1.188 +ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {
1.189 + ssize_t index = 0;
1.190 + while (list) {
1.191 + if (list == elem) {
1.192 + return index;
1.193 + }
1.194 + list = list->next;
1.195 + index++;
1.196 + }
1.197 + return -1;
1.198 +}
1.199 +
1.200 +UcxList *ucx_list_get(const UcxList *l, size_t index) {
1.201 + if (l == NULL) return NULL;
1.202 +
1.203 + const UcxList *e = l;
1.204 + while (e->next && index > 0) {
1.205 + e = e->next;
1.206 + index--;
1.207 + }
1.208 +
1.209 + return (UcxList*)(index == 0 ? e : NULL);
1.210 +}
1.211 +
1.212 +ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
1.213 + ssize_t index = 0;
1.214 + UCX_FOREACH(e, l) {
1.215 + if (fnc) {
1.216 + if (fnc(elem, e->data, cmpdata) == 0) {
1.217 + return index;
1.218 + }
1.219 + } else {
1.220 + if (elem == e->data) {
1.221 + return index;
1.222 + }
1.223 + }
1.224 + index++;
1.225 + }
1.226 + return -1;
1.227 +}
1.228 +
1.229 +int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
1.230 + return ucx_list_find(l, elem, fnc, cmpdata) > -1;
1.231 +}
1.232 +
1.233 +size_t ucx_list_size(const UcxList *l) {
1.234 + if (l == NULL) return 0;
1.235 +
1.236 + const UcxList *e = l;
1.237 + size_t s = 1;
1.238 + while (e->next != NULL) {
1.239 + e = e->next;
1.240 + s++;
1.241 + }
1.242 +
1.243 + return s;
1.244 +}
1.245 +
1.246 +static UcxList *ucx_list_sort_merge(int length,
1.247 + UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
1.248 + cmp_func fnc, void* data) {
1.249 +
1.250 + UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
1.251 + UcxList *rc, *lc;
1.252 +
1.253 + lc = ls; rc = le;
1.254 + int n = 0;
1.255 + while (lc && lc != le && rc != re) {
1.256 + if (fnc(lc->data, rc->data, data) <= 0) {
1.257 + sorted[n] = lc;
1.258 + lc = lc->next;
1.259 + } else {
1.260 + sorted[n] = rc;
1.261 + rc = rc->next;
1.262 + }
1.263 + n++;
1.264 + }
1.265 + while (lc && lc != le) {
1.266 + sorted[n] = lc;
1.267 + lc = lc->next;
1.268 + n++;
1.269 + }
1.270 + while (rc && rc != re) {
1.271 + sorted[n] = rc;
1.272 + rc = rc->next;
1.273 + n++;
1.274 + }
1.275 +
1.276 + // Update pointer
1.277 + sorted[0]->prev = NULL;
1.278 + for (int i = 0 ; i < length-1 ; i++) {
1.279 + sorted[i]->next = sorted[i+1];
1.280 + sorted[i+1]->prev = sorted[i];
1.281 + }
1.282 + sorted[length-1]->next = NULL;
1.283 +
1.284 + UcxList *ret = sorted[0];
1.285 + free(sorted);
1.286 + return ret;
1.287 +}
1.288 +
1.289 +UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
1.290 + if (l == NULL) {
1.291 + return NULL;
1.292 + }
1.293 +
1.294 + UcxList *lc;
1.295 + int ln = 1;
1.296 +
1.297 + UcxList *restrict ls = l, *restrict le, *restrict re;
1.298 +
1.299 + // check how many elements are already sorted
1.300 + lc = ls;
1.301 + while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
1.302 + lc = lc->next;
1.303 + ln++;
1.304 + }
1.305 + le = lc->next;
1.306 +
1.307 + if (le == NULL) {
1.308 + return l; // this list is already sorted :)
1.309 + } else {
1.310 + UcxList *rc;
1.311 + int rn = 1;
1.312 + rc = le;
1.313 + // skip already sorted elements
1.314 + while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
1.315 + rc = rc->next;
1.316 + rn++;
1.317 + }
1.318 + re = rc->next;
1.319 +
1.320 + // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
1.321 + UcxList *sorted = ucx_list_sort_merge(ln+rn,
1.322 + ls, le, re,
1.323 + fnc, data);
1.324 +
1.325 + // Something left? Sort it!
1.326 + size_t remainder_length = ucx_list_size(re);
1.327 + if (remainder_length > 0) {
1.328 + UcxList *remainder = ucx_list_sort(re, fnc, data);
1.329 +
1.330 + // merge sorted list with (also sorted) remainder
1.331 + l = ucx_list_sort_merge(ln+rn+remainder_length,
1.332 + sorted, remainder, NULL, fnc, data);
1.333 + } else {
1.334 + // no remainder - we've got our sorted list
1.335 + l = sorted;
1.336 + }
1.337 +
1.338 + return l;
1.339 + }
1.340 +}
1.341 +
1.342 +UcxList *ucx_list_first(const UcxList *l) {
1.343 + if (!l) {
1.344 + return NULL;
1.345 + }
1.346 +
1.347 + const UcxList *e = l;
1.348 + while (e->prev) {
1.349 + e = e->prev;
1.350 + }
1.351 + return (UcxList *)e;
1.352 +}
1.353 +
1.354 +UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
1.355 + return ucx_list_remove_a(ucx_default_allocator(), l, e);
1.356 +}
1.357 +
1.358 +UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
1.359 + if (l == e) {
1.360 + l = e->next;
1.361 + }
1.362 +
1.363 + if (e->next) {
1.364 + e->next->prev = e->prev;
1.365 + }
1.366 +
1.367 + if (e->prev) {
1.368 + e->prev->next = e->next;
1.369 + }
1.370 +
1.371 + alfree(alloc, e);
1.372 + return l;
1.373 +}
