1 /***************************************************************************************************
2
3 Zyan Core Library (Zycore-C)
4
5 Original Author : Florian Bernd
6
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in all
15 * copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24
25 ***************************************************************************************************/
26
27 #include <Zycore/LibC.h>
28 #include <Zycore/List.h>
29
30 /* ============================================================================================== */
31 /* Internal macros */
32 /* ============================================================================================== */
33
34 /**
35 * Returns a pointer to the data of the given `node`.
36 *
37 * @param node A pointer to the `ZyanNodeData` struct.
38 *
39 * @return A pointer to the data of the given `node`.
40 */
41 #define ZYCORE_LIST_GET_NODE_DATA(node) \
42 ((void*)(node + 1))
43
44 /* ============================================================================================== */
45 /* Internal functions */
46 /* ============================================================================================== */
47
48 /* ---------------------------------------------------------------------------------------------- */
49 /* Helper functions */
50 /* ---------------------------------------------------------------------------------------------- */
51
52 /**
53 * Allocates memory for a new list node.
54 *
55 * @param list A pointer to the `ZyanList` instance.
56 * @param node Receives a pointer to the new `ZyanListNode` struct.
57 *
58 * @return A zyan status code.
59 */
ZyanListAllocateNode(ZyanList * list,ZyanListNode ** node)60 static ZyanStatus ZyanListAllocateNode(ZyanList* list, ZyanListNode** node)
61 {
62 ZYAN_ASSERT(list);
63 ZYAN_ASSERT(node);
64
65 const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
66 if (is_dynamic)
67 {
68 ZYAN_ASSERT(list->allocator->allocate);
69 ZYAN_CHECK(list->allocator->allocate(list->allocator, (void**)node,
70 sizeof(ZyanListNode) + list->element_size, 1));
71 } else
72 {
73 if (list->first_unused)
74 {
75 *node = list->first_unused;
76 list->first_unused = (*node)->next;
77 } else
78 {
79 const ZyanUSize size = list->size * (sizeof(ZyanListNode) + list->element_size);
80 if (size + (sizeof(ZyanListNode) + list->element_size) > list->capacity)
81 {
82 return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
83 }
84
85 *node = (ZyanListNode*)((ZyanU8*)list->buffer + size);
86 }
87 }
88
89 return ZYAN_STATUS_SUCCESS;
90 }
91
92 /**
93 * Frees memory of a node.
94 *
95 * @param list A pointer to the `ZyanList` instance.
96 * @param node A pointer to the `ZyanListNode` struct.
97 *
98 * @return A zyan status code.
99 */
ZyanListDeallocateNode(ZyanList * list,ZyanListNode * node)100 static ZyanStatus ZyanListDeallocateNode(ZyanList* list, ZyanListNode* node)
101 {
102 ZYAN_ASSERT(list);
103 ZYAN_ASSERT(node);
104
105 const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
106 if (is_dynamic)
107 {
108 ZYAN_ASSERT(list->allocator->deallocate);
109 ZYAN_CHECK(list->allocator->deallocate(list->allocator, (void*)node,
110 sizeof(ZyanListNode) + list->element_size, 1));
111 } else
112 {
113 node->next = list->first_unused;
114 list->first_unused = node;
115 }
116
117 return ZYAN_STATUS_SUCCESS;
118 }
119
120 /* ---------------------------------------------------------------------------------------------- */
121
122 /* ============================================================================================== */
123 /* Exported functions */
124 /* ============================================================================================== */
125
126 /* ---------------------------------------------------------------------------------------------- */
127 /* Constructor and destructor */
128 /* ---------------------------------------------------------------------------------------------- */
129
130 #ifndef ZYAN_NO_LIBC
131
ZyanListInit(ZyanList * list,ZyanUSize element_size,ZyanMemberProcedure destructor)132 ZYAN_REQUIRES_LIBC ZyanStatus ZyanListInit(ZyanList* list, ZyanUSize element_size,
133 ZyanMemberProcedure destructor)
134 {
135 return ZyanListInitEx(list, element_size, destructor, ZyanAllocatorDefault());
136 }
137
138 #endif // ZYAN_NO_LIBC
139
ZyanListInitEx(ZyanList * list,ZyanUSize element_size,ZyanMemberProcedure destructor,ZyanAllocator * allocator)140 ZyanStatus ZyanListInitEx(ZyanList* list, ZyanUSize element_size, ZyanMemberProcedure destructor,
141 ZyanAllocator* allocator)
142 {
143 if (!list || !element_size || !allocator)
144 {
145 return ZYAN_STATUS_INVALID_ARGUMENT;
146 }
147
148 list->allocator = allocator;
149 list->size = 0;
150 list->element_size = element_size;
151 list->destructor = destructor;
152 list->head = ZYAN_NULL;
153 list->tail = ZYAN_NULL;
154 list->buffer = ZYAN_NULL;
155 list->capacity = 0;
156 list->first_unused = ZYAN_NULL;
157
158 return ZYAN_STATUS_SUCCESS;
159 }
160
ZyanListInitCustomBuffer(ZyanList * list,ZyanUSize element_size,ZyanMemberProcedure destructor,void * buffer,ZyanUSize capacity)161 ZyanStatus ZyanListInitCustomBuffer(ZyanList* list, ZyanUSize element_size,
162 ZyanMemberProcedure destructor, void* buffer, ZyanUSize capacity)
163 {
164 if (!list || !element_size || !buffer || !capacity)
165 {
166 return ZYAN_STATUS_INVALID_ARGUMENT;
167 }
168
169 list->allocator = ZYAN_NULL;
170 list->size = 0;
171 list->element_size = element_size;
172 list->destructor = destructor;
173 list->head = ZYAN_NULL;
174 list->tail = ZYAN_NULL;
175 list->buffer = buffer;
176 list->capacity = capacity;
177 list->first_unused = ZYAN_NULL;
178
179 return ZYAN_STATUS_SUCCESS;
180 }
181
ZyanListDestroy(ZyanList * list)182 ZyanStatus ZyanListDestroy(ZyanList* list)
183 {
184 if (!list)
185 {
186 return ZYAN_STATUS_INVALID_ARGUMENT;
187 }
188
189 ZYAN_ASSERT(list->element_size);
190
191 const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
192 ZyanListNode* node = (is_dynamic || list->destructor) ? list->head : ZYAN_NULL;
193 while (node)
194 {
195 if (list->destructor)
196 {
197 list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
198 }
199
200 ZyanListNode* const next = node->next;
201
202 if (is_dynamic)
203 {
204 ZYAN_CHECK(list->allocator->deallocate(list->allocator, node,
205 sizeof(ZyanListNode) + list->element_size, 1));
206 }
207
208 node = next;
209 }
210
211 return ZYAN_STATUS_SUCCESS;
212 }
213
214 /* ---------------------------------------------------------------------------------------------- */
215 /* Duplication */
216 /* ---------------------------------------------------------------------------------------------- */
217
218
219
220 /* ---------------------------------------------------------------------------------------------- */
221 /* Item access */
222 /* ---------------------------------------------------------------------------------------------- */
223
ZyanListGetHeadNode(const ZyanList * list,const ZyanListNode ** node)224 ZyanStatus ZyanListGetHeadNode(const ZyanList* list, const ZyanListNode** node)
225 {
226 if (!list)
227 {
228 return ZYAN_STATUS_INVALID_ARGUMENT;
229 }
230
231 *node = list->head;
232
233 return ZYAN_STATUS_SUCCESS;
234 }
235
ZyanListGetTailNode(const ZyanList * list,const ZyanListNode ** node)236 ZyanStatus ZyanListGetTailNode(const ZyanList* list, const ZyanListNode** node)
237 {
238 if (!list)
239 {
240 return ZYAN_STATUS_INVALID_ARGUMENT;
241 }
242
243 *node = list->tail;
244
245 return ZYAN_STATUS_SUCCESS;
246 }
247
ZyanListGetPrevNode(const ZyanListNode ** node)248 ZyanStatus ZyanListGetPrevNode(const ZyanListNode** node)
249 {
250 if (!node || !*node)
251 {
252 return ZYAN_STATUS_INVALID_ARGUMENT;
253 }
254
255 *node = (*node)->prev;
256
257 return ZYAN_STATUS_SUCCESS;
258 }
259
ZyanListGetNextNode(const ZyanListNode ** node)260 ZyanStatus ZyanListGetNextNode(const ZyanListNode** node)
261 {
262 if (!node || !*node)
263 {
264 return ZYAN_STATUS_INVALID_ARGUMENT;
265 }
266
267 *node = (*node)->next;
268
269 return ZYAN_STATUS_SUCCESS;
270 }
271
ZyanListGetNodeData(const ZyanListNode * node)272 const void* ZyanListGetNodeData(const ZyanListNode* node)
273 {
274 if (!node)
275 {
276 return ZYAN_NULL;
277 }
278
279 return (const void*)ZYCORE_LIST_GET_NODE_DATA(node);
280 }
281
ZyanListGetNodeDataEx(const ZyanListNode * node,const void ** value)282 ZyanStatus ZyanListGetNodeDataEx(const ZyanListNode* node, const void** value)
283 {
284 if (!node)
285 {
286 return ZYAN_STATUS_INVALID_ARGUMENT;
287 }
288
289 *value = (const void*)ZYCORE_LIST_GET_NODE_DATA(node);
290
291 return ZYAN_STATUS_SUCCESS;
292 }
293
ZyanListGetNodeDataMutable(const ZyanListNode * node)294 void* ZyanListGetNodeDataMutable(const ZyanListNode* node)
295 {
296 if (!node)
297 {
298 return ZYAN_NULL;
299 }
300
301 return ZYCORE_LIST_GET_NODE_DATA(node);
302 }
303
ZyanListGetNodeDataMutableEx(const ZyanListNode * node,void ** value)304 ZyanStatus ZyanListGetNodeDataMutableEx(const ZyanListNode* node, void** value)
305 {
306 if (!node)
307 {
308 return ZYAN_STATUS_INVALID_ARGUMENT;
309 }
310
311 *value = ZYCORE_LIST_GET_NODE_DATA(node);
312
313 return ZYAN_STATUS_SUCCESS;
314 }
315
ZyanListSetNodeData(const ZyanList * list,const ZyanListNode * node,const void * value)316 ZyanStatus ZyanListSetNodeData(const ZyanList* list, const ZyanListNode* node, const void* value)
317 {
318 if (!list || !node || !value)
319 {
320 return ZYAN_STATUS_INVALID_ARGUMENT;
321 }
322
323 if (list->destructor)
324 {
325 list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
326 }
327
328 ZYAN_ASSERT(list->element_size);
329 ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), value, list->element_size);
330
331 return ZYAN_STATUS_SUCCESS;
332 }
333
334 /* ---------------------------------------------------------------------------------------------- */
335 /* Insertion */
336 /* ---------------------------------------------------------------------------------------------- */
337
ZyanListPushBack(ZyanList * list,const void * item)338 ZyanStatus ZyanListPushBack(ZyanList* list, const void* item)
339 {
340 if (!list || !item)
341 {
342 return ZYAN_STATUS_INVALID_ARGUMENT;
343 }
344
345 ZyanListNode* node;
346 ZYAN_CHECK(ZyanListAllocateNode(list, &node));
347 node->prev = list->tail;
348 node->next = ZYAN_NULL;
349
350 ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), item, list->element_size);
351
352 if (!list->head)
353 {
354 list->head = node;
355 list->tail = node;
356 } else
357 {
358 list->tail->next = node;
359 list->tail = node;
360 }
361 ++list->size;
362
363 return ZYAN_STATUS_SUCCESS;
364 }
365
ZyanListPushFront(ZyanList * list,const void * item)366 ZyanStatus ZyanListPushFront(ZyanList* list, const void* item)
367 {
368 if (!list || !item)
369 {
370 return ZYAN_STATUS_INVALID_ARGUMENT;
371 }
372
373 ZyanListNode* node;
374 ZYAN_CHECK(ZyanListAllocateNode(list, &node));
375 node->prev = ZYAN_NULL;
376 node->next = list->head;
377
378 ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), item, list->element_size);
379
380 if (!list->head)
381 {
382 list->head = node;
383 list->tail = node;
384 } else
385 {
386 list->head->prev= node;
387 list->head = node;
388 }
389 ++list->size;
390
391 return ZYAN_STATUS_SUCCESS;
392 }
393
ZyanListEmplaceBack(ZyanList * list,void ** item,ZyanMemberFunction constructor)394 ZyanStatus ZyanListEmplaceBack(ZyanList* list, void** item, ZyanMemberFunction constructor)
395 {
396 if (!list || !item)
397 {
398 return ZYAN_STATUS_INVALID_ARGUMENT;
399 }
400
401 ZyanListNode* node;
402 ZYAN_CHECK(ZyanListAllocateNode(list, &node));
403 node->prev = list->tail;
404 node->next = ZYAN_NULL;
405
406 *item = ZYCORE_LIST_GET_NODE_DATA(node);
407 if (constructor)
408 {
409 constructor(*item);
410 }
411
412 if (!list->head)
413 {
414 list->head = node;
415 list->tail = node;
416 } else
417 {
418 list->tail->next = node;
419 list->tail = node;
420 }
421 ++list->size;
422
423 return ZYAN_STATUS_SUCCESS;
424 }
425
ZyanListEmplaceFront(ZyanList * list,void ** item,ZyanMemberFunction constructor)426 ZyanStatus ZyanListEmplaceFront(ZyanList* list, void** item, ZyanMemberFunction constructor)
427 {
428 if (!list || !item)
429 {
430 return ZYAN_STATUS_INVALID_ARGUMENT;
431 }
432
433 ZyanListNode* node;
434 ZYAN_CHECK(ZyanListAllocateNode(list, &node));
435 node->prev = ZYAN_NULL;
436 node->next = list->head;
437
438 *item = ZYCORE_LIST_GET_NODE_DATA(node);
439 if (constructor)
440 {
441 constructor(*item);
442 }
443
444 if (!list->head)
445 {
446 list->head = node;
447 list->tail = node;
448 } else
449 {
450 list->head->prev= node;
451 list->head = node;
452 }
453 ++list->size;
454
455 return ZYAN_STATUS_SUCCESS;
456 }
457
458 /* ---------------------------------------------------------------------------------------------- */
459 /* Deletion */
460 /* ---------------------------------------------------------------------------------------------- */
461
ZyanListPopBack(ZyanList * list)462 ZyanStatus ZyanListPopBack(ZyanList* list)
463 {
464 if (!list)
465 {
466 return ZYAN_STATUS_INVALID_ARGUMENT;
467 }
468 if (!list->tail)
469 {
470 return ZYAN_STATUS_INVALID_OPERATION;
471 }
472
473 ZyanListNode* const node = list->tail;
474
475 if (list->destructor)
476 {
477 list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
478 }
479
480 list->tail = node->prev;
481 if (list->tail)
482 {
483 list->tail->next = ZYAN_NULL;
484 }
485 if (list->head == node)
486 {
487 list->head = list->tail;
488 }
489 --list->size;
490
491 return ZyanListDeallocateNode(list, node);
492 }
493
ZyanListPopFront(ZyanList * list)494 ZyanStatus ZyanListPopFront(ZyanList* list)
495 {
496 if (!list)
497 {
498 return ZYAN_STATUS_INVALID_ARGUMENT;
499 }
500 if (!list->head)
501 {
502 return ZYAN_STATUS_INVALID_OPERATION;
503 }
504
505 ZyanListNode* const node = list->head;
506
507 if (list->destructor)
508 {
509 list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
510 }
511
512 list->head = node->next;
513 if (list->head)
514 {
515 list->head->prev = ZYAN_NULL;
516 }
517 if (list->tail == node)
518 {
519 list->tail = list->head;
520 }
521 --list->size;
522
523 return ZyanListDeallocateNode(list, node);
524 }
525
ZyanListRemove(ZyanList * list,const ZyanListNode * node)526 ZyanStatus ZyanListRemove(ZyanList* list, const ZyanListNode* node)
527 {
528 ZYAN_UNUSED(list);
529 ZYAN_UNUSED(node);
530 return ZYAN_STATUS_SUCCESS;
531 }
532
ZyanListRemoveRange(ZyanList * list,const ZyanListNode * first,const ZyanListNode * last)533 ZyanStatus ZyanListRemoveRange(ZyanList* list, const ZyanListNode* first, const ZyanListNode* last)
534 {
535 ZYAN_UNUSED(list);
536 ZYAN_UNUSED(first);
537 ZYAN_UNUSED(last);
538 return ZYAN_STATUS_SUCCESS;
539 }
540
ZyanListClear(ZyanList * list)541 ZyanStatus ZyanListClear(ZyanList* list)
542 {
543 return ZyanListResizeEx(list, 0, ZYAN_NULL);
544 }
545
546 /* ---------------------------------------------------------------------------------------------- */
547 /* Searching */
548 /* ---------------------------------------------------------------------------------------------- */
549
550
551
552 /* ---------------------------------------------------------------------------------------------- */
553 /* Memory management */
554 /* ---------------------------------------------------------------------------------------------- */
555
ZyanListResize(ZyanList * list,ZyanUSize size)556 ZyanStatus ZyanListResize(ZyanList* list, ZyanUSize size)
557 {
558 return ZyanListResizeEx(list, size, ZYAN_NULL);
559 }
560
ZyanListResizeEx(ZyanList * list,ZyanUSize size,const void * initializer)561 ZyanStatus ZyanListResizeEx(ZyanList* list, ZyanUSize size, const void* initializer)
562 {
563 if (!list)
564 {
565 return ZYAN_STATUS_INVALID_ARGUMENT;
566 }
567 if (size == list->size)
568 {
569 return ZYAN_STATUS_SUCCESS;
570 }
571
572 if (size == 0)
573 {
574 const ZyanBool is_dynamic = (list->allocator != ZYAN_NULL);
575 ZyanListNode* node = (is_dynamic || list->destructor) ? list->head : ZYAN_NULL;
576 while (node)
577 {
578 if (list->destructor)
579 {
580 list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
581 }
582
583 ZyanListNode* const next = node->next;
584
585 if (is_dynamic)
586 {
587 ZYAN_CHECK(list->allocator->deallocate(list->allocator, node,
588 sizeof(ZyanListNode) + list->element_size, 1));
589 }
590
591 node = next;
592 }
593
594 list->size = 0;
595 list->head = 0;
596 list->tail = 0;
597 list->first_unused = ZYAN_NULL;
598
599 return ZYAN_STATUS_SUCCESS;
600 }
601
602 if (size > list->size)
603 {
604 ZyanListNode* node;
605 for (ZyanUSize i = list->size; i < size; ++i)
606 {
607 ZYAN_CHECK(ZyanListAllocateNode(list, &node));
608 node->prev = list->tail;
609 node->next = ZYAN_NULL;
610
611 if (initializer)
612 {
613 ZYAN_MEMCPY(ZYCORE_LIST_GET_NODE_DATA(node), initializer, list->element_size);
614 }
615
616 if (!list->head)
617 {
618 list->head = node;
619 list->tail = node;
620 } else
621 {
622 list->tail->next = node;
623 list->tail = node;
624 }
625
626 // `ZyanListAllocateNode` needs the list size
627 ++list->size;
628 }
629 } else
630 {
631 for (ZyanUSize i = size; i < list->size; ++i)
632 {
633 ZyanListNode* const node = list->tail;
634
635 if (list->destructor)
636 {
637 list->destructor(ZYCORE_LIST_GET_NODE_DATA(node));
638 }
639
640 list->tail = node->prev;
641 if (list->tail)
642 {
643 list->tail->next = ZYAN_NULL;
644 }
645
646 ZYAN_CHECK(ZyanListDeallocateNode(list, node));
647 }
648
649 list->size = size;
650 }
651
652 return ZYAN_STATUS_SUCCESS;
653 }
654
655 /* ---------------------------------------------------------------------------------------------- */
656 /* Information */
657 /* ---------------------------------------------------------------------------------------------- */
658
ZyanListGetSize(const ZyanList * list,ZyanUSize * size)659 ZyanStatus ZyanListGetSize(const ZyanList* list, ZyanUSize* size)
660 {
661 if (!list)
662 {
663 return ZYAN_STATUS_INVALID_ARGUMENT;
664 }
665
666 *size = list->size;
667
668 return ZYAN_STATUS_SUCCESS;
669 }
670
671 /* ---------------------------------------------------------------------------------------------- */
672
673 /* ============================================================================================== */
674