--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/array.c	Wed Nov 09 19:26:09 2011 +0100
@@ -0,0 +1,314 @@
+/*
+ * 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(arr->data + OFFSET(i1), o1, arr->unit) == 0;
+
+	if (!found)
+		return -1;
+
+	for (i2 = found = 0; !found && i2 < arr->length; ++i2)
+		found = memcmp(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, void (*fn)(void *, void *), 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 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(const struct array *arr, int (*fn)(void *, void *), int *ix, void *u)
+{
+	int st, i;
+	void *data;
+
+	for (i = st = 0; i < arr->length && st != 1; ++i)
+		st = fn((char *) arr->data + OFFSET(i), u);
+
+	if (st)	{
+		data = (char *) arr->data + OFFSET(--i);
+		if (ix)
+			*ix = i;
+	} else
+		data = NULL;
+
+	return data;
+}
+
+/*
+ * 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;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/array.h	Wed Nov 09 19:26:09 2011 +0100
@@ -0,0 +1,83 @@
+/*
+ * array.h -- 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.
+ */
+
+#ifndef _ARRAY_H_
+#define _ARRAY_H_
+
+/* Add some nonnull attributes for gcc/clang */
+#ifdef __GNUC__
+#  define __at_malloc		__attribute__ ((malloc))
+#  define __at_nonnull(...)	__attribute__ ((nonnull (__VA_ARGS__)))
+#else
+#  define __at_malloc
+#  define __at_nonnull(...)
+#endif
+
+#define ARRAY_DEFAULT_BSIZE	128
+
+enum array_type {
+	ARRAY_FIXED	= 0,
+	ARRAY_AUTO	= 1
+};
+
+struct array {
+	enum array_type	type;	/* array's type (default FIXED) */
+	void		*data;	/* array of data */
+	int		length;	/* number of element inside */
+	size_t		size;	/* current buffer size (allocated memory) */
+	size_t		unit;	/* unit size (sizeof the object) */
+	int		bsize;	/* block size (used when growing array) */
+	int		i;	/* only for ARRAY_FOREACH(_R) */
+};
+
+typedef void (*array_map_fn)(void *, void *);
+typedef int (*array_cmp_fn)(void *, void *);
+
+struct array	*array_new(enum array_type, size_t, int) __at_malloc;
+int		array_push(struct array *, const void *) __at_nonnull(1, 2);
+int		array_insert(struct array *, const void *, int) __at_nonnull(1, 2);
+int		array_append(struct array *, const void *) __at_nonnull(1, 2);
+void		array_pop(struct array *) __at_nonnull(1);
+void		array_unqueue(struct array *) __at_nonnull(1);
+void		array_remove(struct array *, int) __at_nonnull(1);
+void		array_unref(struct array *, const void *) __at_nonnull(1);
+int		array_iswap(struct array *, int, int) __at_nonnull(1);
+int		array_pswap(struct array *, const void *, const void *) __at_nonnull(1);
+void		array_map(const struct array *, array_map_fn, void *) __at_nonnull(1, 2);
+void		*array_find(const struct array *, array_cmp_fn, int *, void *) __at_nonnull(1, 2);
+void		array_clear(struct array *) __at_nonnull(1);
+void		array_free(struct array *) __at_nonnull(1);
+
+#define ARRAY_HEAD(a, type)							\
+	(((type *)a->data)[0])
+#define ARRAY_TAIL(a, type)							\
+	(((type *)a->data)[(a->length == 0) ? 0 : a->length - 1])
+#define ARRAY_INDEX(a, i, type)							\
+	((type *)(a)->data)[((i) < 0)						\
+	    ? 0 : ((i) >= (a)->length) ? (a)->length - 1 : (i)]
+
+#define ARRAY_FOREACH_R(a, var)							\
+	for ((a)->i = 0, var = ARRAY_TAIL((a));					\
+	    (a)->i < (a)->length; ++(a)->i, --var)
+
+#define ARRAY_FOREACH(a, var, type)						\
+	for ((a)->i = 0, var = ARRAY_HEAD((a), type);				\
+		(a)->i < (a)->length;						\
+		++(a)->i, var = ARRAY_INDEX((a), (a)->i, type))
+
+#endif /* _ARRAY_H_ */

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/parray.h	Wed Nov 09 19:26:09 2011 +0100
@@ -0,0 +1,94 @@
+/*
+ * array.h -- manipulate dynamic pointer 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.
+ */
+
+#ifndef _PARRAY_H_
+#define _PARRAY_H_
+
+/* Add some nonnull attributes for gcc/clang */
+#ifdef __GNUC__
+#  define __at_malloc		__attribute__ ((malloc))
+#  define __at_nonnull(...)	__attribute__ ((nonnull (__VA_ARGS__)))
+#else
+#  define __at_malloc
+#  define __at_nonnull(...)
+#endif
+
+#define PARRAY_DEFAULT_BSIZE	128
+
+enum parray_type {
+	PARRAY_FIXED	= 0,
+	PARRAY_AUTO	= 1
+};
+
+struct parray {
+	enum parray_type type;		/* array type (default FIXED) */
+	void		**datas;	/* array of data */
+	int		length;		/* number of element inside */
+	size_t		size;		/* current buffer size (allocated memory) */
+	int		bsize;		/* block size (used when growing array) */
+	int		i;		/* only for PARRAY_FOREACH(_R) */
+};
+
+typedef void (*parray_map_fn)(void *, void *);
+typedef int (*parray_cmp_fn)(void *, void *);
+
+struct parray	*parray_new(enum parray_type, int)  __at_malloc;
+int		parray_push(struct parray *, void *) __at_nonnull(1);
+int		parray_insert(struct parray *, void *, int) __at_nonnull(1);
+int		parray_append(struct parray *, void *) __at_nonnull(1);
+void		parray_pop(struct parray *) __at_nonnull(1);
+void		parray_unqueue(struct parray *) __at_nonnull(1);
+void		parray_remove(struct parray *, int) __at_nonnull(1);
+void		parray_unref(struct parray *, const void *) __at_nonnull(1);
+int		parray_iswap(struct parray *, int, int) __at_nonnull(1);
+int		parray_pswap(struct parray *, const void *, const void *) __at_nonnull(1);
+void		parray_map(const struct parray *, parray_map_fn, void *) __at_nonnull(1, 2);
+void		*parray_find(const struct parray *, parray_cmp_fn, int *, void *) __at_nonnull(1, 2);
+void		parray_clear(struct parray *) __at_nonnull(1);
+void		parray_free(struct parray *) __at_nonnull(1);
+
+#define PARRAY_HEAD(a)								\
+	(a->datas[0])
+#define PARRAY_TAIL(a)								\
+	(a->datas[(a->length == 0) ? 0 : a->length - 1])
+#define PARRAY_INDEX(a, i)							\
+	(((i) < 0 || (a)->length == 0) ? (PARRAY_HEAD((a)))	/* < 0 head */	\
+	    : ((i) >= (a)->length) ? (PARRAY_TAIL((a)))		/* > l tail */	\
+	    : ((a)->datas[i]))					/* correct */
+
+#define PARRAY_FOREACH_R(a, var)						\
+	for ((a)->i = 0, var = PARRAY_TAIL((a));				\
+	    (a)->i < (a)->length; ++(a)->i, var = PARRAY_INDEX((a), (a)->i))
+
+#define PARRAY_FOREACH(a, var)							\
+	for ((a)->i = 0, var = PARRAY_INDEX((a), (a)->i);			\
+	    (a)->i < (a)->length; ++(a)->i, var = PARRAY_INDEX((a), (a)->i))
+
+#define PARRAY_FLUSH(a)								\
+do {										\
+	void *i;								\
+										\
+	PARRAY_FOREACH_R(a, i) {						\
+		free(i);							\
+		parray_unqueue((a));						\
+	}									\
+										\
+	(a)->length = 0;							\
+} while (/* CONSTCOND */ 0);
+
+#endif /* _PARRAY_H_ */