Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 639
309e8b08c60e
parent 638
eafb45eefc51
child 640
55cc3b373c5e
equal deleted inserted replaced
638:eafb45eefc51 639:309e8b08c60e
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_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data)) 41 #define ll_data(node) (((char*)(node))+loc_data)
42 #define ll_data(node) ll_data_f(node,follow_ptr)
43 42
44 void *cx_linked_list_at( 43 void *cx_linked_list_at(
45 void const *start, 44 void const *start,
46 size_t start_index, 45 size_t start_index,
47 ptrdiff_t loc_advance, 46 ptrdiff_t loc_advance,
60 59
61 size_t cx_linked_list_find( 60 size_t cx_linked_list_find(
62 void const *start, 61 void const *start,
63 ptrdiff_t loc_advance, 62 ptrdiff_t loc_advance,
64 ptrdiff_t loc_data, 63 ptrdiff_t loc_data,
65 bool follow_ptr,
66 CxListComparator cmp_func, 64 CxListComparator cmp_func,
67 void const *elem 65 void const *elem
68 ) { 66 ) {
69 assert(start != NULL); 67 assert(start != NULL);
70 assert(loc_advance >= 0); 68 assert(loc_advance >= 0);
284 282
285 static void *cx_linked_list_sort_merge( 283 static void *cx_linked_list_sort_merge(
286 ptrdiff_t loc_prev, 284 ptrdiff_t loc_prev,
287 ptrdiff_t loc_next, 285 ptrdiff_t loc_next,
288 ptrdiff_t loc_data, 286 ptrdiff_t loc_data,
289 bool follow_ptr,
290 size_t length, 287 size_t length,
291 void *ls, 288 void *ls,
292 void *le, 289 void *le,
293 void *re, 290 void *re,
294 CxListComparator cmp_func 291 CxListComparator cmp_func
341 void **begin, 338 void **begin,
342 void **end, 339 void **end,
343 ptrdiff_t loc_prev, 340 ptrdiff_t loc_prev,
344 ptrdiff_t loc_next, 341 ptrdiff_t loc_next,
345 ptrdiff_t loc_data, 342 ptrdiff_t loc_data,
346 bool follow_ptr,
347 CxListComparator cmp_func 343 CxListComparator cmp_func
348 ) { 344 ) {
349 assert(begin != NULL); 345 assert(begin != NULL);
350 assert(loc_next >= 0); 346 assert(loc_next >= 0);
351 assert(loc_data >= 0); 347 assert(loc_data >= 0);
376 rn++; 372 rn++;
377 } 373 }
378 re = ll_next(rc); 374 re = ll_next(rc);
379 375
380 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 376 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
381 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, 377 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
382 ln + rn, ls, le, re, cmp_func); 378 ln + rn, ls, le, re, cmp_func);
383 379
384 // Something left? Sort it! 380 // Something left? Sort it!
385 size_t remainder_length = cx_linked_list_size(re, loc_next); 381 size_t remainder_length = cx_linked_list_size(re, loc_next);
386 if (remainder_length > 0) { 382 if (remainder_length > 0) {
387 void *remainder = re; 383 void *remainder = re;
388 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); 384 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
389 385
390 // merge sorted list with (also sorted) remainder 386 // merge sorted list with (also sorted) remainder
391 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, 387 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
392 ln + rn + remainder_length, 388 ln + rn + remainder_length,
393 sorted, remainder, NULL, cmp_func); 389 sorted, remainder, NULL, cmp_func);
394 } else { 390 } else {
395 // no remainder - we've got our sorted list 391 // no remainder - we've got our sorted list
396 *begin = sorted; 392 *begin = sorted;
402 int cx_linked_list_compare( 398 int cx_linked_list_compare(
403 void const *begin_left, 399 void const *begin_left,
404 void const *begin_right, 400 void const *begin_right,
405 ptrdiff_t loc_advance, 401 ptrdiff_t loc_advance,
406 ptrdiff_t loc_data, 402 ptrdiff_t loc_data,
407 bool follow_ptr_left,
408 bool follow_ptr_right,
409 CxListComparator cmp_func 403 CxListComparator cmp_func
410 ) { 404 ) {
411 void const *left = begin_left, *right = begin_right; 405 void const *left = begin_left, *right = begin_right;
412 406
413 while (left != NULL && right != NULL) { 407 while (left != NULL && right != NULL) {
414 void const *left_data = ll_data_f(left, follow_ptr_left); 408 void const *left_data = ll_data(left);
415 void const *right_data = ll_data_f(right, follow_ptr_right); 409 void const *right_data = ll_data(right);
416 int result = cmp_func(left_data, right_data); 410 int result = cmp_func(left_data, right_data);
417 if (result != 0) return result; 411 if (result != 0) return result;
418 left = ll_advance(left); 412 left = ll_advance(left);
419 right = ll_advance(right); 413 right = ll_advance(right);
420 } 414 }
470 464
471 typedef struct { 465 typedef struct {
472 struct cx_list_s base; 466 struct cx_list_s base;
473 cx_linked_list_node *begin; 467 cx_linked_list_node *begin;
474 cx_linked_list_node *end; 468 cx_linked_list_node *end;
475 bool follow_ptr;
476 } cx_linked_list; 469 } cx_linked_list;
477 470
478 static cx_linked_list_node *cx_ll_node_at( 471 static cx_linked_list_node *cx_ll_node_at(
479 cx_linked_list const *list, 472 cx_linked_list const *list,
480 size_t index 473 size_t index
574 size_t n 567 size_t n
575 ) { 568 ) {
576 return cx_ll_insert_array(list, list->size, array, n); 569 return cx_ll_insert_array(list, list->size, array, n);
577 } 570 }
578 571
579 static int cx_pll_insert(
580 struct cx_list_s *list,
581 size_t index,
582 void const *elem
583 ) {
584 return cx_ll_insert(list, index, &elem);
585 }
586
587 static int cx_pll_add(
588 struct cx_list_s *list,
589 void const *elem
590 ) {
591 return cx_ll_insert(list, list->size, &elem);
592 }
593
594 static int cx_ll_remove( 572 static int cx_ll_remove(
595 struct cx_list_s *list, 573 struct cx_list_s *list,
596 size_t index 574 size_t index
597 ) { 575 ) {
598 cx_linked_list *ll = (cx_linked_list *) list; 576 cx_linked_list *ll = (cx_linked_list *) list;
621 cx_linked_list *ll = (cx_linked_list *) list; 599 cx_linked_list *ll = (cx_linked_list *) list;
622 cx_linked_list_node *node = cx_ll_node_at(ll, index); 600 cx_linked_list_node *node = cx_ll_node_at(ll, index);
623 return node == NULL ? NULL : node->payload; 601 return node == NULL ? NULL : node->payload;
624 } 602 }
625 603
626 static void *cx_pll_at(
627 struct cx_list_s const *list,
628 size_t index
629 ) {
630 cx_linked_list *ll = (cx_linked_list *) list;
631 cx_linked_list_node *node = cx_ll_node_at(ll, index);
632 return node == NULL ? NULL : *(void **) node->payload;
633 }
634
635 static size_t cx_ll_find( 604 static size_t cx_ll_find(
636 struct cx_list_s const *list, 605 struct cx_list_s const *list,
637 void const *elem 606 void const *elem
638 ) { 607 ) {
639 cx_linked_list *ll = (cx_linked_list *) list;
640 return cx_linked_list_find(((cx_linked_list *) list)->begin, 608 return cx_linked_list_find(((cx_linked_list *) list)->begin,
641 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 609 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
642 ll->follow_ptr, list->cmpfunc, elem); 610 list->cmpfunc, elem);
643 } 611 }
644 612
645 static void cx_ll_sort(struct cx_list_s *list) { 613 static void cx_ll_sort(struct cx_list_s *list) {
646 cx_linked_list *ll = (cx_linked_list *) list; 614 cx_linked_list *ll = (cx_linked_list *) list;
647 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 615 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
648 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 616 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
649 ll->follow_ptr, list->cmpfunc); 617 list->cmpfunc);
650 } 618 }
651 619
652 static void cx_ll_reverse(struct cx_list_s *list) { 620 static void cx_ll_reverse(struct cx_list_s *list) {
653 cx_linked_list *ll = (cx_linked_list *) list; 621 cx_linked_list *ll = (cx_linked_list *) list;
654 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 622 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
660 ) { 628 ) {
661 cx_linked_list *left = (cx_linked_list *) list; 629 cx_linked_list *left = (cx_linked_list *) list;
662 cx_linked_list *right = (cx_linked_list *) other; 630 cx_linked_list *right = (cx_linked_list *) other;
663 return cx_linked_list_compare(left->begin, right->begin, 631 return cx_linked_list_compare(left->begin, right->begin,
664 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 632 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
665 left->follow_ptr, right->follow_ptr, list->cmpfunc); 633 list->cmpfunc);
666 } 634 }
667 635
668 static bool cx_ll_iter_valid(void const *it) { 636 static bool cx_ll_iter_valid(void const *it) {
669 struct cx_iterator_s const *iter = it; 637 struct cx_iterator_s const *iter = it;
670 return iter->elem_handle != NULL; 638 return iter->elem_handle != NULL;
694 struct cx_iterator_s const *iter = it; 662 struct cx_iterator_s const *iter = it;
695 cx_linked_list_node *node = iter->elem_handle; 663 cx_linked_list_node *node = iter->elem_handle;
696 return node->payload; 664 return node->payload;
697 } 665 }
698 666
699 static void *cx_pll_iter_current(void const *it) {
700 struct cx_iterator_s const *iter = it;
701 cx_linked_list_node *node = iter->elem_handle;
702 return *(void **) node->payload;
703 }
704
705 static bool cx_ll_iter_flag_rm(void *it) { 667 static bool cx_ll_iter_flag_rm(void *it) {
706 struct cx_iterator_base_s *iter = it; 668 struct cx_iterator_base_s *iter = it;
707 if (iter->mutating) { 669 if (iter->mutating) {
708 iter->remove = true; 670 iter->remove = true;
709 return true; 671 return true;
727 iter.base.mutating = false; 689 iter.base.mutating = false;
728 iter.base.remove = false; 690 iter.base.remove = false;
729 return iter; 691 return iter;
730 } 692 }
731 693
732 static CxIterator cx_pll_iterator(
733 struct cx_list_s const *list,
734 size_t index
735 ) {
736 CxIterator iter = cx_ll_iterator(list, index);
737 iter.base.current = cx_pll_iter_current;
738 return iter;
739 }
740
741 static CxMutIterator cx_ll_mut_iterator( 694 static CxMutIterator cx_ll_mut_iterator(
742 struct cx_list_s *list, 695 struct cx_list_s *list,
743 size_t index 696 size_t index
744 ) { 697 ) {
745 CxIterator it = cx_ll_iterator(list, index); 698 CxIterator it = cx_ll_iterator(list, index);
746 it.base.mutating = true; 699 it.base.mutating = true;
747 700
748 // we know the iterators share the same memory layout 701 // we know the iterators share the same memory layout
749 CxMutIterator iter; 702 CxMutIterator iter;
750 memcpy(&iter, &it, sizeof(CxMutIterator)); 703 memcpy(&iter, &it, sizeof(CxMutIterator));
751 return iter;
752 }
753
754 static CxMutIterator cx_pll_mut_iterator(
755 struct cx_list_s *list,
756 size_t index
757 ) {
758 CxMutIterator iter = cx_ll_mut_iterator(list, index);
759 iter.base.current = cx_pll_iter_current;
760 return iter; 704 return iter;
761 } 705 }
762 706
763 static int cx_ll_insert_iter( 707 static int cx_ll_insert_iter(
764 CxMutIterator *iter, 708 CxMutIterator *iter,
776 } else { 720 } else {
777 int result = cx_ll_insert(list, list->size, elem); 721 int result = cx_ll_insert(list, list->size, elem);
778 iter->index = list->size; 722 iter->index = list->size;
779 return result; 723 return result;
780 } 724 }
781 }
782
783 static int cx_pll_insert_iter(
784 CxMutIterator *iter,
785 void const *elem,
786 int prepend
787 ) {
788 return cx_ll_insert_iter(iter, &elem, prepend);
789 } 725 }
790 726
791 static void cx_ll_destructor(CxList *list) { 727 static void cx_ll_destructor(CxList *list) {
792 cx_linked_list *ll = (cx_linked_list *) list; 728 cx_linked_list *ll = (cx_linked_list *) list;
793 729
815 cx_ll_reverse, 751 cx_ll_reverse,
816 cx_ll_iterator, 752 cx_ll_iterator,
817 cx_ll_mut_iterator, 753 cx_ll_mut_iterator,
818 }; 754 };
819 755
820 static cx_list_class cx_pointer_linked_list_class = {
821 cx_ll_destructor,
822 cx_pll_add,
823 cx_ll_add_array,
824 cx_pll_insert,
825 cx_ll_insert_array,
826 cx_pll_insert_iter,
827 cx_ll_remove,
828 cx_pll_at,
829 cx_ll_find,
830 cx_ll_sort,
831 cx_ll_compare,
832 cx_ll_reverse,
833 cx_pll_iterator,
834 cx_pll_mut_iterator,
835 };
836
837 CxList *cxLinkedListCreate( 756 CxList *cxLinkedListCreate(
838 CxAllocator const *allocator, 757 CxAllocator const *allocator,
839 CxListComparator comparator, 758 CxListComparator comparator,
840 size_t item_size 759 size_t item_size
841 ) { 760 ) {
842 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 761 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
843 if (list == NULL) return NULL; 762 if (list == NULL) return NULL;
844 763
845 list->follow_ptr = false;
846 list->base.cl = &cx_linked_list_class; 764 list->base.cl = &cx_linked_list_class;
847 list->base.allocator = allocator; 765 list->base.allocator = allocator;
848 list->base.cmpfunc = comparator; 766 list->base.cmpfunc = comparator;
849 list->base.itemsize = item_size; 767 list->base.itemsize = item_size;
850 list->base.capacity = SIZE_MAX; 768 list->base.capacity = SIZE_MAX;
851 769
852 return (CxList *) list; 770 return (CxList *) list;
853 } 771 }
854
855 CxList *cxPointerLinkedListCreate(
856 CxAllocator const *allocator,
857 CxListComparator comparator
858 ) {
859 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
860 if (list == NULL) return NULL;
861
862 list->follow_ptr = true;
863 list->base.cl = &cx_pointer_linked_list_class;
864 list->base.allocator = allocator;
865 list->base.cmpfunc = comparator;
866 list->base.itemsize = sizeof(void *);
867 list->base.capacity = SIZE_MAX;
868
869 return (CxList *) list;
870 }

Mercurial Repository: ucx

mercurial