comparison: src/ucx/list.c
src/ucx/list.c
- branch
- config
- changeset 254
- 4784c14aa639
- parent 135
- 471e28cca288
- child 260
- 4779a6fb4fbe
equal
deleted
inserted
replaced
| 253:ddfead6ea863 | 254:4784c14aa639 |
|---|---|
| 1 /* | 1 /* |
| 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
| 3 * | 3 * |
| 4 * Copyright 2016 Olaf Wintermann. All rights reserved. | 4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. |
| 5 * | 5 * |
| 6 * Redistribution and use in source and binary forms, with or without | 6 * Redistribution and use in source and binary forms, with or without |
| 7 * modification, are permitted provided that the following conditions are met: | 7 * modification, are permitted provided that the following conditions are met: |
| 8 * | 8 * |
| 9 * 1. Redistributions of source code must retain the above copyright | 9 * 1. Redistributions of source code must retain the above copyright |
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | 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 | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "list.h" | 29 #include "ucx/list.h" |
| 30 | 30 |
| 31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { | 31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { |
| 32 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); | 32 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); |
| 33 } | 33 } |
| 34 | 34 |
| 75 alfree(alloc, f); | 75 alfree(alloc, f); |
| 76 } | 76 } |
| 77 } | 77 } |
| 78 | 78 |
| 79 void ucx_list_free_content(UcxList* list, ucx_destructor destr) { | 79 void ucx_list_free_content(UcxList* list, ucx_destructor destr) { |
| 80 if (!destr) destr = free; | |
| 80 while (list != NULL) { | 81 while (list != NULL) { |
| 81 destr(list->data); | 82 destr(list->data); |
| 82 list = list->next; | 83 list = list->next; |
| 83 } | 84 } |
| 84 } | 85 } |
| 203 } | 204 } |
| 204 | 205 |
| 205 return s; | 206 return s; |
| 206 } | 207 } |
| 207 | 208 |
| 208 static UcxList *ucx_list_sort_merge(int length, | 209 static UcxList *ucx_list_sort_merge(size_t length, |
| 209 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, | 210 UcxList* ls, UcxList* le, UcxList* re, |
| 210 cmp_func fnc, void* data) { | 211 cmp_func fnc, void* data) { |
| 211 | 212 |
| 212 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | 213 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
| 213 UcxList *rc, *lc; | 214 UcxList *rc, *lc; |
| 214 | 215 |
| 215 lc = ls; rc = le; | 216 lc = ls; rc = le; |
| 216 int n = 0; | 217 size_t n = 0; |
| 217 while (lc && lc != le && rc != re) { | 218 while (lc && lc != le && rc != re) { |
| 218 if (fnc(lc->data, rc->data, data) <= 0) { | 219 if (fnc(lc->data, rc->data, data) <= 0) { |
| 219 sorted[n] = lc; | 220 sorted[n] = lc; |
| 220 lc = lc->next; | 221 lc = lc->next; |
| 221 } else { | 222 } else { |
| 252 if (l == NULL) { | 253 if (l == NULL) { |
| 253 return NULL; | 254 return NULL; |
| 254 } | 255 } |
| 255 | 256 |
| 256 UcxList *lc; | 257 UcxList *lc; |
| 257 int ln = 1; | 258 size_t ln = 1; |
| 258 | 259 |
| 259 UcxList *restrict ls = l, *restrict le, *restrict re; | 260 UcxList *ls = l, *le, *re; |
| 260 | 261 |
| 261 // check how many elements are already sorted | 262 // check how many elements are already sorted |
| 262 lc = ls; | 263 lc = ls; |
| 263 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | 264 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { |
| 264 lc = lc->next; | 265 lc = lc->next; |
| 268 | 269 |
| 269 if (le == NULL) { | 270 if (le == NULL) { |
| 270 return l; // this list is already sorted :) | 271 return l; // this list is already sorted :) |
| 271 } else { | 272 } else { |
| 272 UcxList *rc; | 273 UcxList *rc; |
| 273 int rn = 1; | 274 size_t rn = 1; |
| 274 rc = le; | 275 rc = le; |
| 275 // skip already sorted elements | 276 // skip already sorted elements |
| 276 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | 277 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
| 277 rc = rc->next; | 278 rc = rc->next; |
| 278 rn++; | 279 rn++; |
