Mercurial > hg > webserver / file comparison

comparison: src/ucx/linked_list.c

src/ucx/linked_list.c

changeset 438
22eca559aded
parent 415
d938228c382e
child 490
d218607f5a7e
equal deleted inserted replaced
437:545010bc5e71 438:22eca559aded
30 #include "cx/utils.h" 30 #include "cx/utils.h"
31 #include <stdint.h> 31 #include <stdint.h>
32 #include <string.h> 32 #include <string.h>
33 #include <assert.h> 33 #include <assert.h>
34 34
35 /* LOW LEVEL LINKED LIST FUNCTIONS */ 35 // LOW LEVEL LINKED LIST FUNCTIONS
36 36
37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
38 #define ll_prev(node) CX_LL_PTR(node, loc_prev) 38 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
39 #define ll_next(node) CX_LL_PTR(node, loc_next) 39 #define ll_next(node) CX_LL_PTR(node, loc_next)
40 #define ll_advance(node) CX_LL_PTR(node, loc_advance) 40 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
335 free(sorted); 335 free(sorted);
336 } 336 }
337 return ret; 337 return ret;
338 } 338 }
339 339
340 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */ 340 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
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,
453 *end = *begin; 453 *end = *begin;
454 } 454 }
455 *begin = prev; 455 *begin = prev;
456 } 456 }
457 457
458 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 458 // HIGH LEVEL LINKED LIST IMPLEMENTATION
459 459
460 typedef struct cx_linked_list_node cx_linked_list_node; 460 typedef struct cx_linked_list_node cx_linked_list_node;
461 struct cx_linked_list_node { 461 struct cx_linked_list_node {
462 cx_linked_list_node *prev; 462 cx_linked_list_node *prev;
463 cx_linked_list_node *next; 463 cx_linked_list_node *next;
538 void const *elem 538 void const *elem
539 ) { 539 ) {
540 return cx_ll_insert(list, list->size, elem); 540 return cx_ll_insert(list, list->size, elem);
541 } 541 }
542 542
543 static size_t cx_ll_add_array(
544 struct cx_list_s *list,
545 void const *array,
546 size_t n
547 ) {
548 // TODO: redirect to cx_ll_insert_array
549 cx_for_n (i, n) {
550 if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
551 return i;
552 }
553 }
554 return n;
555 }
556
543 static int cx_pll_insert( 557 static int cx_pll_insert(
544 struct cx_list_s *list, 558 struct cx_list_s *list,
545 size_t index, 559 size_t index,
546 void const *elem 560 void const *elem
547 ) { 561 ) {
627 return cx_linked_list_compare(left->begin, right->begin, 641 return cx_linked_list_compare(left->begin, right->begin,
628 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 642 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
629 left->follow_ptr, right->follow_ptr, list->cmpfunc); 643 left->follow_ptr, right->follow_ptr, list->cmpfunc);
630 } 644 }
631 645
632 static bool cx_ll_iter_valid(CxIterator const *iter) { 646 static bool cx_ll_iter_valid(void const *it) {
647 struct cx_iterator_s const *iter = it;
633 return iter->elem_handle != NULL; 648 return iter->elem_handle != NULL;
634 } 649 }
635 650
636 static void cx_ll_iter_next(CxIterator *iter) { 651 static void cx_ll_iter_next(void *it) {
637 if (iter->remove) { 652 struct cx_iterator_base_s *itbase = it;
638 iter->remove = false; 653 if (itbase->remove) {
654 itbase->remove = false;
655 struct cx_mut_iterator_s *iter = it;
639 cx_linked_list *ll = iter->src_handle; 656 cx_linked_list *ll = iter->src_handle;
640 cx_linked_list_node *node = iter->elem_handle; 657 cx_linked_list_node *node = iter->elem_handle;
641 iter->elem_handle = node->next; 658 iter->elem_handle = node->next;
642 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 659 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
643 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 660 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
644 ll->base.size--; 661 ll->base.size--;
645 cxFree(ll->base.allocator, node); 662 cxFree(ll->base.allocator, node);
646 } else { 663 } else {
664 struct cx_iterator_s *iter = it;
647 iter->index++; 665 iter->index++;
648 cx_linked_list_node *node = iter->elem_handle; 666 cx_linked_list_node *node = iter->elem_handle;
649 iter->elem_handle = node->next; 667 iter->elem_handle = node->next;
650 } 668 }
651 } 669 }
652 670
653 static void *cx_ll_iter_current(CxIterator const *iter) { 671 static void *cx_ll_iter_current(void const *it) {
672 struct cx_iterator_s const *iter = it;
654 cx_linked_list_node *node = iter->elem_handle; 673 cx_linked_list_node *node = iter->elem_handle;
655 return node->payload; 674 return node->payload;
656 } 675 }
657 676
658 static void *cx_pll_iter_current(CxIterator const *iter) { 677 static void *cx_pll_iter_current(void const *it) {
678 struct cx_iterator_s const *iter = it;
659 cx_linked_list_node *node = iter->elem_handle; 679 cx_linked_list_node *node = iter->elem_handle;
660 return *(void **) node->payload; 680 return *(void **) node->payload;
661 } 681 }
662 682
683 static bool cx_ll_iter_flag_rm(void *it) {
684 struct cx_iterator_base_s *iter = it;
685 if (iter->mutating) {
686 iter->remove = true;
687 return true;
688 } else {
689 return false;
690 }
691 }
692
663 static CxIterator cx_ll_iterator( 693 static CxIterator cx_ll_iterator(
664 struct cx_list_s *list, 694 struct cx_list_s const *list,
665 size_t index 695 size_t index
666 ) { 696 ) {
667 CxIterator iter; 697 CxIterator iter;
668 iter.index = index; 698 iter.index = index;
669 iter.src_handle = list; 699 iter.src_handle = list;
670 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 700 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
671 iter.valid = cx_ll_iter_valid; 701 iter.base.valid = cx_ll_iter_valid;
672 iter.current = cx_ll_iter_current; 702 iter.base.current = cx_ll_iter_current;
673 iter.next = cx_ll_iter_next; 703 iter.base.next = cx_ll_iter_next;
674 iter.remove = false; 704 iter.base.flag_removal = cx_ll_iter_flag_rm;
705 iter.base.mutating = false;
706 iter.base.remove = false;
675 return iter; 707 return iter;
676 } 708 }
677 709
678 static CxIterator cx_pll_iterator( 710 static CxIterator cx_pll_iterator(
711 struct cx_list_s const *list,
712 size_t index
713 ) {
714 CxIterator iter = cx_ll_iterator(list, index);
715 iter.base.current = cx_pll_iter_current;
716 return iter;
717 }
718
719 static CxMutIterator cx_ll_mut_iterator(
679 struct cx_list_s *list, 720 struct cx_list_s *list,
680 size_t index 721 size_t index
681 ) { 722 ) {
682 CxIterator iter = cx_ll_iterator(list, index); 723 CxIterator it = cx_ll_iterator(list, index);
683 iter.current = cx_pll_iter_current; 724 it.base.mutating = true;
725
726 // we know the iterators share the same memory layout
727 CxMutIterator iter;
728 memcpy(&iter, &it, sizeof(CxMutIterator));
684 return iter; 729 return iter;
685 } 730 }
686 731
732 static CxMutIterator cx_pll_mut_iterator(
733 struct cx_list_s *list,
734 size_t index
735 ) {
736 CxMutIterator iter = cx_ll_mut_iterator(list, index);
737 iter.base.current = cx_pll_iter_current;
738 return iter;
739 }
740
687 static int cx_ll_insert_iter( 741 static int cx_ll_insert_iter(
688 CxIterator *iter, 742 CxMutIterator *iter,
689 void const *elem, 743 void const *elem,
690 int prepend 744 int prepend
691 ) { 745 ) {
692 struct cx_list_s *list = iter->src_handle; 746 struct cx_list_s *list = iter->src_handle;
693 cx_linked_list_node *node = iter->elem_handle; 747 cx_linked_list_node *node = iter->elem_handle;
703 return result; 757 return result;
704 } 758 }
705 } 759 }
706 760
707 static int cx_pll_insert_iter( 761 static int cx_pll_insert_iter(
708 CxIterator *iter, 762 CxMutIterator *iter,
709 void const *elem, 763 void const *elem,
710 int prepend 764 int prepend
711 ) { 765 ) {
712 return cx_ll_insert_iter(iter, &elem, prepend); 766 return cx_ll_insert_iter(iter, &elem, prepend);
713 } 767 }
725 } 779 }
726 780
727 static cx_list_class cx_linked_list_class = { 781 static cx_list_class cx_linked_list_class = {
728 cx_ll_destructor, 782 cx_ll_destructor,
729 cx_ll_add, 783 cx_ll_add,
784 cx_ll_add_array,
730 cx_ll_insert, 785 cx_ll_insert,
731 cx_ll_insert_iter, 786 cx_ll_insert_iter,
732 cx_ll_remove, 787 cx_ll_remove,
733 cx_ll_at, 788 cx_ll_at,
734 cx_ll_find, 789 cx_ll_find,
735 cx_ll_sort, 790 cx_ll_sort,
736 cx_ll_compare, 791 cx_ll_compare,
737 cx_ll_reverse, 792 cx_ll_reverse,
738 cx_ll_iterator 793 cx_ll_iterator,
794 cx_ll_mut_iterator,
739 }; 795 };
740 796
741 static cx_list_class cx_pointer_linked_list_class = { 797 static cx_list_class cx_pointer_linked_list_class = {
742 cx_ll_destructor, 798 cx_ll_destructor,
743 cx_pll_add, 799 cx_pll_add,
800 cx_ll_add_array,
744 cx_pll_insert, 801 cx_pll_insert,
745 cx_pll_insert_iter, 802 cx_pll_insert_iter,
746 cx_ll_remove, 803 cx_ll_remove,
747 cx_pll_at, 804 cx_pll_at,
748 cx_ll_find, 805 cx_ll_find,
749 cx_ll_sort, 806 cx_ll_sort,
750 cx_ll_compare, 807 cx_ll_compare,
751 cx_ll_reverse, 808 cx_ll_reverse,
752 cx_pll_iterator, 809 cx_pll_iterator,
810 cx_pll_mut_iterator,
753 }; 811 };
754 812
755 CxList *cxLinkedListCreate( 813 CxList *cxLinkedListCreate(
756 CxAllocator const *allocator, 814 CxAllocator const *allocator,
757 CxListComparator comparator, 815 CxListComparator comparator,
784 list->base.itemsize = sizeof(void *); 842 list->base.itemsize = sizeof(void *);
785 list->base.capacity = SIZE_MAX; 843 list->base.capacity = SIZE_MAX;
786 844
787 return (CxList *) list; 845 return (CxList *) list;
788 } 846 }
789
790 CxList *cxLinkedListFromArray(
791 CxAllocator const *allocator,
792 CxListComparator comparator,
793 size_t item_size,
794 size_t num_items,
795 void const *array
796 ) {
797 CxList *list = cxLinkedListCreate(allocator, comparator, item_size);
798 if (list == NULL) return NULL;
799 cx_for_n (i, num_items) {
800 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
801 cx_ll_destructor(list);
802 cxFree(allocator, list);
803 return NULL;
804 }
805 }
806 return list;
807 }

Mercurial Repository: webserver

mercurial