/**
   \file

   Typesafe dynamically sized arrays
*/


#include "vector.h"

#include <errno.h>
#include <stdint.h>
#include <string.h>

/** The minimum number of elements to allocate even when fewer elements are used */
#define MIN_VECTOR_ALLOC 4

/**
   Multiplies two size_t values, checking for overflows

   Both arguments are limited to the size of a uint32_t (to keep the check simple)

   Returns SIZE_MAX and sets errno on failure.
*/
static inline size_t mul_check(size_t members, size_t size) {
	uint64_t v = (uint64_t)members * size;

	if (members > UINT32_MAX || size > UINT32_MAX || v > SIZE_MAX) {
		errno = EOVERFLOW;
		return SIZE_MAX;
	}

	return v;
}

/**
   Reallocates a block of memory for an array on the heap

   May fail with EOVERFLOW (when members or size does not fit into a uint32_t,
   or their product does not fit into a size_t) or ENOMEM.
*/
static inline void * realloc_array(void *ptr, size_t members, size_t size) {
	errno = 0;
	size_t array_size = mul_check(members, size);
	if (errno)
		return NULL;

	return realloc(ptr, array_size);
}

/**
   Resizes a vector

   Vector allocations are always powers of 2.

   Internal function, use VECTOR_RESIZE() instead.
*/
bool _vector_resize(vector_desc_t *desc, void **data, size_t n, size_t elemsize) {
	desc->length = n;

	size_t alloc = desc->allocated;

	if (!alloc) {
		alloc = MIN_VECTOR_ALLOC;
		n = n*3/2;
	}

	while (alloc < n) {
		alloc <<= 1;
		if (!alloc) {
			errno = ENOMEM;
			return false;
		}
	}

	if (alloc != desc->allocated) {
		desc->allocated = alloc;
		void *tmp = realloc_array(*data, alloc, elemsize);
		if (!tmp)
			return false;

		*data = tmp;
	}

	return true;
}

/**
   Inserts an element into a vector

   Internal function, use VECTOR_INSERT() and VECTOR_ADD() instead.
*/
bool _vector_insert(vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize) {
	if (!_vector_resize(desc, data, desc->length+1, elemsize))
		return false;

	void *p = *data + pos*elemsize;

	memmove(p+elemsize, p, (desc->length-pos-1)*elemsize);
	memcpy(p, element, elemsize);

	return true;
}

/**
   Deletes an element from a vector

   Internal function, use VECTOR_DELETE() instead.
*/
void _vector_delete(vector_desc_t *desc, void **data, size_t pos, size_t elemsize) {
	void *p = *data + pos*elemsize;
	memmove(p, p+elemsize, (desc->length-pos-1)*elemsize);

	desc->length--;
}