/**
 * \file
 *
 * \brief Simple and efficient ring buffer implementation.
 *
 * - Compiler:           IAR EWAVR32 and GNU GCC for AVR32
 * - Supported devices:  All devices
 * - AppNote:
 *
 * \author               Atmel Corporation: http://www.atmel.com \n
 *                       Support and FAQ: http://support.atmel.no/
 *
 * \page License
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * 3. The name of Atmel may not be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * 4. This software may only be redistributed and used in connection with an
 * Atmel AVR product.
 *
 * THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE
 * EXPRESSLY AND SPECIFICALLY DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 */
#ifndef RING_H_INCLUDED
#define RING_H_INCLUDED

#include <stdbool.h>

/**
 * \brief Ring buffer management data.
 *
 * This keeps track of the state of the ring buffer. The actual buffer
 * is user-defined. Typically, this struct is embedded into the same
 * struct as the ring buffer itself, but this is not a requirement.
 *
 * Note that \a head and \a tail are incremented without wrapping as
 * items are added to the buffer, so they can't be used directly as
 * offsets (they may point far outside the buffer). Always use
 * ring_get_head() and ring_get_tail(), which always return offsets
 * within the buffer, to access them.
 *
 * Also note that in order to keep the size and complexity of the code
 * down, this structure does not keep track of the size of the ring
 * buffer. The caller must pass the size as a parameter to the
 * functions which need it. This improves the code size and speed
 * significantly when the buffer size is constant.
 */
struct ring_head {
	/** \brief Offset of the next free entry in the buffer. */
	unsigned long head;
	/** \brief Offset of the first used entry in the buffer. */
	unsigned long tail;
};

#ifdef CONFIG_RING_DEBUG
#include <util.h>

/*
 * Undefined to force a link error when the ring size is constant and
 * not a power of two.
 */
extern void __bad_constant_ring_size(unsigned long size);

/* Implement this to catch bad non-constant ring sizes */
extern void bad_ring_size(unsigned long size);

static inline void ring_check_size(unsigned long size)
{
	if (!is_power_of_two(size)) {
		if (__builtin_constant_p(size))
			__bad_constant_ring_size(size);
		else
			bad_ring_size(size);
	}
}
#else
static inline void ring_check_size(unsigned long size)
{

}
#endif

/**
 * \brief Get the offset of the next unused entry in the buffer.
 *
 * Note that the value returned by this function is only meaningful if
 * there actually are any unused entries in the buffer.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \return The offset into the buffer of the next unused entry.
 */
static inline unsigned long ring_get_head(struct ring_head *ring,
		unsigned long ring_size)
{
	ring_check_size(ring_size);

	return ring->head & (ring_size - 1);
}

/**
 * \brief Get the offset of the first used entry in the buffer.
 *
 * Note that the value returned by this function is only meaningful if
 * there actually are any used entries in the buffer.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \return The offset into the buffer of the first used entry.
 */
static inline unsigned long ring_get_tail(struct ring_head *ring,
		unsigned long ring_size)
{
	ring_check_size(ring_size);

	return ring->tail & (ring_size - 1);
}

/**
 * \brief Get the number of used entries in the buffer.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \return The number of entries which can be extracted before the
 * buffer is empty.
 */
static inline unsigned long ring_entries_used(struct ring_head *ring,
		unsigned long ring_size)
{
	ring_check_size(ring_size);

	return ring->head - ring->tail;
}

/**
 * \brief Get the number of used entries in the buffer before it wraps.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \return The number of entries which can be extracted before the
 * buffer is empty or wraps around to the beginning.
 */
static inline unsigned long ring_entries_used_before_end(struct ring_head *ring,
		unsigned long ring_size)
{
	unsigned long head = ring->head;
	unsigned long tail = ring->tail;

	ring_check_size(ring_size);

	if ((head ^ tail) & ring_size)
		return ring_size - (tail & (ring_size - 1));
	else
		return head - tail;
}

/**
 * \brief Get the number of unused entries in the buffer.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \return The number of entries which can be inserted before the
 * buffer is full.
 */
static inline unsigned long ring_entries_unused(struct ring_head *ring,
		unsigned long ring_size)
{
	return ring_size - ring_entries_used(ring, ring_size);
}

/**
 * \brief Get the number of unused entries in the buffer before it
 * wraps.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \return The number of entries which can be inserted before the
 * buffer is full or wraps around to the beginning.
 */
static inline unsigned long ring_entries_unused_before_end(
		struct ring_head *ring, unsigned long ring_size)
{
	unsigned long head = ring->head;
	unsigned long tail = ring->tail;

	ring_check_size(ring_size);

	if ((head ^ tail) & ring_size)
		return ring_size + tail - head;
	else
		return ring_size - (head & (ring_size - 1));
}

/**
 * \brief Test if the ring buffer is empty.
 *
 * \param ring The ring buffer
 * \param ring_size The total number of entries in the ring buffer
 *
 * \retval true There are no used entries in the buffer.
 * \retval false There is at least one used entry in the buffer.
 */
static inline bool ring_is_empty(struct ring_head *ring,
		unsigned long ring_size)
{
	return ring->head == ring->tail;
}

/**
 * \brief Insert entries into a ring buffer.
 *
 * Adjust the buffer head to account for entries being inserted into
 * the buffer. Normally, this should be called after the actual buffer
 * contents have been updated; the barrier ensures that the compiler
 * doesn't move any buffer accesses after updating the head.
 *
 * \param ring The ring buffer
 * \param nr_entries The number of entries to insert
 */
static inline void ring_insert_entries(struct ring_head *ring,
		unsigned long nr_entries)
{
	barrier();
	ring->head += nr_entries;
}

/**
 * \brief Extract entries from a ring buffer.
 *
 * Adjust the buffer tail to account for entries being extracted from
 * the buffer. Normally, this should be called after the actual buffer
 * contents have been read; the barrier ensures that the compiler
 * doesn't move any buffer accesses after updating the tail.
 *
 * \param ring The ring buffer
 * \param nr_entries The number of entries to extract
 */
static inline void ring_extract_entries(struct ring_head *ring,
		unsigned long nr_entries)
{
	barrier();
	ring->tail += nr_entries;
}

/**
 * \brief Reset the ring buffer.
 *
 * This will mark the ring buffer as empty, and move both head and
 * tail to the beginning of the buffer.
 *
 * \param ring The ring buffer
 */
static inline void ring_reset(struct ring_head *ring)
{
	ring->head = ring->tail = 0;
}

#endif /* RING_H_INCLUDED */
