comparison: src/linked_list.c
src/linked_list.c
- changeset 476
- 60ff4561dc04
- parent 475
- 31bf97fdbf71
- child 477
- 73a93c7a56ae
equal
deleted
inserted
replaced
| 475:31bf97fdbf71 | 476:60ff4561dc04 |
|---|---|
| 135 assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL); | 135 assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL); |
| 136 *begin = new_node; | 136 *begin = new_node; |
| 137 } | 137 } |
| 138 } | 138 } |
| 139 | 139 |
| 140 void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { | 140 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { |
| 141 assert(loc_next >= 0); | 141 assert(loc_next >= 0); |
| 142 assert(loc_prev >= 0 || begin != NULL); | 142 assert(loc_prev >= 0 || begin != NULL); |
| 143 | 143 |
| 144 // find adjacent nodes | 144 // find adjacent nodes |
| 145 void *next = CX_LL_PTR(node, loc_next); | 145 void *next = CX_LL_PTR(node, loc_next); |
| 148 prev = CX_LL_PTR(node, loc_prev); | 148 prev = CX_LL_PTR(node, loc_prev); |
| 149 } else { | 149 } else { |
| 150 prev = cx_linked_list_prev(*begin, loc_next, node); | 150 prev = cx_linked_list_prev(*begin, loc_next, node); |
| 151 } | 151 } |
| 152 | 152 |
| 153 // update links of adjacent nodes | 153 // update next pointer of prev node, or set begin |
| 154 if (prev != NULL) { | 154 if (prev == NULL) { |
| 155 if (begin != NULL) { | |
| 156 *begin = next; | |
| 157 } | |
| 158 } else { | |
| 155 CX_LL_PTR(prev, loc_next) = next; | 159 CX_LL_PTR(prev, loc_next) = next; |
| 156 } | 160 } |
| 157 if (next != NULL && loc_prev >= 0) { | 161 |
| 162 // update prev pointer of next node, or set end | |
| 163 if (next == NULL) { | |
| 164 if (end != NULL) { | |
| 165 *end = prev; | |
| 166 } | |
| 167 } else if (loc_prev >= 0) { | |
| 158 CX_LL_PTR(next, loc_prev) = prev; | 168 CX_LL_PTR(next, loc_prev) = prev; |
| 159 } | 169 } |
| 160 | |
| 161 // erase links of the target node | |
| 162 CX_LL_PTR(node, loc_next) = NULL; | |
| 163 if (loc_prev >= 0) { | |
| 164 CX_LL_PTR(node, loc_prev) = NULL; | |
| 165 } | |
| 166 | |
| 167 // update begin, if required | |
| 168 if (*begin == node) { | |
| 169 *begin = next; | |
| 170 } | |
| 171 | |
| 172 // update end, if required | |
| 173 if (end != NULL && *end == node) { | |
| 174 *end = prev; | |
| 175 } | |
| 176 | |
| 177 return prev == NULL ? next : prev; | |
| 178 } | 170 } |
| 179 | 171 |
| 180 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { | 172 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { |
| 181 assert(loc_next >= 0); | 173 assert(loc_next >= 0); |
| 182 size_t size = 0; | 174 size_t size = 0; |
| 237 free(sorted); | 229 free(sorted); |
| 238 } | 230 } |
| 239 return ret; | 231 return ret; |
| 240 } | 232 } |
| 241 | 233 |
| 242 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, | 234 void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */ |
| 243 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { | 235 void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, |
| 236 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { | |
| 244 assert(begin != NULL); | 237 assert(begin != NULL); |
| 245 assert(loc_next >= 0); | 238 assert(loc_next >= 0); |
| 246 assert(loc_data >= 0); | 239 assert(loc_data >= 0); |
| 247 assert(cmp_func); | 240 assert(cmp_func); |
| 248 | 241 |
| 422 cx_linked_list_node *node = cx_ll_node_at(ll, index); | 415 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 423 | 416 |
| 424 // out-of-bounds check | 417 // out-of-bounds check |
| 425 if (node == NULL) return 1; | 418 if (node == NULL) return 1; |
| 426 | 419 |
| 427 // change left side connection | 420 // remove |
| 428 if (node->prev == NULL) { | 421 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, |
| 429 ll->begin = node->next; | 422 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); |
| 430 } else { | |
| 431 node->prev->next = node->next; | |
| 432 } | |
| 433 | |
| 434 // change right side connection | |
| 435 if (node->next == NULL) { | |
| 436 ll->end = node->prev; | |
| 437 } else { | |
| 438 node->next->prev = node->prev; | |
| 439 } | |
| 440 | 423 |
| 441 // adjust size | 424 // adjust size |
| 442 list->size--; | 425 list->size--; |
| 443 | 426 |
| 444 // free and return | 427 // free and return |
