467:95e42a963520 | 468:75ae1dccd101 |
---|---|
31 #include <string.h> | 31 #include <string.h> |
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 | 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 size_t i = start_index; | 39 size_t i = start_index; |
40 void *cur = start; | 40 void *cur = start; |
41 while (i != index && cur != NULL) { | 41 while (i != index && cur != NULL) { |
42 cur = *CX_LL_PTR(cur, loc_advance); | 42 cur = CX_LL_PTR(cur, loc_advance); |
43 i < index ? i++ : i--; | 43 i < index ? i++ : i--; |
44 } | 44 } |
45 return cur; | 45 return cur; |
46 } | 46 } |
47 | 47 |
51 | 51 |
52 void *cur = begin; | 52 void *cur = begin; |
53 void *last; | 53 void *last; |
54 do { | 54 do { |
55 last = cur; | 55 last = cur; |
56 } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL); | 56 } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL); |
57 | 57 |
58 return last; | 58 return last; |
59 } | 59 } |
60 | 60 |
61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { | 61 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) { |
69 if (last == NULL) { | 69 if (last == NULL) { |
70 assert(begin != NULL); | 70 assert(begin != NULL); |
71 *begin = new_node; | 71 *begin = new_node; |
72 } else { | 72 } else { |
73 // if there is a last node, update its next pointer | 73 // if there is a last node, update its next pointer |
74 void **next = CX_LL_PTR(last, loc_next); | 74 CX_LL_PTR(last, loc_next) = new_node; |
75 *next = new_node; | |
76 } | 75 } |
77 | 76 |
78 // if there is an end pointer, update it | 77 // if there is an end pointer, update it |
79 if (end != NULL) { | 78 if (end != NULL) { |
80 *end = cx_linked_list_last(new_node, loc_next); | 79 *end = cx_linked_list_last(new_node, loc_next); |
81 } | 80 } |
82 | 81 |
83 // if the nodes use a prev pointer, update it | 82 // if the nodes use a prev pointer, update it |
84 if (loc_prev >= 0) { | 83 if (loc_prev >= 0) { |
85 void **prev = CX_LL_PTR(new_node, loc_prev); | 84 CX_LL_PTR(new_node, loc_prev) = last; |
86 *prev = last; | 85 } |
87 } | 86 } |
88 } | 87 |
88 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) { | |
89 size_t size = 0; | |
90 while (node != NULL) { | |
91 node = CX_LL_PTR(node, loc_next); | |
92 size++; | |
93 } | |
94 return size; | |
95 } | |
96 | |
97 #define ll_prev(node) CX_LL_PTR(node, loc_prev) | |
98 #define ll_next(node) CX_LL_PTR(node, loc_next) | |
99 #define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data)) | |
100 | |
101 static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next, | |
102 ptrdiff_t loc_data, int follow_ptr, | |
103 size_t length, void *ls, void *le, void *re, | |
104 CxListComparator cmp_func) { | |
105 const size_t sbo_len = 1024; | |
106 void *sbo[sbo_len]; | |
107 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; | |
108 void *rc, *lc; | |
109 | |
110 lc = ls; | |
111 rc = le; | |
112 size_t n = 0; | |
113 while (lc && lc != le && rc != re) { | |
114 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { | |
115 sorted[n] = lc; | |
116 lc = ll_next(lc); | |
117 } else { | |
118 sorted[n] = rc; | |
119 rc = ll_next(rc); | |
120 } | |
121 n++; | |
122 } | |
123 while (lc && lc != le) { | |
124 sorted[n] = lc; | |
125 lc = ll_next(lc); | |
126 n++; | |
127 } | |
128 while (rc && rc != re) { | |
129 sorted[n] = rc; | |
130 rc = ll_next(rc); | |
131 n++; | |
132 } | |
133 | |
134 // Update pointer | |
135 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; | |
136 for (size_t i = 0; i < length - 1; i++) { | |
137 ll_next(sorted[i]) = sorted[i + 1]; | |
138 if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i]; | |
139 } | |
140 ll_next(sorted[length - 1]) = NULL; | |
141 | |
142 void *ret = sorted[0]; | |
143 if (sorted != sbo) { | |
144 free(sorted); | |
145 } | |
146 return ret; | |
147 } | |
148 | |
149 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) { | |
151 assert(begin != NULL); | |
152 | |
153 void *lc, *ls, *le, *re; | |
154 | |
155 // set start node | |
156 ls = *begin; | |
157 | |
158 // check how many elements are already sorted | |
159 lc = ls; | |
160 size_t ln = 1; | |
161 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { | |
162 lc = ll_next(lc); | |
163 ln++; | |
164 } | |
165 le = ll_next(lc); | |
166 | |
167 // if first unsorted node is NULL, the list is already completely sorted | |
168 if (le != NULL) { | |
169 void *rc; | |
170 size_t rn = 1; | |
171 rc = le; | |
172 // skip already sorted elements | |
173 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { | |
174 rc = ll_next(rc); | |
175 rn++; | |
176 } | |
177 re = ll_next(rc); | |
178 | |
179 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
180 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, | |
181 ln + rn, ls, le, re, cmp_func); | |
182 | |
183 // Something left? Sort it! | |
184 size_t remainder_length = cx_linked_list_size(re, loc_next); | |
185 if (remainder_length > 0) { | |
186 void *remainder = re; | |
187 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); | |
188 | |
189 // merge sorted list with (also sorted) remainder | |
190 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, | |
191 ln + rn + remainder_length, | |
192 sorted, remainder, NULL, cmp_func); | |
193 } else { | |
194 // no remainder - we've got our sorted list | |
195 *begin = sorted; | |
196 } | |
197 if (end) *end = cx_linked_list_last(sorted, loc_next); | |
198 } | |
199 } | |
200 | |
201 #undef ll_next | |
202 #undef ll_data | |
89 | 203 |
90 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ | 204 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ |
91 | 205 |
92 typedef struct cx_linked_list_node cx_linked_list_node; | 206 typedef struct cx_linked_list_node cx_linked_list_node; |
93 struct cx_linked_list_node { | 207 struct cx_linked_list_node { |
107 | 221 |
108 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) { | 222 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) { |
109 if (index >= list->base.size) { | 223 if (index >= list->base.size) { |
110 return NULL; | 224 return NULL; |
111 } else if (index > list->base.size / 2) { | 225 } else if (index > list->base.size / 2) { |
112 return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index); | 226 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); |
113 } else { | 227 } else { |
114 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); | 228 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); |
115 } | 229 } |
116 } | 230 } |
117 | 231 |
142 ll->end->next = node; | 256 ll->end->next = node; |
143 node->prev = ll->end; | 257 node->prev = ll->end; |
144 node->next = NULL; | 258 node->next = NULL; |
145 ll->end = node; | 259 ll->end = node; |
146 } | 260 } |
147 // check if this shall be the new start node | 261 // check if this shall be the new start node |
148 else if (index == 0) { | 262 else if (index == 0) { |
149 ll->begin->prev = node; | 263 ll->begin->prev = node; |
150 node->next = ll->begin; | 264 node->next = ll->begin; |
151 node->prev = NULL; | 265 node->prev = NULL; |
152 ll->begin = node; | 266 ll->begin = node; |
217 } | 331 } |
218 | 332 |
219 static void *cx_pll_at(cx_list_s *list, size_t index) { | 333 static void *cx_pll_at(cx_list_s *list, size_t index) { |
220 cx_linked_list *ll = (cx_linked_list *) list; | 334 cx_linked_list *ll = (cx_linked_list *) list; |
221 cx_linked_list_node *node = cx_ll_node_at(ll, index); | 335 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
222 return node == NULL ? NULL : *(void**)node->payload; | 336 return node == NULL ? NULL : *(void **) node->payload; |
223 } | 337 } |
224 | 338 |
225 static size_t cx_ll_find(cx_list_s *list, void *elem) { | 339 static size_t cx_ll_find(cx_list_s *list, void *elem) { |
226 CxListComparator cmp = list->cmpfunc; | 340 CxListComparator cmp = list->cmpfunc; |
227 cx_linked_list *ll = (cx_linked_list *) list; | 341 cx_linked_list *ll = (cx_linked_list *) list; |
243 cx_linked_list *ll = (cx_linked_list *) list; | 357 cx_linked_list *ll = (cx_linked_list *) list; |
244 | 358 |
245 size_t index; | 359 size_t index; |
246 cx_linked_list_node *node = ll->begin; | 360 cx_linked_list_node *node = ll->begin; |
247 for (index = 0; index < list->size; index++) { | 361 for (index = 0; index < list->size; index++) { |
248 void *current = *(void**)node->payload; | 362 void *current = *(void **) node->payload; |
249 if (cmp(current, elem) == 0) { | 363 if (cmp(current, elem) == 0) { |
250 return index; | 364 return index; |
251 } | 365 } |
252 node = node->next; | 366 node = node->next; |
253 } | 367 } |
261 } | 375 } |
262 | 376 |
263 static void *cx_pll_last(cx_list_s *list) { | 377 static void *cx_pll_last(cx_list_s *list) { |
264 cx_linked_list *ll = (cx_linked_list *) list; | 378 cx_linked_list *ll = (cx_linked_list *) list; |
265 cx_linked_list_node *last = ll->end; | 379 cx_linked_list_node *last = ll->end; |
266 return last == NULL ? NULL : *(void**)last->payload; | 380 return last == NULL ? NULL : *(void **) last->payload; |
267 } | 381 } |
268 | 382 |
269 static cx_list_class cx_linked_list_class = { | 383 static cx_list_class cx_linked_list_class = { |
270 cx_ll_add, | 384 cx_ll_add, |
271 cx_ll_insert, | 385 cx_ll_insert, |
308 return NULL; | 422 return NULL; |
309 | 423 |
310 list->base.cl = &cx_pointer_linked_list_class; | 424 list->base.cl = &cx_pointer_linked_list_class; |
311 list->base.allocator = allocator; | 425 list->base.allocator = allocator; |
312 list->base.cmpfunc = comparator; | 426 list->base.cmpfunc = comparator; |
313 list->base.itemsize = sizeof(void*); | 427 list->base.itemsize = sizeof(void *); |
314 list->base.capacity = SIZE_MAX; | 428 list->base.capacity = SIZE_MAX; |
315 list->base.size = 0; | 429 list->base.size = 0; |
316 | 430 |
317 list->begin = NULL; | 431 list->begin = NULL; |
318 list->end = NULL; | 432 list->end = NULL; |