1#include <stdio.h>
  2
  3#include "alba.h"
  4
  5#include <stdlib.h>
  6#include <string.h>
  7
  8AlbaArray alba_create_array(const uint64_t element_size, const uint64_t capacity)
  9{
 10    AlbaArray array = {0};
 11    array.element_size = element_size;
 12    if (capacity > 0)
 13    {
 14        array.capacity = capacity;
 15        array.data = reallocarray(array.data, capacity, element_size);
 16    }
 17    return array;
 18}
 19
 20void alba_array_reserve(AlbaArray* array, const uint64_t request)
 21{
 22    if (array->capacity > request) return;
 23    if (array->capacity == 0) array->capacity = 16;
 24    while (request > array->capacity)
 25    {
 26        array->capacity *= 2;
 27    }
 28    array->data = reallocarray(array->data, array->capacity, array->element_size);
 29}
 30
 31void alba_array_append(AlbaArray* array, const void* value)
 32{
 33    alba_array_extend(array, 1, value);
 34}
 35
 36void alba_array_extend(AlbaArray* array, const uint64_t size, const void* data)
 37{
 38    alba_array_reserve(array, array->length + size);
 39    memcpy(array->data + array->length * array->element_size, data, size * array->element_size);
 40    array->length += size;
 41}
 42
 43void alba_array_release(const AlbaArray* array)
 44{
 45    free(array->data);
 46}
 47
 48void alba_array_clear(AlbaArray* array)
 49{
 50    array->length = 0;
 51}
 52
 53static void swap(const uint64_t element_size, void* a, void* b, void* temp)
 54{
 55    memcpy(temp, a, element_size);
 56    memcpy(a, b, element_size);
 57    memcpy(b, temp, element_size);
 58}
 59
 60static void quicksort(
 61    const uint64_t element_size, const uint64_t length, void* data,
 62    uint32_t (*is_before_pivot)(void* pivot, void* elem), void* temp
 63)
 64{
 65    if (length < 2) return;
 66
 67    void* pivot = data + (length - 1) * element_size;
 68    void* larger = NULL;
 69    for (uint64_t i = 0; i < length; i++)
 70    {
 71        void* current = data + i * element_size;
 72        if (is_before_pivot(pivot, current))
 73        {
 74            if (larger == NULL) continue;
 75            swap(element_size, larger, current, temp);
 76            larger += element_size;
 77        }
 78        else if (larger == NULL)
 79        {
 80            larger = current;
 81        }
 82    }
 83
 84    if (larger != NULL)
 85    {
 86        swap(element_size, larger, pivot, temp);
 87        pivot = larger;
 88    }
 89
 90    const uint64_t size_before = (pivot - data);
 91    const uint64_t num_elem_before = size_before / element_size;
 92    quicksort(element_size, num_elem_before, data, is_before_pivot, temp);
 93    quicksort(element_size, length - num_elem_before - 1, data + size_before + element_size, is_before_pivot, temp);
 94}
 95
 96void alba_array_sort(const AlbaArray* array, uint32_t (*is_before_pivot)(void* pivot, void* elem))
 97{
 98    void* temp = malloc(array->element_size);
 99    quicksort(array->element_size, array->length, array->data, is_before_pivot, temp);
100    free(temp);
101}
102
103void alba_array_print(const AlbaArray* array, void (*print_element)(void* element))
104{
105    printf("len: %lu\n", array->length);
106    for (uint64_t i = 0; i < array->length; i++)
107    {
108        print_element(array->data + i * array->element_size);
109    }
110}
111
112void* alba_array_last(const AlbaArray* array)
113{
114    return array->data + array->length - 1;
115}