comparison: ucx/list.c
ucx/list.c
- changeset 157
- 0b33b9396851
- parent 152
- 62921b370c60
- child 162
- 18892c0a9adc
equal
deleted
inserted
replaced
| 156:62f1a55535e7 | 157:0b33b9396851 |
|---|---|
| 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 } |
| 104 nl->prev = NULL; | 105 nl->prev = NULL; |
| 105 return nl; | 106 return nl; |
| 106 } | 107 } |
| 107 } | 108 } |
| 108 | 109 |
| 109 UcxList *ucx_list_append_once(UcxList *l, void *data, | |
| 110 cmp_func cmpfnc, void *cmpdata) { | |
| 111 return ucx_list_append_once_a(ucx_default_allocator(), l, | |
| 112 data, cmpfnc, cmpdata); | |
| 113 } | |
| 114 | |
| 115 UcxList *ucx_list_append_once_a(UcxAllocator *alloc, UcxList *l, void *data, | |
| 116 cmp_func cmpfnc, void *cmpdata) { | |
| 117 | |
| 118 UcxList *last = NULL; | |
| 119 { | |
| 120 UcxList *e = l; | |
| 121 while (e) { | |
| 122 if (cmpfnc(e->data, data, cmpdata) == 0) { | |
| 123 return l; | |
| 124 } | |
| 125 last = e; | |
| 126 e = e->next; | |
| 127 } | |
| 128 } | |
| 129 | |
| 130 UcxList *nl = ucx_list_append_a(alloc, NULL, data); | |
| 131 if (!nl) { | |
| 132 return NULL; | |
| 133 } | |
| 134 | |
| 135 if (last == NULL) { | |
| 136 return nl; | |
| 137 } else { | |
| 138 nl->prev = last; | |
| 139 last->next = nl; | |
| 140 return l; | |
| 141 } | |
| 142 } | |
| 143 | |
| 144 UcxList *ucx_list_prepend(UcxList *l, void *data) { | 110 UcxList *ucx_list_prepend(UcxList *l, void *data) { |
| 145 return ucx_list_prepend_a(ucx_default_allocator(), l, data); | 111 return ucx_list_prepend_a(ucx_default_allocator(), l, data); |
| 146 } | 112 } |
| 147 | 113 |
| 148 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { | 114 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { |
| 239 | 205 |
| 240 return s; | 206 return s; |
| 241 } | 207 } |
| 242 | 208 |
| 243 static UcxList *ucx_list_sort_merge(int length, | 209 static UcxList *ucx_list_sort_merge(int length, |
| 244 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, | 210 UcxList* ls, UcxList* le, UcxList* re, |
| 245 cmp_func fnc, void* data) { | 211 cmp_func fnc, void* data) { |
| 246 | 212 |
| 247 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | 213 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
| 248 UcxList *rc, *lc; | 214 UcxList *rc, *lc; |
| 249 | 215 |
| 289 } | 255 } |
| 290 | 256 |
| 291 UcxList *lc; | 257 UcxList *lc; |
| 292 int ln = 1; | 258 int ln = 1; |
| 293 | 259 |
| 294 UcxList *restrict ls = l, *restrict le, *restrict re; | 260 UcxList *ls = l, *le, *re; |
| 295 | 261 |
| 296 // check how many elements are already sorted | 262 // check how many elements are already sorted |
| 297 lc = ls; | 263 lc = ls; |
| 298 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) { |
| 299 lc = lc->next; | 265 lc = lc->next; |
