Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 854
fe0d69d72bcd
parent 853
d4baf4dd55c3
child 855
35bcb3216c0d
equal deleted inserted replaced
853:d4baf4dd55c3 854:fe0d69d72bcd
499 499
500 static cx_linked_list_node *cx_ll_node_at( 500 static cx_linked_list_node *cx_ll_node_at(
501 cx_linked_list const *list, 501 cx_linked_list const *list,
502 size_t index 502 size_t index
503 ) { 503 ) {
504 if (index >= list->base.size) { 504 if (index >= list->base.base.size) {
505 return NULL; 505 return NULL;
506 } else if (index > list->base.size / 2) { 506 } else if (index > list->base.base.size / 2) {
507 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); 507 return cx_linked_list_at(list->end, list->base.base.size - 1, CX_LL_LOC_PREV, index);
508 } else { 508 } else {
509 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 509 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
510 } 510 }
511 } 511 }
512 512
515 cx_linked_list_node *node, 515 cx_linked_list_node *node,
516 void const *elem 516 void const *elem
517 ) { 517 ) {
518 518
519 // create the new new_node 519 // create the new new_node
520 cx_linked_list_node *new_node = cxMalloc(list->allocator, 520 cx_linked_list_node *new_node = cxMalloc(list->base.allocator,
521 sizeof(cx_linked_list_node) + list->item_size); 521 sizeof(cx_linked_list_node) + list->base.item_size);
522 522
523 // sortir if failed 523 // sortir if failed
524 if (new_node == NULL) return 1; 524 if (new_node == NULL) return 1;
525 525
526 // initialize new new_node 526 // initialize new new_node
527 new_node->prev = new_node->next = NULL; 527 new_node->prev = new_node->next = NULL;
528 memcpy(new_node->payload, elem, list->item_size); 528 memcpy(new_node->payload, elem, list->base.item_size);
529 529
530 // insert 530 // insert
531 cx_linked_list *ll = (cx_linked_list *) list; 531 cx_linked_list *ll = (cx_linked_list *) list;
532 cx_linked_list_insert_chain( 532 cx_linked_list_insert_chain(
533 (void **) &ll->begin, (void **) &ll->end, 533 (void **) &ll->begin, (void **) &ll->end,
534 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, 534 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
535 node, new_node, new_node 535 node, new_node, new_node
536 ); 536 );
537 537
538 // increase the size and return 538 // increase the size and return
539 list->size++; 539 list->base.size++;
540 return 0; 540 return 0;
541 } 541 }
542 542
543 static size_t cx_ll_insert_array( 543 static size_t cx_ll_insert_array(
544 struct cx_list_s *list, 544 struct cx_list_s *list,
545 size_t index, 545 size_t index,
546 void const *array, 546 void const *array,
547 size_t n 547 size_t n
548 ) { 548 ) {
549 // out-of bounds and corner case check 549 // out-of bounds and corner case check
550 if (index > list->size || n == 0) return 0; 550 if (index > list->base.size || n == 0) return 0;
551 551
552 // find position efficiently 552 // find position efficiently
553 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 553 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
554 554
555 // perform first insert 555 // perform first insert
564 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 564 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
565 565
566 // we can add the remaining nodes and immedately advance to the inserted node 566 // we can add the remaining nodes and immedately advance to the inserted node
567 char const *source = array; 567 char const *source = array;
568 for (size_t i = 1; i < n; i++) { 568 for (size_t i = 1; i < n; i++) {
569 source += list->item_size; 569 source += list->base.item_size;
570 if (0 != cx_ll_insert_at(list, node, source)) { 570 if (0 != cx_ll_insert_at(list, node, source)) {
571 return i; 571 return i;
572 } 572 }
573 node = node->next; 573 node = node->next;
574 } 574 }
599 // remove 599 // remove
600 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 600 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
601 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 601 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
602 602
603 // adjust size 603 // adjust size
604 list->size--; 604 list->base.size--;
605 605
606 // free and return 606 // free and return
607 cxFree(list->allocator, node); 607 cxFree(list->base.allocator, node);
608 608
609 return 0; 609 return 0;
610 } 610 }
611 611
612 static void cx_ll_clear(struct cx_list_s *list) { 612 static void cx_ll_clear(struct cx_list_s *list) {
613 if (list->size == 0) return; 613 if (list->base.size == 0) return;
614 614
615 cx_linked_list *ll = (cx_linked_list *) list; 615 cx_linked_list *ll = (cx_linked_list *) list;
616 cx_linked_list_node *node = ll->begin; 616 cx_linked_list_node *node = ll->begin;
617 while (node != NULL) { 617 while (node != NULL) {
618 cx_invoke_destructor(list, node->payload); 618 cx_invoke_destructor(list, node->payload);
619 cx_linked_list_node *next = node->next; 619 cx_linked_list_node *next = node->next;
620 cxFree(list->allocator, node); 620 cxFree(list->base.allocator, node);
621 node = next; 621 node = next;
622 } 622 }
623 ll->begin = ll->end = NULL; 623 ll->begin = ll->end = NULL;
624 list->size = 0; 624 list->base.size = 0;
625 } 625 }
626 626
627 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE 627 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
628 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 628 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128
629 #endif 629 #endif
632 static int cx_ll_swap( 632 static int cx_ll_swap(
633 struct cx_list_s *list, 633 struct cx_list_s *list,
634 size_t i, 634 size_t i,
635 size_t j 635 size_t j
636 ) { 636 ) {
637 if (i >= list->size || j >= list->size) return 1; 637 if (i >= list->base.size || j >= list->base.size) return 1;
638 if (i == j) return 0; 638 if (i == j) return 0;
639 639
640 // perform an optimized search that finds both elements in one run 640 // perform an optimized search that finds both elements in one run
641 cx_linked_list *ll = (cx_linked_list *) list; 641 cx_linked_list *ll = (cx_linked_list *) list;
642 size_t mid = list->size / 2; 642 size_t mid = list->base.size / 2;
643 size_t left, right; 643 size_t left, right;
644 if (i < j) { 644 if (i < j) {
645 left = i; 645 left = i;
646 right = j; 646 right = j;
647 } else { 647 } else {
669 // case 3: one item left, one item right 669 // case 3: one item left, one item right
670 670
671 // chose the closest to begin / end 671 // chose the closest to begin / end
672 size_t closest; 672 size_t closest;
673 size_t other; 673 size_t other;
674 size_t diff2boundary = list->size - right - 1; 674 size_t diff2boundary = list->base.size - right - 1;
675 if (left <= diff2boundary) { 675 if (left <= diff2boundary) {
676 closest = left; 676 closest = left;
677 other = right; 677 other = right;
678 nleft = cx_ll_node_at(ll, left); 678 nleft = cx_ll_node_at(ll, left);
679 } else { 679 } else {
705 nleft = cx_ll_node_at(ll, other); 705 nleft = cx_ll_node_at(ll, other);
706 } 706 }
707 } 707 }
708 } 708 }
709 709
710 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { 710 if (list->base.item_size > CX_LINKED_LIST_SWAP_SBO_SIZE) {
711 cx_linked_list_node *prev = nleft->prev; 711 cx_linked_list_node *prev = nleft->prev;
712 cx_linked_list_node *next = nright->next; 712 cx_linked_list_node *next = nright->next;
713 cx_linked_list_node *midstart = nleft->next; 713 cx_linked_list_node *midstart = nleft->next;
714 cx_linked_list_node *midend = nright->prev; 714 cx_linked_list_node *midend = nright->prev;
715 715
737 next->prev = nleft; 737 next->prev = nleft;
738 } 738 }
739 } else { 739 } else {
740 // swap payloads to avoid relinking 740 // swap payloads to avoid relinking
741 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; 741 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
742 memcpy(buf, nleft->payload, list->item_size); 742 memcpy(buf, nleft->payload, list->base.item_size);
743 memcpy(nleft->payload, nright->payload, list->item_size); 743 memcpy(nleft->payload, nright->payload, list->base.item_size);
744 memcpy(nright->payload, buf, list->item_size); 744 memcpy(nright->payload, buf, list->base.item_size);
745 } 745 }
746 746
747 return 0; 747 return 0;
748 } 748 }
749 749
766 cx_linked_list_node *node; 766 cx_linked_list_node *node;
767 ssize_t index = cx_linked_list_find_node( 767 ssize_t index = cx_linked_list_find_node(
768 (void **) &node, 768 (void **) &node,
769 ll->begin, 769 ll->begin,
770 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 770 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
771 list->cmpfunc, elem 771 list->base.cmpfunc, elem
772 ); 772 );
773 if (node != NULL) { 773 if (node != NULL) {
774 cx_invoke_destructor(list, node->payload); 774 cx_invoke_destructor(list, node->payload);
775 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 775 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
776 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 776 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
777 list->size--; 777 list->base.size--;
778 cxFree(list->allocator, node); 778 cxFree(list->base.allocator, node);
779 } 779 }
780 return index; 780 return index;
781 } else { 781 } else {
782 return cx_linked_list_find( 782 return cx_linked_list_find(
783 ((cx_linked_list *) list)->begin, 783 ((cx_linked_list *) list)->begin,
784 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 784 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
785 list->cmpfunc, elem 785 list->base.cmpfunc, elem
786 ); 786 );
787 } 787 }
788 } 788 }
789 789
790 static void cx_ll_sort(struct cx_list_s *list) { 790 static void cx_ll_sort(struct cx_list_s *list) {
791 cx_linked_list *ll = (cx_linked_list *) list; 791 cx_linked_list *ll = (cx_linked_list *) list;
792 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 792 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
793 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 793 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
794 list->cmpfunc); 794 list->base.cmpfunc);
795 } 795 }
796 796
797 static void cx_ll_reverse(struct cx_list_s *list) { 797 static void cx_ll_reverse(struct cx_list_s *list) {
798 cx_linked_list *ll = (cx_linked_list *) list; 798 cx_linked_list *ll = (cx_linked_list *) list;
799 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 799 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
805 ) { 805 ) {
806 cx_linked_list *left = (cx_linked_list *) list; 806 cx_linked_list *left = (cx_linked_list *) list;
807 cx_linked_list *right = (cx_linked_list *) other; 807 cx_linked_list *right = (cx_linked_list *) other;
808 return cx_linked_list_compare(left->begin, right->begin, 808 return cx_linked_list_compare(left->begin, right->begin,
809 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 809 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
810 list->cmpfunc); 810 list->base.cmpfunc);
811 } 811 }
812 812
813 static bool cx_ll_iter_valid(void const *it) { 813 static bool cx_ll_iter_valid(void const *it) {
814 struct cx_iterator_s const *iter = it; 814 struct cx_iterator_s const *iter = it;
815 return iter->elem_handle != NULL; 815 return iter->elem_handle != NULL;
816 } 816 }
817 817
818 static void cx_ll_iter_next(void *it) { 818 static void cx_ll_iter_next(void *it) {
819 struct cx_iterator_s *iter = it; 819 struct cx_iterator_s *iter = it;
820 if (iter->remove) { 820 if (iter->base.remove) {
821 iter->remove = false; 821 iter->base.remove = false;
822 struct cx_list_s *list = iter->src_handle.m; 822 struct cx_list_s *list = iter->src_handle.m;
823 cx_linked_list *ll = iter->src_handle.m; 823 cx_linked_list *ll = iter->src_handle.m;
824 cx_linked_list_node *node = iter->elem_handle; 824 cx_linked_list_node *node = iter->elem_handle;
825 iter->elem_handle = node->next; 825 iter->elem_handle = node->next;
826 cx_invoke_destructor(list, node->payload); 826 cx_invoke_destructor(list, node->payload);
827 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 827 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
828 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 828 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
829 list->size--; 829 list->base.size--;
830 cxFree(list->allocator, node); 830 cxFree(list->base.allocator, node);
831 } else { 831 } else {
832 iter->index++; 832 iter->index++;
833 cx_linked_list_node *node = iter->elem_handle; 833 cx_linked_list_node *node = iter->elem_handle;
834 iter->elem_handle = node->next; 834 iter->elem_handle = node->next;
835 } 835 }
836 } 836 }
837 837
838 static void cx_ll_iter_prev(void *it) { 838 static void cx_ll_iter_prev(void *it) {
839 struct cx_iterator_s *iter = it; 839 struct cx_iterator_s *iter = it;
840 if (iter->remove) { 840 if (iter->base.remove) {
841 iter->remove = false; 841 iter->base.remove = false;
842 struct cx_list_s *list = iter->src_handle.m; 842 struct cx_list_s *list = iter->src_handle.m;
843 cx_linked_list *ll = iter->src_handle.m; 843 cx_linked_list *ll = iter->src_handle.m;
844 cx_linked_list_node *node = iter->elem_handle; 844 cx_linked_list_node *node = iter->elem_handle;
845 iter->elem_handle = node->prev; 845 iter->elem_handle = node->prev;
846 iter->index--; 846 iter->index--;
847 cx_invoke_destructor(list, node->payload); 847 cx_invoke_destructor(list, node->payload);
848 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 848 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
849 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 849 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
850 list->size--; 850 list->base.size--;
851 cxFree(list->allocator, node); 851 cxFree(list->base.allocator, node);
852 } else { 852 } else {
853 iter->index--; 853 iter->index--;
854 cx_linked_list_node *node = iter->elem_handle; 854 cx_linked_list_node *node = iter->elem_handle;
855 iter->elem_handle = node->prev; 855 iter->elem_handle = node->prev;
856 } 856 }
869 ) { 869 ) {
870 CxIterator iter; 870 CxIterator iter;
871 iter.index = index; 871 iter.index = index;
872 iter.src_handle.c = list; 872 iter.src_handle.c = list;
873 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 873 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
874 iter.elem_size = list->item_size; 874 iter.elem_size = list->base.item_size;
875 iter.elem_count = list->size; 875 iter.elem_count = list->base.size;
876 iter.valid = cx_ll_iter_valid; 876 iter.base.valid = cx_ll_iter_valid;
877 iter.current = cx_ll_iter_current; 877 iter.base.current = cx_ll_iter_current;
878 iter.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; 878 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
879 iter.mutating = false; 879 iter.base.mutating = false;
880 iter.remove = false; 880 iter.base.remove = false;
881 return iter; 881 return iter;
882 } 882 }
883 883
884 static int cx_ll_insert_iter( 884 static int cx_ll_insert_iter(
885 CxIterator *iter, 885 CxIterator *iter,
893 cx_linked_list_node *choice[2] = {node, node->prev}; 893 cx_linked_list_node *choice[2] = {node, node->prev};
894 int result = cx_ll_insert_at(list, choice[prepend], elem); 894 int result = cx_ll_insert_at(list, choice[prepend], elem);
895 iter->index += prepend * (0 == result); 895 iter->index += prepend * (0 == result);
896 return result; 896 return result;
897 } else { 897 } else {
898 int result = cx_ll_insert_element(list, list->size, elem); 898 int result = cx_ll_insert_element(list, list->base.size, elem);
899 iter->index = list->size; 899 iter->index = list->base.size;
900 return result; 900 return result;
901 } 901 }
902 } 902 }
903 903
904 static void cx_ll_destructor(CxList *list) { 904 static void cx_ll_destructor(CxList *list) {
906 906
907 cx_linked_list_node *node = ll->begin; 907 cx_linked_list_node *node = ll->begin;
908 while (node) { 908 while (node) {
909 cx_invoke_destructor(list, node->payload); 909 cx_invoke_destructor(list, node->payload);
910 void *next = node->next; 910 void *next = node->next;
911 cxFree(list->allocator, node); 911 cxFree(list->base.allocator, node);
912 node = next; 912 node = next;
913 } 913 }
914 914
915 cxFree(list->allocator, list); 915 cxFree(list->base.allocator, list);
916 } 916 }
917 917
918 static cx_list_class cx_linked_list_class = { 918 static cx_list_class cx_linked_list_class = {
919 cx_ll_destructor, 919 cx_ll_destructor,
920 cx_ll_insert_element, 920 cx_ll_insert_element,
942 942
943 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 943 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
944 if (list == NULL) return NULL; 944 if (list == NULL) return NULL;
945 945
946 list->base.cl = &cx_linked_list_class; 946 list->base.cl = &cx_linked_list_class;
947 list->base.allocator = allocator; 947 list->base.base.allocator = allocator;
948 948
949 if (item_size > 0) { 949 if (item_size > 0) {
950 list->base.item_size = item_size; 950 list->base.base.item_size = item_size;
951 list->base.cmpfunc = comparator; 951 list->base.base.cmpfunc = comparator;
952 } else { 952 } else {
953 list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; 953 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
954 cxListStorePointers((CxList *) list); 954 cxListStorePointers((CxList *) list);
955 } 955 }
956 956
957 return (CxList *) list; 957 return (CxList *) list;
958 } 958 }

Mercurial Repository: ucx

mercurial