comparison: src/linked_list.c
src/linked_list.c
- changeset 499
- 3dc9075df822
- parent 495
- 2856c74e18ba
- child 500
- eb9e7bd40a8e
equal
deleted
inserted
replaced
| 498:435c9965b2dd | 499:3dc9075df822 |
|---|---|
| 479 } else { | 479 } else { |
| 480 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); | 480 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); |
| 481 } | 481 } |
| 482 } | 482 } |
| 483 | 483 |
| 484 static int cx_ll_insert( | 484 static int cx_ll_insert_at( |
| 485 cx_list_s *list, | 485 cx_list_s *list, |
| 486 size_t index, | 486 cx_linked_list_node *node, |
| 487 void const *elem | 487 void const *elem |
| 488 ) { | 488 ) { |
| 489 // out-of bounds check | |
| 490 if (index > list->size) return 1; | |
| 491 | |
| 492 // cast a linked list pointer | |
| 493 cx_linked_list *ll = (cx_linked_list *) list; | |
| 494 | 489 |
| 495 // create the new new_node | 490 // create the new new_node |
| 496 cx_linked_list_node *new_node = cxMalloc(list->allocator, | 491 cx_linked_list_node *new_node = cxMalloc(list->allocator, |
| 497 sizeof(cx_linked_list_node) + list->itemsize); | 492 sizeof(cx_linked_list_node) + list->itemsize); |
| 498 | 493 |
| 501 | 496 |
| 502 // initialize new new_node | 497 // initialize new new_node |
| 503 new_node->prev = new_node->next = NULL; | 498 new_node->prev = new_node->next = NULL; |
| 504 memcpy(new_node->payload, elem, list->itemsize); | 499 memcpy(new_node->payload, elem, list->itemsize); |
| 505 | 500 |
| 506 // find position efficiently | |
| 507 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at(ll, index - 1); | |
| 508 | |
| 509 // insert | 501 // insert |
| 502 cx_linked_list *ll = (cx_linked_list *) list; | |
| 510 cx_linked_list_insert_chain( | 503 cx_linked_list_insert_chain( |
| 511 (void **) &ll->begin, (void **) &ll->end, | 504 (void **) &ll->begin, (void **) &ll->end, |
| 512 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, | 505 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, |
| 513 node, new_node, new_node | 506 node, new_node, new_node |
| 514 ); | 507 ); |
| 515 | 508 |
| 516 // increase the size and return | 509 // increase the size and return |
| 517 list->size++; | 510 list->size++; |
| 518 return 0; | 511 return 0; |
| 512 } | |
| 513 | |
| 514 static int cx_ll_insert( | |
| 515 cx_list_s *list, | |
| 516 size_t index, | |
| 517 void const *elem | |
| 518 ) { | |
| 519 // out-of bounds check | |
| 520 if (index > list->size) return 1; | |
| 521 | |
| 522 // find position efficiently | |
| 523 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); | |
| 524 | |
| 525 // perform insert | |
| 526 return cx_ll_insert_at(list, node, elem); | |
| 519 } | 527 } |
| 520 | 528 |
| 521 static int cx_ll_add( | 529 static int cx_ll_add( |
| 522 cx_list_s *list, | 530 cx_list_s *list, |
| 523 void const *elem | 531 void const *elem |
| 693 CxIterator iter = cx_ll_iterator(list, index); | 701 CxIterator iter = cx_ll_iterator(list, index); |
| 694 iter.current = cx_pll_iter_current; | 702 iter.current = cx_pll_iter_current; |
| 695 return iter; | 703 return iter; |
| 696 } | 704 } |
| 697 | 705 |
| 706 static int cx_ll_insert_iter( | |
| 707 CxIterator *iter, | |
| 708 void const *elem, | |
| 709 int prepend | |
| 710 ) { | |
| 711 cx_list_s *list = iter->src_handle; | |
| 712 cx_linked_list_node *node = iter->elem_handle; | |
| 713 if (node != NULL) { | |
| 714 assert(prepend >= 0 && prepend <= 1); | |
| 715 cx_linked_list_node *choice[2] = {node, node->prev}; | |
| 716 int result = cx_ll_insert_at(list, choice[prepend], elem); | |
| 717 iter->index += prepend * (0 == result); | |
| 718 return result; | |
| 719 } else { | |
| 720 int result = cx_ll_insert(list, list->size, elem); | |
| 721 iter->index = list->size; | |
| 722 return result; | |
| 723 } | |
| 724 } | |
| 725 | |
| 726 static int cx_pll_insert_iter( | |
| 727 CxIterator *iter, | |
| 728 void const *elem, | |
| 729 int prepend | |
| 730 ) { | |
| 731 return cx_ll_insert_iter(iter, &elem, prepend); | |
| 732 } | |
| 733 | |
| 698 static cx_list_class cx_linked_list_class = { | 734 static cx_list_class cx_linked_list_class = { |
| 699 cx_ll_add, | 735 cx_ll_add, |
| 700 cx_ll_insert, | 736 cx_ll_insert, |
| 737 cx_ll_insert_iter, | |
| 701 cx_ll_remove, | 738 cx_ll_remove, |
| 702 cx_ll_at, | 739 cx_ll_at, |
| 703 cx_ll_find, | 740 cx_ll_find, |
| 704 cx_ll_sort, | 741 cx_ll_sort, |
| 705 cx_ll_compare, | 742 cx_ll_compare, |
| 706 cx_ll_reverse, | 743 cx_ll_reverse, |
| 707 cx_ll_iterator, | 744 cx_ll_iterator |
| 708 }; | 745 }; |
| 709 | 746 |
| 710 static cx_list_class cx_pointer_linked_list_class = { | 747 static cx_list_class cx_pointer_linked_list_class = { |
| 711 cx_pll_add, | 748 cx_pll_add, |
| 712 cx_pll_insert, | 749 cx_pll_insert, |
| 750 cx_pll_insert_iter, | |
| 713 cx_ll_remove, | 751 cx_ll_remove, |
| 714 cx_pll_at, | 752 cx_pll_at, |
| 715 cx_pll_find, | 753 cx_pll_find, |
| 716 cx_pll_sort, | 754 cx_pll_sort, |
| 717 cx_pll_compare, | 755 cx_pll_compare, |
