Mercurial > hg > dav / file comparison

comparison: ucx/array_list.c

ucx/array_list.c

changeset 888
af685cc9d623
parent 854
1c8401ece69e
equal deleted inserted replaced
877:b60487c3ec36 888:af685cc9d623
34 34
35 // Default array reallocator 35 // Default array reallocator
36 36
37 static void *cx_array_default_realloc( 37 static void *cx_array_default_realloc(
38 void *array, 38 void *array,
39 size_t capacity, 39 cx_attr_unused size_t old_capacity,
40 size_t new_capacity,
40 size_t elem_size, 41 size_t elem_size,
41 cx_attr_unused CxArrayReallocator *alloc 42 cx_attr_unused CxArrayReallocator *alloc
42 ) { 43 ) {
43 size_t n; 44 size_t n;
44 if (cx_szmul(capacity, elem_size, &n)) { 45 if (cx_szmul(new_capacity, elem_size, &n)) {
45 errno = EOVERFLOW; 46 errno = EOVERFLOW;
46 return NULL; 47 return NULL;
47 } 48 }
48 return realloc(array, n); 49 return cxReallocDefault(array, n);
49 } 50 }
50 51
51 CxArrayReallocator cx_array_default_reallocator_impl = { 52 CxArrayReallocator cx_array_default_reallocator_impl = {
52 cx_array_default_realloc, NULL, NULL, 0, 0 53 cx_array_default_realloc, NULL, NULL
53 }; 54 };
54 55
55 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl; 56 CxArrayReallocator *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
56 57
57 // Stack-aware array reallocator 58 // Stack-aware array reallocator
58 59
59 static void *cx_array_advanced_realloc( 60 static void *cx_array_advanced_realloc(
60 void *array, 61 void *array,
61 size_t capacity, 62 size_t old_capacity,
63 size_t new_capacity,
62 size_t elem_size, 64 size_t elem_size,
63 cx_attr_unused CxArrayReallocator *alloc 65 cx_attr_unused CxArrayReallocator *alloc
64 ) { 66 ) {
65 // check for overflow 67 // check for overflow
66 size_t n; 68 size_t n;
67 if (cx_szmul(capacity, elem_size, &n)) { 69 if (cx_szmul(new_capacity, elem_size, &n)) {
68 errno = EOVERFLOW; 70 errno = EOVERFLOW;
69 return NULL; 71 return NULL;
70 } 72 }
71 73
72 // retrieve the pointer to the actual allocator 74 // retrieve the pointer to the actual allocator
73 const CxAllocator *al = alloc->ptr1; 75 const CxAllocator *al = alloc->allocator;
74 76
75 // check if the array is still located on the stack 77 // check if the array is still located on the stack
76 void *newmem; 78 void *newmem;
77 if (array == alloc->ptr2) { 79 if (array == alloc->stack_ptr) {
78 newmem = cxMalloc(al, n); 80 newmem = cxMalloc(al, n);
79 if (newmem != NULL && array != NULL) { 81 if (newmem != NULL && array != NULL) {
80 memcpy(newmem, array, n); 82 memcpy(newmem, array, old_capacity*elem_size);
81 } 83 }
82 } else { 84 } else {
83 newmem = cxRealloc(al, array, n); 85 newmem = cxRealloc(al, array, n);
84 } 86 }
85 return newmem; 87 return newmem;
86 } 88 }
87 89
88 struct cx_array_reallocator_s cx_array_reallocator( 90 struct cx_array_reallocator_s cx_array_reallocator(
89 const struct cx_allocator_s *allocator, 91 const struct cx_allocator_s *allocator,
90 const void *stackmem 92 const void *stack_ptr
91 ) { 93 ) {
92 if (allocator == NULL) { 94 if (allocator == NULL) {
93 allocator = cxDefaultAllocator; 95 allocator = cxDefaultAllocator;
94 } 96 }
95 return (struct cx_array_reallocator_s) { 97 return (struct cx_array_reallocator_s) {
96 cx_array_advanced_realloc, 98 cx_array_advanced_realloc,
97 (void*) allocator, (void*) stackmem, 99 allocator, stack_ptr,
98 0, 0
99 }; 100 };
100 } 101 }
101 102
102 // LOW LEVEL ARRAY LIST FUNCTIONS 103 // LOW LEVEL ARRAY LIST FUNCTIONS
103 104
105 /**
106 * Increases the capacity until it is a multiple of a some alignment or reaches the maximum.
107 *
108 * @param cap the required capacity (must not be larger than @p max)
109 * @param alignment the alignment
110 * @param max the maximum capacity
111 * @return the aligned capacity
112 */
104 static size_t cx_array_align_capacity( 113 static size_t cx_array_align_capacity(
105 size_t cap, 114 size_t cap,
106 size_t alignment, 115 size_t alignment,
107 size_t max 116 size_t max
108 ) { 117 ) {
178 // calculate new capacity (next number divisible by 16) 187 // calculate new capacity (next number divisible by 16)
179 newcap = cx_array_align_capacity(newcap, 16, max_size); 188 newcap = cx_array_align_capacity(newcap, 16, max_size);
180 189
181 // perform reallocation 190 // perform reallocation
182 void *newmem = reallocator->realloc( 191 void *newmem = reallocator->realloc(
183 *array, newcap, elem_size, reallocator 192 *array, oldcap, newcap, elem_size, reallocator
184 ); 193 );
185 if (newmem == NULL) { 194 if (newmem == NULL) {
186 return 1; // LCOV_EXCL_LINE 195 return 1; // LCOV_EXCL_LINE
187 } 196 }
188 197
284 newcap = cx_array_align_capacity(newsize, 16, max_size); 293 newcap = cx_array_align_capacity(newsize, 16, max_size);
285 assert(newcap > newsize); 294 assert(newcap > newsize);
286 295
287 // perform reallocation 296 // perform reallocation
288 void *newmem = reallocator->realloc( 297 void *newmem = reallocator->realloc(
289 *target, newcap, elem_size, reallocator 298 *target, oldcap, newcap, elem_size, reallocator
290 ); 299 );
291 if (newmem == NULL) { 300 if (newmem == NULL) {
292 return 1; 301 return 1; // LCOV_EXCL_LINE
293 } 302 }
294 303
295 // repair src pointer, if necessary 304 // repair src pointer, if necessary
296 if (repairsrc) { 305 if (repairsrc) {
297 src = ((char *) newmem) + (srcaddr - targetaddr); 306 src = ((char *) newmem) + (srcaddr - targetaddr);
331 340
332 // return successfully 341 // return successfully
333 return 0; 342 return 0;
334 } 343 }
335 344
336 int cx_array_insert_sorted( 345 static int cx_array_insert_sorted_impl(
337 void **target, 346 void **target,
338 size_t *size, 347 size_t *size,
339 size_t *capacity, 348 size_t *capacity,
340 cx_compare_func cmp_func, 349 cx_compare_func cmp_func,
341 const void *sorted_data, 350 const void *sorted_data,
342 size_t elem_size, 351 size_t elem_size,
343 size_t elem_count, 352 size_t elem_count,
344 CxArrayReallocator *reallocator 353 CxArrayReallocator *reallocator,
354 bool allow_duplicates
345 ) { 355 ) {
346 // assert pointers 356 // assert pointers
347 assert(target != NULL); 357 assert(target != NULL);
348 assert(size != NULL); 358 assert(size != NULL);
349 assert(capacity != NULL); 359 assert(capacity != NULL);
364 return 1; 374 return 1;
365 } 375 }
366 376
367 // store some counts 377 // store some counts
368 size_t old_size = *size; 378 size_t old_size = *size;
379 size_t old_capacity = *capacity;
380 // the necessary capacity is the worst case assumption, including duplicates
369 size_t needed_capacity = old_size + elem_count; 381 size_t needed_capacity = old_size + elem_count;
370 382
371 // if we need more than we have, try a reallocation 383 // if we need more than we have, try a reallocation
372 if (needed_capacity > *capacity) { 384 if (needed_capacity > old_capacity) {
373 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX); 385 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
374 void *new_mem = reallocator->realloc( 386 void *new_mem = reallocator->realloc(
375 *target, new_capacity, elem_size, reallocator 387 *target, old_capacity, new_capacity, elem_size, reallocator
376 ); 388 );
377 if (new_mem == NULL) { 389 if (new_mem == NULL) {
378 // give it up right away, there is no contract 390 // give it up right away, there is no contract
379 // that requires us to insert as much as we can 391 // that requires us to insert as much as we can
380 return 1; // LCOV_EXCL_LINE 392 return 1; // LCOV_EXCL_LINE
413 elem_count - si, 425 elem_count - si,
414 elem_size, 426 elem_size,
415 bptr, 427 bptr,
416 cmp_func 428 cmp_func
417 ); 429 );
430 // binary search gives us the smallest index;
431 // we also want to include equal elements here
432 while (si + copy_len < elem_count
433 && cmp_func(bptr, src+copy_len*elem_size) == 0) {
434 copy_len++;
435 }
418 436
419 // copy the source elements 437 // copy the source elements
420 bytes_copied = copy_len * elem_size; 438 if (copy_len > 0) {
421 memcpy(dest, src, bytes_copied); 439 if (allow_duplicates) {
422 dest += bytes_copied; 440 // we can copy the entire chunk
423 src += bytes_copied; 441 bytes_copied = copy_len * elem_size;
424 si += copy_len; 442 memcpy(dest, src, bytes_copied);
443 dest += bytes_copied;
444 src += bytes_copied;
445 si += copy_len;
446 di += copy_len;
447 } else {
448 // first, check the end of the source chunk
449 // for being a duplicate of the bptr
450 const char *end_of_src = src + (copy_len - 1) * elem_size;
451 size_t skip_len = 0;
452 while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) {
453 end_of_src -= elem_size;
454 skip_len++;
455 copy_len--;
456 }
457 char *last = dest == *target ? NULL : dest - elem_size;
458 // then iterate through the source chunk
459 // and skip all duplicates with the last element in the array
460 size_t more_skipped = 0;
461 for (unsigned j = 0; j < copy_len; j++) {
462 if (last != NULL && cmp_func(last, src) == 0) {
463 // duplicate - skip
464 src += elem_size;
465 si++;
466 more_skipped++;
467 } else {
468 memcpy(dest, src, elem_size);
469 src += elem_size;
470 last = dest;
471 dest += elem_size;
472 si++;
473 di++;
474 }
475 }
476 // skip the previously identified elements as well
477 src += skip_len * elem_size;
478 si += skip_len;
479 skip_len += more_skipped;
480 // reduce the actual size by the number of skipped elements
481 *size -= skip_len;
482 }
483 }
425 484
426 // when all source elements are in place, we are done 485 // when all source elements are in place, we are done
427 if (si >= elem_count) break; 486 if (si >= elem_count) break;
428 487
429 // determine how many buffered elements need to be restored 488 // determine how many buffered elements need to be restored
438 // restore the buffered elements 497 // restore the buffered elements
439 bytes_copied = copy_len * elem_size; 498 bytes_copied = copy_len * elem_size;
440 memmove(dest, bptr, bytes_copied); 499 memmove(dest, bptr, bytes_copied);
441 dest += bytes_copied; 500 dest += bytes_copied;
442 bptr += bytes_copied; 501 bptr += bytes_copied;
502 di += copy_len;
443 bi += copy_len; 503 bi += copy_len;
444 } 504 }
445 505
446 // still source elements left? simply append them 506 // still source elements left?
447 if (si < elem_count) { 507 if (si < elem_count) {
448 memcpy(dest, src, elem_size * (elem_count - si)); 508 if (allow_duplicates) {
449 } 509 // duplicates allowed or nothing inserted yet: simply copy everything
450 510 memcpy(dest, src, elem_size * (elem_count - si));
451 // still buffer elements left? 511 } else {
452 // don't worry, we already moved them to the correct place 512 if (dest != *target) {
513 // skip all source elements that equal the last element
514 char *last = dest - elem_size;
515 while (si < elem_count) {
516 if (last != NULL && cmp_func(last, src) == 0) {
517 src += elem_size;
518 si++;
519 (*size)--;
520 } else {
521 break;
522 }
523 }
524 }
525 // we must check the elements in the chunk one by one
526 while (si < elem_count) {
527 // find a chain of elements that can be copied
528 size_t copy_len = 1, skip_len = 0;
529 {
530 const char *left_src = src;
531 while (si + copy_len < elem_count) {
532 const char *right_src = left_src + elem_size;
533 int d = cmp_func(left_src, right_src);
534 if (d < 0) {
535 if (skip_len > 0) {
536 // new larger element found;
537 // handle it in the next cycle
538 break;
539 }
540 left_src += elem_size;
541 copy_len++;
542 } else if (d == 0) {
543 left_src += elem_size;
544 skip_len++;
545 } else {
546 break;
547 }
548 }
549 }
550 size_t bytes_copied = copy_len * elem_size;
551 memcpy(dest, src, bytes_copied);
552 dest += bytes_copied;
553 src += bytes_copied + skip_len * elem_size;
554 si += copy_len + skip_len;
555 di += copy_len;
556 *size -= skip_len;
557 }
558 }
559 }
560
561 // buffered elements need to be moved when we skipped duplicates
562 size_t total_skipped = new_size - *size;
563 if (bi < new_size && total_skipped > 0) {
564 // move the remaining buffer to the end of the array
565 memmove(dest, bptr, elem_size * (new_size - bi));
566 }
453 567
454 return 0; 568 return 0;
569 }
570
571 int cx_array_insert_sorted(
572 void **target,
573 size_t *size,
574 size_t *capacity,
575 cx_compare_func cmp_func,
576 const void *sorted_data,
577 size_t elem_size,
578 size_t elem_count,
579 CxArrayReallocator *reallocator
580 ) {
581 return cx_array_insert_sorted_impl(target, size, capacity,
582 cmp_func, sorted_data, elem_size, elem_count, reallocator, true);
583 }
584
585 int cx_array_insert_unique(
586 void **target,
587 size_t *size,
588 size_t *capacity,
589 cx_compare_func cmp_func,
590 const void *sorted_data,
591 size_t elem_size,
592 size_t elem_count,
593 CxArrayReallocator *reallocator
594 ) {
595 return cx_array_insert_sorted_impl(target, size, capacity,
596 cmp_func, sorted_data, elem_size, elem_count, reallocator, false);
455 } 597 }
456 598
457 size_t cx_array_binary_search_inf( 599 size_t cx_array_binary_search_inf(
458 const void *arr, 600 const void *arr,
459 size_t size, 601 size_t size,
497 pivot_index = left_index + (right_index - left_index) / 2; 639 pivot_index = left_index + (right_index - left_index) / 2;
498 const char *arr_elem = array + pivot_index * elem_size; 640 const char *arr_elem = array + pivot_index * elem_size;
499 result = cmp_func(elem, arr_elem); 641 result = cmp_func(elem, arr_elem);
500 if (result == 0) { 642 if (result == 0) {
501 // found it! 643 // found it!
644 // check previous elements;
645 // when they are equal, report the smallest index
646 arr_elem -= elem_size;
647 while (pivot_index > 0 && cmp_func(elem, arr_elem) == 0) {
648 pivot_index--;
649 arr_elem -= elem_size;
650 }
502 return pivot_index; 651 return pivot_index;
503 } else if (result < 0) { 652 } else if (result < 0) {
504 // element is smaller than pivot, continue search left 653 // element is smaller than pivot, continue search left
505 right_index = pivot_index - 1; 654 right_index = pivot_index - 1;
506 } else { 655 } else {
570 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE]; 719 char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
571 void *tmp; 720 void *tmp;
572 721
573 // decide if we can use the local buffer 722 // decide if we can use the local buffer
574 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) { 723 if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
575 tmp = malloc(elem_size); 724 tmp = cxMallocDefault(elem_size);
576 // we don't want to enforce error handling 725 // we don't want to enforce error handling
577 if (tmp == NULL) abort(); 726 if (tmp == NULL) abort();
578 } else { 727 } else {
579 tmp = sbo_mem; 728 tmp = sbo_mem;
580 } 729 }
589 memcpy(left, right, elem_size); 738 memcpy(left, right, elem_size);
590 memcpy(right, tmp, elem_size); 739 memcpy(right, tmp, elem_size);
591 740
592 // free dynamic memory, if it was needed 741 // free dynamic memory, if it was needed
593 if (tmp != sbo_mem) { 742 if (tmp != sbo_mem) {
594 free(tmp); 743 cxFreeDefault(tmp);
595 } 744 }
596 } 745 }
597 746
598 // HIGH LEVEL ARRAY LIST FUNCTIONS 747 // HIGH LEVEL ARRAY LIST FUNCTIONS
599 748
636 if (index > list->collection.size || n == 0) return 0; 785 if (index > list->collection.size || n == 0) return 0;
637 786
638 // get a correctly typed pointer to the list 787 // get a correctly typed pointer to the list
639 cx_array_list *arl = (cx_array_list *) list; 788 cx_array_list *arl = (cx_array_list *) list;
640 789
790 // guarantee enough capacity
791 if (arl->capacity < list->collection.size + n) {
792 size_t new_capacity = list->collection.size + n;
793 new_capacity = cx_array_align_capacity(new_capacity, 16, SIZE_MAX);
794 if (cxReallocateArray(
795 list->collection.allocator,
796 &arl->data, new_capacity,
797 list->collection.elem_size)
798 ) {
799 return 0;
800 }
801 arl->capacity = new_capacity;
802 }
803
804 // determine insert position
805 char *arl_data = arl->data;
806 char *insert_pos = arl_data + index * list->collection.elem_size;
807
641 // do we need to move some elements? 808 // do we need to move some elements?
642 if (index < list->collection.size) { 809 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; 810 size_t elems_to_move = list->collection.size - index;
646 size_t start_of_moved = index + n; 811 char *target = insert_pos + n * list->collection.elem_size;
647 812 memmove(target, insert_pos, elems_to_move * list->collection.elem_size);
648 if (cx_array_copy( 813 }
649 &arl->data, 814
650 &list->collection.size, 815 // place the new elements, if any
651 &arl->capacity, 816 if (array != NULL) {
652 0, 817 memcpy(insert_pos, array, n * list->collection.elem_size);
653 start_of_moved, 818 }
654 first_to_move, 819 list->collection.size += n;
655 list->collection.elem_size, 820
656 elems_to_move, 821 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 } 822 }
686 823
687 static size_t cx_arl_insert_sorted( 824 static size_t cx_arl_insert_sorted(
688 struct cx_list_s *list, 825 struct cx_list_s *list,
689 const void *sorted_data, 826 const void *sorted_data,
707 } else { 844 } else {
708 return n; 845 return n;
709 } 846 }
710 } 847 }
711 848
712 static int cx_arl_insert_element( 849 static size_t cx_arl_insert_unique(
850 struct cx_list_s *list,
851 const void *sorted_data,
852 size_t n
853 ) {
854 // get a correctly typed pointer to the list
855 cx_array_list *arl = (cx_array_list *) list;
856
857 if (cx_array_insert_unique(
858 &arl->data,
859 &list->collection.size,
860 &arl->capacity,
861 list->collection.cmpfunc,
862 sorted_data,
863 list->collection.elem_size,
864 n,
865 &arl->reallocator
866 )) {
867 // array list implementation is "all or nothing"
868 return 0;
869 } else {
870 return n;
871 }
872 }
873
874 static void *cx_arl_insert_element(
713 struct cx_list_s *list, 875 struct cx_list_s *list,
714 size_t index, 876 size_t index,
715 const void *element 877 const void *element
716 ) { 878 ) {
717 return 1 != cx_arl_insert_array(list, index, element, 1); 879 if (cx_arl_insert_array(list, index, element, 1) == 1) {
880 return ((char*)((cx_array_list *) list)->data) + index * list->collection.elem_size;
881 } else {
882 return NULL;
883 }
718 } 884 }
719 885
720 static int cx_arl_insert_iter( 886 static int cx_arl_insert_iter(
721 struct cx_iterator_s *iter, 887 struct cx_iterator_s *iter,
722 const void *elem, 888 const void *elem,
723 int prepend 889 int prepend
724 ) { 890 ) {
725 struct cx_list_s *list = iter->src_handle.m; 891 struct cx_list_s *list = iter->src_handle;
726 if (iter->index < list->collection.size) { 892 if (iter->index < list->collection.size) {
727 int result = cx_arl_insert_element( 893 if (cx_arl_insert_element(list,
728 list, 894 iter->index + 1 - prepend, elem) == NULL) {
729 iter->index + 1 - prepend, 895 return 1;
730 elem 896 }
731 ); 897 iter->elem_count++;
732 if (result == 0) { 898 if (prepend != 0) {
733 iter->elem_count++; 899 iter->index++;
734 if (prepend != 0) { 900 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
735 iter->index++; 901 }
736 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size; 902 return 0;
737 } 903 } else {
738 } 904 if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) {
739 return result; 905 return 1;
740 } else { 906 }
741 int result = cx_arl_insert_element(list, list->collection.size, elem); 907 iter->elem_count++;
742 if (result == 0) { 908 iter->index = list->collection.size;
743 iter->elem_count++; 909 return 0;
744 iter->index = list->collection.size;
745 }
746 return result;
747 } 910 }
748 } 911 }
749 912
750 static size_t cx_arl_remove( 913 static size_t cx_arl_remove(
751 struct cx_list_s *list, 914 struct cx_list_s *list,
934 } 1097 }
935 } 1098 }
936 1099
937 static bool cx_arl_iter_valid(const void *it) { 1100 static bool cx_arl_iter_valid(const void *it) {
938 const struct cx_iterator_s *iter = it; 1101 const struct cx_iterator_s *iter = it;
939 const struct cx_list_s *list = iter->src_handle.c; 1102 const struct cx_list_s *list = iter->src_handle;
940 return iter->index < list->collection.size; 1103 return iter->index < list->collection.size;
941 } 1104 }
942 1105
943 static void *cx_arl_iter_current(const void *it) { 1106 static void *cx_arl_iter_current(const void *it) {
944 const struct cx_iterator_s *iter = it; 1107 const struct cx_iterator_s *iter = it;
947 1110
948 static void cx_arl_iter_next(void *it) { 1111 static void cx_arl_iter_next(void *it) {
949 struct cx_iterator_s *iter = it; 1112 struct cx_iterator_s *iter = it;
950 if (iter->base.remove) { 1113 if (iter->base.remove) {
951 iter->base.remove = false; 1114 iter->base.remove = false;
952 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL); 1115 cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
1116 iter->elem_count--;
953 } else { 1117 } else {
954 iter->index++; 1118 iter->index++;
955 iter->elem_handle = 1119 iter->elem_handle =
956 ((char *) iter->elem_handle) 1120 ((char *) iter->elem_handle)
957 + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size; 1121 + ((const struct cx_list_s *) iter->src_handle)->collection.elem_size;
958 } 1122 }
959 } 1123 }
960 1124
961 static void cx_arl_iter_prev(void *it) { 1125 static void cx_arl_iter_prev(void *it) {
962 struct cx_iterator_s *iter = it; 1126 struct cx_iterator_s *iter = it;
963 const cx_array_list *list = iter->src_handle.c;
964 if (iter->base.remove) { 1127 if (iter->base.remove) {
965 iter->base.remove = false; 1128 iter->base.remove = false;
966 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL); 1129 cx_arl_remove(iter->src_handle, iter->index, 1, NULL);
1130 iter->elem_count--;
967 } 1131 }
968 iter->index--; 1132 iter->index--;
1133 cx_array_list *list = iter->src_handle;
969 if (iter->index < list->base.collection.size) { 1134 if (iter->index < list->base.collection.size) {
970 iter->elem_handle = ((char *) list->data) 1135 iter->elem_handle = ((char *) list->data)
971 + iter->index * list->base.collection.elem_size; 1136 + iter->index * list->base.collection.elem_size;
972 } 1137 }
973 } 1138 }
979 bool backwards 1144 bool backwards
980 ) { 1145 ) {
981 struct cx_iterator_s iter; 1146 struct cx_iterator_s iter;
982 1147
983 iter.index = index; 1148 iter.index = index;
984 iter.src_handle.c = list; 1149 iter.src_handle = (void*)list;
985 iter.elem_handle = cx_arl_at(list, index); 1150 iter.elem_handle = cx_arl_at(list, index);
986 iter.elem_size = list->collection.elem_size; 1151 iter.elem_size = list->collection.elem_size;
987 iter.elem_count = list->collection.size; 1152 iter.elem_count = list->collection.size;
988 iter.base.valid = cx_arl_iter_valid; 1153 iter.base.valid = cx_arl_iter_valid;
989 iter.base.current = cx_arl_iter_current; 1154 iter.base.current = cx_arl_iter_current;
990 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; 1155 iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
991 iter.base.remove = false; 1156 iter.base.remove = false;
992 iter.base.mutating = false; 1157 iter.base.allow_remove = true;
993 1158
994 return iter; 1159 return iter;
995 } 1160 }
996 1161
997 static cx_list_class cx_array_list_class = { 1162 static cx_list_class cx_array_list_class = {
998 cx_arl_destructor, 1163 cx_arl_destructor,
999 cx_arl_insert_element, 1164 cx_arl_insert_element,
1000 cx_arl_insert_array, 1165 cx_arl_insert_array,
1001 cx_arl_insert_sorted, 1166 cx_arl_insert_sorted,
1167 cx_arl_insert_unique,
1002 cx_arl_insert_iter, 1168 cx_arl_insert_iter,
1003 cx_arl_remove, 1169 cx_arl_remove,
1004 cx_arl_clear, 1170 cx_arl_clear,
1005 cx_arl_swap, 1171 cx_arl_swap,
1006 cx_arl_at, 1172 cx_arl_at,

Mercurial Repository: dav

mercurial