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 2013 Olaf Wintermann. All rights reserved. |
4 * Copyright 2014 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 |
70 void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { |
70 void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { |
71 UcxList *e = l, *f; |
71 UcxList *e = l, *f; |
72 while (e != NULL) { |
72 while (e != NULL) { |
73 f = e; |
73 f = e; |
74 e = e->next; |
74 e = e->next; |
75 alloc->free(alloc->pool, f); |
75 alfree(alloc, f); |
76 } |
76 } |
77 } |
77 } |
78 |
78 |
79 UcxList *ucx_list_append(UcxList *l, void *data) { |
79 UcxList *ucx_list_append(UcxList *l, void *data) { |
80 return ucx_list_append_a(ucx_default_allocator(), l, data); |
80 return ucx_list_append_a(ucx_default_allocator(), l, data); |
81 } |
81 } |
82 |
82 |
83 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { |
83 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { |
84 UcxList *nl = (UcxList*) alloc->malloc(alloc->pool, sizeof(UcxList)); |
84 UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList)); |
85 if (!nl) { |
85 if (!nl) { |
86 return NULL; |
86 return NULL; |
87 } |
87 } |
88 |
88 |
89 nl->data = data; |
89 nl->data = data; |
194 } |
196 } |
195 |
197 |
196 return s; |
198 return s; |
197 } |
199 } |
198 |
200 |
199 UcxList *ucx_list_sort_merge(int length, |
201 static UcxList *ucx_list_sort_merge(int length, |
200 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, |
202 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, |
201 cmp_func fnc, void* data) { |
203 cmp_func fnc, void* data) { |
202 |
204 |
203 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
205 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
204 UcxList *rc, *lc; |
206 UcxList *rc, *lc; |
259 return l; // this list is already sorted :) |
263 return l; // this list is already sorted :) |
260 } else { |
264 } else { |
261 UcxList *rc; |
265 UcxList *rc; |
262 int rn = 1; |
266 int rn = 1; |
263 rc = le; |
267 rc = le; |
|
268 // skip already sorted elements |
264 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
269 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
265 rc = rc->next; |
270 rc = rc->next; |
266 rn++; |
271 rn++; |
267 } |
272 } |
268 re = rc->next; |
273 re = rc->next; |
269 |
|
270 // Something left? Sort it! |
|
271 UcxList *remainder = re; |
|
272 size_t remainder_length = ucx_list_size(remainder); |
|
273 if (remainder != NULL) { |
|
274 remainder = ucx_list_sort(remainder, fnc, data); |
|
275 } |
|
276 |
274 |
277 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them |
275 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them |
278 UcxList *sorted = ucx_list_sort_merge(ln+rn, |
276 UcxList *sorted = ucx_list_sort_merge(ln+rn, |
279 ls, le, re, |
277 ls, le, re, |
280 fnc, data); |
278 fnc, data); |
281 |
279 |
282 // merge sorted list with (also sorted) remainder |
280 // Something left? Sort it! |
283 l = ucx_list_sort_merge(ln+rn+remainder_length, |
281 size_t remainder_length = ucx_list_size(re); |
284 sorted, remainder, NULL, fnc, data); |
282 if (remainder_length > 0) { |
|
283 UcxList *remainder = ucx_list_sort(re, fnc, data); |
|
284 |
|
285 // merge sorted list with (also sorted) remainder |
|
286 l = ucx_list_sort_merge(ln+rn+remainder_length, |
|
287 sorted, remainder, NULL, fnc, data); |
|
288 } else { |
|
289 // no remainder - we've got our sorted list |
|
290 l = sorted; |
|
291 } |
285 |
292 |
286 return l; |
293 return l; |
287 } |
294 } |
288 } |
295 } |
289 |
296 |
302 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
309 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
303 return ucx_list_remove_a(ucx_default_allocator(), l, e); |
310 return ucx_list_remove_a(ucx_default_allocator(), l, e); |
304 } |
311 } |
305 |
312 |
306 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { |
313 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { |
307 if (e->prev == NULL) { |
314 if (l == e) { |
308 if(e->next != NULL) { |
315 l = e->next; |
309 e->next->prev = NULL; |
316 } |
310 l = e->next; |
317 |
311 } else { |
318 if (e->next) { |
312 l = NULL; |
319 e->next->prev = e->prev; |
313 } |
320 } |
314 |
321 |
315 } else { |
322 if (e->prev) { |
316 e->prev->next = e->next; |
323 e->prev->next = e->next; |
317 e->next->prev = e->prev; |
324 } |
318 } |
325 |
319 alloc->free(alloc->pool, e); |
326 alfree(alloc, e); |
320 return l; |
327 return l; |
321 } |
328 } |