comparison: src/ucx/list.c
src/ucx/list.c
- changeset 61
- 47a5fc33590a
- parent 60
- 9f25df78925e
- child 62
- 3fff4c364ffc
equal
deleted
inserted
replaced
| 60:9f25df78925e | 61:47a5fc33590a |
|---|---|
| 1 /* | |
| 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | |
| 3 * | |
| 4 * Copyright 2015 Olaf Wintermann. All rights reserved. | |
| 5 * | |
| 6 * Redistribution and use in source and binary forms, with or without | |
| 7 * modification, are permitted provided that the following conditions are met: | |
| 8 * | |
| 9 * 1. Redistributions of source code must retain the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer. | |
| 11 * | |
| 12 * 2. Redistributions in binary form must reproduce the above copyright | |
| 13 * notice, this list of conditions and the following disclaimer in the | |
| 14 * documentation and/or other materials provided with the distribution. | |
| 15 * | |
| 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
| 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
| 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
| 26 * POSSIBILITY OF SUCH DAMAGE. | |
| 27 */ | |
| 28 | |
| 29 #include "list.h" | |
| 30 | |
| 31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { | |
| 32 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); | |
| 33 } | |
| 34 | |
| 35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l, | |
| 36 copy_func fnc, void *data) { | |
| 37 UcxList *ret = NULL; | |
| 38 while (l) { | |
| 39 if (fnc) { | |
| 40 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); | |
| 41 } else { | |
| 42 ret = ucx_list_append_a(alloc, ret, l->data); | |
| 43 } | |
| 44 l = l->next; | |
| 45 } | |
| 46 return ret; | |
| 47 } | |
| 48 | |
| 49 int ucx_list_equals(const UcxList *l1, const UcxList *l2, | |
| 50 cmp_func fnc, void* data) { | |
| 51 if (l1 == l2) return 1; | |
| 52 | |
| 53 while (l1 != NULL && l2 != NULL) { | |
| 54 if (fnc == NULL) { | |
| 55 if (l1->data != l2->data) return 0; | |
| 56 } else { | |
| 57 if (fnc(l1->data, l2->data, data) != 0) return 0; | |
| 58 } | |
| 59 l1 = l1->next; | |
| 60 l2 = l2->next; | |
| 61 } | |
| 62 | |
| 63 return (l1 == NULL && l2 == NULL); | |
| 64 } | |
| 65 | |
| 66 void ucx_list_free(UcxList *l) { | |
| 67 ucx_list_free_a(ucx_default_allocator(), l); | |
| 68 } | |
| 69 | |
| 70 void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { | |
| 71 UcxList *e = l, *f; | |
| 72 while (e != NULL) { | |
| 73 f = e; | |
| 74 e = e->next; | |
| 75 alfree(alloc, f); | |
| 76 } | |
| 77 } | |
| 78 | |
| 79 void ucx_list_free_content(UcxList* list, ucx_destructor destr) { | |
| 80 while (list != NULL) { | |
| 81 destr(list->data); | |
| 82 list = list->next; | |
| 83 } | |
| 84 } | |
| 85 | |
| 86 UcxList *ucx_list_append(UcxList *l, void *data) { | |
| 87 return ucx_list_append_a(ucx_default_allocator(), l, data); | |
| 88 } | |
| 89 | |
| 90 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { | |
| 91 UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList)); | |
| 92 if (!nl) { | |
| 93 return NULL; | |
| 94 } | |
| 95 | |
| 96 nl->data = data; | |
| 97 nl->next = NULL; | |
| 98 if (l) { | |
| 99 UcxList *t = ucx_list_last(l); | |
| 100 t->next = nl; | |
| 101 nl->prev = t; | |
| 102 return l; | |
| 103 } else { | |
| 104 nl->prev = NULL; | |
| 105 return nl; | |
| 106 } | |
| 107 } | |
| 108 | |
| 109 UcxList *ucx_list_prepend(UcxList *l, void *data) { | |
| 110 return ucx_list_prepend_a(ucx_default_allocator(), l, data); | |
| 111 } | |
| 112 | |
| 113 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { | |
| 114 UcxList *nl = ucx_list_append_a(alloc, NULL, data); | |
| 115 if (!nl) { | |
| 116 return NULL; | |
| 117 } | |
| 118 l = ucx_list_first(l); | |
| 119 | |
| 120 if (l) { | |
| 121 nl->next = l; | |
| 122 l->prev = nl; | |
| 123 } | |
| 124 return nl; | |
| 125 } | |
| 126 | |
| 127 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { | |
| 128 if (l1) { | |
| 129 UcxList *last = ucx_list_last(l1); | |
| 130 last->next = l2; | |
| 131 if (l2) { | |
| 132 l2->prev = last; | |
| 133 } | |
| 134 return l1; | |
| 135 } else { | |
| 136 return l2; | |
| 137 } | |
| 138 } | |
| 139 | |
| 140 UcxList *ucx_list_last(const UcxList *l) { | |
| 141 if (l == NULL) return NULL; | |
| 142 | |
| 143 const UcxList *e = l; | |
| 144 while (e->next != NULL) { | |
| 145 e = e->next; | |
| 146 } | |
| 147 return (UcxList*)e; | |
| 148 } | |
| 149 | |
| 150 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) { | |
| 151 ssize_t index = 0; | |
| 152 while (list) { | |
| 153 if (list == elem) { | |
| 154 return index; | |
| 155 } | |
| 156 list = list->next; | |
| 157 index++; | |
| 158 } | |
| 159 return -1; | |
| 160 } | |
| 161 | |
| 162 UcxList *ucx_list_get(const UcxList *l, size_t index) { | |
| 163 if (l == NULL) return NULL; | |
| 164 | |
| 165 const UcxList *e = l; | |
| 166 while (e->next && index > 0) { | |
| 167 e = e->next; | |
| 168 index--; | |
| 169 } | |
| 170 | |
| 171 return (UcxList*)(index == 0 ? e : NULL); | |
| 172 } | |
| 173 | |
| 174 ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | |
| 175 ssize_t index = 0; | |
| 176 UCX_FOREACH(e, l) { | |
| 177 if (fnc) { | |
| 178 if (fnc(elem, e->data, cmpdata) == 0) { | |
| 179 return index; | |
| 180 } | |
| 181 } else { | |
| 182 if (elem == e->data) { | |
| 183 return index; | |
| 184 } | |
| 185 } | |
| 186 index++; | |
| 187 } | |
| 188 return -1; | |
| 189 } | |
| 190 | |
| 191 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | |
| 192 return ucx_list_find(l, elem, fnc, cmpdata) > -1; | |
| 193 } | |
| 194 | |
| 195 size_t ucx_list_size(const UcxList *l) { | |
| 196 if (l == NULL) return 0; | |
| 197 | |
| 198 const UcxList *e = l; | |
| 199 size_t s = 1; | |
| 200 while (e->next != NULL) { | |
| 201 e = e->next; | |
| 202 s++; | |
| 203 } | |
| 204 | |
| 205 return s; | |
| 206 } | |
| 207 | |
| 208 static UcxList *ucx_list_sort_merge(int length, | |
| 209 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, | |
| 210 cmp_func fnc, void* data) { | |
| 211 | |
| 212 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | |
| 213 UcxList *rc, *lc; | |
| 214 | |
| 215 lc = ls; rc = le; | |
| 216 int n = 0; | |
| 217 while (lc && lc != le && rc != re) { | |
| 218 if (fnc(lc->data, rc->data, data) <= 0) { | |
| 219 sorted[n] = lc; | |
| 220 lc = lc->next; | |
| 221 } else { | |
| 222 sorted[n] = rc; | |
| 223 rc = rc->next; | |
| 224 } | |
| 225 n++; | |
| 226 } | |
| 227 while (lc && lc != le) { | |
| 228 sorted[n] = lc; | |
| 229 lc = lc->next; | |
| 230 n++; | |
| 231 } | |
| 232 while (rc && rc != re) { | |
| 233 sorted[n] = rc; | |
| 234 rc = rc->next; | |
| 235 n++; | |
| 236 } | |
| 237 | |
| 238 // Update pointer | |
| 239 sorted[0]->prev = NULL; | |
| 240 for (int i = 0 ; i < length-1 ; i++) { | |
| 241 sorted[i]->next = sorted[i+1]; | |
| 242 sorted[i+1]->prev = sorted[i]; | |
| 243 } | |
| 244 sorted[length-1]->next = NULL; | |
| 245 | |
| 246 UcxList *ret = sorted[0]; | |
| 247 free(sorted); | |
| 248 return ret; | |
| 249 } | |
| 250 | |
| 251 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { | |
| 252 if (l == NULL) { | |
| 253 return NULL; | |
| 254 } | |
| 255 | |
| 256 UcxList *lc; | |
| 257 int ln = 1; | |
| 258 | |
| 259 UcxList *restrict ls = l, *restrict le, *restrict re; | |
| 260 | |
| 261 // check how many elements are already sorted | |
| 262 lc = ls; | |
| 263 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
| 264 lc = lc->next; | |
| 265 ln++; | |
| 266 } | |
| 267 le = lc->next; | |
| 268 | |
| 269 if (le == NULL) { | |
| 270 return l; // this list is already sorted :) | |
| 271 } else { | |
| 272 UcxList *rc; | |
| 273 int rn = 1; | |
| 274 rc = le; | |
| 275 // skip already sorted elements | |
| 276 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | |
| 277 rc = rc->next; | |
| 278 rn++; | |
| 279 } | |
| 280 re = rc->next; | |
| 281 | |
| 282 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
| 283 UcxList *sorted = ucx_list_sort_merge(ln+rn, | |
| 284 ls, le, re, | |
| 285 fnc, data); | |
| 286 | |
| 287 // Something left? Sort it! | |
| 288 size_t remainder_length = ucx_list_size(re); | |
| 289 if (remainder_length > 0) { | |
| 290 UcxList *remainder = ucx_list_sort(re, fnc, data); | |
| 291 | |
| 292 // merge sorted list with (also sorted) remainder | |
| 293 l = ucx_list_sort_merge(ln+rn+remainder_length, | |
| 294 sorted, remainder, NULL, fnc, data); | |
| 295 } else { | |
| 296 // no remainder - we've got our sorted list | |
| 297 l = sorted; | |
| 298 } | |
| 299 | |
| 300 return l; | |
| 301 } | |
| 302 } | |
| 303 | |
| 304 UcxList *ucx_list_first(const UcxList *l) { | |
| 305 if (!l) { | |
| 306 return NULL; | |
| 307 } | |
| 308 | |
| 309 const UcxList *e = l; | |
| 310 while (e->prev) { | |
| 311 e = e->prev; | |
| 312 } | |
| 313 return (UcxList *)e; | |
| 314 } | |
| 315 | |
| 316 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { | |
| 317 return ucx_list_remove_a(ucx_default_allocator(), l, e); | |
| 318 } | |
| 319 | |
| 320 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { | |
| 321 if (l == e) { | |
| 322 l = e->next; | |
| 323 } | |
| 324 | |
| 325 if (e->next) { | |
| 326 e->next->prev = e->prev; | |
| 327 } | |
| 328 | |
| 329 if (e->prev) { | |
| 330 e->prev->next = e->next; | |
| 331 } | |
| 332 | |
| 333 alfree(alloc, e); | |
| 334 return l; | |
| 335 } |
