24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 * POSSIBILITY OF SUCH DAMAGE. |
26 * POSSIBILITY OF SUCH DAMAGE. |
27 */ |
27 */ |
28 |
28 |
29 #include "ucx/list.h" |
29 #include "cx/list.h" |
30 |
30 |
31 UcxList *ucx_list_clone(UcxList *l, copy_func fnc, void *data) { |
31 #include <string.h> |
32 return ucx_list_clone_a(ucx_default_allocator(), l, fnc, data); |
32 |
33 } |
33 // <editor-fold desc="Store Pointers Functionality"> |
34 |
34 |
35 UcxList *ucx_list_clone_a(UcxAllocator *alloc, UcxList *l, |
35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; |
36 copy_func fnc, void *data) { |
36 |
37 UcxList *ret = NULL; |
37 static int cx_pl_cmpfunc( |
38 while (l) { |
38 void const *l, |
39 if (fnc) { |
39 void const *r |
40 ret = ucx_list_append_a(alloc, ret, fnc(l->data, data)); |
40 ) { |
|
41 void *const *lptr = l; |
|
42 void *const *rptr = r; |
|
43 void const *left = lptr == NULL ? NULL : *lptr; |
|
44 void const *right = rptr == NULL ? NULL : *rptr; |
|
45 return cx_pl_cmpfunc_impl(left, right); |
|
46 } |
|
47 |
|
48 static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) { |
|
49 // cast away const - this is the hacky thing |
|
50 struct cx_list_s *l = (struct cx_list_s *) list; |
|
51 cx_pl_cmpfunc_impl = l->cmpfunc; |
|
52 l->cmpfunc = cx_pl_cmpfunc; |
|
53 } |
|
54 |
|
55 static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) { |
|
56 // cast away const - this is the hacky thing |
|
57 struct cx_list_s *l = (struct cx_list_s *) list; |
|
58 l->cmpfunc = cx_pl_cmpfunc_impl; |
|
59 } |
|
60 |
|
61 static void cx_pl_destructor(struct cx_list_s *list) { |
|
62 list->climpl->destructor(list); |
|
63 } |
|
64 |
|
65 static int cx_pl_insert_element( |
|
66 struct cx_list_s *list, |
|
67 size_t index, |
|
68 void const *element |
|
69 ) { |
|
70 return list->climpl->insert_element(list, index, &element); |
|
71 } |
|
72 |
|
73 static size_t cx_pl_insert_array( |
|
74 struct cx_list_s *list, |
|
75 size_t index, |
|
76 void const *array, |
|
77 size_t n |
|
78 ) { |
|
79 return list->climpl->insert_array(list, index, array, n); |
|
80 } |
|
81 |
|
82 static int cx_pl_insert_iter( |
|
83 struct cx_mut_iterator_s *iter, |
|
84 void const *elem, |
|
85 int prepend |
|
86 ) { |
|
87 struct cx_list_s *list = iter->src_handle; |
|
88 return list->climpl->insert_iter(iter, &elem, prepend); |
|
89 } |
|
90 |
|
91 static int cx_pl_remove( |
|
92 struct cx_list_s *list, |
|
93 size_t index |
|
94 ) { |
|
95 return list->climpl->remove(list, index); |
|
96 } |
|
97 |
|
98 static void cx_pl_clear(struct cx_list_s *list) { |
|
99 list->climpl->clear(list); |
|
100 } |
|
101 |
|
102 static int cx_pl_swap( |
|
103 struct cx_list_s *list, |
|
104 size_t i, |
|
105 size_t j |
|
106 ) { |
|
107 return list->climpl->swap(list, i, j); |
|
108 } |
|
109 |
|
110 static void *cx_pl_at( |
|
111 struct cx_list_s const *list, |
|
112 size_t index |
|
113 ) { |
|
114 void **ptr = list->climpl->at(list, index); |
|
115 return ptr == NULL ? NULL : *ptr; |
|
116 } |
|
117 |
|
118 static size_t cx_pl_find( |
|
119 struct cx_list_s const *list, |
|
120 void const *elem |
|
121 ) { |
|
122 cx_pl_hack_cmpfunc(list); |
|
123 size_t ret = list->climpl->find(list, &elem); |
|
124 cx_pl_unhack_cmpfunc(list); |
|
125 return ret; |
|
126 } |
|
127 |
|
128 static void cx_pl_sort(struct cx_list_s *list) { |
|
129 cx_pl_hack_cmpfunc(list); |
|
130 list->climpl->sort(list); |
|
131 cx_pl_unhack_cmpfunc(list); |
|
132 } |
|
133 |
|
134 static int cx_pl_compare( |
|
135 struct cx_list_s const *list, |
|
136 struct cx_list_s const *other |
|
137 ) { |
|
138 cx_pl_hack_cmpfunc(list); |
|
139 int ret = list->climpl->compare(list, other); |
|
140 cx_pl_unhack_cmpfunc(list); |
|
141 return ret; |
|
142 } |
|
143 |
|
144 static void cx_pl_reverse(struct cx_list_s *list) { |
|
145 list->climpl->reverse(list); |
|
146 } |
|
147 |
|
148 static void *cx_pl_iter_current(void const *it) { |
|
149 struct cx_iterator_s const *iter = it; |
|
150 void **ptr = iter->base.current_impl(it); |
|
151 return ptr == NULL ? NULL : *ptr; |
|
152 } |
|
153 |
|
154 static struct cx_iterator_s cx_pl_iterator( |
|
155 struct cx_list_s const *list, |
|
156 size_t index, |
|
157 bool backwards |
|
158 ) { |
|
159 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); |
|
160 iter.base.current_impl = iter.base.current; |
|
161 iter.base.current = cx_pl_iter_current; |
|
162 return iter; |
|
163 } |
|
164 |
|
165 static cx_list_class cx_pointer_list_class = { |
|
166 cx_pl_destructor, |
|
167 cx_pl_insert_element, |
|
168 cx_pl_insert_array, |
|
169 cx_pl_insert_iter, |
|
170 cx_pl_remove, |
|
171 cx_pl_clear, |
|
172 cx_pl_swap, |
|
173 cx_pl_at, |
|
174 cx_pl_find, |
|
175 cx_pl_sort, |
|
176 cx_pl_compare, |
|
177 cx_pl_reverse, |
|
178 cx_pl_iterator, |
|
179 }; |
|
180 |
|
181 void cxListStoreObjects(CxList *list) { |
|
182 list->store_pointer = false; |
|
183 if (list->climpl != NULL) { |
|
184 list->cl = list->climpl; |
|
185 list->climpl = NULL; |
|
186 } |
|
187 } |
|
188 |
|
189 void cxListStorePointers(CxList *list) { |
|
190 list->item_size = sizeof(void *); |
|
191 list->store_pointer = true; |
|
192 list->climpl = list->cl; |
|
193 list->cl = &cx_pointer_list_class; |
|
194 } |
|
195 |
|
196 // </editor-fold> |
|
197 |
|
198 void cxListDestroy(CxList *list) { |
|
199 if (list->simple_destructor) { |
|
200 CxIterator iter = cxListIterator(list); |
|
201 cx_foreach(void*, elem, iter) { |
|
202 // already correctly resolved pointer - immediately invoke dtor |
|
203 list->simple_destructor(elem); |
|
204 } |
|
205 } |
|
206 if (list->advanced_destructor) { |
|
207 CxIterator iter = cxListIterator(list); |
|
208 cx_foreach(void*, elem, iter) { |
|
209 // already correctly resolved pointer - immediately invoke dtor |
|
210 list->advanced_destructor(list->destructor_data, elem); |
|
211 } |
|
212 } |
|
213 |
|
214 list->cl->destructor(list); |
|
215 cxFree(list->allocator, list); |
|
216 } |
|
217 |
|
218 int cxListCompare( |
|
219 CxList const *list, |
|
220 CxList const *other |
|
221 ) { |
|
222 if ((list->store_pointer ^ other->store_pointer) || |
|
223 ((list->climpl == NULL) ^ (other->climpl != NULL)) || |
|
224 ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != |
|
225 (other->climpl != NULL ? other->climpl->compare : other->cl->compare))) { |
|
226 // lists are definitely different - cannot use internal compare function |
|
227 if (list->size == other->size) { |
|
228 CxIterator left = cxListIterator(list); |
|
229 CxIterator right = cxListIterator(other); |
|
230 for (size_t i = 0; i < list->size; i++) { |
|
231 void *leftValue = cxIteratorCurrent(left); |
|
232 void *rightValue = cxIteratorCurrent(right); |
|
233 int d = list->cmpfunc(leftValue, rightValue); |
|
234 if (d != 0) { |
|
235 return d; |
|
236 } |
|
237 cxIteratorNext(left); |
|
238 cxIteratorNext(right); |
|
239 } |
|
240 return 0; |
41 } else { |
241 } else { |
42 ret = ucx_list_append_a(alloc, ret, l->data); |
242 return list->size < other->size ? -1 : 1; |
43 } |
243 } |
44 l = l->next; |
|
45 } |
|
46 return ret; |
|
47 } |
|
48 |
|
49 int ucx_list_equals(const UcxList *l1, const UcxList *l2, |
|
50 cmp_func fnc, void* data) { |
|
51 if (l1 == l2) return 1; |
|
52 |
|
53 while (l1 != NULL && l2 != NULL) { |
|
54 if (fnc == NULL) { |
|
55 if (l1->data != l2->data) return 0; |
|
56 } else { |
|
57 if (fnc(l1->data, l2->data, data) != 0) return 0; |
|
58 } |
|
59 l1 = l1->next; |
|
60 l2 = l2->next; |
|
61 } |
|
62 |
|
63 return (l1 == NULL && l2 == NULL); |
|
64 } |
|
65 |
|
66 void ucx_list_free(UcxList *l) { |
|
67 ucx_list_free_a(ucx_default_allocator(), l); |
|
68 } |
|
69 |
|
70 void ucx_list_free_a(UcxAllocator *alloc, UcxList *l) { |
|
71 UcxList *e = l, *f; |
|
72 while (e != NULL) { |
|
73 f = e; |
|
74 e = e->next; |
|
75 alfree(alloc, f); |
|
76 } |
|
77 } |
|
78 |
|
79 void ucx_list_free_content(UcxList* list, ucx_destructor destr) { |
|
80 if (!destr) destr = free; |
|
81 while (list != NULL) { |
|
82 destr(list->data); |
|
83 list = list->next; |
|
84 } |
|
85 } |
|
86 |
|
87 UcxList *ucx_list_append(UcxList *l, void *data) { |
|
88 return ucx_list_append_a(ucx_default_allocator(), l, data); |
|
89 } |
|
90 |
|
91 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data) { |
|
92 UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList)); |
|
93 if (!nl) { |
|
94 return NULL; |
|
95 } |
|
96 |
|
97 nl->data = data; |
|
98 nl->next = NULL; |
|
99 if (l) { |
|
100 UcxList *t = ucx_list_last(l); |
|
101 t->next = nl; |
|
102 nl->prev = t; |
|
103 return l; |
|
104 } else { |
244 } else { |
105 nl->prev = NULL; |
245 // lists are compatible |
106 return nl; |
246 return list->cl->compare(list, other); |
107 } |
247 } |
108 } |
248 } |
109 |
249 |
110 UcxList *ucx_list_prepend(UcxList *l, void *data) { |
250 CxMutIterator cxListMutIteratorAt( |
111 return ucx_list_prepend_a(ucx_default_allocator(), l, data); |
251 CxList *list, |
112 } |
252 size_t index |
113 |
253 ) { |
114 UcxList *ucx_list_prepend_a(UcxAllocator *alloc, UcxList *l, void *data) { |
254 CxIterator it = list->cl->iterator(list, index, false); |
115 UcxList *nl = ucx_list_append_a(alloc, NULL, data); |
255 it.base.mutating = true; |
116 if (!nl) { |
256 |
117 return NULL; |
257 // we know the iterators share the same memory layout |
118 } |
258 CxMutIterator iter; |
119 l = ucx_list_first(l); |
259 memcpy(&iter, &it, sizeof(CxMutIterator)); |
120 |
260 return iter; |
121 if (l) { |
261 } |
122 nl->next = l; |
262 |
123 l->prev = nl; |
263 CxMutIterator cxListMutBackwardsIteratorAt( |
124 } |
264 CxList *list, |
125 return nl; |
265 size_t index |
126 } |
266 ) { |
127 |
267 CxIterator it = list->cl->iterator(list, index, true); |
128 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { |
268 it.base.mutating = true; |
129 if (l1) { |
269 |
130 UcxList *last = ucx_list_last(l1); |
270 // we know the iterators share the same memory layout |
131 last->next = l2; |
271 CxMutIterator iter; |
132 if (l2) { |
272 memcpy(&iter, &it, sizeof(CxMutIterator)); |
133 l2->prev = last; |
273 return iter; |
134 } |
274 } |
135 return l1; |
|
136 } else { |
|
137 return l2; |
|
138 } |
|
139 } |
|
140 |
|
141 UcxList *ucx_list_last(const UcxList *l) { |
|
142 if (l == NULL) return NULL; |
|
143 |
|
144 const UcxList *e = l; |
|
145 while (e->next != NULL) { |
|
146 e = e->next; |
|
147 } |
|
148 return (UcxList*)e; |
|
149 } |
|
150 |
|
151 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem) { |
|
152 ssize_t index = 0; |
|
153 while (list) { |
|
154 if (list == elem) { |
|
155 return index; |
|
156 } |
|
157 list = list->next; |
|
158 index++; |
|
159 } |
|
160 return -1; |
|
161 } |
|
162 |
|
163 UcxList *ucx_list_get(const UcxList *l, size_t index) { |
|
164 if (l == NULL) return NULL; |
|
165 |
|
166 const UcxList *e = l; |
|
167 while (e->next && index > 0) { |
|
168 e = e->next; |
|
169 index--; |
|
170 } |
|
171 |
|
172 return (UcxList*)(index == 0 ? e : NULL); |
|
173 } |
|
174 |
|
175 ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { |
|
176 ssize_t index = 0; |
|
177 UCX_FOREACH(e, l) { |
|
178 if (fnc) { |
|
179 if (fnc(elem, e->data, cmpdata) == 0) { |
|
180 return index; |
|
181 } |
|
182 } else { |
|
183 if (elem == e->data) { |
|
184 return index; |
|
185 } |
|
186 } |
|
187 index++; |
|
188 } |
|
189 return -1; |
|
190 } |
|
191 |
|
192 int ucx_list_contains(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { |
|
193 return ucx_list_find(l, elem, fnc, cmpdata) > -1; |
|
194 } |
|
195 |
|
196 size_t ucx_list_size(const UcxList *l) { |
|
197 if (l == NULL) return 0; |
|
198 |
|
199 const UcxList *e = l; |
|
200 size_t s = 1; |
|
201 while (e->next != NULL) { |
|
202 e = e->next; |
|
203 s++; |
|
204 } |
|
205 |
|
206 return s; |
|
207 } |
|
208 |
|
209 static UcxList *ucx_list_sort_merge(int length, |
|
210 UcxList* ls, UcxList* le, UcxList* re, |
|
211 cmp_func fnc, void* data) { |
|
212 |
|
213 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
|
214 UcxList *rc, *lc; |
|
215 |
|
216 lc = ls; rc = le; |
|
217 int n = 0; |
|
218 while (lc && lc != le && rc != re) { |
|
219 if (fnc(lc->data, rc->data, data) <= 0) { |
|
220 sorted[n] = lc; |
|
221 lc = lc->next; |
|
222 } else { |
|
223 sorted[n] = rc; |
|
224 rc = rc->next; |
|
225 } |
|
226 n++; |
|
227 } |
|
228 while (lc && lc != le) { |
|
229 sorted[n] = lc; |
|
230 lc = lc->next; |
|
231 n++; |
|
232 } |
|
233 while (rc && rc != re) { |
|
234 sorted[n] = rc; |
|
235 rc = rc->next; |
|
236 n++; |
|
237 } |
|
238 |
|
239 // Update pointer |
|
240 sorted[0]->prev = NULL; |
|
241 for (int i = 0 ; i < length-1 ; i++) { |
|
242 sorted[i]->next = sorted[i+1]; |
|
243 sorted[i+1]->prev = sorted[i]; |
|
244 } |
|
245 sorted[length-1]->next = NULL; |
|
246 |
|
247 UcxList *ret = sorted[0]; |
|
248 free(sorted); |
|
249 return ret; |
|
250 } |
|
251 |
|
252 UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) { |
|
253 if (l == NULL) { |
|
254 return NULL; |
|
255 } |
|
256 |
|
257 UcxList *lc; |
|
258 int ln = 1; |
|
259 |
|
260 UcxList *ls = l, *le, *re; |
|
261 |
|
262 // check how many elements are already sorted |
|
263 lc = ls; |
|
264 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { |
|
265 lc = lc->next; |
|
266 ln++; |
|
267 } |
|
268 le = lc->next; |
|
269 |
|
270 if (le == NULL) { |
|
271 return l; // this list is already sorted :) |
|
272 } else { |
|
273 UcxList *rc; |
|
274 int rn = 1; |
|
275 rc = le; |
|
276 // skip already sorted elements |
|
277 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
|
278 rc = rc->next; |
|
279 rn++; |
|
280 } |
|
281 re = rc->next; |
|
282 |
|
283 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them |
|
284 UcxList *sorted = ucx_list_sort_merge(ln+rn, |
|
285 ls, le, re, |
|
286 fnc, data); |
|
287 |
|
288 // Something left? Sort it! |
|
289 size_t remainder_length = ucx_list_size(re); |
|
290 if (remainder_length > 0) { |
|
291 UcxList *remainder = ucx_list_sort(re, fnc, data); |
|
292 |
|
293 // merge sorted list with (also sorted) remainder |
|
294 l = ucx_list_sort_merge(ln+rn+remainder_length, |
|
295 sorted, remainder, NULL, fnc, data); |
|
296 } else { |
|
297 // no remainder - we've got our sorted list |
|
298 l = sorted; |
|
299 } |
|
300 |
|
301 return l; |
|
302 } |
|
303 } |
|
304 |
|
305 UcxList *ucx_list_first(const UcxList *l) { |
|
306 if (!l) { |
|
307 return NULL; |
|
308 } |
|
309 |
|
310 const UcxList *e = l; |
|
311 while (e->prev) { |
|
312 e = e->prev; |
|
313 } |
|
314 return (UcxList *)e; |
|
315 } |
|
316 |
|
317 UcxList *ucx_list_remove(UcxList *l, UcxList *e) { |
|
318 return ucx_list_remove_a(ucx_default_allocator(), l, e); |
|
319 } |
|
320 |
|
321 UcxList *ucx_list_remove_a(UcxAllocator *alloc, UcxList *l, UcxList *e) { |
|
322 if (l == e) { |
|
323 l = e->next; |
|
324 } |
|
325 |
|
326 if (e->next) { |
|
327 e->next->prev = e->prev; |
|
328 } |
|
329 |
|
330 if (e->prev) { |
|
331 e->prev->next = e->next; |
|
332 } |
|
333 |
|
334 alfree(alloc, e); |
|
335 return l; |
|
336 } |
|