/*
 * parray.c -- manipulate dynamic pointer arrays
 *
 * Copyright (c) 2011, 2012, 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 "parray.h"

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

static int		grow(struct parray *);

int
parray_init(struct parray *arr)
{
	/* Set defaults if needed */
	arr->bsize	= (arr->bsize <= 0) ? PARRAY_DEFAULT_BSIZE : arr->bsize;
	arr->malloc	= (arr->malloc == NULL) ? &malloc : arr->malloc;
	arr->realloc	= (arr->realloc == NULL) ? &realloc : arr->realloc;

	arr->bsize	+= (arr->flags & PARRAY_NULLEND) ? 1 : 0;
	arr->size	= LENGTH(arr->bsize);

	if ((arr->data = arr->malloc(arr->size)) == NULL)
		return -1;

	memset(arr->data, 0, arr->size);

	return 0;
}

/*
 * Valid options that can be set for an array :
 * l -> optional array block size of type int
 * m -> malloc function that must matches void * (*malloc)(size_t)
 * r -> realloc function that must matches void * (*realloc)(void *, size_t)
 * f -> parray flags of type int
 */
void
parray_set(struct parray *arr, const char *fmt, ...)
{
	va_list ap;
	const char *p;

	va_start(ap, fmt);
	for (p = fmt; *p != '\0'; ++p)
		switch (*p) {
		case 'l':
			arr->bsize = va_arg(ap, int);
			break;
		case 'm':
			arr->malloc = va_arg(ap, void * (*)(size_t));
			break;
		case 'r':
			arr->realloc = va_arg(ap, void * (*)(void *, size_t));
			break;
		case 'f':
			arr->flags = va_arg(ap, int);
			break;
		default:
			break;
		}
}

/*
 * 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. Returns -1 on failure or 0 on success.
 */
int
parray_push(struct parray *arr, void *data)
{
	if (grow(arr) < 0)
		return -1;

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

	if (arr->flags & PARRAY_NULLEND)
		arr->data[arr->length] = NULL;

	return 0;
}

/*
 * Insert the data at the specified index. The function returns -1 on
 * allocation failure or the position of the added element.
 */
int
parray_insert(struct parray *arr, void *data, int index)
{
	if (arr->flags & PARRAY_INSERTSAFE)
		if (index < 0 || index > arr->length)
			return -1;

	if (index < 0)
		return parray_push(arr, data);
	if (index >= arr->length)
		return parray_append(arr, data);

	/* Good place */
	memmove(&arr->data[index + 1], &arr->data[index],
		LENGTH(arr->length++ - index));
	arr->data[index] = data;

	if (arr->flags & PARRAY_NULLEND)
		arr->data[arr->length] = NULL;

	return index;
}

/*
 * Append the data to the end of array. Returns -1 on failure or the position
 * of the added element.
 */
int
parray_append(struct parray *arr, void *data)
{
	if (grow(arr) < 0)
		return -1;

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

	if (arr->flags & PARRAY_NULLEND)
		arr->data[arr->length] = NULL;

	return (arr->length - 1);
}

/*
 * Remove the array's head.
 */
void
parray_pop(struct parray *arr)
{
	parray_iremove(arr, 0);
}

/*
 * Remove the array's tail.
 */
void
parray_unqueue(struct parray *arr)
{
	parray_iremove(arr, arr->length - 1);
}

/*
 * Remove the data at the specified index. Bounds are checked.
 */
void
parray_iremove(struct parray *arr, int index)
{
	if (arr->length > 0 && index >= 0 && index < arr->length) {
		if (arr->flags & PARRAY_FASTREMOVE)
			arr->data[index] = arr->data[--arr->length];
		else
			memmove(&arr->data[index], &arr->data[index + 1],
			    LENGTH(arr->length-- - index - 1));
	}

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

/*
 * Remove the object referenced by the `data' argument. Useful when you
 * don't know the index.
 */
void
parray_premove(struct parray *arr, const void *data)
{
	void *elm;
	int i;

	PARRAY_FOREACH(arr, elm, i) {
		if (elm == data) {
			parray_iremove(arr, i);
			break;
		}
	}
}

/*
 * 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
parray_iswap(struct parray *arr, int i1, int i2)
{
	void *tmp;

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

	tmp = arr->data[i1];
	arr->data[i1] = arr->data[i2];
	arr->data[i2] = 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
parray_pswap(struct parray *arr, const void *o1, const void *o2)
{
	int found, i1, i2;

	for (i1 = found = 0; !found && i1 < arr->length; ++i1)
		found = arr->data[i1] == o1;

	if (!found)
		return -1;

	for (i2 = found = 0; !found && i2 < arr->length; ++i2)
		found = arr->data[i2] == o2;

	if (!found)
		return -1;

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

/*
 * Apply the function `fn' on each object and give the optional `udata'
 * argument to the function too.
 */
void
parray_map(const struct parray *arr, parray_map_t fn, void *udata)
{
	int i;

	for (i = 0; i < arr->length; ++i)
		fn(arr->data[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 points to the array data at the correct index. If the comparison
 * function nevers returns 1, array_find returns -1.
 */
int
parray_find(const struct parray *arr, parray_cmp_t fn, void *ptr, void *u)
{
	int st, i;

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

	if (st && ptr)
		*(void **)ptr = arr->data[i - 1];

	return (st) ? i - 1 : -1;
}

void *
parray_first(const struct parray *arr)
{
	return arr->data[0];
}

void *
parray_get(const struct parray *arr, int idx)
{
	if (idx < 0)
		return parray_first(arr);
	if (idx >= arr->length)
		return parray_last(arr);

	return arr->data[idx];
}

void *
parray_last(const struct parray *arr)
{
	if (arr->length == 0)
		return parray_first(arr);

	return arr->data[arr->length - 1];
}

/*
 * Reset the array by setting each pointer to NULL and the length to 0.
 */
void
parray_clear(struct parray *arr)
{
	arr->data[0]	= NULL;
	arr->length	= 0;
}

/*
 * Same as parray_clear except it also free the array object.
 */
void
parray_free(struct parray *arr)
{
	parray_clear(arr);
	free(arr->data);

	arr->data	= NULL;
	arr->size	= 0;
}

/*
 * Trim down the array to the correct size.
 */
void *
parray_trim(struct parray *arr)
{
	int count = arr->length;

	if (arr->flags & PARRAY_NULLEND)
		++ count;

	return arr->realloc(arr->data, count * sizeof (void *));
}

/*
 * 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
grow(struct parray *arr)
{
	unsigned int toadd = (arr->flags & PARRAY_NULLEND) ? 2 : 1;

	if ((arr->size / sizeof (void *)) - arr->length >= toadd)
		return 0;

	if (!(arr->flags & PARRAY_FIXED)) {
		if ((arr->data = arr->realloc(arr->data, arr->size +
		    LENGTH(arr->bsize))) == NULL) {
			arr->size = arr->length = 0;
			return -1;
		}

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

	return 0;
}