#include <string.h>
#include "array.h"

/* Invariant: There are always >= next_pot(n_elements) elements
 * allocated for data.
 */
struct array_t
{
    size_t      element_size;
    size_t      n_elements;
    /* uint8_t     data[]; */
};

static size_t
next_pot (size_t n)
{
    n -= 1;
        
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    if (sizeof (n) > 4)
        n |= (n >> 32);

    return n + 1;
}

static bool_t
array_reallocate (array_t **array, size_t n_elements)
{
    size_t alloc = next_pot (n_elements);

    if (alloc != next_pot ((*array)->n_elements))
    {
        array_t *new_array;

        if (!(new_array = realloc (
                  (*array), sizeof (array_t) + alloc * (*array)->element_size)))
            return FALSE;

        *array = new_array;
    }

    (*array)->n_elements = n_elements;
    return TRUE;
}

bool_t
array_create (array_t **array, size_t element_size)
{
    if (!(*array = malloc (sizeof (array_t))))
        return FALSE;

    (*array)->element_size = element_size;
    (*array)->n_elements = 0;

    return TRUE;
}

/* Delete the last n_elements */
void
array_delete_tail (array_t **array, size_t n_delete)
{
    array_reallocate (array, (*array)->n_elements - n_delete);
}

void
array_free (array_t **array)
{
    free (*array);
    *array = NULL;
}

void *
array_get_data (array_t **array, size_t *n_elements)
{
    if (n_elements)
        *n_elements = (*array)->n_elements;

    return (*array) + 1;
}

bool_t
array_append (array_t **array, size_t n_elements, void *tail)
{
    size_t old_n_elements = (*array)->n_elements;
    size_t tail_offset = old_n_elements * (*array)->element_size;
    
    if (!array_reallocate (array, old_n_elements + n_elements))
        return FALSE;

    if (tail)
        *(void **)tail = ((uint8_t *)((*array) + 1)) + tail_offset;

    return TRUE;
}