/*
 * array.c -- manipulate dynamic arrays
 *
 * 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 OFFSET(x)	(arr->unit * (x))

static int	array_grow(struct array *);

struct array *
array_new(enum array_type type, size_t unit, int length)
{
	struct array *arr;

	if (unit == 0 || (arr = malloc(sizeof (struct array))) == NULL)
		return NULL;

	memset(arr, 0, sizeof (struct array));
	arr->type	= type;
	arr->bsize	= (length == 0) ? ARRAY_DEFAULT_BSIZE : length;
	arr->unit	= unit;
	arr->size	= OFFSET(arr->bsize);

	if ((arr->data = malloc(arr->size)) == NULL) {
		free(arr);
		return NULL;
	}

	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.
 */

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

	memmove((char *)arr->data + arr->unit, arr->data, OFFSET(arr->length++));
	memcpy((char *)arr->data, data, arr->unit);

	return 0;
}

/*
 * Insert the data at the specified index. The function returns -1 on
 * allocation failure or when the index is outof 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((char *)arr->data + OFFSET(index + 1),
	    (char *)arr->data + OFFSET(index), OFFSET(arr->length++ - index));
	memcpy((char *)arr->data + OFFSET(index), data, arr->unit);

	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;

	memcpy((char *)arr->data + OFFSET(arr->length++), data, arr->unit);

	return 0;
}

/*
 * Remove the array's head.
 */

void
array_pop(struct array *arr)
{
	if (arr->length > 0) {
		memmove((char *)arr->data, (char *)arr->data + OFFSET(1),
		    OFFSET(--arr->length));
		memset((char *)arr->data + OFFSET(arr->length), 0, arr->unit);
	}
}

/*
 * Remove the array's tail.
 */

void
array_unqueue(struct array *arr)
{
	if (arr->length > 0)
		memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit);
}

/*
 * Remove the data at the specified index. Bounds are checked.
 */

void
array_remove(struct array *arr, int index)
{
	if (arr->length > 0 && index >= 0 && index < arr->length) {
		memmove((char *)arr->data + OFFSET(index),
		    (char *)arr->data + OFFSET(index + 1),
		    OFFSET(arr->length - index - 1));
		memset((char *)arr->data + OFFSET(--arr->length), 0, arr->unit);
	}
}

/*
 * Remove the object referenced by the `data' argument. Useful when you
 * don't know the index.
 */

void
array_unref(struct array *arr, const void *data)
{
	void *elm;
	int i;

	for (i = 0; i < arr->length; ++i) {
		elm = (char *)arr->data + OFFSET(i);

		if (memcmp(elm, data, arr->unit) == 0)
			array_remove(arr, i);
	}
}

/*
 * Swap the two elements referenced by index `i1' and `i2'. This function needs
 * to allocate data to swap elements thus if the functions fails it returns -1
 * otherwise 0 is returned.
 */

int
array_iswap(struct array *arr, int i1, int i2)
{
	void *tmp;

	/* Out of bounds */
	if (i1 >= arr->length || i1 < 0 || i2 >= arr->length || i2 < 0)
		return -1;

	/*
	 * Only allocate at this time, the user may do not want to use this
	 * function.
	 */

	if ((tmp = malloc(arr->unit)) == NULL)
		return -1;

	memcpy((char *)tmp, (char *)arr->data + OFFSET(i1), arr->unit);
	memcpy((char *)arr->data + OFFSET(i1), (char *)arr->data + OFFSET(i2),
	    arr->unit);
	memcpy((char *)arr->data + OFFSET(i2), (char *)tmp, arr->unit);

	/*
	 * Clear bytes for safety you probably don't want a password or
	 * secure data to be left somewhere in the memory.
	 */

	memset(tmp, 0, arr->unit);
	free(tmp);

	return 0;
}

/*
 * Swap the two elements referenced by data `o1' and `o2'. This function
 * may be slow on large arrays since it must travel all the object
 * to find the indexes.
 */

int
array_pswap(struct array *arr, const void *o1, const void *o2)
{
	int found, i1, i2;

	for (i1 = found = 0; !found && i1 < arr->length; ++i1)
		found = memcmp((char *)arr->data + OFFSET(i1), o1, arr->unit) == 0;

	if (!found)
		return -1;

	for (i2 = found = 0; !found && i2 < arr->length; ++i2)
		found = memcmp((char *)arr->data + OFFSET(i2), o2, arr->unit) == 0;

	if (!found)
		return -1;

	return array_iswap(arr, --i1, --i2);
}

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

void
array_map(const struct array *arr, array_map_fn fn, void *udata)
{
	int i;

	for (i = 0; i < arr->length; ++i)
		fn((char *)arr->data + OFFSET(i), udata);
}

/*
 * Compare each object with the user supplied function. If the `fn' function
 * returns 1 then the index of the data position is returned and the parameter
 * data is filled with the array data at the correct index. If the comparison
 * function nevers returns 1, array_find returns -1.
 */

int
array_find(const struct array *arr, array_cmp_fn fn, void *data, void *u)
{
	int st, i;

	for (i = st = 0; i < arr->length && st != 1; ++i)
		st = fn((char *)arr->data + OFFSET(i), u);

	if (st)
		memcpy(data, (char *)arr->data + OFFSET(--i), arr->unit);
	else
		i = -1;

	return i;
}

/*
 * Erase every bytes and set the length to 0.
 */

void
array_clear(struct array *arr)
{
	memset(arr->data, 0, arr->size);
	arr->length = 0;
}

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

void
array_free(struct array *arr)
{
	array_clear(arr);

	if (arr->data)
		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 / arr->unit) > (size_t) arr->length)
		return 0;

	if (arr->type == ARRAY_AUTO) {
		if ((arr->data = realloc(arr->data, arr->size +
		    OFFSET(arr->bsize))) == NULL)
			return -1;

		arr->size += OFFSET(arr->bsize);
	} else
		return -1;

	return 0;
}