comparison: src/linked_list.c
src/linked_list.c
- changeset 879
- 9c24a4eb5ac9
- parent 876
- f4ce7df9cff0
- child 880
- 54133f14043f
equal
deleted
inserted
replaced
| 878:1c1ee61c01f9 | 879:9c24a4eb5ac9 |
|---|---|
| 245 } else { | 245 } else { |
| 246 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); | 246 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); |
| 247 } | 247 } |
| 248 } | 248 } |
| 249 | 249 |
| 250 void cx_linked_list_insert_sorted( | |
| 251 void **begin, | |
| 252 void **end, | |
| 253 ptrdiff_t loc_prev, | |
| 254 ptrdiff_t loc_next, | |
| 255 void *new_node, | |
| 256 cx_compare_func cmp_func | |
| 257 ) { | |
| 258 assert(ll_next(new_node) == NULL); | |
| 259 cx_linked_list_insert_sorted_chain( | |
| 260 begin, end, loc_prev, loc_next, new_node, cmp_func); | |
| 261 } | |
| 262 | |
| 263 void cx_linked_list_insert_sorted_chain( | |
| 264 void **begin, | |
| 265 void **end, | |
| 266 ptrdiff_t loc_prev, | |
| 267 ptrdiff_t loc_next, | |
| 268 void *insert_begin, | |
| 269 cx_compare_func cmp_func | |
| 270 ) { | |
| 271 assert(begin != NULL); | |
| 272 assert(loc_next >= 0); | |
| 273 assert(insert_begin != NULL); | |
| 274 | |
| 275 // track currently observed nodes | |
| 276 void *dest_prev = NULL; | |
| 277 void *dest = *begin; | |
| 278 void *src = insert_begin; | |
| 279 | |
| 280 // special case: list is empty | |
| 281 if (dest == NULL) { | |
| 282 *begin = src; | |
| 283 if (end != NULL) { | |
| 284 *end = cx_linked_list_last(src, loc_next); | |
| 285 } | |
| 286 return; | |
| 287 } | |
| 288 | |
| 289 // search the list for insertion points | |
| 290 while (dest != NULL && src != NULL) { | |
| 291 // compare current list node with source node | |
| 292 // if less or equal, skip | |
| 293 if (cmp_func(dest, src) <= 0) { | |
| 294 dest_prev = dest; | |
| 295 dest = ll_next(dest); | |
| 296 continue; | |
| 297 } | |
| 298 | |
| 299 // determine chain of elements that can be inserted | |
| 300 void *end_of_chain = src; | |
| 301 void *next_in_chain = ll_next(src); | |
| 302 while (next_in_chain != NULL) { | |
| 303 // once we become larger than the list elem, break | |
| 304 if (cmp_func(dest, next_in_chain) <= 0) { | |
| 305 break; | |
| 306 } | |
| 307 // otherwise, we can insert one more | |
| 308 end_of_chain = next_in_chain; | |
| 309 next_in_chain = ll_next(next_in_chain); | |
| 310 } | |
| 311 | |
| 312 // insert the elements | |
| 313 if (dest_prev == NULL) { | |
| 314 // new begin | |
| 315 *begin = src; | |
| 316 } else { | |
| 317 cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | |
| 318 } | |
| 319 cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next); | |
| 320 | |
| 321 // continue with next | |
| 322 src = next_in_chain; | |
| 323 dest_prev = dest; | |
| 324 dest = ll_next(dest); | |
| 325 } | |
| 326 | |
| 327 // insert remaining items | |
| 328 if (src != NULL) { | |
| 329 cx_linked_list_link(dest_prev, src, loc_prev, loc_next); | |
| 330 } | |
| 331 | |
| 332 // determine new end of list, if requested | |
| 333 if (end != NULL) { | |
| 334 *end = cx_linked_list_last( | |
| 335 dest != NULL ? dest : dest_prev, loc_next); | |
| 336 } | |
| 337 } | |
| 338 | |
| 250 void cx_linked_list_remove( | 339 void cx_linked_list_remove( |
| 251 void **begin, | 340 void **begin, |
| 252 void **end, | 341 void **end, |
| 253 ptrdiff_t loc_prev, | 342 ptrdiff_t loc_prev, |
| 254 ptrdiff_t loc_next, | 343 ptrdiff_t loc_next, |
| 508 } else { | 597 } else { |
| 509 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); | 598 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); |
| 510 } | 599 } |
| 511 } | 600 } |
| 512 | 601 |
| 602 static cx_linked_list_node *cx_ll_malloc_node(struct cx_list_s const *list) { | |
| 603 return cxMalloc(list->collection.allocator, | |
| 604 sizeof(cx_linked_list_node) + list->collection.elem_size); | |
| 605 } | |
| 606 | |
| 513 static int cx_ll_insert_at( | 607 static int cx_ll_insert_at( |
| 514 struct cx_list_s *list, | 608 struct cx_list_s *list, |
| 515 cx_linked_list_node *node, | 609 cx_linked_list_node *node, |
| 516 void const *elem | 610 void const *elem |
| 517 ) { | 611 ) { |
| 518 | 612 |
| 519 // create the new new_node | 613 // create the new new_node |
| 520 cx_linked_list_node *new_node = cxMalloc(list->collection.allocator, | 614 cx_linked_list_node *new_node = cx_ll_malloc_node(list); |
| 521 sizeof(cx_linked_list_node) + list->collection.elem_size); | |
| 522 | 615 |
| 523 // sortir if failed | 616 // sortir if failed |
| 524 if (new_node == NULL) return 1; | 617 if (new_node == NULL) return 1; |
| 525 | 618 |
| 526 // initialize new new_node | 619 // initialize new new_node |
| 561 if (n == 1) return 1; | 654 if (n == 1) return 1; |
| 562 | 655 |
| 563 // we now know exactly where we are | 656 // we now know exactly where we are |
| 564 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; | 657 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; |
| 565 | 658 |
| 566 // we can add the remaining nodes and immedately advance to the inserted node | 659 // we can add the remaining nodes and immediately advance to the inserted node |
| 567 char const *source = array; | 660 char const *source = array; |
| 568 for (size_t i = 1; i < n; i++) { | 661 for (size_t i = 1; i < n; i++) { |
| 569 source += list->collection.elem_size; | 662 source += list->collection.elem_size; |
| 570 if (0 != cx_ll_insert_at(list, node, source)) { | 663 if (0 != cx_ll_insert_at(list, node, source)) { |
| 571 return i; | 664 return i; |
| 579 struct cx_list_s *list, | 672 struct cx_list_s *list, |
| 580 size_t index, | 673 size_t index, |
| 581 void const *element | 674 void const *element |
| 582 ) { | 675 ) { |
| 583 return 1 != cx_ll_insert_array(list, index, element, 1); | 676 return 1 != cx_ll_insert_array(list, index, element, 1); |
| 677 } | |
| 678 | |
| 679 static cx_compare_func cx_ll_insert_sorted_cmp_func; | |
| 680 | |
| 681 static int cx_ll_insert_sorted_cmp_helper(void const *l, void const *r) { | |
| 682 cx_linked_list_node const *left = l; | |
| 683 cx_linked_list_node const *right = r; | |
| 684 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload); | |
| 685 } | |
| 686 | |
| 687 static size_t cx_ll_insert_sorted( | |
| 688 struct cx_list_s *list, | |
| 689 void const *array, | |
| 690 size_t n | |
| 691 ) { | |
| 692 // special case | |
| 693 if (n == 0) return 0; | |
| 694 | |
| 695 // create a new chain of nodes | |
| 696 cx_linked_list_node *chain = cx_ll_malloc_node(list); | |
| 697 if (chain == NULL) return 0; | |
| 698 | |
| 699 memcpy(chain->payload, array, list->collection.elem_size); | |
| 700 chain->prev = NULL; | |
| 701 chain->next = NULL; | |
| 702 | |
| 703 // add all elements from the array to that chain | |
| 704 cx_linked_list_node *prev = chain; | |
| 705 char const *src = array; | |
| 706 size_t inserted = 1; | |
| 707 for (; inserted < n; inserted++) { | |
| 708 cx_linked_list_node *next = cx_ll_malloc_node(list); | |
| 709 if (next == NULL) break; | |
| 710 src += list->collection.elem_size; | |
| 711 memcpy(next->payload, src, list->collection.elem_size); | |
| 712 prev->next = next; | |
| 713 next->prev = prev; | |
| 714 prev = next; | |
| 715 } | |
| 716 prev->next = NULL; | |
| 717 | |
| 718 // invoke the low level function | |
| 719 cx_linked_list *ll = (cx_linked_list *) list; | |
| 720 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; | |
| 721 cx_linked_list_insert_sorted_chain( | |
| 722 (void **) &ll->begin, | |
| 723 (void **) &ll->end, | |
| 724 CX_LL_LOC_PREV, | |
| 725 CX_LL_LOC_NEXT, | |
| 726 chain, | |
| 727 cx_ll_insert_sorted_cmp_helper | |
| 728 ); | |
| 729 | |
| 730 // adjust the list metadata | |
| 731 list->collection.size += inserted; | |
| 732 | |
| 733 return inserted; | |
| 584 } | 734 } |
| 585 | 735 |
| 586 static int cx_ll_remove( | 736 static int cx_ll_remove( |
| 587 struct cx_list_s *list, | 737 struct cx_list_s *list, |
| 588 size_t index | 738 size_t index |
| 925 | 1075 |
| 926 static cx_list_class cx_linked_list_class = { | 1076 static cx_list_class cx_linked_list_class = { |
| 927 cx_ll_destructor, | 1077 cx_ll_destructor, |
| 928 cx_ll_insert_element, | 1078 cx_ll_insert_element, |
| 929 cx_ll_insert_array, | 1079 cx_ll_insert_array, |
| 930 cx_list_default_insert_sorted, | 1080 cx_ll_insert_sorted, |
| 931 cx_ll_insert_iter, | 1081 cx_ll_insert_iter, |
| 932 cx_ll_remove, | 1082 cx_ll_remove, |
| 933 cx_ll_clear, | 1083 cx_ll_clear, |
| 934 cx_ll_swap, | 1084 cx_ll_swap, |
| 935 cx_ll_at, | 1085 cx_ll_at, |
