Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 473
1bd4b8c28722
parent 469
0458bff0b1cd
child 474
9c1fccda16bc
equal deleted inserted replaced
472:18f964adad1b 473:1bd4b8c28722
34 /* LOW LEVEL LINKED LIST FUNCTIONS */ 34 /* LOW LEVEL LINKED LIST FUNCTIONS */
35 35
36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off)) 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
37 37
38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { 38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
39 assert(start != NULL);
40 assert(loc_advance >= 0);
39 size_t i = start_index; 41 size_t i = start_index;
40 void *cur = start; 42 void *cur = start;
41 while (i != index && cur != NULL) { 43 while (i != index && cur != NULL) {
42 cur = CX_LL_PTR(cur, loc_advance); 44 cur = CX_LL_PTR(cur, loc_advance);
43 i < index ? i++ : i--; 45 i < index ? i++ : i--;
44 } 46 }
45 return cur; 47 return cur;
46 } 48 }
47 49
48 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) { 50 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
51 assert(loc_next >= 0);
49 if (begin == NULL) 52 if (begin == NULL)
50 return NULL; 53 return NULL;
51 54
52 void *cur = begin; 55 void *cur = begin;
53 void *last; 56 void *last;
56 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL); 59 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
57 60
58 return last; 61 return last;
59 } 62 }
60 63
64 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
65 assert(begin != NULL);
66 assert(loc_next >= 0);
67 if (begin == node) return NULL;
68 void *cur = begin;
69 void *next;
70 while (1) {
71 next = CX_LL_PTR(cur, loc_next);
72 if (next == node) return cur;
73 cur = next;
74 }
75 }
76
61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { 77 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
78 assert(loc_next >= 0);
62 void *last; 79 void *last;
63 if (end == NULL) { 80 if (end == NULL) {
64 assert(begin != NULL); 81 assert(begin != NULL);
65 last = cx_linked_list_last(*begin, loc_next); 82 last = cx_linked_list_last(*begin, loc_next);
66 } else { 83 } else {
83 if (loc_prev >= 0) { 100 if (loc_prev >= 0) {
84 CX_LL_PTR(new_node, loc_prev) = last; 101 CX_LL_PTR(new_node, loc_prev) = last;
85 } 102 }
86 } 103 }
87 104
105 void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
106 assert(loc_next >= 0);
107 assert(loc_prev >= 0 || begin != NULL);
108
109 // find adjacent nodes
110 void *next = CX_LL_PTR(node, loc_next);
111 void *prev;
112 if (loc_prev >= 0) {
113 prev = CX_LL_PTR(node, loc_prev);
114 } else {
115 prev = cx_linked_list_prev(*begin, loc_next, node);
116 }
117
118 // update links of adjacent nodes
119 if (prev != NULL) {
120 CX_LL_PTR(prev, loc_next) = next;
121 }
122 if (next != NULL && loc_prev >= 0) {
123 CX_LL_PTR(next, loc_prev) = prev;
124 }
125
126 // erase links of the target node
127 CX_LL_PTR(node, loc_next) = NULL;
128 if (loc_prev >= 0) {
129 CX_LL_PTR(node, loc_prev) = NULL;
130 }
131
132 // update begin, if required
133 if (*begin == node) {
134 *begin = next;
135 }
136
137 // update end, if required
138 if (end != NULL && *end == node) {
139 *end = prev;
140 }
141
142 return prev == NULL ? next : prev;
143 }
144
88 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { 145 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
146 assert(loc_next >= 0);
89 size_t size = 0; 147 size_t size = 0;
90 while (node != NULL) { 148 while (node != NULL) {
91 node = CX_LL_PTR(node, loc_next); 149 node = CX_LL_PTR(node, loc_next);
92 size++; 150 size++;
93 } 151 }
147 } 205 }
148 206
149 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, 207 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
150 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) { 208 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
151 assert(begin != NULL); 209 assert(begin != NULL);
210 assert(loc_next >= 0);
211 assert(loc_data >= 0);
212 assert(cmp_func);
152 213
153 void *lc, *ls, *le, *re; 214 void *lc, *ls, *le, *re;
154 215
155 // set start node 216 // set start node
156 ls = *begin; 217 ls = *begin;
199 } 260 }
200 261
201 #undef ll_next 262 #undef ll_next
202 #undef ll_data 263 #undef ll_data
203 264
265 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
266 assert(begin != NULL);
267 assert(loc_next >= 0);
268
269 // swap all links
270 void *prev = NULL;
271 void *cur = *begin;
272 while (cur != NULL) {
273 void *next = CX_LL_PTR(cur, loc_next);
274
275 CX_LL_PTR(cur, loc_next) = prev;
276 if (loc_prev >= 0) {
277 CX_LL_PTR(cur, loc_prev) = next;
278 }
279
280 prev = cur;
281 cur = next;
282 }
283
284 // update begin and end
285 if (end != NULL) {
286 *end = *begin;
287 }
288 *begin = prev;
289 }
290
204 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 291 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
205 292
206 typedef struct cx_linked_list_node cx_linked_list_node; 293 typedef struct cx_linked_list_node cx_linked_list_node;
207 struct cx_linked_list_node { 294 struct cx_linked_list_node {
208 cx_linked_list_node *prev; 295 cx_linked_list_node *prev;

Mercurial Repository: ucx

mercurial