1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
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
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "cx/list.h"
30
31 #include <string.h>
32
33 // <editor-fold desc="Store Pointers Functionality">
34
35 static _Thread_local cx_compare_func cx_pl_cmpfunc_impl;
36
37 static int cx_pl_cmpfunc(
38 const void *l,
39 const void *r
40 ) {
41 void *const *lptr = l;
42 void *const *rptr = r;
43 const void *left = lptr == NULL ? NULL : *lptr;
44 const void *right = rptr == NULL ? NULL : *rptr;
45 return cx_pl_cmpfunc_impl(left, right);
46 }
47
48 static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) {
49 // cast away const - this is the hacky thing
50 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
51 cx_pl_cmpfunc_impl = l->cmpfunc;
52 l->cmpfunc = cx_pl_cmpfunc;
53 }
54
55 static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) {
56 // cast away const - this is the hacky thing
57 struct cx_collection_s *l = (struct cx_collection_s*) &list->collection;
58 l->cmpfunc = cx_pl_cmpfunc_impl;
59 }
60
61 static void cx_pl_destructor(struct cx_list_s *list) {
62 list->climpl->deallocate(list);
63 }
64
65 static int cx_pl_insert_element(
66 struct cx_list_s *list,
67 size_t index,
68 const void *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 const void *array,
77 size_t n
78 ) {
79 return list->climpl->insert_array(list, index, array, n);
80 }
81
82 static size_t cx_pl_insert_sorted(
83 struct cx_list_s *list,
84 const void *array,
85 size_t n
86 ) {
87 cx_pl_hack_cmpfunc(list);
88 size_t result = list->climpl->insert_sorted(list, array, n);
89 cx_pl_unhack_cmpfunc(list);
90 return result;
91 }
92
93 static int cx_pl_insert_iter(
94 struct cx_iterator_s *iter,
95 const void *elem,
96 int prepend
97 ) {
98 struct cx_list_s *list = iter->src_handle.m;
99 return list->climpl->insert_iter(iter, &elem, prepend);
100 }
101
102 static size_t cx_pl_remove(
103 struct cx_list_s *list,
104 size_t index,
105 size_t num,
106 void *targetbuf
107 ) {
108 return list->climpl->remove(list, index, num, targetbuf);
109 }
110
111 static void cx_pl_clear(struct cx_list_s *list) {
112 list->climpl->clear(list);
113 }
114
115 static int cx_pl_swap(
116 struct cx_list_s *list,
117 size_t i,
118 size_t j
119 ) {
120 return list->climpl->swap(list, i, j);
121 }
122
123 static void *cx_pl_at(
124 const struct cx_list_s *list,
125 size_t index
126 ) {
127 void **ptr = list->climpl->at(list, index);
128 return ptr == NULL ? NULL : *ptr;
129 }
130
131 static ssize_t cx_pl_find_remove(
132 struct cx_list_s *list,
133 const void *elem,
134 bool remove
135 ) {
136 cx_pl_hack_cmpfunc(list);
137 ssize_t ret = list->climpl->find_remove(list, &elem, remove);
138 cx_pl_unhack_cmpfunc(list);
139 return ret;
140 }
141
142 static void cx_pl_sort(struct cx_list_s *list) {
143 cx_pl_hack_cmpfunc(list);
144 list->climpl->sort(list);
145 cx_pl_unhack_cmpfunc(list);
146 }
147
148 static int cx_pl_compare(
149 const struct cx_list_s *list,
150 const struct cx_list_s *other
151 ) {
152 cx_pl_hack_cmpfunc(list);
153 int ret = list->climpl->compare(list, other);
154 cx_pl_unhack_cmpfunc(list);
155 return ret;
156 }
157
158 static void cx_pl_reverse(struct cx_list_s *list) {
159 list->climpl->reverse(list);
160 }
161
162 static void *cx_pl_iter_current(const void *it) {
163 const struct cx_iterator_s *iter = it;
164 void **ptr = iter->base.current_impl(it);
165 return ptr == NULL ? NULL : *ptr;
166 }
167
168 static struct cx_iterator_s cx_pl_iterator(
169 const struct cx_list_s *list,
170 size_t index,
171 bool backwards
172 ) {
173 struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
174 iter.base.current_impl = iter.base.current;
175 iter.base.current = cx_pl_iter_current;
176 return iter;
177 }
178
179 static cx_list_class cx_pointer_list_class = {
180 cx_pl_destructor,
181 cx_pl_insert_element,
182 cx_pl_insert_array,
183 cx_pl_insert_sorted,
184 cx_pl_insert_iter,
185 cx_pl_remove,
186 cx_pl_clear,
187 cx_pl_swap,
188 cx_pl_at,
189 cx_pl_find_remove,
190 cx_pl_sort,
191 cx_pl_compare,
192 cx_pl_reverse,
193 cx_pl_iterator,
194 };
195
196 void cxListStoreObjects(CxList *list) {
197 list->collection.store_pointer = false;
198 if (list->climpl != NULL) {
199 list->cl = list->climpl;
200 list->climpl = NULL;
201 }
202 }
203
204 void cxListStorePointers(CxList *list) {
205 list->collection.elem_size = sizeof(void *);
206 list->collection.store_pointer = true;
207 list->climpl = list->cl;
208 list->cl = &cx_pointer_list_class;
209 }
210
211 // </editor-fold>
212
213 // <editor-fold desc="empty list implementation">
214
215 static void cx_emptyl_noop(cx_attr_unused CxList *list) {
216 // this is a noop, but MUST be implemented
217 }
218
219 static void *cx_emptyl_at(
220 cx_attr_unused const struct cx_list_s *list,
221 cx_attr_unused size_t index
222 ) {
223 return NULL;
224 }
225
226 static ssize_t cx_emptyl_find_remove(
227 cx_attr_unused struct cx_list_s *list,
228 cx_attr_unused const void *elem,
229 cx_attr_unused bool remove
230 ) {
231 return -1;
232 }
233
234 static bool cx_emptyl_iter_valid(cx_attr_unused const void *iter) {
235 return false;
236 }
237
238 static CxIterator cx_emptyl_iterator(
239 const struct cx_list_s *list,
240 size_t index,
241 cx_attr_unused bool backwards
242 ) {
243 CxIterator iter = {0};
244 iter.src_handle.c = list;
245 iter.index = index;
246 iter.base.valid = cx_emptyl_iter_valid;
247 return iter;
248 }
249
250 static cx_list_class cx_empty_list_class = {
251 cx_emptyl_noop,
252 NULL,
253 NULL,
254 NULL,
255 NULL,
256 NULL,
257 cx_emptyl_noop,
258 NULL,
259 cx_emptyl_at,
260 cx_emptyl_find_remove,
261 cx_emptyl_noop,
262 NULL,
263 cx_emptyl_noop,
264 cx_emptyl_iterator,
265 };
266
267 CxList cx_empty_list = {
268 {
269 NULL,
270 NULL,
271 0,
272 0,
273 NULL,
274 NULL,
275 NULL,
276 false
277 },
278 &cx_empty_list_class,
279 NULL
280 };
281
282 CxList *const cxEmptyList = &cx_empty_list;
283
284 // </editor-fold>
285
286 #define invoke_list_func(name, list, ...) \
287 ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \
288 (list, __VA_ARGS__)
289
290 size_t cx_list_default_insert_array(
291 struct cx_list_s *list,
292 size_t index,
293 const void *data,
294 size_t n
295 ) {
296 size_t elem_size = list->collection.elem_size;
297 const char *src = data;
298 size_t i = 0;
299 for (; i < n; i++) {
300 if (0 != invoke_list_func(
301 insert_element, list, index + i,
302 src + (i * elem_size))) return i;
303 }
304 return i;
305 }
306
307 size_t cx_list_default_insert_sorted(
308 struct cx_list_s *list,
309 const void *sorted_data,
310 size_t n
311 ) {
312 // corner case
313 if (n == 0) return 0;
314
315 size_t elem_size = list->collection.elem_size;
316 cx_compare_func cmp = list->collection.cmpfunc;
317 const char *src = sorted_data;
318
319 // track indices and number of inserted items
320 size_t di = 0, si = 0, inserted = 0;
321
322 // search the list for insertion points
323 for (; di < list->collection.size; di++) {
324 const void *list_elm = invoke_list_func(at, list, di);
325
326 // compare current list element with first source element
327 // if less or equal, skip
328 if (cmp(list_elm, src) <= 0) {
329 continue;
330 }
331
332 // determine number of consecutive elements that can be inserted
333 size_t ins = 1;
334 const char *next = src;
335 while (++si < n) {
336 next += elem_size;
337 // once we become larger than the list elem, break
338 if (cmp(list_elm, next) <= 0) {
339 break;
340 }
341 // otherwise, we can insert one more
342 ins++;
343 }
344
345 // insert the elements at location si
346 if (ins == 1) {
347 if (0 != invoke_list_func(
348 insert_element, list, di, src)) return inserted;
349 } else {
350 size_t r = invoke_list_func(insert_array, list, di, src, ins);
351 if (r < ins) return inserted + r;
352 }
353 inserted += ins;
354 di += ins;
355
356 // everything inserted?
357 if (inserted == n) return inserted;
358 src = next;
359 }
360
361 // insert remaining items
362 if (si < n) {
363 inserted += invoke_list_func(insert_array, list, di, src, n - si);
364 }
365
366 return inserted;
367 }
368
369 void cx_list_default_sort(struct cx_list_s *list) {
370 size_t elem_size = list->collection.elem_size;
371 size_t list_size = list->collection.size;
372 void *tmp = malloc(elem_size * list_size);
373 if (tmp == NULL) abort();
374
375 // copy elements from source array
376 char *loc = tmp;
377 for (size_t i = 0; i < list_size; i++) {
378 void *src = invoke_list_func(at, list, i);
379 memcpy(loc, src, elem_size);
380 loc += elem_size;
381 }
382
383 // qsort
384 qsort(tmp, list_size, elem_size,
385 list->collection.cmpfunc);
386
387 // copy elements back
388 loc = tmp;
389 for (size_t i = 0; i < list_size; i++) {
390 void *dest = invoke_list_func(at, list, i);
391 memcpy(dest, loc, elem_size);
392 loc += elem_size;
393 }
394
395 free(tmp);
396 }
397
398 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) {
399 if (i == j) return 0;
400 if (i >= list->collection.size) return 1;
401 if (j >= list->collection.size) return 1;
402
403 size_t elem_size = list->collection.elem_size;
404
405 void *tmp = malloc(elem_size);
406 if (tmp == NULL) return 1;
407
408 void *ip = invoke_list_func(at, list, i);
409 void *jp = invoke_list_func(at, list, j);
410
411 memcpy(tmp, ip, elem_size);
412 memcpy(ip, jp, elem_size);
413 memcpy(jp, tmp, elem_size);
414
415 free(tmp);
416
417 return 0;
418 }
419
420 int cxListCompare(
421 const CxList *list,
422 const CxList *other
423 ) {
424 bool cannot_optimize = false;
425
426 // if one is storing pointers but the other is not
427 cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer;
428
429 // if one class is wrapped but the other is not
430 cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL);
431
432 // if the compare functions do not match or both are NULL
433 if (!cannot_optimize) {
434 cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ?
435 list->climpl->compare : list->cl->compare);
436 cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ?
437 other->climpl->compare : other->cl->compare);
438 cannot_optimize |= list_cmp != other_cmp;
439 cannot_optimize |= list_cmp == NULL;
440 }
441
442 if (cannot_optimize) {
443 // lists are definitely different - cannot use internal compare function
444 if (list->collection.size == other->collection.size) {
445 CxIterator left = list->cl->iterator(list, 0, false);
446 CxIterator right = other->cl->iterator(other, 0, false);
447 for (size_t i = 0; i < list->collection.size; i++) {
448 void *leftValue = cxIteratorCurrent(left);
449 void *rightValue = cxIteratorCurrent(right);
450 int d = list->collection.cmpfunc(leftValue, rightValue);
451 if (d != 0) {
452 return d;
453 }
454 cxIteratorNext(left);
455 cxIteratorNext(right);
456 }
457 return 0;
458 } else {
459 return list->collection.size < other->collection.size ? -1 : 1;
460 }
461 } else {
462 // lists are compatible
463 return list->cl->compare(list, other);
464 }
465 }
466
467 CxIterator cxListMutIteratorAt(
468 CxList *list,
469 size_t index
470 ) {
471 CxIterator it = list->cl->iterator(list, index, false);
472 it.base.mutating = true;
473 return it;
474 }
475
476 CxIterator cxListMutBackwardsIteratorAt(
477 CxList *list,
478 size_t index
479 ) {
480 CxIterator it = list->cl->iterator(list, index, true);
481 it.base.mutating = true;
482 return it;
483 }
484
485 void cxListFree(CxList *list) {
486 if (list == NULL) return;
487 list->cl->deallocate(list);
488 }
489