Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 890
54565fd74e74
parent 880
54133f14043f
child 919
75da57d4634e
equal deleted inserted replaced
889:f549fd9fbd8f 890:54565fd74e74
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) (((char*)(node))+loc_data) 41 #define ll_data(node) (((char*)(node))+loc_data)
42 42
43 void *cx_linked_list_at( 43 void *cx_linked_list_at(
44 void const *start, 44 const void *start,
45 size_t start_index, 45 size_t start_index,
46 ptrdiff_t loc_advance, 46 ptrdiff_t loc_advance,
47 size_t index 47 size_t index
48 ) { 48 ) {
49 assert(start != NULL); 49 assert(start != NULL);
50 assert(loc_advance >= 0); 50 assert(loc_advance >= 0);
51 size_t i = start_index; 51 size_t i = start_index;
52 void const *cur = start; 52 const void *cur = start;
53 while (i != index && cur != NULL) { 53 while (i != index && cur != NULL) {
54 cur = ll_advance(cur); 54 cur = ll_advance(cur);
55 i < index ? i++ : i--; 55 i < index ? i++ : i--;
56 } 56 }
57 return (void *) cur; 57 return (void *) cur;
58 } 58 }
59 59
60 ssize_t cx_linked_list_find( 60 ssize_t cx_linked_list_find(
61 void const *start, 61 const void *start,
62 ptrdiff_t loc_advance, 62 ptrdiff_t loc_advance,
63 ptrdiff_t loc_data, 63 ptrdiff_t loc_data,
64 cx_compare_func cmp_func, 64 cx_compare_func cmp_func,
65 void const *elem 65 const void *elem
66 ) { 66 ) {
67 void *dummy; 67 void *dummy;
68 return cx_linked_list_find_node( 68 return cx_linked_list_find_node(
69 &dummy, start, 69 &dummy, start,
70 loc_advance, loc_data, 70 loc_advance, loc_data,
72 ); 72 );
73 } 73 }
74 74
75 ssize_t cx_linked_list_find_node( 75 ssize_t cx_linked_list_find_node(
76 void **result, 76 void **result,
77 void const *start, 77 const void *start,
78 ptrdiff_t loc_advance, 78 ptrdiff_t loc_advance,
79 ptrdiff_t loc_data, 79 ptrdiff_t loc_data,
80 cx_compare_func cmp_func, 80 cx_compare_func cmp_func,
81 void const *elem 81 const void *elem
82 ) { 82 ) {
83 assert(result != NULL); 83 assert(result != NULL);
84 assert(start != NULL); 84 assert(start != NULL);
85 assert(loc_advance >= 0); 85 assert(loc_advance >= 0);
86 assert(loc_data >= 0); 86 assert(loc_data >= 0);
87 assert(cmp_func); 87 assert(cmp_func);
88 88
89 void const *node = start; 89 const void *node = start;
90 ssize_t index = 0; 90 ssize_t index = 0;
91 do { 91 do {
92 void *current = ll_data(node); 92 void *current = ll_data(node);
93 if (cmp_func(current, elem) == 0) { 93 if (cmp_func(current, elem) == 0) {
94 *result = (void*) node; 94 *result = (void*) node;
100 *result = NULL; 100 *result = NULL;
101 return -1; 101 return -1;
102 } 102 }
103 103
104 void *cx_linked_list_first( 104 void *cx_linked_list_first(
105 void const *node, 105 const void *node,
106 ptrdiff_t loc_prev 106 ptrdiff_t loc_prev
107 ) { 107 ) {
108 return cx_linked_list_last(node, loc_prev); 108 return cx_linked_list_last(node, loc_prev);
109 } 109 }
110 110
111 void *cx_linked_list_last( 111 void *cx_linked_list_last(
112 void const *node, 112 const void *node,
113 ptrdiff_t loc_next 113 ptrdiff_t loc_next
114 ) { 114 ) {
115 assert(node != NULL); 115 assert(node != NULL);
116 assert(loc_next >= 0); 116 assert(loc_next >= 0);
117 117
118 void const *cur = node; 118 const void *cur = node;
119 void const *last; 119 const void *last;
120 do { 120 do {
121 last = cur; 121 last = cur;
122 } while ((cur = ll_next(cur)) != NULL); 122 } while ((cur = ll_next(cur)) != NULL);
123 123
124 return (void *) last; 124 return (void *) last;
125 } 125 }
126 126
127 void *cx_linked_list_prev( 127 void *cx_linked_list_prev(
128 void const *begin, 128 const void *begin,
129 ptrdiff_t loc_next, 129 ptrdiff_t loc_next,
130 void const *node 130 const void *node
131 ) { 131 ) {
132 assert(begin != NULL); 132 assert(begin != NULL);
133 assert(node != NULL); 133 assert(node != NULL);
134 assert(loc_next >= 0); 134 assert(loc_next >= 0);
135 if (begin == node) return NULL; 135 if (begin == node) return NULL;
136 void const *cur = begin; 136 const void *cur = begin;
137 void const *next; 137 const void *next;
138 while (1) { 138 while (1) {
139 next = ll_next(cur); 139 next = ll_next(cur);
140 if (next == node) return (void *) cur; 140 if (next == node) return (void *) cur;
141 cur = next; 141 cur = next;
142 } 142 }
374 ll_prev(next) = prev; 374 ll_prev(next) = prev;
375 } 375 }
376 } 376 }
377 377
378 size_t cx_linked_list_size( 378 size_t cx_linked_list_size(
379 void const *node, 379 const void *node,
380 ptrdiff_t loc_next 380 ptrdiff_t loc_next
381 ) { 381 ) {
382 assert(loc_next >= 0); 382 assert(loc_next >= 0);
383 size_t size = 0; 383 size_t size = 0;
384 while (node != NULL) { 384 while (node != NULL) {
512 if (end) *end = sorted_end; 512 if (end) *end = sorted_end;
513 } 513 }
514 } 514 }
515 515
516 int cx_linked_list_compare( 516 int cx_linked_list_compare(
517 void const *begin_left, 517 const void *begin_left,
518 void const *begin_right, 518 const void *begin_right,
519 ptrdiff_t loc_advance, 519 ptrdiff_t loc_advance,
520 ptrdiff_t loc_data, 520 ptrdiff_t loc_data,
521 cx_compare_func cmp_func 521 cx_compare_func cmp_func
522 ) { 522 ) {
523 void const *left = begin_left, *right = begin_right; 523 const void *left = begin_left, *right = begin_right;
524 524
525 while (left != NULL && right != NULL) { 525 while (left != NULL && right != NULL) {
526 void const *left_data = ll_data(left); 526 const void *left_data = ll_data(left);
527 void const *right_data = ll_data(right); 527 const void *right_data = ll_data(right);
528 int result = cmp_func(left_data, right_data); 528 int result = cmp_func(left_data, right_data);
529 if (result != 0) return result; 529 if (result != 0) return result;
530 left = ll_advance(left); 530 left = ll_advance(left);
531 right = ll_advance(right); 531 right = ll_advance(right);
532 } 532 }
585 cx_linked_list_node *begin; 585 cx_linked_list_node *begin;
586 cx_linked_list_node *end; 586 cx_linked_list_node *end;
587 } cx_linked_list; 587 } cx_linked_list;
588 588
589 static cx_linked_list_node *cx_ll_node_at( 589 static cx_linked_list_node *cx_ll_node_at(
590 cx_linked_list const *list, 590 const cx_linked_list *list,
591 size_t index 591 size_t index
592 ) { 592 ) {
593 if (index >= list->base.collection.size) { 593 if (index >= list->base.collection.size) {
594 return NULL; 594 return NULL;
595 } else if (index > list->base.collection.size / 2) { 595 } else if (index > list->base.collection.size / 2) {
597 } else { 597 } else {
598 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 598 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
599 } 599 }
600 } 600 }
601 601
602 static cx_linked_list_node *cx_ll_malloc_node(struct cx_list_s const *list) { 602 static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
603 return cxMalloc(list->collection.allocator, 603 return cxMalloc(list->collection.allocator,
604 sizeof(cx_linked_list_node) + list->collection.elem_size); 604 sizeof(cx_linked_list_node) + list->collection.elem_size);
605 } 605 }
606 606
607 static int cx_ll_insert_at( 607 static int cx_ll_insert_at(
608 struct cx_list_s *list, 608 struct cx_list_s *list,
609 cx_linked_list_node *node, 609 cx_linked_list_node *node,
610 void const *elem 610 const void *elem
611 ) { 611 ) {
612 612
613 // create the new new_node 613 // create the new new_node
614 cx_linked_list_node *new_node = cx_ll_malloc_node(list); 614 cx_linked_list_node *new_node = cx_ll_malloc_node(list);
615 615
634 } 634 }
635 635
636 static size_t cx_ll_insert_array( 636 static size_t cx_ll_insert_array(
637 struct cx_list_s *list, 637 struct cx_list_s *list,
638 size_t index, 638 size_t index,
639 void const *array, 639 const void *array,
640 size_t n 640 size_t n
641 ) { 641 ) {
642 // out-of bounds and corner case check 642 // out-of bounds and corner case check
643 if (index > list->collection.size || n == 0) return 0; 643 if (index > list->collection.size || n == 0) return 0;
644 644
655 655
656 // we now know exactly where we are 656 // we now know exactly where we are
657 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 657 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
658 658
659 // we can add the remaining nodes and immediately advance to the inserted node 659 // we can add the remaining nodes and immediately advance to the inserted node
660 char const *source = array; 660 const char *source = array;
661 for (size_t i = 1; i < n; i++) { 661 for (size_t i = 1; i < n; i++) {
662 source += list->collection.elem_size; 662 source += list->collection.elem_size;
663 if (0 != cx_ll_insert_at(list, node, source)) { 663 if (0 != cx_ll_insert_at(list, node, source)) {
664 return i; 664 return i;
665 } 665 }
669 } 669 }
670 670
671 static int cx_ll_insert_element( 671 static int cx_ll_insert_element(
672 struct cx_list_s *list, 672 struct cx_list_s *list,
673 size_t index, 673 size_t index,
674 void const *element 674 const void *element
675 ) { 675 ) {
676 return 1 != cx_ll_insert_array(list, index, element, 1); 676 return 1 != cx_ll_insert_array(list, index, element, 1);
677 } 677 }
678 678
679 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; 679 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
680 680
681 static int cx_ll_insert_sorted_cmp_helper(void const *l, void const *r) { 681 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
682 cx_linked_list_node const *left = l; 682 const cx_linked_list_node *left = l;
683 cx_linked_list_node const *right = r; 683 const cx_linked_list_node *right = r;
684 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload); 684 return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
685 } 685 }
686 686
687 static size_t cx_ll_insert_sorted( 687 static size_t cx_ll_insert_sorted(
688 struct cx_list_s *list, 688 struct cx_list_s *list,
689 void const *array, 689 const void *array,
690 size_t n 690 size_t n
691 ) { 691 ) {
692 // special case 692 // special case
693 if (n == 0) return 0; 693 if (n == 0) return 0;
694 694
700 chain->prev = NULL; 700 chain->prev = NULL;
701 chain->next = NULL; 701 chain->next = NULL;
702 702
703 // add all elements from the array to that chain 703 // add all elements from the array to that chain
704 cx_linked_list_node *prev = chain; 704 cx_linked_list_node *prev = chain;
705 char const *src = array; 705 const char *src = array;
706 size_t inserted = 1; 706 size_t inserted = 1;
707 for (; inserted < n; inserted++) { 707 for (; inserted < n; inserted++) {
708 cx_linked_list_node *next = cx_ll_malloc_node(list); 708 cx_linked_list_node *next = cx_ll_malloc_node(list);
709 if (next == NULL) break; 709 if (next == NULL) break;
710 src += list->collection.elem_size; 710 src += list->collection.elem_size;
896 896
897 return 0; 897 return 0;
898 } 898 }
899 899
900 static void *cx_ll_at( 900 static void *cx_ll_at(
901 struct cx_list_s const *list, 901 const struct cx_list_s *list,
902 size_t index 902 size_t index
903 ) { 903 ) {
904 cx_linked_list *ll = (cx_linked_list *) list; 904 cx_linked_list *ll = (cx_linked_list *) list;
905 cx_linked_list_node *node = cx_ll_node_at(ll, index); 905 cx_linked_list_node *node = cx_ll_node_at(ll, index);
906 return node == NULL ? NULL : node->payload; 906 return node == NULL ? NULL : node->payload;
907 } 907 }
908 908
909 static ssize_t cx_ll_find_remove( 909 static ssize_t cx_ll_find_remove(
910 struct cx_list_s *list, 910 struct cx_list_s *list,
911 void const *elem, 911 const void *elem,
912 bool remove 912 bool remove
913 ) { 913 ) {
914 if (remove) { 914 if (remove) {
915 cx_linked_list *ll = ((cx_linked_list *) list); 915 cx_linked_list *ll = ((cx_linked_list *) list);
916 cx_linked_list_node *node; 916 cx_linked_list_node *node;
948 cx_linked_list *ll = (cx_linked_list *) list; 948 cx_linked_list *ll = (cx_linked_list *) list;
949 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 949 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
950 } 950 }
951 951
952 static int cx_ll_compare( 952 static int cx_ll_compare(
953 struct cx_list_s const *list, 953 const struct cx_list_s *list,
954 struct cx_list_s const *other 954 const struct cx_list_s *other
955 ) { 955 ) {
956 cx_linked_list *left = (cx_linked_list *) list; 956 cx_linked_list *left = (cx_linked_list *) list;
957 cx_linked_list *right = (cx_linked_list *) other; 957 cx_linked_list *right = (cx_linked_list *) other;
958 return cx_linked_list_compare(left->begin, right->begin, 958 return cx_linked_list_compare(left->begin, right->begin,
959 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 959 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
960 list->collection.cmpfunc); 960 list->collection.cmpfunc);
961 } 961 }
962 962
963 static bool cx_ll_iter_valid(void const *it) { 963 static bool cx_ll_iter_valid(const void *it) {
964 struct cx_iterator_s const *iter = it; 964 const struct cx_iterator_s *iter = it;
965 return iter->elem_handle != NULL; 965 return iter->elem_handle != NULL;
966 } 966 }
967 967
968 static void cx_ll_iter_next(void *it) { 968 static void cx_ll_iter_next(void *it) {
969 struct cx_iterator_s *iter = it; 969 struct cx_iterator_s *iter = it;
1004 cx_linked_list_node *node = iter->elem_handle; 1004 cx_linked_list_node *node = iter->elem_handle;
1005 iter->elem_handle = node->prev; 1005 iter->elem_handle = node->prev;
1006 } 1006 }
1007 } 1007 }
1008 1008
1009 static void *cx_ll_iter_current(void const *it) { 1009 static void *cx_ll_iter_current(const void *it) {
1010 struct cx_iterator_s const *iter = it; 1010 const struct cx_iterator_s *iter = it;
1011 cx_linked_list_node *node = iter->elem_handle; 1011 cx_linked_list_node *node = iter->elem_handle;
1012 return node->payload; 1012 return node->payload;
1013 } 1013 }
1014 1014
1015 static CxIterator cx_ll_iterator( 1015 static CxIterator cx_ll_iterator(
1016 struct cx_list_s const *list, 1016 const struct cx_list_s *list,
1017 size_t index, 1017 size_t index,
1018 bool backwards 1018 bool backwards
1019 ) { 1019 ) {
1020 CxIterator iter; 1020 CxIterator iter;
1021 iter.index = index; 1021 iter.index = index;
1022 iter.src_handle.c = list; 1022 iter.src_handle.c = list;
1023 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 1023 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index);
1024 iter.elem_size = list->collection.elem_size; 1024 iter.elem_size = list->collection.elem_size;
1025 iter.elem_count = list->collection.size; 1025 iter.elem_count = list->collection.size;
1026 iter.base.valid = cx_ll_iter_valid; 1026 iter.base.valid = cx_ll_iter_valid;
1027 iter.base.current = cx_ll_iter_current; 1027 iter.base.current = cx_ll_iter_current;
1028 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; 1028 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
1031 return iter; 1031 return iter;
1032 } 1032 }
1033 1033
1034 static int cx_ll_insert_iter( 1034 static int cx_ll_insert_iter(
1035 CxIterator *iter, 1035 CxIterator *iter,
1036 void const *elem, 1036 const void *elem,
1037 int prepend 1037 int prepend
1038 ) { 1038 ) {
1039 struct cx_list_s *list = iter->src_handle.m; 1039 struct cx_list_s *list = iter->src_handle.m;
1040 cx_linked_list_node *node = iter->elem_handle; 1040 cx_linked_list_node *node = iter->elem_handle;
1041 if (node != NULL) { 1041 if (node != NULL) {
1089 cx_ll_reverse, 1089 cx_ll_reverse,
1090 cx_ll_iterator, 1090 cx_ll_iterator,
1091 }; 1091 };
1092 1092
1093 CxList *cxLinkedListCreate( 1093 CxList *cxLinkedListCreate(
1094 CxAllocator const *allocator, 1094 const CxAllocator *allocator,
1095 cx_compare_func comparator, 1095 cx_compare_func comparator,
1096 size_t elem_size 1096 size_t elem_size
1097 ) { 1097 ) {
1098 if (allocator == NULL) { 1098 if (allocator == NULL) {
1099 allocator = cxDefaultAllocator; 1099 allocator = cxDefaultAllocator;

Mercurial Repository: ucx

mercurial