1#include <stdio.h>
  2
  3#include "alba.h"
  4
  5#include <stdlib.h>
  6#include <string.h>
  7
  8DynArray dynarray_new(const uint64_t element_size, const uint64_t capacity)
  9{
 10    DynArray array = {0};
 11    array.element_size = element_size;
 12    if (capacity > 0)
 13    {
 14        dynarray_reserve(&array, capacity);
 15    }
 16    return array;
 17}
 18
 19void dynarray_reserve(DynArray* array, const uint64_t request)
 20{
 21    if (array->capacity > request) return;
 22    if (array->capacity == 0) array->capacity = 16;
 23    while (request > array->capacity)
 24    {
 25        array->capacity *= 2;
 26    }
 27    array->data = reallocarray(array->data, array->capacity, array->element_size);
 28}
 29
 30void dynarray_append(DynArray* array, const void* value)
 31{
 32    dynarray_extend(array, 1, value);
 33}
 34
 35void dynarray_extend(DynArray* array, const uint64_t size, const void* data)
 36{
 37    dynarray_reserve(array, array->length + size);
 38    memcpy(array->data + array->length * array->element_size, data, size * array->element_size);
 39    array->length += size;
 40}
 41
 42void dynarray_release(const DynArray* array)
 43{
 44    free(array->data);
 45}
 46
 47void dynarray_clear(DynArray* array)
 48{
 49    array->length = 0;
 50}
 51
 52static void swap(const uint64_t element_size, void* a, void* b, void* temp)
 53{
 54    memcpy(temp, a, element_size);
 55    memcpy(a, b, element_size);
 56    memcpy(b, temp, element_size);
 57}
 58
 59static void quicksort(
 60    const uint64_t element_size, const uint64_t length, void* data,
 61    uint32_t (*is_before_pivot)(void* pivot, void* elem), void* temp
 62)
 63{
 64    if (length < 2) return;
 65
 66    void* pivot = data + (length - 1) * element_size;
 67    void* larger = NULL;
 68    for (uint64_t i = 0; i < length; i++)
 69    {
 70        void* current = data + i * element_size;
 71        if (is_before_pivot(pivot, current))
 72        {
 73            if (larger == NULL) continue;
 74            swap(element_size, larger, current, temp);
 75            larger += element_size;
 76        }
 77        else if (larger == NULL)
 78        {
 79            larger = current;
 80        }
 81    }
 82
 83    if (larger != NULL)
 84    {
 85        swap(element_size, larger, pivot, temp);
 86        pivot = larger;
 87    }
 88
 89    const uint64_t size_before = (pivot - data);
 90    const uint64_t num_elem_before = size_before / element_size;
 91    quicksort(element_size, num_elem_before, data, is_before_pivot, temp);
 92    quicksort(element_size, length - num_elem_before - 1, data + size_before + element_size, is_before_pivot, temp);
 93}
 94
 95void dynarray_sort(const DynArray* array, uint32_t (*is_before_pivot)(void* pivot, void* elem))
 96{
 97    void* temp = malloc(array->element_size);
 98    quicksort(array->element_size, array->length, array->data, is_before_pivot, temp);
 99    free(temp);
100}