1.1 --- a/src/ucx/list.c Thu Nov 10 18:44:48 2016 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,335 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2015 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 "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_prepend(UcxList *l, void *data) {
1.113 - return ucx_list_prepend_a(ucx_default_allocator(), l, data);
1.114 -}
1.115 -
1.116 -UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) {
1.117 - UcxList *nl = ucx_list_append_a(alloc, NULL, data);
1.118 - if (!nl) {
1.119 - return NULL;
1.120 - }
1.121 - l = ucx_list_first(l);
1.122 -
1.123 - if (l) {
1.124 - nl->next = l;
1.125 - l->prev = nl;
1.126 - }
1.127 - return nl;
1.128 -}
1.129 -
1.130 -UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) {
1.131 - if (l1) {
1.132 - UcxList *last = ucx_list_last(l1);
1.133 - last->next = l2;
1.134 - if (l2) {
1.135 - l2->prev = last;
1.136 - }
1.137 - return l1;
1.138 - } else {
1.139 - return l2;
1.140 - }
1.141 -}
1.142 -
1.143 -UcxList *ucx_list_last(const UcxList *l) {
1.144 - if (l == NULL) return NULL;
1.145 -
1.146 - const UcxList *e = l;
1.147 - while (e->next != NULL) {
1.148 - e = e->next;
1.149 - }
1.150 - return (UcxList*)e;
1.151 -}
1.152 -
1.153 -ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) {
1.154 - ssize_t index = 0;
1.155 - while (list) {
1.156 - if (list == elem) {
1.157 - return index;
1.158 - }
1.159 - list = list->next;
1.160 - index++;
1.161 - }
1.162 - return -1;
1.163 -}
1.164 -
1.165 -UcxList *ucx_list_get(const UcxList *l, size_t index) {
1.166 - if (l == NULL) return NULL;
1.167 -
1.168 - const UcxList *e = l;
1.169 - while (e->next && index > 0) {
1.170 - e = e->next;
1.171 - index--;
1.172 - }
1.173 -
1.174 - return (UcxList*)(index == 0 ? e : NULL);
1.175 -}
1.176 -
1.177 -ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
1.178 - ssize_t index = 0;
1.179 - UCX_FOREACH(e, l) {
1.180 - if (fnc) {
1.181 - if (fnc(elem, e->data, cmpdata) == 0) {
1.182 - return index;
1.183 - }
1.184 - } else {
1.185 - if (elem == e->data) {
1.186 - return index;
1.187 - }
1.188 - }
1.189 - index++;
1.190 - }
1.191 - return -1;
1.192 -}
1.193 -
1.194 -int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) {
1.195 - return ucx_list_find(l, elem, fnc, cmpdata) > -1;
1.196 -}
1.197 -
1.198 -size_t ucx_list_size(const UcxList *l) {
1.199 - if (l == NULL) return 0;
1.200 -
1.201 - const UcxList *e = l;
1.202 - size_t s = 1;
1.203 - while (e->next != NULL) {
1.204 - e = e->next;
1.205 - s++;
1.206 - }
1.207 -
1.208 - return s;
1.209 -}
1.210 -
1.211 -static UcxList *ucx_list_sort_merge(int length,
1.212 - UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
1.213 - cmp_func fnc, void* data) {
1.214 -
1.215 - UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length);
1.216 - UcxList *rc, *lc;
1.217 -
1.218 - lc = ls; rc = le;
1.219 - int n = 0;
1.220 - while (lc && lc != le && rc != re) {
1.221 - if (fnc(lc->data, rc->data, data) <= 0) {
1.222 - sorted[n] = lc;
1.223 - lc = lc->next;
1.224 - } else {
1.225 - sorted[n] = rc;
1.226 - rc = rc->next;
1.227 - }
1.228 - n++;
1.229 - }
1.230 - while (lc && lc != le) {
1.231 - sorted[n] = lc;
1.232 - lc = lc->next;
1.233 - n++;
1.234 - }
1.235 - while (rc && rc != re) {
1.236 - sorted[n] = rc;
1.237 - rc = rc->next;
1.238 - n++;
1.239 - }
1.240 -
1.241 - // Update pointer
1.242 - sorted[0]->prev = NULL;
1.243 - for (int i = 0 ; i < length-1 ; i++) {
1.244 - sorted[i]->next = sorted[i+1];
1.245 - sorted[i+1]->prev = sorted[i];
1.246 - }
1.247 - sorted[length-1]->next = NULL;
1.248 -
1.249 - UcxList *ret = sorted[0];
1.250 - free(sorted);
1.251 - return ret;
1.252 -}
1.253 -
1.254 -UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
1.255 - if (l == NULL) {
1.256 - return NULL;
1.257 - }
1.258 -
1.259 - UcxList *lc;
1.260 - int ln = 1;
1.261 -
1.262 - UcxList *restrict ls = l, *restrict le, *restrict re;
1.263 -
1.264 - // check how many elements are already sorted
1.265 - lc = ls;
1.266 - while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
1.267 - lc = lc->next;
1.268 - ln++;
1.269 - }
1.270 - le = lc->next;
1.271 -
1.272 - if (le == NULL) {
1.273 - return l; // this list is already sorted :)
1.274 - } else {
1.275 - UcxList *rc;
1.276 - int rn = 1;
1.277 - rc = le;
1.278 - // skip already sorted elements
1.279 - while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
1.280 - rc = rc->next;
1.281 - rn++;
1.282 - }
1.283 - re = rc->next;
1.284 -
1.285 - // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
1.286 - UcxList *sorted = ucx_list_sort_merge(ln+rn,
1.287 - ls, le, re,
1.288 - fnc, data);
1.289 -
1.290 - // Something left? Sort it!
1.291 - size_t remainder_length = ucx_list_size(re);
1.292 - if (remainder_length > 0) {
1.293 - UcxList *remainder = ucx_list_sort(re, fnc, data);
1.294 -
1.295 - // merge sorted list with (also sorted) remainder
1.296 - l = ucx_list_sort_merge(ln+rn+remainder_length,
1.297 - sorted, remainder, NULL, fnc, data);
1.298 - } else {
1.299 - // no remainder - we've got our sorted list
1.300 - l = sorted;
1.301 - }
1.302 -
1.303 - return l;
1.304 - }
1.305 -}
1.306 -
1.307 -UcxList *ucx_list_first(const UcxList *l) {
1.308 - if (!l) {
1.309 - return NULL;
1.310 - }
1.311 -
1.312 - const UcxList *e = l;
1.313 - while (e->prev) {
1.314 - e = e->prev;
1.315 - }
1.316 - return (UcxList *)e;
1.317 -}
1.318 -
1.319 -UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
1.320 - return ucx_list_remove_a(ucx_default_allocator(), l, e);
1.321 -}
1.322 -
1.323 -UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) {
1.324 - if (l == e) {
1.325 - l = e->next;
1.326 - }
1.327 -
1.328 - if (e->next) {
1.329 - e->next->prev = e->prev;
1.330 - }
1.331 -
1.332 - if (e->prev) {
1.333 - e->prev->next = e->next;
1.334 - }
1.335 -
1.336 - alfree(alloc, e);
1.337 - return l;
1.338 -}
