32 #include <assert.h> |
32 #include <assert.h> |
33 |
33 |
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 #define ll_prev(node) CX_LL_PTR(node, loc_prev) |
|
38 #define ll_next(node) CX_LL_PTR(node, loc_next) |
|
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)) |
37 |
41 |
38 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { |
42 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) { |
39 assert(start != NULL); |
43 assert(start != NULL); |
40 assert(loc_advance >= 0); |
44 assert(loc_advance >= 0); |
41 size_t i = start_index; |
45 size_t i = start_index; |
42 void *cur = start; |
46 void *cur = start; |
43 while (i != index && cur != NULL) { |
47 while (i != index && cur != NULL) { |
44 cur = CX_LL_PTR(cur, loc_advance); |
48 cur = ll_advance(cur); |
45 i < index ? i++ : i--; |
49 i < index ? i++ : i--; |
46 } |
50 } |
47 return cur; |
51 return cur; |
|
52 } |
|
53 |
|
54 size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr, |
|
55 CxListComparator cmp_func, void *elem) { |
|
56 assert(start != NULL); |
|
57 assert(loc_advance >= 0); |
|
58 assert(loc_data >= 0); |
|
59 assert(cmp_func); |
|
60 |
|
61 void *node = start; |
|
62 size_t index = 0; |
|
63 do { |
|
64 void *current = ll_data(node); |
|
65 if (cmp_func(current, elem) == 0) { |
|
66 return index; |
|
67 } |
|
68 node = ll_advance(node); |
|
69 index++; |
|
70 } while (node != NULL); |
|
71 return index; |
48 } |
72 } |
49 |
73 |
50 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) { |
74 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) { |
51 return cx_linked_list_last(node, loc_prev); |
75 return cx_linked_list_last(node, loc_prev); |
52 } |
76 } |
70 assert(loc_next >= 0); |
94 assert(loc_next >= 0); |
71 if (begin == node) return NULL; |
95 if (begin == node) return NULL; |
72 void *cur = begin; |
96 void *cur = begin; |
73 void *next; |
97 void *next; |
74 while (1) { |
98 while (1) { |
75 next = CX_LL_PTR(cur, loc_next); |
99 next = ll_next(cur); |
76 if (next == node) return cur; |
100 if (next == node) return cur; |
77 cur = next; |
101 cur = next; |
78 } |
102 } |
79 } |
103 } |
80 |
104 |
81 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { |
105 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { |
82 assert(new_node != NULL); |
106 assert(new_node != NULL); |
83 assert(loc_next >= 0); |
107 assert(loc_next >= 0); |
84 assert(CX_LL_PTR(new_node, loc_next) == NULL); |
108 assert(ll_next(new_node) == NULL); |
85 void *last; |
109 void *last; |
86 if (end == NULL) { |
110 if (end == NULL) { |
87 assert(begin != NULL); |
111 assert(begin != NULL); |
88 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); |
112 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); |
89 } else { |
113 } else { |
93 if (begin != NULL) { |
117 if (begin != NULL) { |
94 *begin = new_node; |
118 *begin = new_node; |
95 } |
119 } |
96 } else { |
120 } else { |
97 // if there is a last node, update its next pointer |
121 // if there is a last node, update its next pointer |
98 CX_LL_PTR(last, loc_next) = new_node; |
122 ll_next(last) = new_node; |
99 } |
123 } |
100 |
124 |
101 // if there is an end pointer, update it |
125 // if there is an end pointer, update it |
102 if (end != NULL) { |
126 if (end != NULL) { |
103 *end = new_node; |
127 *end = new_node; |
104 } |
128 } |
105 |
129 |
106 // if the nodes use a prev pointer, update it |
130 // if the nodes use a prev pointer, update it |
107 if (loc_prev >= 0) { |
131 if (loc_prev >= 0) { |
108 assert(CX_LL_PTR(new_node, loc_prev) == NULL); |
132 assert(ll_prev(new_node) == NULL); |
109 CX_LL_PTR(new_node, loc_prev) = last; |
133 ll_prev(new_node) = last; |
110 } |
134 } |
111 } |
135 } |
112 |
136 |
113 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { |
137 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { |
114 assert(new_node != NULL); |
138 assert(new_node != NULL); |
115 assert(loc_next >= 0); |
139 assert(loc_next >= 0); |
116 assert(CX_LL_PTR(new_node, loc_next) == NULL); |
140 assert(ll_next(new_node) == NULL); |
117 void *first; |
141 void *first; |
118 if (begin == NULL) { |
142 if (begin == NULL) { |
119 assert(end != NULL); |
143 assert(end != NULL); |
120 assert(loc_prev >= 0); |
144 assert(loc_prev >= 0); |
121 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev); |
145 first = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev); |
125 if (first == NULL) { |
149 if (first == NULL) { |
126 if (end != NULL) { |
150 if (end != NULL) { |
127 *end = new_node; |
151 *end = new_node; |
128 } |
152 } |
129 } else { |
153 } else { |
130 CX_LL_PTR(new_node, loc_next) = first; |
154 ll_next(new_node) = first; |
131 if (loc_prev >= 0) { |
155 if (loc_prev >= 0) { |
132 CX_LL_PTR(first, loc_prev) = new_node; |
156 ll_prev(first) = new_node; |
133 } |
157 } |
134 } |
158 } |
135 |
159 |
136 if (begin != NULL) { |
160 if (begin != NULL) { |
137 assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL); |
161 assert(loc_prev < 0 || ll_prev(new_node) == NULL); |
138 *begin = new_node; |
162 *begin = new_node; |
139 } |
163 } |
140 } |
164 } |
141 |
165 |
142 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { |
166 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) { |
143 assert(node != NULL); |
167 assert(node != NULL); |
144 assert(loc_next >= 0); |
168 assert(loc_next >= 0); |
145 assert(loc_prev >= 0 || begin != NULL); |
169 assert(loc_prev >= 0 || begin != NULL); |
146 |
170 |
147 // find adjacent nodes |
171 // find adjacent nodes |
148 void *next = CX_LL_PTR(node, loc_next); |
172 void *next = ll_next(node); |
149 void *prev; |
173 void *prev; |
150 if (loc_prev >= 0) { |
174 if (loc_prev >= 0) { |
151 prev = CX_LL_PTR(node, loc_prev); |
175 prev = ll_prev(node); |
152 } else { |
176 } else { |
153 prev = cx_linked_list_prev(*begin, loc_next, node); |
177 prev = cx_linked_list_prev(*begin, loc_next, node); |
154 } |
178 } |
155 |
179 |
156 // update next pointer of prev node, or set begin |
180 // update next pointer of prev node, or set begin |
157 if (prev == NULL) { |
181 if (prev == NULL) { |
158 if (begin != NULL) { |
182 if (begin != NULL) { |
159 *begin = next; |
183 *begin = next; |
160 } |
184 } |
161 } else { |
185 } else { |
162 CX_LL_PTR(prev, loc_next) = next; |
186 ll_next(prev) = next; |
163 } |
187 } |
164 |
188 |
165 // update prev pointer of next node, or set end |
189 // update prev pointer of next node, or set end |
166 if (next == NULL) { |
190 if (next == NULL) { |
167 if (end != NULL) { |
191 if (end != NULL) { |
168 *end = prev; |
192 *end = prev; |
169 } |
193 } |
170 } else if (loc_prev >= 0) { |
194 } else if (loc_prev >= 0) { |
171 CX_LL_PTR(next, loc_prev) = prev; |
195 ll_prev(next) = prev; |
172 } |
196 } |
173 } |
197 } |
174 |
198 |
175 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { |
199 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { |
176 assert(loc_next >= 0); |
200 assert(loc_next >= 0); |
177 size_t size = 0; |
201 size_t size = 0; |
178 while (node != NULL) { |
202 while (node != NULL) { |
179 node = CX_LL_PTR(node, loc_next); |
203 node = ll_next(node); |
180 size++; |
204 size++; |
181 } |
205 } |
182 return size; |
206 return size; |
183 } |
207 } |
184 |
|
185 #define ll_prev(node) CX_LL_PTR(node, loc_prev) |
|
186 #define ll_next(node) CX_LL_PTR(node, loc_next) |
|
187 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) |
|
188 |
208 |
189 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, |
209 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, |
190 ptrdiff_t loc_data, int follow_ptr, |
210 ptrdiff_t loc_data, int follow_ptr, |
191 size_t length, void *ls, void *le, void *re, |
211 size_t length, void *ls, void *le, void *re, |
192 CxListComparator cmp_func) { |
212 CxListComparator cmp_func) { |
288 } |
308 } |
289 if (end) *end = cx_linked_list_last(sorted, loc_next); |
309 if (end) *end = cx_linked_list_last(sorted, loc_next); |
290 } |
310 } |
291 } |
311 } |
292 |
312 |
293 #undef ll_next |
|
294 #undef ll_data |
|
295 |
|
296 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { |
313 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) { |
297 assert(begin != NULL); |
314 assert(begin != NULL); |
298 assert(loc_next >= 0); |
315 assert(loc_next >= 0); |
299 |
316 |
300 // swap all links |
317 // swap all links |
301 void *prev = NULL; |
318 void *prev = NULL; |
302 void *cur = *begin; |
319 void *cur = *begin; |
303 while (cur != NULL) { |
320 while (cur != NULL) { |
304 void *next = CX_LL_PTR(cur, loc_next); |
321 void *next = ll_next(cur); |
305 |
322 |
306 CX_LL_PTR(cur, loc_next) = prev; |
323 ll_next(cur) = prev; |
307 if (loc_prev >= 0) { |
324 if (loc_prev >= 0) { |
308 CX_LL_PTR(cur, loc_prev) = next; |
325 ll_prev(cur) = next; |
309 } |
326 } |
310 |
327 |
311 prev = cur; |
328 prev = cur; |
312 cur = next; |
329 cur = next; |
313 } |
330 } |
444 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
461 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
445 return node == NULL ? NULL : *(void **) node->payload; |
462 return node == NULL ? NULL : *(void **) node->payload; |
446 } |
463 } |
447 |
464 |
448 static size_t cx_ll_find(cx_list_s *list, void *elem) { |
465 static size_t cx_ll_find(cx_list_s *list, void *elem) { |
449 CxListComparator cmp = list->cmpfunc; |
466 return cx_linked_list_find(((cx_linked_list *) list)->begin, |
450 cx_linked_list *ll = (cx_linked_list *) list; |
467 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
451 |
468 0, list->cmpfunc, elem); |
452 size_t index; |
|
453 cx_linked_list_node *node = ll->begin; |
|
454 for (index = 0; index < list->size; index++) { |
|
455 void *current = node->payload; |
|
456 if (cmp(current, elem) == 0) { |
|
457 return index; |
|
458 } |
|
459 node = node->next; |
|
460 } |
|
461 return index; |
|
462 } |
469 } |
463 |
470 |
464 static size_t cx_pll_find(cx_list_s *list, void *elem) { |
471 static size_t cx_pll_find(cx_list_s *list, void *elem) { |
465 CxListComparator cmp = list->cmpfunc; |
472 return cx_linked_list_find(((cx_linked_list *) list)->begin, |
466 cx_linked_list *ll = (cx_linked_list *) list; |
473 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
467 |
474 1, list->cmpfunc, elem); |
468 size_t index; |
|
469 cx_linked_list_node *node = ll->begin; |
|
470 for (index = 0; index < list->size; index++) { |
|
471 void *current = *(void **) node->payload; |
|
472 if (cmp(current, elem) == 0) { |
|
473 return index; |
|
474 } |
|
475 node = node->next; |
|
476 } |
|
477 return index; |
|
478 } |
475 } |
479 |
476 |
480 static void cx_ll_sort(cx_list_s *list) { |
477 static void cx_ll_sort(cx_list_s *list) { |
481 cx_linked_list *ll = (cx_linked_list *) list; |
478 cx_linked_list *ll = (cx_linked_list *) list; |
482 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, |
479 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, |