/*
 * array.h -- manipulate dymanic array
 *
 * Copyright (c) 2011, David Demelier <markand@malikania.fr>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "array.h"

#define SIZE(x)	(sizeof (void *) * (x))

static int	array_grow(struct array *);

struct array *
array_new(const void *data, size_t bsize, int flags)
{
	struct array *arr;

	if (!(arr = malloc(sizeof (struct array))))
		return NULL;

	memset(arr, 0, sizeof (struct array));
	arr->bsize	= (bsize == 0) ? ARRAY_DEFAULT_BSIZE : bsize;
	arr->size	= bsize + 1;
	arr->flags	= flags;

	if (!(arr->data = calloc(bsize + 1, sizeof (void *)))) {
		free(arr);
		return NULL;
	}

	if (data)
		arr->data[arr->length++] = (void *) data;

	return arr;
}

/*
 * Add to the head of array. NOTE: this may be very slow when adding a lot
 * of object (about 100000). If you need to add a lot of data please consider
 * using linked list instead or use array_append and then use reverse foreach
 * functions.
 */

int
array_push(struct array *arr, const void *data)
{
	if (array_grow(arr) < 0)
		return -1;

	memmove(arr->data + 1, arr->data, SIZE(arr->length++));
	arr->data[0] = (void *) data;

	return 0;
}

/*
 * Insert the data to the specified index. The function returns -1 on
 * allocation failure if the array need to grow or when the index is out
 * of bounds otherwise 0 is returned.
 */

int
array_insert(struct array *arr, const void *data, int index)
{
	if (index > arr->length - 1 || index < 0 || array_grow(arr) < 0)
		return -1;

	memmove(arr->data + index + 1, arr->data + index,
	    SIZE(arr->length++ - index));
	arr->data[index] = (void *) data;

	return 0;
}

/*
 * Append the data to the end of array.
 */

int
array_append(struct array *arr, const void *data)
{
	if (array_grow(arr) < 0)
		return -1;

	arr->data[arr->length++] = (void *) data;

	return 0;
}

/*
 * Remove the array's head and return the object or NULL if
 * the array is empty.
 */

void *
array_pop(struct array *arr)
{
	void *data;

	if (arr->length == 0)
		return NULL;

	data = arr->data[0];
	memmove(arr->data, arr->data + 1, SIZE(arr->length));
	arr->data[--arr->length] = NULL;

	return data;
}

/*
 * Remove the array's queue and return the object or NULL
 * if the array is empty.
 */

void *
array_unqueue(struct array *arr)
{
	void *data;

	if (arr->length == 0)
		return NULL;

	data = arr->data[--arr->length];
	arr->data[arr->length] = NULL;

	return data;
}

/*
 * Remove the entry at the specified index and return it. If the index is out of
 * bounds or the list is empty the functions returns NULL.
 */

void *
array_remove(struct array *arr, int index)
{
	void *data;

	if (arr->length == 0 || index < 0 || index > arr->length - 1)
		return NULL;

	data = arr->data[index];
	memmove(arr->data + index, arr->data + index + 1,
	    SIZE(arr->length - index));
	arr->data[--arr->length] = NULL;

	return data;
}

/*
 * Apply the function `fn' on each object and give the optional `udata'
 * argument to the function too.
 */

void
array_map(struct array *arr, void (*fn)(void *, void *), void *udata)
{
	size_t i;

	for (i = 0; arr->data[i]; ++i)
		fn(arr->data[i], udata);
}

/*
 * Compare each object with the user supplied function. If the `fn' function
 * returns 1 then the data is returned. Optional idx argument can be set to
 * indicate the data position. If the data was not found the function returns
 * NULL.
 */

void *
array_find(struct array *arr, int (*fn)(void *, void *), void *udata, int *idx)
{
	size_t i;
	int st;
	void *data;

	for (i = st = 0; arr->data[i] && !st; ++i)
		st = fn(arr->data[i], udata);

	if (st)	{
		data = arr->data[--i];
		if (idx)
			*idx = i;
	} else
		data = NULL;

	return data;
}

/*
 * Reset the array, if the trash argument is set it will free the object
 * too, otherwise the array is just truncated to 0 length.
 */

void
array_clear(struct array *arr, int trashit)
{
	if (trashit) {
		size_t i;

		for (i = 0; arr->data[i]; ++i)
			free(arr->data[i]);
	}

	memset(arr->data, 0, SIZE(arr->size));
	arr->length = 0;
}

/*
 * Same as array_clear except it also free the array object.
 */

void
array_free(struct array *arr, int trashit)
{
	array_clear(arr, trashit);

	free(arr->data);
	free(arr);
}

/*
 * Increate the array storage when it is full. If the buffer is fixed size
 * it returns -1 on full buffer otherwise 0 is returned if allocation
 * succeeded.
 */

static int
array_grow(struct array *arr)
{
	if (arr->size - 1 > arr->length)
		return 0;

	if (arr->flags & ARRAY_AUTO) {
		if (!(arr->data = realloc(arr->data, SIZE(arr->size + arr->bsize))))
			return -1;

		arr->size += arr->bsize;
	} else
		return (arr->size - 1 == arr->length) ? -1 : 0;

	memset(arr->data + arr->length, 0, SIZE(arr->size - arr->length));

	return 0;
}