comparison: src/array_list.c
src/array_list.c
- changeset 1316
- c41538edfcef
- parent 1163
- 68ff0839bc6a
- child 1318
- 12fa1d37fe48
equal
deleted
inserted
replaced
| 1315:b4c3e0b4c3d5 | 1316:c41538edfcef |
|---|---|
| 636 if (index > list->collection.size || n == 0) return 0; | 636 if (index > list->collection.size || n == 0) return 0; |
| 637 | 637 |
| 638 // get a correctly typed pointer to the list | 638 // get a correctly typed pointer to the list |
| 639 cx_array_list *arl = (cx_array_list *) list; | 639 cx_array_list *arl = (cx_array_list *) list; |
| 640 | 640 |
| 641 // guarantee enough capacity | |
| 642 if (arl->capacity < list->collection.size + n) { | |
| 643 size_t new_capacity = list->collection.size + n; | |
| 644 new_capacity = new_capacity - (new_capacity % 16) + 16; | |
| 645 if (cxReallocateArray( | |
| 646 list->collection.allocator, | |
| 647 &arl->data, new_capacity, | |
| 648 list->collection.elem_size) | |
| 649 ) { | |
| 650 return 0; | |
| 651 } | |
| 652 arl->capacity = new_capacity; | |
| 653 } | |
| 654 | |
| 655 // determine insert position | |
| 656 char *arl_data = arl->data; | |
| 657 char *insert_pos = arl_data + index * list->collection.elem_size; | |
| 658 | |
| 641 // do we need to move some elements? | 659 // do we need to move some elements? |
| 642 if (index < list->collection.size) { | 660 if (index < list->collection.size) { |
| 643 const char *first_to_move = (const char *) arl->data; | |
| 644 first_to_move += index * list->collection.elem_size; | |
| 645 size_t elems_to_move = list->collection.size - index; | 661 size_t elems_to_move = list->collection.size - index; |
| 646 size_t start_of_moved = index + n; | 662 char *target = insert_pos + n * list->collection.elem_size; |
| 647 | 663 memmove(target, insert_pos, elems_to_move * list->collection.elem_size); |
| 648 if (cx_array_copy( | 664 } |
| 649 &arl->data, | 665 |
| 650 &list->collection.size, | 666 // place the new elements, if any |
| 651 &arl->capacity, | 667 if (array != NULL) { |
| 652 0, | 668 memcpy(insert_pos, array, n * list->collection.elem_size); |
| 653 start_of_moved, | 669 } |
| 654 first_to_move, | 670 list->collection.size += n; |
| 655 list->collection.elem_size, | 671 |
| 656 elems_to_move, | 672 return n; |
| 657 &arl->reallocator | |
| 658 )) { | |
| 659 // if moving existing elems is unsuccessful, abort | |
| 660 return 0; | |
| 661 } | |
| 662 } | |
| 663 | |
| 664 // note that if we had to move the elements, the following operation | |
| 665 // is guaranteed to succeed, because we have the memory already allocated | |
| 666 // therefore, it is impossible to leave this function with an invalid array | |
| 667 | |
| 668 // place the new elements | |
| 669 if (cx_array_copy( | |
| 670 &arl->data, | |
| 671 &list->collection.size, | |
| 672 &arl->capacity, | |
| 673 0, | |
| 674 index, | |
| 675 array, | |
| 676 list->collection.elem_size, | |
| 677 n, | |
| 678 &arl->reallocator | |
| 679 )) { | |
| 680 // array list implementation is "all or nothing" | |
| 681 return 0; | |
| 682 } else { | |
| 683 return n; | |
| 684 } | |
| 685 } | 673 } |
| 686 | 674 |
| 687 static size_t cx_arl_insert_sorted( | 675 static size_t cx_arl_insert_sorted( |
| 688 struct cx_list_s *list, | 676 struct cx_list_s *list, |
| 689 const void *sorted_data, | 677 const void *sorted_data, |
| 707 } else { | 695 } else { |
| 708 return n; | 696 return n; |
| 709 } | 697 } |
| 710 } | 698 } |
| 711 | 699 |
| 712 static int cx_arl_insert_element( | 700 static void *cx_arl_insert_element( |
| 713 struct cx_list_s *list, | 701 struct cx_list_s *list, |
| 714 size_t index, | 702 size_t index, |
| 715 const void *element | 703 const void *element |
| 716 ) { | 704 ) { |
| 717 return 1 != cx_arl_insert_array(list, index, element, 1); | 705 if (cx_arl_insert_array(list, index, element, 1) == 1) { |
| 706 return ((char*)((cx_array_list *) list)->data) + index * list->collection.elem_size; | |
| 707 } else { | |
| 708 return NULL; | |
| 709 } | |
| 718 } | 710 } |
| 719 | 711 |
| 720 static int cx_arl_insert_iter( | 712 static int cx_arl_insert_iter( |
| 721 struct cx_iterator_s *iter, | 713 struct cx_iterator_s *iter, |
| 722 const void *elem, | 714 const void *elem, |
| 723 int prepend | 715 int prepend |
| 724 ) { | 716 ) { |
| 725 struct cx_list_s *list = iter->src_handle.m; | 717 struct cx_list_s *list = iter->src_handle.m; |
| 726 if (iter->index < list->collection.size) { | 718 if (iter->index < list->collection.size) { |
| 727 int result = cx_arl_insert_element( | 719 if (cx_arl_insert_element(list, |
| 728 list, | 720 iter->index + 1 - prepend, elem) == NULL) { |
| 729 iter->index + 1 - prepend, | 721 return 1; |
| 730 elem | 722 } |
| 731 ); | 723 iter->elem_count++; |
| 732 if (result == 0) { | 724 if (prepend != 0) { |
| 733 iter->elem_count++; | 725 iter->index++; |
| 734 if (prepend != 0) { | 726 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; |
| 735 iter->index++; | 727 } |
| 736 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; | 728 return 0; |
| 737 } | 729 } else { |
| 738 } | 730 if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) { |
| 739 return result; | 731 return 1; |
| 740 } else { | 732 } |
| 741 int result = cx_arl_insert_element(list, list->collection.size, elem); | 733 iter->elem_count++; |
| 742 if (result == 0) { | 734 iter->index = list->collection.size; |
| 743 iter->elem_count++; | 735 return 0; |
| 744 iter->index = list->collection.size; | |
| 745 } | |
| 746 return result; | |
| 747 } | 736 } |
| 748 } | 737 } |
| 749 | 738 |
| 750 static size_t cx_arl_remove( | 739 static size_t cx_arl_remove( |
| 751 struct cx_list_s *list, | 740 struct cx_list_s *list, |
