comparison: src/linked_list.c
src/linked_list.c
- changeset 919
- 75da57d4634e
- parent 890
- 54565fd74e74
equal
deleted
inserted
replaced
| 918:ec1f2015ec79 | 919:75da57d4634e |
|---|---|
| 89 const void *node = start; | 89 const void *node = start; |
| 90 ssize_t index = 0; | 90 ssize_t index = 0; |
| 91 do { | 91 do { |
| 92 void *current = ll_data(node); | 92 void *current = ll_data(node); |
| 93 if (cmp_func(current, elem) == 0) { | 93 if (cmp_func(current, elem) == 0) { |
| 94 *result = (void*) node; | 94 *result = (void *) node; |
| 95 return index; | 95 return index; |
| 96 } | 96 } |
| 97 node = ll_advance(node); | 97 node = ll_advance(node); |
| 98 index++; | 98 index++; |
| 99 } while (node != NULL); | 99 } while (node != NULL); |
| 334 *end = cx_linked_list_last( | 334 *end = cx_linked_list_last( |
| 335 dest != NULL ? dest : dest_prev, loc_next); | 335 dest != NULL ? dest : dest_prev, loc_next); |
| 336 } | 336 } |
| 337 } | 337 } |
| 338 | 338 |
| 339 void cx_linked_list_remove( | 339 size_t cx_linked_list_remove_chain( |
| 340 void **begin, | 340 void **begin, |
| 341 void **end, | 341 void **end, |
| 342 ptrdiff_t loc_prev, | 342 ptrdiff_t loc_prev, |
| 343 ptrdiff_t loc_next, | 343 ptrdiff_t loc_next, |
| 344 void *node | 344 void *node, |
| 345 size_t num | |
| 345 ) { | 346 ) { |
| 346 assert(node != NULL); | 347 assert(node != NULL); |
| 347 assert(loc_next >= 0); | 348 assert(loc_next >= 0); |
| 348 assert(loc_prev >= 0 || begin != NULL); | 349 assert(loc_prev >= 0 || begin != NULL); |
| 349 | 350 |
| 351 // easy exit | |
| 352 if (num == 0) return 0; | |
| 353 | |
| 350 // find adjacent nodes | 354 // find adjacent nodes |
| 351 void *next = ll_next(node); | |
| 352 void *prev; | 355 void *prev; |
| 353 if (loc_prev >= 0) { | 356 if (loc_prev >= 0) { |
| 354 prev = ll_prev(node); | 357 prev = ll_prev(node); |
| 355 } else { | 358 } else { |
| 356 prev = cx_linked_list_prev(*begin, loc_next, node); | 359 prev = cx_linked_list_prev(*begin, loc_next, node); |
| 360 } | |
| 361 | |
| 362 void *next = ll_next(node); | |
| 363 size_t removed = 1; | |
| 364 for (; removed < num && next != NULL ; removed++) { | |
| 365 next = ll_next(next); | |
| 357 } | 366 } |
| 358 | 367 |
| 359 // update next pointer of prev node, or set begin | 368 // update next pointer of prev node, or set begin |
| 360 if (prev == NULL) { | 369 if (prev == NULL) { |
| 361 if (begin != NULL) { | 370 if (begin != NULL) { |
| 371 *end = prev; | 380 *end = prev; |
| 372 } | 381 } |
| 373 } else if (loc_prev >= 0) { | 382 } else if (loc_prev >= 0) { |
| 374 ll_prev(next) = prev; | 383 ll_prev(next) = prev; |
| 375 } | 384 } |
| 385 | |
| 386 return removed; | |
| 376 } | 387 } |
| 377 | 388 |
| 378 size_t cx_linked_list_size( | 389 size_t cx_linked_list_size( |
| 379 const void *node, | 390 const void *node, |
| 380 ptrdiff_t loc_next | 391 ptrdiff_t loc_next |
| 440 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); | 451 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); |
| 441 } | 452 } |
| 442 ll_next(sorted[length - 1]) = NULL; | 453 ll_next(sorted[length - 1]) = NULL; |
| 443 | 454 |
| 444 *begin = sorted[0]; | 455 *begin = sorted[0]; |
| 445 *end = sorted[length-1]; | 456 *end = sorted[length - 1]; |
| 446 if (sorted != sbo) { | 457 if (sorted != sbo) { |
| 447 free(sorted); | 458 free(sorted); |
| 448 } | 459 } |
| 449 } | 460 } |
| 450 | 461 |
| 731 list->collection.size += inserted; | 742 list->collection.size += inserted; |
| 732 | 743 |
| 733 return inserted; | 744 return inserted; |
| 734 } | 745 } |
| 735 | 746 |
| 736 static int cx_ll_remove( | 747 static size_t cx_ll_remove( |
| 737 struct cx_list_s *list, | 748 struct cx_list_s *list, |
| 738 size_t index | 749 size_t index, |
| 750 size_t num, | |
| 751 void *targetbuf | |
| 739 ) { | 752 ) { |
| 740 cx_linked_list *ll = (cx_linked_list *) list; | 753 cx_linked_list *ll = (cx_linked_list *) list; |
| 741 cx_linked_list_node *node = cx_ll_node_at(ll, index); | 754 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 742 | 755 |
| 743 // out-of-bounds check | 756 // out-of-bounds check |
| 744 if (node == NULL) return 1; | 757 if (node == NULL) return 0; |
| 745 | |
| 746 // element destruction | |
| 747 cx_invoke_destructor(list, node->payload); | |
| 748 | 758 |
| 749 // remove | 759 // remove |
| 750 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, | 760 size_t removed = cx_linked_list_remove_chain( |
| 751 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); | 761 (void **) &ll->begin, |
| 762 (void **) &ll->end, | |
| 763 CX_LL_LOC_PREV, | |
| 764 CX_LL_LOC_NEXT, | |
| 765 node, | |
| 766 num | |
| 767 ); | |
| 752 | 768 |
| 753 // adjust size | 769 // adjust size |
| 754 list->collection.size--; | 770 list->collection.size -= removed; |
| 755 | 771 |
| 756 // free and return | 772 // copy or destroy the removed chain |
| 757 cxFree(list->collection.allocator, node); | 773 if (targetbuf == NULL) { |
| 758 | 774 cx_linked_list_node *n = node; |
| 759 return 0; | 775 cx_for_n(i, removed) { |
| 776 // element destruction | |
| 777 cx_invoke_destructor(list, n->payload); | |
| 778 | |
| 779 // free the node | |
| 780 cxFree(list->collection.allocator, n); | |
| 781 | |
| 782 // next | |
| 783 n = n->next; | |
| 784 } | |
| 785 } else { | |
| 786 char *dest = targetbuf; | |
| 787 cx_linked_list_node *n = node; | |
| 788 cx_for_n(i, removed) { | |
| 789 // copy payload | |
| 790 memcpy(dest, n->payload, list->collection.elem_size); | |
| 791 | |
| 792 // advance target buffer | |
| 793 dest += list->collection.elem_size; | |
| 794 | |
| 795 // free the node | |
| 796 cxFree(list->collection.allocator, n); | |
| 797 | |
| 798 // next | |
| 799 n = n->next; | |
| 800 } | |
| 801 } | |
| 802 | |
| 803 return removed; | |
| 760 } | 804 } |
| 761 | 805 |
| 762 static void cx_ll_clear(struct cx_list_s *list) { | 806 static void cx_ll_clear(struct cx_list_s *list) { |
| 763 if (list->collection.size == 0) return; | 807 if (list->collection.size == 0) return; |
| 764 | 808 |
