Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 677
b09aae58bba4
parent 670
4ad8ea3aee49
child 699
35b2b99ee523
equal deleted inserted replaced
676:d0680a23d850 677:b09aae58bba4
58 58
59 size_t cx_linked_list_find( 59 size_t cx_linked_list_find(
60 void const *start, 60 void const *start,
61 ptrdiff_t loc_advance, 61 ptrdiff_t loc_advance,
62 ptrdiff_t loc_data, 62 ptrdiff_t loc_data,
63 CxListComparator cmp_func, 63 cx_compare_func cmp_func,
64 void const *elem 64 void const *elem
65 ) { 65 ) {
66 assert(start != NULL); 66 assert(start != NULL);
67 assert(loc_advance >= 0); 67 assert(loc_advance >= 0);
68 assert(loc_data >= 0); 68 assert(loc_data >= 0);
289 ptrdiff_t loc_data, 289 ptrdiff_t loc_data,
290 size_t length, 290 size_t length,
291 void *ls, 291 void *ls,
292 void *le, 292 void *le,
293 void *re, 293 void *re,
294 CxListComparator cmp_func 294 cx_compare_func cmp_func
295 ) { 295 ) {
296 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; 296 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
297 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? 297 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
298 malloc(sizeof(void *) * length) : sbo; 298 malloc(sizeof(void *) * length) : sbo;
299 if (sorted == NULL) abort(); 299 if (sorted == NULL) abort();
341 void **begin, 341 void **begin,
342 void **end, 342 void **end,
343 ptrdiff_t loc_prev, 343 ptrdiff_t loc_prev,
344 ptrdiff_t loc_next, 344 ptrdiff_t loc_next,
345 ptrdiff_t loc_data, 345 ptrdiff_t loc_data,
346 CxListComparator cmp_func 346 cx_compare_func cmp_func
347 ) { 347 ) {
348 assert(begin != NULL); 348 assert(begin != NULL);
349 assert(loc_next >= 0); 349 assert(loc_next >= 0);
350 assert(loc_data >= 0); 350 assert(loc_data >= 0);
351 assert(cmp_func); 351 assert(cmp_func);
401 int cx_linked_list_compare( 401 int cx_linked_list_compare(
402 void const *begin_left, 402 void const *begin_left,
403 void const *begin_right, 403 void const *begin_right,
404 ptrdiff_t loc_advance, 404 ptrdiff_t loc_advance,
405 ptrdiff_t loc_data, 405 ptrdiff_t loc_data,
406 CxListComparator cmp_func 406 cx_compare_func cmp_func
407 ) { 407 ) {
408 void const *left = begin_left, *right = begin_right; 408 void const *left = begin_left, *right = begin_right;
409 409
410 while (left != NULL && right != NULL) { 410 while (left != NULL && right != NULL) {
411 void const *left_data = ll_data(left); 411 void const *left_data = ll_data(left);
492 void const *elem 492 void const *elem
493 ) { 493 ) {
494 494
495 // create the new new_node 495 // create the new new_node
496 cx_linked_list_node *new_node = cxMalloc(list->allocator, 496 cx_linked_list_node *new_node = cxMalloc(list->allocator,
497 sizeof(cx_linked_list_node) + list->itemsize); 497 sizeof(cx_linked_list_node) + list->item_size);
498 498
499 // sortir if failed 499 // sortir if failed
500 if (new_node == NULL) return 1; 500 if (new_node == NULL) return 1;
501 501
502 // initialize new new_node 502 // initialize new new_node
503 new_node->prev = new_node->next = NULL; 503 new_node->prev = new_node->next = NULL;
504 memcpy(new_node->payload, elem, list->itemsize); 504 memcpy(new_node->payload, elem, list->item_size);
505 505
506 // insert 506 // insert
507 cx_linked_list *ll = (cx_linked_list *) list; 507 cx_linked_list *ll = (cx_linked_list *) list;
508 cx_linked_list_insert_chain( 508 cx_linked_list_insert_chain(
509 (void **) &ll->begin, (void **) &ll->end, 509 (void **) &ll->begin, (void **) &ll->end,
540 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 540 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
541 541
542 // we can add the remaining nodes and immedately advance to the inserted node 542 // we can add the remaining nodes and immedately advance to the inserted node
543 char const *source = array; 543 char const *source = array;
544 for (size_t i = 1; i < n; i++) { 544 for (size_t i = 1; i < n; i++) {
545 source += list->itemsize; 545 source += list->item_size;
546 if (0 != cx_ll_insert_at(list, node, source)) { 546 if (0 != cx_ll_insert_at(list, node, source)) {
547 return i; 547 return i;
548 } 548 }
549 node = node->next; 549 node = node->next;
550 } 550 }
568 568
569 // out-of-bounds check 569 // out-of-bounds check
570 if (node == NULL) return 1; 570 if (node == NULL) return 1;
571 571
572 // element destruction 572 // element destruction
573 if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { 573 cx_invoke_destructor(list, node->payload);
574 cx_list_invoke_destructor(list, node->payload);
575 }
576 574
577 // remove 575 // remove
578 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 576 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
579 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 577 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
580 578
590 static void cx_ll_clear(struct cx_list_s *list) { 588 static void cx_ll_clear(struct cx_list_s *list) {
591 if (list->size == 0) return; 589 if (list->size == 0) return;
592 590
593 cx_linked_list *ll = (cx_linked_list *) list; 591 cx_linked_list *ll = (cx_linked_list *) list;
594 cx_linked_list_node *node = ll->begin; 592 cx_linked_list_node *node = ll->begin;
595 593 while (node != NULL) {
596 // looks super redundant, but avoids repeatedly checking 594 cx_invoke_destructor(list, node->payload);
597 // the destructor type for each element 595 cx_linked_list_node *next = node->next;
598 switch (list->content_destructor_type) { 596 cxFree(list->allocator, node);
599 case CX_DESTRUCTOR_SIMPLE: { 597 node = next;
600 while (node != NULL) { 598 }
601 cx_list_invoke_simple_destructor(list, node->payload);
602 cx_linked_list_node *next = node->next;
603 cxFree(list->allocator, node);
604 node = next;
605 }
606 break;
607 }
608 case CX_DESTRUCTOR_ADVANCED: {
609 while (node != NULL) {
610 cx_list_invoke_advanced_destructor(list, node->payload);
611 cx_linked_list_node *next = node->next;
612 cxFree(list->allocator, node);
613 node = next;
614 }
615 break;
616 }
617 case CX_DESTRUCTOR_NONE: {
618 while (node != NULL) {
619 cx_linked_list_node *next = node->next;
620 cxFree(list->allocator, node);
621 node = next;
622 }
623 break;
624 }
625 }
626
627 ll->begin = ll->end = NULL; 599 ll->begin = ll->end = NULL;
628 list->size = 0; 600 list->size = 0;
629 } 601 }
630 602
631 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE 603 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
706 nleft = cx_ll_node_at(ll, other); 678 nleft = cx_ll_node_at(ll, other);
707 } 679 }
708 } 680 }
709 } 681 }
710 682
711 if (list->itemsize > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { 683 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
712 cx_linked_list_node *prev = nleft->prev; 684 cx_linked_list_node *prev = nleft->prev;
713 cx_linked_list_node *next = nright->next; 685 cx_linked_list_node *next = nright->next;
714 cx_linked_list_node *midstart = nleft->next; 686 cx_linked_list_node *midstart = nleft->next;
715 cx_linked_list_node *midend = nright->prev; 687 cx_linked_list_node *midend = nright->prev;
716 688
738 next->prev = nleft; 710 next->prev = nleft;
739 } 711 }
740 } else { 712 } else {
741 // swap payloads to avoid relinking 713 // swap payloads to avoid relinking
742 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; 714 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
743 memcpy(buf, nleft->payload, list->itemsize); 715 memcpy(buf, nleft->payload, list->item_size);
744 memcpy(nleft->payload, nright->payload, list->itemsize); 716 memcpy(nleft->payload, nright->payload, list->item_size);
745 memcpy(nright->payload, buf, list->itemsize); 717 memcpy(nright->payload, buf, list->item_size);
746 } 718 }
747 719
748 return 0; 720 return 0;
749 } 721 }
750 722
801 struct cx_mut_iterator_s *iter = it; 773 struct cx_mut_iterator_s *iter = it;
802 struct cx_list_s *list = iter->src_handle; 774 struct cx_list_s *list = iter->src_handle;
803 cx_linked_list *ll = iter->src_handle; 775 cx_linked_list *ll = iter->src_handle;
804 cx_linked_list_node *node = iter->elem_handle; 776 cx_linked_list_node *node = iter->elem_handle;
805 iter->elem_handle = node->next; 777 iter->elem_handle = node->next;
806 if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { 778 cx_invoke_destructor(list, node->payload);
807 cx_list_invoke_destructor(list, node->payload);
808 }
809 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 779 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
810 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 780 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
811 list->size--; 781 list->size--;
812 cxFree(list->allocator, node); 782 cxFree(list->allocator, node);
813 } else { 783 } else {
826 struct cx_list_s *list = iter->src_handle; 796 struct cx_list_s *list = iter->src_handle;
827 cx_linked_list *ll = iter->src_handle; 797 cx_linked_list *ll = iter->src_handle;
828 cx_linked_list_node *node = iter->elem_handle; 798 cx_linked_list_node *node = iter->elem_handle;
829 iter->elem_handle = node->prev; 799 iter->elem_handle = node->prev;
830 iter->index--; 800 iter->index--;
831 if (list->content_destructor_type != CX_DESTRUCTOR_NONE) { 801 cx_invoke_destructor(list, node->payload);
832 cx_list_invoke_destructor(list, node->payload);
833 }
834 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 802 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
835 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 803 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
836 list->size--; 804 list->size--;
837 cxFree(list->allocator, node); 805 cxFree(list->allocator, node);
838 } else { 806 } else {
925 cx_ll_iterator, 893 cx_ll_iterator,
926 }; 894 };
927 895
928 CxList *cxLinkedListCreate( 896 CxList *cxLinkedListCreate(
929 CxAllocator const *allocator, 897 CxAllocator const *allocator,
930 CxListComparator comparator, 898 cx_compare_func comparator,
931 size_t item_size 899 size_t item_size
932 ) { 900 ) {
933 if (allocator == NULL) { 901 if (allocator == NULL) {
934 allocator = cxDefaultAllocator; 902 allocator = cxDefaultAllocator;
935 } 903 }
938 if (list == NULL) return NULL; 906 if (list == NULL) return NULL;
939 907
940 list->base.cl = &cx_linked_list_class; 908 list->base.cl = &cx_linked_list_class;
941 list->base.allocator = allocator; 909 list->base.allocator = allocator;
942 list->base.cmpfunc = comparator; 910 list->base.cmpfunc = comparator;
943 list->base.capacity = SIZE_MAX;
944 911
945 if (item_size > 0) { 912 if (item_size > 0) {
946 list->base.itemsize = item_size; 913 list->base.item_size = item_size;
947 } else { 914 } else {
948 cxListStorePointers((CxList *) list); 915 cxListStorePointers((CxList *) list);
949 } 916 }
950 917
951 return (CxList *) list; 918 return (CxList *) list;

Mercurial Repository: ucx

mercurial