comparison: src/linked_list.c
src/linked_list.c
- changeset 552
- 4373c2a90066
- parent 528
- 4fbfac557df8
- child 592
- bb69ef3ad1f3
equal
deleted
inserted
replaced
| 551:2946e13c89a4 | 552:4373c2a90066 |
|---|---|
| 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) |
| 41 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) | 41 #define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) |
| 42 #define ll_data(node) ll_data_f(node,follow_ptr) | |
| 42 | 43 |
| 43 void *cx_linked_list_at( | 44 void *cx_linked_list_at( |
| 44 void const *start, | 45 void const *start, |
| 45 size_t start_index, | 46 size_t start_index, |
| 46 ptrdiff_t loc_advance, | 47 ptrdiff_t loc_advance, |
| 401 int cx_linked_list_compare( | 402 int cx_linked_list_compare( |
| 402 void const *begin_left, | 403 void const *begin_left, |
| 403 void const *begin_right, | 404 void const *begin_right, |
| 404 ptrdiff_t loc_advance, | 405 ptrdiff_t loc_advance, |
| 405 ptrdiff_t loc_data, | 406 ptrdiff_t loc_data, |
| 406 bool follow_ptr, | 407 bool follow_ptr_left, |
| 408 bool follow_ptr_right, | |
| 407 CxListComparator cmp_func | 409 CxListComparator cmp_func |
| 408 ) { | 410 ) { |
| 409 void const *left = begin_left, *right = begin_right; | 411 void const *left = begin_left, *right = begin_right; |
| 410 | 412 |
| 411 while (left != NULL && right != NULL) { | 413 while (left != NULL && right != NULL) { |
| 412 int result = cmp_func(ll_data(left), ll_data(right)); | 414 void const *left_data = ll_data_f(left, follow_ptr_left); |
| 415 void const *right_data = ll_data_f(right, follow_ptr_right); | |
| 416 int result = cmp_func(left_data, right_data); | |
| 413 if (result != 0) return result; | 417 if (result != 0) return result; |
| 414 left = ll_advance(left); | 418 left = ll_advance(left); |
| 415 right = ll_advance(right); | 419 right = ll_advance(right); |
| 416 } | 420 } |
| 417 | 421 |
| 466 | 470 |
| 467 typedef struct { | 471 typedef struct { |
| 468 struct cx_list_s base; | 472 struct cx_list_s base; |
| 469 cx_linked_list_node *begin; | 473 cx_linked_list_node *begin; |
| 470 cx_linked_list_node *end; | 474 cx_linked_list_node *end; |
| 475 bool follow_ptr; | |
| 471 } cx_linked_list; | 476 } cx_linked_list; |
| 472 | 477 |
| 473 static cx_linked_list_node *cx_ll_node_at( | 478 static cx_linked_list_node *cx_ll_node_at( |
| 474 cx_linked_list const *list, | 479 cx_linked_list const *list, |
| 475 size_t index | 480 size_t index |
| 593 | 598 |
| 594 static size_t cx_ll_find( | 599 static size_t cx_ll_find( |
| 595 struct cx_list_s const *list, | 600 struct cx_list_s const *list, |
| 596 void const *elem | 601 void const *elem |
| 597 ) { | 602 ) { |
| 603 cx_linked_list *ll = (cx_linked_list *) list; | |
| 598 return cx_linked_list_find(((cx_linked_list *) list)->begin, | 604 return cx_linked_list_find(((cx_linked_list *) list)->begin, |
| 599 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 605 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 600 false, list->cmpfunc, elem); | 606 ll->follow_ptr, list->cmpfunc, elem); |
| 601 } | |
| 602 | |
| 603 static size_t cx_pll_find( | |
| 604 struct cx_list_s const *list, | |
| 605 void const *elem | |
| 606 ) { | |
| 607 return cx_linked_list_find(((cx_linked_list *) list)->begin, | |
| 608 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | |
| 609 true, list->cmpfunc, elem); | |
| 610 } | 607 } |
| 611 | 608 |
| 612 static void cx_ll_sort(struct cx_list_s *list) { | 609 static void cx_ll_sort(struct cx_list_s *list) { |
| 613 cx_linked_list *ll = (cx_linked_list *) list; | 610 cx_linked_list *ll = (cx_linked_list *) list; |
| 614 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, | 611 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, |
| 615 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 612 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 616 false, list->cmpfunc); | 613 ll->follow_ptr, list->cmpfunc); |
| 617 } | |
| 618 | |
| 619 static void cx_pll_sort(struct cx_list_s *list) { | |
| 620 cx_linked_list *ll = (cx_linked_list *) list; | |
| 621 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, | |
| 622 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | |
| 623 true, list->cmpfunc); | |
| 624 } | 614 } |
| 625 | 615 |
| 626 static void cx_ll_reverse(struct cx_list_s *list) { | 616 static void cx_ll_reverse(struct cx_list_s *list) { |
| 627 cx_linked_list *ll = (cx_linked_list *) list; | 617 cx_linked_list *ll = (cx_linked_list *) list; |
| 628 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); | 618 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); |
| 634 ) { | 624 ) { |
| 635 cx_linked_list *left = (cx_linked_list *) list; | 625 cx_linked_list *left = (cx_linked_list *) list; |
| 636 cx_linked_list *right = (cx_linked_list *) other; | 626 cx_linked_list *right = (cx_linked_list *) other; |
| 637 return cx_linked_list_compare(left->begin, right->begin, | 627 return cx_linked_list_compare(left->begin, right->begin, |
| 638 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 628 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 639 false, list->cmpfunc); | 629 left->follow_ptr, right->follow_ptr, list->cmpfunc); |
| 640 } | |
| 641 | |
| 642 static int cx_pll_compare( | |
| 643 struct cx_list_s const *list, | |
| 644 struct cx_list_s const *other | |
| 645 ) { | |
| 646 cx_linked_list *left = (cx_linked_list *) list; | |
| 647 cx_linked_list *right = (cx_linked_list *) other; | |
| 648 return cx_linked_list_compare(left->begin, right->begin, | |
| 649 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | |
| 650 true, list->cmpfunc); | |
| 651 } | 630 } |
| 652 | 631 |
| 653 static bool cx_ll_iter_valid(CxIterator const *iter) { | 632 static bool cx_ll_iter_valid(CxIterator const *iter) { |
| 654 return iter->elem_handle != NULL; | 633 return iter->elem_handle != NULL; |
| 655 } | 634 } |
| 764 cx_pll_add, | 743 cx_pll_add, |
| 765 cx_pll_insert, | 744 cx_pll_insert, |
| 766 cx_pll_insert_iter, | 745 cx_pll_insert_iter, |
| 767 cx_ll_remove, | 746 cx_ll_remove, |
| 768 cx_pll_at, | 747 cx_pll_at, |
| 769 cx_pll_find, | 748 cx_ll_find, |
| 770 cx_pll_sort, | 749 cx_ll_sort, |
| 771 cx_pll_compare, | 750 cx_ll_compare, |
| 772 cx_ll_reverse, | 751 cx_ll_reverse, |
| 773 cx_pll_iterator, | 752 cx_pll_iterator, |
| 774 }; | 753 }; |
| 775 | 754 |
| 776 CxList *cxLinkedListCreate( | 755 CxList *cxLinkedListCreate( |
| 779 size_t item_size | 758 size_t item_size |
| 780 ) { | 759 ) { |
| 781 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); | 760 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
| 782 if (list == NULL) return NULL; | 761 if (list == NULL) return NULL; |
| 783 | 762 |
| 763 list->follow_ptr = false; | |
| 784 list->base.cl = &cx_linked_list_class; | 764 list->base.cl = &cx_linked_list_class; |
| 785 list->base.allocator = allocator; | 765 list->base.allocator = allocator; |
| 786 list->base.cmpfunc = comparator; | 766 list->base.cmpfunc = comparator; |
| 787 list->base.itemsize = item_size; | 767 list->base.itemsize = item_size; |
| 788 list->base.capacity = SIZE_MAX; | 768 list->base.capacity = SIZE_MAX; |
| 795 CxListComparator comparator | 775 CxListComparator comparator |
| 796 ) { | 776 ) { |
| 797 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); | 777 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
| 798 if (list == NULL) return NULL; | 778 if (list == NULL) return NULL; |
| 799 | 779 |
| 780 list->follow_ptr = true; | |
| 800 list->base.cl = &cx_pointer_linked_list_class; | 781 list->base.cl = &cx_pointer_linked_list_class; |
| 801 list->base.allocator = allocator; | 782 list->base.allocator = allocator; |
| 802 list->base.cmpfunc = comparator; | 783 list->base.cmpfunc = comparator; |
| 803 list->base.itemsize = sizeof(void *); | 784 list->base.itemsize = sizeof(void *); |
| 804 list->base.capacity = SIZE_MAX; | 785 list->base.capacity = SIZE_MAX; |
