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   */
 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   */
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
526  ZyanStatus ZyanListRemove(ZyanList* list, const ZyanListNode* node)
527  {
528      ZYAN_UNUSED(list);
529      ZYAN_UNUSED(node);
530      return ZYAN_STATUS_SUCCESS;
531  }
532  
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  
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  
556  ZyanStatus ZyanListResize(ZyanList* list, ZyanUSize size)
557  {
558      return ZyanListResizeEx(list, size, ZYAN_NULL);
559  }
560  
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  
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  /* ============================================================================================== */