comparison: src/linked_list.c
src/linked_list.c
- changeset 508
- 8aea65ae1eaf
- parent 503
- a89857072ace
- child 509
- 0d3c6075f82c
equal
deleted
inserted
replaced
| 507:2e8878770de0 | 508:8aea65ae1eaf |
|---|---|
| 38 #define ll_next(node) CX_LL_PTR(node, loc_next) | 38 #define ll_next(node) CX_LL_PTR(node, loc_next) |
| 39 #define ll_advance(node) CX_LL_PTR(node, loc_advance) | 39 #define ll_advance(node) CX_LL_PTR(node, loc_advance) |
| 40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) | 40 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) |
| 41 | 41 |
| 42 void *cx_linked_list_at( | 42 void *cx_linked_list_at( |
| 43 void *start, | 43 void const *start, |
| 44 size_t start_index, | 44 size_t start_index, |
| 45 ptrdiff_t loc_advance, | 45 ptrdiff_t loc_advance, |
| 46 size_t index | 46 size_t index |
| 47 ) { | 47 ) { |
| 48 assert(start != NULL); | 48 assert(start != NULL); |
| 49 assert(loc_advance >= 0); | 49 assert(loc_advance >= 0); |
| 50 size_t i = start_index; | 50 size_t i = start_index; |
| 51 void *cur = start; | 51 void const *cur = start; |
| 52 while (i != index && cur != NULL) { | 52 while (i != index && cur != NULL) { |
| 53 cur = ll_advance(cur); | 53 cur = ll_advance(cur); |
| 54 i < index ? i++ : i--; | 54 i < index ? i++ : i--; |
| 55 } | 55 } |
| 56 return cur; | 56 return (void *) cur; |
| 57 } | 57 } |
| 58 | 58 |
| 59 size_t cx_linked_list_find( | 59 size_t cx_linked_list_find( |
| 60 void const *start, | 60 void const *start, |
| 61 ptrdiff_t loc_advance, | 61 ptrdiff_t loc_advance, |
| 81 } while (node != NULL); | 81 } while (node != NULL); |
| 82 return index; | 82 return index; |
| 83 } | 83 } |
| 84 | 84 |
| 85 void *cx_linked_list_first( | 85 void *cx_linked_list_first( |
| 86 void *node, | 86 void const *node, |
| 87 ptrdiff_t loc_prev | 87 ptrdiff_t loc_prev |
| 88 ) { | 88 ) { |
| 89 return cx_linked_list_last(node, loc_prev); | 89 return cx_linked_list_last(node, loc_prev); |
| 90 } | 90 } |
| 91 | 91 |
| 92 void *cx_linked_list_last( | 92 void *cx_linked_list_last( |
| 93 void *node, | 93 void const *node, |
| 94 ptrdiff_t loc_next | 94 ptrdiff_t loc_next |
| 95 ) { | 95 ) { |
| 96 assert(node != NULL); | 96 assert(node != NULL); |
| 97 assert(loc_next >= 0); | 97 assert(loc_next >= 0); |
| 98 | 98 |
| 99 void *cur = node; | 99 void const *cur = node; |
| 100 void *last; | 100 void const *last; |
| 101 do { | 101 do { |
| 102 last = cur; | 102 last = cur; |
| 103 } while ((cur = ll_next(cur)) != NULL); | 103 } while ((cur = ll_next(cur)) != NULL); |
| 104 | 104 |
| 105 return last; | 105 return (void *) last; |
| 106 } | 106 } |
| 107 | 107 |
| 108 void *cx_linked_list_prev( | 108 void *cx_linked_list_prev( |
| 109 void *begin, | 109 void const *begin, |
| 110 ptrdiff_t loc_next, | 110 ptrdiff_t loc_next, |
| 111 void *node | 111 void const *node |
| 112 ) { | 112 ) { |
| 113 assert(begin != NULL); | 113 assert(begin != NULL); |
| 114 assert(node != NULL); | 114 assert(node != NULL); |
| 115 assert(loc_next >= 0); | 115 assert(loc_next >= 0); |
| 116 if (begin == node) return NULL; | 116 if (begin == node) return NULL; |
| 117 void *cur = begin; | 117 void const *cur = begin; |
| 118 void *next; | 118 void const *next; |
| 119 while (1) { | 119 while (1) { |
| 120 next = ll_next(cur); | 120 next = ll_next(cur); |
| 121 if (next == node) return cur; | 121 if (next == node) return (void *) cur; |
| 122 cur = next; | 122 cur = next; |
| 123 } | 123 } |
| 124 } | 124 } |
| 125 | 125 |
| 126 void cx_linked_list_link( | 126 void cx_linked_list_link( |
| 292 CxListComparator cmp_func | 292 CxListComparator cmp_func |
| 293 ) { | 293 ) { |
| 294 const size_t sbo_len = 1024; | 294 const size_t sbo_len = 1024; |
| 295 void *sbo[sbo_len]; | 295 void *sbo[sbo_len]; |
| 296 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; | 296 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; |
| 297 if (sorted == NULL) abort(); | |
| 297 void *rc, *lc; | 298 void *rc, *lc; |
| 298 | 299 |
| 299 lc = ls; | 300 lc = ls; |
| 300 rc = le; | 301 rc = le; |
| 301 size_t n = 0; | 302 size_t n = 0; |
| 770 cxFree(list->allocator, list); | 771 cxFree(list->allocator, list); |
| 771 return NULL; | 772 return NULL; |
| 772 } | 773 } |
| 773 | 774 |
| 774 CxList *cxLinkedListCreate( | 775 CxList *cxLinkedListCreate( |
| 775 CxAllocator *allocator, | 776 CxAllocator const *allocator, |
| 776 CxListComparator comparator, | 777 CxListComparator comparator, |
| 777 size_t item_size | 778 size_t item_size |
| 778 ) { | 779 ) { |
| 779 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); | 780 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
| 780 if (list == NULL) | 781 if (list == NULL) |
| 789 | 790 |
| 790 return (CxList *) list; | 791 return (CxList *) list; |
| 791 } | 792 } |
| 792 | 793 |
| 793 CxList *cxPointerLinkedListCreate( | 794 CxList *cxPointerLinkedListCreate( |
| 794 CxAllocator *allocator, | 795 CxAllocator const *allocator, |
| 795 CxListComparator comparator | 796 CxListComparator comparator |
| 796 ) { | 797 ) { |
| 797 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); | 798 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); |
| 798 if (list == NULL) | 799 if (list == NULL) |
| 799 return NULL; | 800 return NULL; |
| 807 | 808 |
| 808 return (CxList *) list; | 809 return (CxList *) list; |
| 809 } | 810 } |
| 810 | 811 |
| 811 CxList *cxLinkedListFromArray( | 812 CxList *cxLinkedListFromArray( |
| 812 CxAllocator *allocator, | 813 CxAllocator const *allocator, |
| 813 CxListComparator comparator, | 814 CxListComparator comparator, |
| 814 size_t item_size, | 815 size_t item_size, |
| 815 size_t num_items, | 816 size_t num_items, |
| 816 void const *array | 817 void const *array |
| 817 ) { | 818 ) { |
