comparison: ucx/list.c
ucx/list.c
- changeset 162
- 18892c0a9adc
- parent 157
- 0b33b9396851
equal
deleted
inserted
replaced
| 161:b1eac0878ce7 | 162:18892c0a9adc |
|---|---|
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "ucx/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(const 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 |
| 35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l, | 35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, const UcxList *l, |
| 36 copy_func fnc, void *data) { | 36 copy_func fnc, void *data) { |
| 37 UcxList *ret = NULL; | 37 UcxList *ret = NULL; |
| 38 while (l) { | 38 while (l) { |
| 39 if (fnc) { | 39 if (fnc) { |
| 40 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); | 40 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); |
| 170 } | 170 } |
| 171 | 171 |
| 172 return (UcxList*)(index == 0 ? e : NULL); | 172 return (UcxList*)(index == 0 ? e : NULL); |
| 173 } | 173 } |
| 174 | 174 |
| 175 ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | 175 ssize_t ucx_list_find(const UcxList *l, void *elem, |
| 176 cmp_func fnc, void *cmpdata) { | |
| 176 ssize_t index = 0; | 177 ssize_t index = 0; |
| 177 UCX_FOREACH(e, l) { | 178 UCX_FOREACH(e, l) { |
| 178 if (fnc) { | 179 if (fnc) { |
| 179 if (fnc(elem, e->data, cmpdata) == 0) { | 180 if (fnc(elem, e->data, cmpdata) == 0) { |
| 180 return index; | 181 return index; |
| 187 index++; | 188 index++; |
| 188 } | 189 } |
| 189 return -1; | 190 return -1; |
| 190 } | 191 } |
| 191 | 192 |
| 192 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { | 193 int ucx_list_contains(const UcxList *l, void *elem, |
| 194 cmp_func fnc, void *cmpdata) { | |
| 193 return ucx_list_find(l, elem, fnc, cmpdata) > -1; | 195 return ucx_list_find(l, elem, fnc, cmpdata) > -1; |
| 194 } | 196 } |
| 195 | 197 |
| 196 size_t ucx_list_size(const UcxList *l) { | 198 size_t ucx_list_size(const UcxList *l) { |
| 197 if (l == NULL) return 0; | 199 if (l == NULL) return 0; |
| 204 } | 206 } |
| 205 | 207 |
| 206 return s; | 208 return s; |
| 207 } | 209 } |
| 208 | 210 |
| 209 static UcxList *ucx_list_sort_merge(int length, | 211 static UcxList *ucx_list_sort_merge(size_t length, |
| 210 UcxList* ls, UcxList* le, UcxList* re, | 212 UcxList* ls, UcxList* le, UcxList* re, |
| 211 cmp_func fnc, void* data) { | 213 cmp_func fnc, void* data) { |
| 212 | 214 |
| 213 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | 215 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
| 214 UcxList *rc, *lc; | 216 UcxList *rc, *lc; |
| 215 | 217 |
| 216 lc = ls; rc = le; | 218 lc = ls; rc = le; |
| 217 int n = 0; | 219 size_t n = 0; |
| 218 while (lc && lc != le && rc != re) { | 220 while (lc && lc != le && rc != re) { |
| 219 if (fnc(lc->data, rc->data, data) <= 0) { | 221 if (fnc(lc->data, rc->data, data) <= 0) { |
| 220 sorted[n] = lc; | 222 sorted[n] = lc; |
| 221 lc = lc->next; | 223 lc = lc->next; |
| 222 } else { | 224 } else { |
| 253 if (l == NULL) { | 255 if (l == NULL) { |
| 254 return NULL; | 256 return NULL; |
| 255 } | 257 } |
| 256 | 258 |
| 257 UcxList *lc; | 259 UcxList *lc; |
| 258 int ln = 1; | 260 size_t ln = 1; |
| 259 | 261 |
| 260 UcxList *ls = l, *le, *re; | 262 UcxList *ls = l, *le, *re; |
| 261 | 263 |
| 262 // check how many elements are already sorted | 264 // check how many elements are already sorted |
| 263 lc = ls; | 265 lc = ls; |
| 269 | 271 |
| 270 if (le == NULL) { | 272 if (le == NULL) { |
| 271 return l; // this list is already sorted :) | 273 return l; // this list is already sorted :) |
| 272 } else { | 274 } else { |
| 273 UcxList *rc; | 275 UcxList *rc; |
| 274 int rn = 1; | 276 size_t rn = 1; |
| 275 rc = le; | 277 rc = le; |
| 276 // skip already sorted elements | 278 // skip already sorted elements |
| 277 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | 279 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
| 278 rc = rc->next; | 280 rc = rc->next; |
| 279 rn++; | 281 rn++; |
| 332 } | 334 } |
| 333 | 335 |
| 334 alfree(alloc, e); | 336 alfree(alloc, e); |
| 335 return l; | 337 return l; |
| 336 } | 338 } |
| 339 | |
| 340 | |
| 341 static UcxList* ucx_list_setoperation_a(UcxAllocator *allocator, | |
| 342 UcxList const *left, UcxList const *right, | |
| 343 cmp_func cmpfnc, void* cmpdata, | |
| 344 copy_func cpfnc, void* cpdata, | |
| 345 int op) { | |
| 346 | |
| 347 UcxList *res = NULL; | |
| 348 UcxList *cur = NULL; | |
| 349 const UcxList *src = left; | |
| 350 | |
| 351 do { | |
| 352 UCX_FOREACH(node, src) { | |
| 353 void* elem = node->data; | |
| 354 if ( | |
| 355 (op == 0 && !ucx_list_contains(res, elem, cmpfnc, cmpdata)) || | |
| 356 (op == 1 && ucx_list_contains(right, elem, cmpfnc, cmpdata)) || | |
| 357 (op == 2 && !ucx_list_contains(right, elem, cmpfnc, cmpdata))) { | |
| 358 UcxList *nl = almalloc(allocator, sizeof(UcxList)); | |
| 359 nl->prev = cur; | |
| 360 nl->next = NULL; | |
| 361 if (cpfnc) { | |
| 362 nl->data = cpfnc(elem, cpdata); | |
| 363 } else { | |
| 364 nl->data = elem; | |
| 365 } | |
| 366 if (cur != NULL) | |
| 367 cur->next = nl; | |
| 368 cur = nl; | |
| 369 if (res == NULL) | |
| 370 res = cur; | |
| 371 } | |
| 372 } | |
| 373 if (op == 0 && src == left) | |
| 374 src = right; | |
| 375 else | |
| 376 src = NULL; | |
| 377 } while (src != NULL); | |
| 378 | |
| 379 return res; | |
| 380 } | |
| 381 | |
| 382 UcxList* ucx_list_union(UcxList const *left, UcxList const *right, | |
| 383 cmp_func cmpfnc, void* cmpdata, | |
| 384 copy_func cpfnc, void* cpdata) { | |
| 385 return ucx_list_union_a(ucx_default_allocator(), | |
| 386 left, right, cmpfnc, cmpdata, cpfnc, cpdata); | |
| 387 } | |
| 388 | |
| 389 UcxList* ucx_list_union_a(UcxAllocator *allocator, | |
| 390 UcxList const *left, UcxList const *right, | |
| 391 cmp_func cmpfnc, void* cmpdata, | |
| 392 copy_func cpfnc, void* cpdata) { | |
| 393 | |
| 394 return ucx_list_setoperation_a(allocator, left, right, | |
| 395 cmpfnc, cmpdata, cpfnc, cpdata, 0); | |
| 396 } | |
| 397 | |
| 398 UcxList* ucx_list_intersection(UcxList const *left, UcxList const *right, | |
| 399 cmp_func cmpfnc, void* cmpdata, | |
| 400 copy_func cpfnc, void* cpdata) { | |
| 401 return ucx_list_intersection_a(ucx_default_allocator(), left, right, | |
| 402 cmpfnc, cmpdata, cpfnc, cpdata); | |
| 403 } | |
| 404 | |
| 405 UcxList* ucx_list_intersection_a(UcxAllocator *allocator, | |
| 406 UcxList const *left, UcxList const *right, | |
| 407 cmp_func cmpfnc, void* cmpdata, | |
| 408 copy_func cpfnc, void* cpdata) { | |
| 409 | |
| 410 return ucx_list_setoperation_a(allocator, left, right, | |
| 411 cmpfnc, cmpdata, cpfnc, cpdata, 1); | |
| 412 } | |
| 413 | |
| 414 UcxList* ucx_list_difference(UcxList const *left, UcxList const *right, | |
| 415 cmp_func cmpfnc, void* cmpdata, | |
| 416 copy_func cpfnc, void* cpdata) { | |
| 417 return ucx_list_difference_a(ucx_default_allocator(), left, right, | |
| 418 cmpfnc, cmpdata, cpfnc, cpdata); | |
| 419 } | |
| 420 | |
| 421 UcxList* ucx_list_difference_a(UcxAllocator *allocator, | |
| 422 UcxList const *left, UcxList const *right, | |
| 423 cmp_func cmpfnc, void* cmpdata, | |
| 424 copy_func cpfnc, void* cpdata) { | |
| 425 | |
| 426 return ucx_list_setoperation_a(allocator, left, right, | |
| 427 cmpfnc, cmpdata, cpfnc, cpdata, 2); | |
| 428 } |
