comparison: src/linked_list.c
src/linked_list.c
- changeset 1162
- e3bb67b72d33
- parent 1113
- dce04550fbef
- child 1225
- 086e63c8dd06
equal
deleted
inserted
replaced
| 1161:747c4baed44f | 1162:e3bb67b72d33 |
|---|---|
| 54 i < index ? i++ : i--; | 54 i < index ? i++ : i--; |
| 55 } | 55 } |
| 56 return (void *) cur; | 56 return (void *) cur; |
| 57 } | 57 } |
| 58 | 58 |
| 59 ssize_t cx_linked_list_find( | 59 void *cx_linked_list_find( |
| 60 const void *start, | 60 const void *start, |
| 61 ptrdiff_t loc_advance, | 61 ptrdiff_t loc_advance, |
| 62 ptrdiff_t loc_data, | 62 ptrdiff_t loc_data, |
| 63 cx_compare_func cmp_func, | 63 cx_compare_func cmp_func, |
| 64 const void *elem | 64 const void *elem, |
| 65 ) { | 65 size_t *found_index |
| 66 void *dummy; | 66 ) { |
| 67 return cx_linked_list_find_node( | |
| 68 &dummy, start, | |
| 69 loc_advance, loc_data, | |
| 70 cmp_func, elem | |
| 71 ); | |
| 72 } | |
| 73 | |
| 74 ssize_t cx_linked_list_find_node( | |
| 75 void **result, | |
| 76 const void *start, | |
| 77 ptrdiff_t loc_advance, | |
| 78 ptrdiff_t loc_data, | |
| 79 cx_compare_func cmp_func, | |
| 80 const void *elem | |
| 81 ) { | |
| 82 assert(result != NULL); | |
| 83 assert(start != NULL); | 67 assert(start != NULL); |
| 84 assert(loc_advance >= 0); | 68 assert(loc_advance >= 0); |
| 85 assert(loc_data >= 0); | 69 assert(loc_data >= 0); |
| 86 assert(cmp_func); | 70 assert(cmp_func); |
| 87 | 71 |
| 88 const void *node = start; | 72 void *node = (void*) start; |
| 89 ssize_t index = 0; | 73 size_t index = 0; |
| 90 do { | 74 do { |
| 91 void *current = ll_data(node); | 75 void *current = ll_data(node); |
| 92 if (cmp_func(current, elem) == 0) { | 76 if (cmp_func(current, elem) == 0) { |
| 93 *result = (void *) node; | 77 if (found_index != NULL) { |
| 94 return index; | 78 *found_index = index; |
| 79 } | |
| 80 return node; | |
| 95 } | 81 } |
| 96 node = ll_advance(node); | 82 node = ll_advance(node); |
| 97 index++; | 83 index++; |
| 98 } while (node != NULL); | 84 } while (node != NULL); |
| 99 *result = NULL; | 85 return NULL; |
| 100 return -1; | |
| 101 } | 86 } |
| 102 | 87 |
| 103 void *cx_linked_list_first( | 88 void *cx_linked_list_first( |
| 104 const void *node, | 89 const void *node, |
| 105 ptrdiff_t loc_prev | 90 ptrdiff_t loc_prev |
| 928 cx_linked_list *ll = (cx_linked_list *) list; | 913 cx_linked_list *ll = (cx_linked_list *) list; |
| 929 cx_linked_list_node *node = cx_ll_node_at(ll, index); | 914 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 930 return node == NULL ? NULL : node->payload; | 915 return node == NULL ? NULL : node->payload; |
| 931 } | 916 } |
| 932 | 917 |
| 933 static ssize_t cx_ll_find_remove( | 918 static size_t cx_ll_find_remove( |
| 934 struct cx_list_s *list, | 919 struct cx_list_s *list, |
| 935 const void *elem, | 920 const void *elem, |
| 936 bool remove | 921 bool remove |
| 937 ) { | 922 ) { |
| 923 size_t index; | |
| 924 cx_linked_list *ll = ((cx_linked_list *) list); | |
| 925 cx_linked_list_node *node = cx_linked_list_find( | |
| 926 ll->begin, | |
| 927 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | |
| 928 list->collection.cmpfunc, elem, | |
| 929 &index | |
| 930 ); | |
| 931 if (node == NULL) { | |
| 932 return list->collection.size; | |
| 933 } | |
| 938 if (remove) { | 934 if (remove) { |
| 939 cx_linked_list *ll = ((cx_linked_list *) list); | 935 cx_invoke_destructor(list, node->payload); |
| 940 cx_linked_list_node *node; | 936 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, |
| 941 ssize_t index = cx_linked_list_find_node( | 937 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); |
| 942 (void **) &node, | 938 list->collection.size--; |
| 943 ll->begin, | 939 cxFree(list->collection.allocator, node); |
| 944 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 940 } |
| 945 list->collection.cmpfunc, elem | 941 return index; |
| 946 ); | |
| 947 if (node != NULL) { | |
| 948 cx_invoke_destructor(list, node->payload); | |
| 949 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, | |
| 950 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); | |
| 951 list->collection.size--; | |
| 952 cxFree(list->collection.allocator, node); | |
| 953 } | |
| 954 return index; | |
| 955 } else { | |
| 956 return cx_linked_list_find( | |
| 957 ((cx_linked_list *) list)->begin, | |
| 958 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | |
| 959 list->collection.cmpfunc, elem | |
| 960 ); | |
| 961 } | |
| 962 } | 942 } |
| 963 | 943 |
| 964 static void cx_ll_sort(struct cx_list_s *list) { | 944 static void cx_ll_sort(struct cx_list_s *list) { |
| 965 cx_linked_list *ll = (cx_linked_list *) list; | 945 cx_linked_list *ll = (cx_linked_list *) list; |
| 966 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, | 946 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, |
