1.1 --- a/ucx/dlist.c Mon Jul 22 11:39:06 2013 +0200
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,270 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2013 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 "dlist.h"
1.33 -
1.34 -UcxDlist *ucx_dlist_clone(UcxDlist *l, copy_func fnc, void *data) {
1.35 - UcxDlist *ret = NULL;
1.36 - while (l != NULL) {
1.37 - if (fnc != NULL) {
1.38 - ret = ucx_dlist_append(ret, fnc(l->data, data));
1.39 - } else {
1.40 - ret = ucx_dlist_append(ret, l->data);
1.41 - }
1.42 - l = l->next;
1.43 - }
1.44 - return ret;
1.45 -}
1.46 -
1.47 -int ucx_dlist_equals(const UcxDlist *l1, const UcxDlist *l2,
1.48 - cmp_func fnc, void* data) {
1.49 - if (l1 == l2) return 1;
1.50 -
1.51 - while (l1 != NULL && l2 != NULL) {
1.52 - if (fnc == NULL) {
1.53 - if (l1->data != l2->data) return 0;
1.54 - } else {
1.55 - if (fnc(l1->data, l2->data, data) != 0) return 0;
1.56 - }
1.57 - l1 = l1->next;
1.58 - l2 = l2->next;
1.59 - }
1.60 -
1.61 - return (l1 == NULL && l2 == NULL);
1.62 -}
1.63 -
1.64 -void ucx_dlist_free(UcxDlist *l) {
1.65 - UcxDlist *e = l, *f;
1.66 - while (e != NULL) {
1.67 - f = e;
1.68 - e = e->next;
1.69 - free(f);
1.70 - }
1.71 -}
1.72 -
1.73 -UcxDlist *ucx_dlist_append(UcxDlist *l, void *data) {
1.74 - UcxDlist *nl = (UcxDlist*) malloc(sizeof(UcxDlist));
1.75 - if (nl == NULL) return NULL;
1.76 -
1.77 - nl->data = data;
1.78 - nl->next = NULL;
1.79 - if (l == NULL) {
1.80 - nl->prev = NULL;
1.81 - return nl;
1.82 - } else {
1.83 - UcxDlist *t = ucx_dlist_last(l);
1.84 - t->next = nl;
1.85 - nl->prev = t;
1.86 - return l;
1.87 - }
1.88 -}
1.89 -
1.90 -UcxDlist *ucx_dlist_prepend(UcxDlist *l, void *data) {
1.91 - UcxDlist *nl = ucx_dlist_append(NULL, data);
1.92 - if (nl == NULL) return NULL;
1.93 -
1.94 - if (l != NULL) {
1.95 - nl->next = l;
1.96 - l->prev = nl;
1.97 - }
1.98 - return nl;
1.99 -}
1.100 -
1.101 -UcxDlist *ucx_dlist_concat(UcxDlist *l1, UcxDlist *l2) {
1.102 - if (l1 == NULL) {
1.103 - return l2;
1.104 - } else {
1.105 - UcxDlist *last = ucx_dlist_last(l1);
1.106 - last->next = l2;
1.107 - l2->prev = last;
1.108 - return l1;
1.109 - }
1.110 -}
1.111 -
1.112 -UcxDlist *ucx_dlist_last(const UcxDlist *l) {
1.113 - if (l == NULL) return NULL;
1.114 -
1.115 - const UcxDlist *e = l;
1.116 - while (e->next != NULL) {
1.117 - e = e->next;
1.118 - }
1.119 - return (UcxDlist*)e;
1.120 -}
1.121 -
1.122 -UcxDlist *ucx_dlist_get(const UcxDlist *l, int index) {
1.123 - if (l == NULL) return NULL;
1.124 -
1.125 - const UcxDlist *e = l;
1.126 - while (e->next != NULL && index > 0) {
1.127 - e = e->next;
1.128 - index--;
1.129 - }
1.130 -
1.131 - return (UcxDlist*)(index == 0 ? e : NULL);
1.132 -}
1.133 -
1.134 -int ucx_dlist_contains(UcxDlist *l, void *elem, cmp_func fnc, void *cmpdata) {
1.135 - UCX_FOREACH(l, e) {
1.136 - if (!fnc(elem, e->data, cmpdata)) {
1.137 - return 1;
1.138 - }
1.139 - }
1.140 - return 0;
1.141 -}
1.142 -
1.143 -size_t ucx_dlist_size(const UcxDlist *l) {
1.144 - if (l == NULL) return 0;
1.145 -
1.146 - const UcxDlist *e = l;
1.147 - size_t s = 1;
1.148 - while (e->next != NULL) {
1.149 - e = e->next;
1.150 - s++;
1.151 - }
1.152 -
1.153 - return s;
1.154 -}
1.155 -
1.156 -UcxDlist *ucx_dlist_sort_merge(int length,
1.157 - UcxDlist* restrict ls, UcxDlist* restrict le, UcxDlist* restrict re,
1.158 - cmp_func fnc, void* data) {
1.159 -
1.160 - UcxDlist** sorted = (UcxDlist**) malloc(sizeof(UcxDlist*)*length);
1.161 - UcxDlist *rc, *lc;
1.162 -
1.163 - lc = ls; rc = le;
1.164 - int n = 0;
1.165 - while (lc && lc != le && rc != re) {
1.166 - if (fnc(lc->data, rc->data, data) <= 0) {
1.167 - sorted[n] = lc;
1.168 - lc = lc->next;
1.169 - } else {
1.170 - sorted[n] = rc;
1.171 - rc = rc->next;
1.172 - }
1.173 - n++;
1.174 - }
1.175 - while (lc && lc != le) {
1.176 - sorted[n] = lc;
1.177 - lc = lc->next;
1.178 - n++;
1.179 - }
1.180 - while (rc && rc != re) {
1.181 - sorted[n] = rc;
1.182 - rc = rc->next;
1.183 - n++;
1.184 - }
1.185 -
1.186 - // Update pointer
1.187 - sorted[0]->prev = NULL;
1.188 - for (int i = 0 ; i < length-1 ; i++) {
1.189 - sorted[i]->next = sorted[i+1];
1.190 - sorted[i+1]->prev = sorted[i];
1.191 - }
1.192 - sorted[length-1]->next = NULL;
1.193 -
1.194 - UcxDlist *ret = sorted[0];
1.195 - free(sorted);
1.196 - return ret;
1.197 -}
1.198 -
1.199 -UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) {
1.200 - if (l == NULL) {
1.201 - return NULL;
1.202 - }
1.203 -
1.204 - UcxDlist *lc;
1.205 - int ln = 1;
1.206 -
1.207 - UcxDlist *restrict ls = l, *restrict le, *restrict re;
1.208 - lc = ls;
1.209 - while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
1.210 - lc = lc->next;
1.211 - ln++;
1.212 - }
1.213 - le = lc->next;
1.214 -
1.215 - if (le == NULL) {
1.216 - return l; // this list is already sorted :)
1.217 - } else {
1.218 - UcxDlist *rc;
1.219 - int rn = 1;
1.220 - rc = le;
1.221 - while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
1.222 - rc = rc->next;
1.223 - rn++;
1.224 - }
1.225 - re = rc->next;
1.226 -
1.227 - // Something left? Sort it!
1.228 - UcxDlist *remainder = re;
1.229 - size_t remainder_length = ucx_dlist_size(remainder);
1.230 - if (remainder != NULL) {
1.231 - remainder = ucx_dlist_sort(remainder, fnc, data);
1.232 - }
1.233 -
1.234 - // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
1.235 - UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn,
1.236 - ls, le, re,
1.237 - fnc, data);
1.238 -
1.239 - // merge sorted list with (also sorted) remainder
1.240 - l = ucx_dlist_sort_merge(ln+rn+remainder_length,
1.241 - sorted, remainder, NULL, fnc, data);
1.242 -
1.243 - return l;
1.244 - }
1.245 -}
1.246 -
1.247 -/* dlist specific functions */
1.248 -UcxDlist *ucx_dlist_first(const UcxDlist *l) {
1.249 - if (l == NULL) return NULL;
1.250 -
1.251 - const UcxDlist *e = l;
1.252 - while (e->prev != NULL) {
1.253 - e = e->prev;
1.254 - }
1.255 - return (UcxDlist *)e;
1.256 -}
1.257 -
1.258 -UcxDlist *ucx_dlist_remove(UcxDlist *l, UcxDlist *e) {
1.259 - if (e->prev == NULL) {
1.260 - if(e->next != NULL) {
1.261 - e->next->prev = NULL;
1.262 - l = e->next;
1.263 - } else {
1.264 - l = NULL;
1.265 - }
1.266 -
1.267 - } else {
1.268 - e->prev->next = e->next;
1.269 - e->next->prev = e->prev;
1.270 - }
1.271 - free(e);
1.272 - return l;
1.273 -}
