/*
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/** Non-thread-safe fifo (FIFO) implementation
 *
 * @file src/lib/util/fifo.c
 *
 * @copyright 2005,2006 The FreeRADIUS server project
 * @copyright 2005 Alan DeKok (aland@freeradius.org)
 */
RCSID("$Id: 3c967c14f10148ad89679fcadadb49fb8f212808 $")

#include <string.h>

#include <freeradius-devel/util/fifo.h>

struct fr_fifo_s {
	unsigned int	num;		//!< How many elements exist in the fifo.
	unsigned int	first, last;	//!< Head and tail indexes for the fifo.
	unsigned int	max;		//!< How many elements were created in the fifo.
	fr_fifo_free_t	free_node;	//!< Function to call to free nodes when the fifo is freed.

	char const	*type;		//!< Type of elements.

	void *data[1];
};

/** Free a fifo and optionally, any data still enqueued
 *
 * @param[in] fi	to free.
 * @return 0
 */
static int _fifo_free(fr_fifo_t *fi)
{
	unsigned int i;

	if (fi->free_node) {
		for (i = 0 ; i < fi->num; i++) {
			unsigned int element;

			element = i + fi->first;
			if (element > fi->max) {
				element -= fi->max;
			}

			fi->free_node(fi->data[element]);
			fi->data[element] = NULL;
		}
	}

	memset(fi, 0, sizeof(*fi));

	return 0;
}

/** Create a fifo queue
 *
 * The first element enqueued will be the first to be dequeued.
 *
 * @note The created fifo does not provide any thread synchronisation functionality
 *	such as mutexes.  If multiple threads are enqueueing and dequeueing data
 *	the callers must synchronise their access.
 *
 * @param[in] ctx	to allocate fifo array in.
 * @param[in] type	Talloc type of elements (may be NULL).
 * @param[in] max	The maximum number of elements allowed.
 * @param[in] free_node	Function to use to free node data if the fifo is freed.
 * @return
 *	- A new fifo queue.
 *	- NULL on error.
 */
fr_fifo_t *_fr_fifo_create(TALLOC_CTX *ctx, char const *type, int max, fr_fifo_free_t free_node)
{
	fr_fifo_t *fi;

	if ((max < 2) || (max > (1024 * 1024))) return NULL;

	fi = talloc_zero_size(ctx, (sizeof(*fi) + (sizeof(fi->data[0])*max)));
	if (!fi) return NULL;
	talloc_set_type(fi, fr_fifo_t);
	talloc_set_destructor(fi, _fifo_free);

	fi->max = max;
	fi->type = type;
	fi->free_node = free_node;

	return fi;
}

/** Push data onto the fifo
 *
 * @param[in] fi	FIFO to push data onto.
 * @param[in] data	to push.
 * @return
 *	- 0 on success.
 *	- -1 on error.
 */
int fr_fifo_push(fr_fifo_t *fi, void *data)
{
	if (!fi || !data) return -1;

	if (fi->num >= fi->max) return -1;

#ifndef TALLOC_GET_TYPE_ABORT_NOOP
	if (fi->type) _talloc_get_type_abort(data, fi->type, __location__);
#endif

	fi->data[fi->last++] = data;
	if (fi->last >= fi->max) fi->last = 0;
	fi->num++;

	return 0;
}

/** Pop data off of the fifo
 *
 * @param[in] fi	FIFO to pop data from.
 * @return
 *	- The data popped.
 *	- NULL if the queue is empty.
 */
void *fr_fifo_pop(fr_fifo_t *fi)
{
	void *data;

	if (!fi || (fi->num == 0)) return NULL;

	data = fi->data[fi->first++];

	if (fi->first >= fi->max) {
		fi->first = 0;
	}
	fi->num--;

	return data;
}

/** Examine the next element that would be popped
 *
 * @param[in] fi	FIFO to peek at.
 * @return
 *	- The data at the head of the queue
 *	- NULL if the queue is empty.
 */
void *fr_fifo_peek(fr_fifo_t *fi)
{
	if (!fi || (fi->num == 0)) return NULL;

	return fi->data[fi->first];
}

/** Return the number of elements in the fifo queue
 *
 * @param[in] fi	FIFO to count elements in.
 * @return the number of elements
 */
unsigned int fr_fifo_num_elements(fr_fifo_t *fi)
{
	if (!fi) return 0;

	return fi->num;
}

#ifdef TESTING

/*
 *  cc -DTESTING -I .. fifo.c -o fifo
 *
 *  ./fifo
 */

#define MAX 1024
int main(int argc, char **argv)
{
	int i, j, array[MAX];
	fr_fifo_t *fi;

	fi = fr_fifo_create(NULL, MAX, NULL);
	if (!fi) fr_exit(1);

	for (j = 0; j < 5; j++) {
#define SPLIT (MAX/3)
#define COUNT ((j * SPLIT) + i)
		for (i = 0; i < SPLIT; i++) {
			array[COUNT % MAX] = COUNT;

			if (fr_fifo_push(fi, &array[COUNT % MAX]) < 0) {
				fprintf(stderr, "%d %d\tfailed pushing %d\n",
					j, i, COUNT);
				fr_exit(2);
			}

			if (fr_fifo_num_elements(fi) != (i + 1)) {
				fprintf(stderr, "%d %d\tgot size %d expected %d\n",
					j, i, i + 1, fr_fifo_num_elements(fi));
				fr_exit(1);
			}
		}

		if (fr_fifo_num_elements(fi) != SPLIT) {
			fprintf(stderr, "HALF %d %d\n",
				fr_fifo_num_elements(fi), SPLIT);
			fr_exit(1);
		}

		for (i = 0; i < SPLIT; i++) {
			int *p;

			p = fr_fifo_pop(fi);
			if (!p) {
				fprintf(stderr, "No pop at %d\n", i);
				fr_exit(3);
			}

			if (*p != COUNT) {
				fprintf(stderr, "%d %d\tgot %d expected %d\n",
					j, i, *p, COUNT);
				fr_exit(4);
			}

			if (fr_fifo_num_elements(fi) != SPLIT - (i + 1)) {
				fprintf(stderr, "%d %d\tgot size %d expected %d\n",
					j, i, SPLIT - (i + 1), fr_fifo_num_elements(fi));
				fr_exit(1);
			}
		}

		if (fr_fifo_num_elements(fi) != 0) {
			fprintf(stderr, "ZERO %d %d\n",
				fr_fifo_num_elements(fi), 0);
			fr_exit(1);
		}
	}

	talloc_free(fi);

	fr_exit(0);
}
#endif
