1.1 --- a/src/linked_list.c Fri Oct 08 18:58:49 2021 +0200
1.2 +++ b/src/linked_list.c Fri Oct 08 19:47:31 2021 +0200
1.3 @@ -36,6 +36,8 @@
1.4 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
1.5
1.6 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
1.7 + assert(start != NULL);
1.8 + assert(loc_advance >= 0);
1.9 size_t i = start_index;
1.10 void *cur = start;
1.11 while (i != index && cur != NULL) {
1.12 @@ -46,6 +48,7 @@
1.13 }
1.14
1.15 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
1.16 + assert(loc_next >= 0);
1.17 if (begin == NULL)
1.18 return NULL;
1.19
1.20 @@ -58,7 +61,21 @@
1.21 return last;
1.22 }
1.23
1.24 +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
1.25 + assert(begin != NULL);
1.26 + assert(loc_next >= 0);
1.27 + if (begin == node) return NULL;
1.28 + void *cur = begin;
1.29 + void *next;
1.30 + while (1) {
1.31 + next = CX_LL_PTR(cur, loc_next);
1.32 + if (next == node) return cur;
1.33 + cur = next;
1.34 + }
1.35 +}
1.36 +
1.37 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
1.38 + assert(loc_next >= 0);
1.39 void *last;
1.40 if (end == NULL) {
1.41 assert(begin != NULL);
1.42 @@ -85,7 +102,48 @@
1.43 }
1.44 }
1.45
1.46 +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
1.47 + assert(loc_next >= 0);
1.48 + assert(loc_prev >= 0 || begin != NULL);
1.49 +
1.50 + // find adjacent nodes
1.51 + void *next = CX_LL_PTR(node, loc_next);
1.52 + void *prev;
1.53 + if (loc_prev >= 0) {
1.54 + prev = CX_LL_PTR(node, loc_prev);
1.55 + } else {
1.56 + prev = cx_linked_list_prev(*begin, loc_next, node);
1.57 + }
1.58 +
1.59 + // update links of adjacent nodes
1.60 + if (prev != NULL) {
1.61 + CX_LL_PTR(prev, loc_next) = next;
1.62 + }
1.63 + if (next != NULL && loc_prev >= 0) {
1.64 + CX_LL_PTR(next, loc_prev) = prev;
1.65 + }
1.66 +
1.67 + // erase links of the target node
1.68 + CX_LL_PTR(node, loc_next) = NULL;
1.69 + if (loc_prev >= 0) {
1.70 + CX_LL_PTR(node, loc_prev) = NULL;
1.71 + }
1.72 +
1.73 + // update begin, if required
1.74 + if (*begin == node) {
1.75 + *begin = next;
1.76 + }
1.77 +
1.78 + // update end, if required
1.79 + if (end != NULL && *end == node) {
1.80 + *end = prev;
1.81 + }
1.82 +
1.83 + return prev == NULL ? next : prev;
1.84 +}
1.85 +
1.86 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
1.87 + assert(loc_next >= 0);
1.88 size_t size = 0;
1.89 while (node != NULL) {
1.90 node = CX_LL_PTR(node, loc_next);
1.91 @@ -149,6 +207,9 @@
1.92 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
1.93 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
1.94 assert(begin != NULL);
1.95 + assert(loc_next >= 0);
1.96 + assert(loc_data >= 0);
1.97 + assert(cmp_func);
1.98
1.99 void *lc, *ls, *le, *re;
1.100
1.101 @@ -201,6 +262,32 @@
1.102 #undef ll_next
1.103 #undef ll_data
1.104
1.105 +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
1.106 + assert(begin != NULL);
1.107 + assert(loc_next >= 0);
1.108 +
1.109 + // swap all links
1.110 + void *prev = NULL;
1.111 + void *cur = *begin;
1.112 + while (cur != NULL) {
1.113 + void *next = CX_LL_PTR(cur, loc_next);
1.114 +
1.115 + CX_LL_PTR(cur, loc_next) = prev;
1.116 + if (loc_prev >= 0) {
1.117 + CX_LL_PTR(cur, loc_prev) = next;
1.118 + }
1.119 +
1.120 + prev = cur;
1.121 + cur = next;
1.122 + }
1.123 +
1.124 + // update begin and end
1.125 + if (end != NULL) {
1.126 + *end = *begin;
1.127 + }
1.128 + *begin = prev;
1.129 +}
1.130 +
1.131 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
1.132
1.133 typedef struct cx_linked_list_node cx_linked_list_node;
