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

/** Implementation of a circular buffer with fixed element size
 *
 * This offers similar functionality to ring_buffer.c, but uses a fixed
 * element size, and expects all elements to be talloced.
 *
 * @file src/lib/util/fring.c
 *
 * @copyright 2013 The FreeRADIUS server project
 * @copyright 2013 Arran Cudbard-Bell (a.cudbardb@freeradius.org)
 */
RCSID("$Id: 9438d77eea3fafc3f2a3bb54cdc90a036fba9154 $")

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

#include <pthread.h>

/** Standard thread safe circular buffer
 *
 */
struct fr_fring_buffer {
	void const		*end;			//!< End of allocated memory

	uint32_t		size;
	uint32_t		in;			//!< Write index
	uint32_t		out;			//!< Read index

	void			**data;			//!< Ring buffer data

	bool			lock;			//!< Perform thread synchronisation

	pthread_mutex_t		mutex;			//!< Thread synchronisation mutex
};

/** Destroy mutex associated with ring buffer
 *
 * @param[in] fring being freed.
 * @return 0
 */
static int _fring_free(fr_fring_t *fring)
{
	void *next;

	/*
	 *	Free any data left in the buffer
	 */
	while ((next = fr_fring_next(fring))) talloc_free(next);

	if (fring->lock) pthread_mutex_destroy(&fring->mutex);

	return 0;
}

/** Initialise a ring buffer with fixed element size
 *
 * @param[in] ctx	to allocate the buffer in.
 * @param[in] size	of buffer to allocate.
 * @param[in] lock	If true, insert and next operations will lock the buffer.
 * @return
 *	- New fring.
 *	- NULL on error.
 */
fr_fring_t *fr_fring_alloc(TALLOC_CTX *ctx, uint32_t size, bool lock)
{
	fr_fring_t *fring;

	uint32_t pow;

	/*
	 *	Find the nearest power of 2 (rounding up)
	 */
	for (pow = 0x00000001;
	     pow < size;
	     pow <<= 1);
	size = pow;
	size--;

	fring = talloc_zero(ctx, fr_fring_t);
	if (!fring) return NULL;
	talloc_set_destructor(fring, _fring_free);

	fring->data = talloc_zero_array(fring, void *, size);
	if (!fring->data) {
		talloc_free(fring);
		return NULL;
	}
	fring->size = size;

	if (lock) {
		fring->lock = true;
		pthread_mutex_init(&fring->mutex, NULL);
	}

	return fring;
}

/** Insert a new item into the circular buffer, freeing the tail if we hit it
 *
 * @param[in] fring	to insert item into
 * @param[in] in	item to insert (must have been allocated with talloc).
 * @return
 *	- 0 if we inserted the item without freeing existing items.
 *	- 1 if we inserted the item, but needed to free an existing item.
 */
int fr_fring_overwrite(fr_fring_t *fring, void *in)
{
	bool freed = false;
	if (fring->lock) pthread_mutex_lock(&fring->mutex);

	if (fring->data[fring->in]) {
		freed = true;
		talloc_free(fring->data[fring->in]);
	}

	fring->data[fring->in] = in;
	fring->in = (fring->in + 1) & fring->size;

	/* overwrite - out is advanced ahead of in */
	if (fring->in == fring->out) fring->out = (fring->out + 1) & fring->size;

	if (fring->lock) pthread_mutex_unlock(&fring->mutex);

	return freed ? 1 : 0;
}

/** Insert a new item into the circular buffer if the buffer is not full
 *
 * @param[in] fring	to insert item into.
 * @param[in] in	item to insert.
 * @return
 *	- 0 if we inserted the item.
 *	- -1 if there's no more space in the buffer to insert items
 */
int fr_fring_insert(fr_fring_t *fring, void *in)
{
	if (fring->lock) pthread_mutex_lock(&fring->mutex);

	if (fring->data[fring->in]) {
		if (fring->lock) pthread_mutex_unlock(&fring->mutex);

		return -1;
	}

	fring->data[fring->in] = in;
	fring->in = (fring->in + 1) & fring->size;

	/* overwrite - out is advanced ahead of in */
	if (fring->in == fring->out) fring->out = (fring->out + 1) & fring->size;

	if (fring->lock) pthread_mutex_unlock(&fring->mutex);

	return 0;
}

/** Remove an item from the buffer
 *
 * @param[in] fring	to drain data from.
 * @return
 *	- NULL if no dataents in the buffer.
 *	- An dataent from the buffer reparented to ctx.
 */
void *fr_fring_next(fr_fring_t *fring)
{
	void *out = NULL;

	if (fring->lock) pthread_mutex_lock(&fring->mutex);

	/* Buffer is empty */
	if (fring->out == fring->in) goto done;

	out = fring->data[fring->out];
	fring->data[fring->out] = NULL;
	fring->out = (fring->out + 1) & fring->size;

done:
	if (fring->lock) pthread_mutex_unlock(&fring->mutex);

	return out;
}
