4 * This file is part of BeRTOS.
6 * Bertos is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * As a special exception, you may use this file as part of a free software
21 * library without restriction. Specifically, if other files instantiate
22 * templates or use macros or inline functions from this file, or you compile
23 * this file and link it with other files to produce an executable, this
24 * file does not by itself cause the resulting executable to be covered by
25 * the GNU General Public License. This exception does not however
26 * invalidate any other reasons why the executable file might be covered by
27 * the GNU General Public License.
29 * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
30 * Copyright 2001, 2008 Bernie Innocenti <bernie@codewiz.org>
33 * \defgroup fifobuf FIFO buffer
37 * \brief General pourpose FIFO buffer implemented with a ring buffer
39 * \li \c begin points to the first buffer element;
40 * \li \c end points to the last buffer element (unlike the STL convention);
41 * \li \c head points to the element to be extracted next;
42 * \li \c tail points to the location following the last insertion;
43 * \li when any of the pointers advances beyond \c end, it is reset
48 * +-----------------------------------+
49 * | empty | valid data | empty |
50 * +-----------------------------------+
56 * The buffer is EMPTY when \c head and \c tail point to the same location:
57 * \code head == tail \endcode
59 * The buffer is FULL when \c tail points to the location immediately
61 * \code tail == head - 1 \endcode
63 * The buffer is also FULL when \c tail points to the last buffer
64 * location and head points to the first one:
65 * \code head == begin && tail == end \endcode
67 * \author Bernie Innocenti <bernie@codewiz.org>
73 #include <cpu/types.h>
75 #include <cfg/debug.h>
77 typedef struct FIFOBuffer
79 unsigned char * volatile head;
80 unsigned char * volatile tail;
86 #define ASSERT_VALID_FIFO(fifo) \
88 ASSERT((fifo)->head >= (fifo)->begin); \
89 ASSERT((fifo)->head <= (fifo)->end); \
90 ASSERT((fifo)->tail >= (fifo)->begin); \
91 ASSERT((fifo)->tail <= (fifo)->end); \
96 * Declare a static fifo buffer
98 #define DECLARE_FIFO(_name, _ptr, _size) \
104 .end = (_ptr) + (_size) - 1, \
106 STATIC_ASSERT((_size) > 1)
109 * Check whether the fifo is empty
111 * \note Calling fifo_isempty() is safe while a concurrent
112 * execution context is calling fifo_push() or fifo_pop()
113 * only if the CPU can atomically update a pointer
114 * (which the AVR and other 8-bit processors can't do).
116 * \sa fifo_isempty_locked
118 INLINE bool fifo_isempty(const FIFOBuffer *fb)
120 //ASSERT_VALID_FIFO(fb);
121 return fb->head == fb->tail;
126 * Check whether the fifo is full
128 * \note Calling fifo_isfull() is safe while a concurrent
129 * execution context is calling fifo_pop() and the
130 * CPU can update a pointer atomically.
131 * It is NOT safe when the other context calls
133 * This limitation is not usually problematic in a
134 * consumer/producer scenario because the
135 * fifo_isfull() and fifo_push() are usually called
136 * in the producer context.
138 INLINE bool fifo_isfull(const FIFOBuffer *fb)
140 //ASSERT_VALID_FIFO(fb);
142 ((fb->head == fb->begin) && (fb->tail == fb->end))
143 || (fb->tail == fb->head - 1);
148 * Push a character on the fifo buffer.
150 * \note Calling \c fifo_push() on a full buffer is undefined.
151 * The caller must make sure the buffer has at least
152 * one free slot before calling this function.
154 * \note It is safe to call fifo_pop() and fifo_push() from
155 * concurrent contexts, unless the CPU can't update
156 * a pointer atomically (which the AVR and other 8-bit
157 * processors can't do).
159 * \sa fifo_push_locked
161 INLINE void fifo_push(FIFOBuffer *fb, unsigned char c)
164 #pragma interrupt called
166 //ASSERT_VALID_FIFO(fb);
168 /* Write at tail position */
171 if (UNLIKELY(fb->tail == fb->end))
172 /* wrap tail around */
173 fb->tail = fb->begin;
175 /* Move tail forward */
181 * Pop a character from the fifo buffer.
183 * \note Calling \c fifo_pop() on an empty buffer is undefined.
184 * The caller must make sure the buffer contains at least
185 * one character before calling this function.
187 * \note It is safe to call fifo_pop() and fifo_push() from
188 * concurrent contexts.
190 INLINE unsigned char fifo_pop(FIFOBuffer *fb)
193 #pragma interrupt called
195 //ASSERT_VALID_FIFO(fb);
197 if (UNLIKELY(fb->head == fb->end))
199 /* wrap head around */
200 fb->head = fb->begin;
204 /* move head forward */
205 return *(fb->head++);
210 * Make the fifo empty, discarding all its current contents.
212 INLINE void fifo_flush(FIFOBuffer *fb)
214 //ASSERT_VALID_FIFO(fb);
219 #if CPU_REG_BITS >= CPU_BITS_PER_PTR
222 * 16/32bit CPUs that can update a pointer with a single write
223 * operation, no need to disable interrupts.
225 #define fifo_isempty_locked(fb) fifo_isempty((fb))
226 #define fifo_push_locked(fb, c) fifo_push((fb), (c))
227 #define fifo_pop_locked(fb) fifo_pop((fb))
228 #define fifo_flush_locked(fb) fifo_flush((fb))
230 #else /* CPU_REG_BITS < CPU_BITS_PER_PTR */
233 * Similar to fifo_isempty(), but with stronger guarantees for
234 * concurrent access between user and interrupt code.
236 * \note This is actually only needed for 8-bit processors.
240 INLINE bool fifo_isempty_locked(const FIFOBuffer *fb)
243 ATOMIC(result = fifo_isempty(fb));
249 * Similar to fifo_push(), but with stronger guarantees for
250 * concurrent access between user and interrupt code.
252 * \note This is actually only needed for 8-bit processors.
256 INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c)
258 ATOMIC(fifo_push(fb, c));
261 /* Probably not really needed, but hard to prove. */
262 INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb)
265 ATOMIC(c = fifo_pop(fb));
270 * Similar to fifo_flush(), but with stronger guarantees for
271 * concurrent access between user and interrupt code.
273 * \note This is actually only needed for 8-bit processors.
277 INLINE void fifo_flush_locked(FIFOBuffer *fb)
279 ATOMIC(fifo_flush(fb));
282 #endif /* CPU_REG_BITS < BITS_PER_PTR */
286 * Thread safe version of fifo_isfull()
288 INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb)
291 ATOMIC(result = fifo_isfull(_fb));
297 * FIFO Initialization.
299 INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size)
301 /* FIFO buffers have a known bug with 1-byte buffers. */
304 fb->head = fb->tail = fb->begin = buf;
305 fb->end = buf + size - 1;
309 * \return Lenght of the FIFOBuffer \a fb.
311 INLINE size_t fifo_len(FIFOBuffer *fb)
313 return fb->end - fb->begin;
320 * UNTESTED: if uncommented, to be moved in fifobuf.c
322 void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len)
326 /* Se c'e' spazio da tail alla fine del buffer */
327 if (fb->tail >= fb->head)
329 freelen = fb->end - fb->tail + 1;
331 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
334 /* Scrivi quello che entra fino alla fine del buffer */
335 memcpy(fb->tail, block, freelen);
338 fb->tail = fb->begin;
342 /* Scrivi tutto il blocco */
343 memcpy(fb->tail, block, len);
351 while (!(freelen = fb->head - fb->tail - 1))
352 Delay(FIFO_POLLDELAY);
354 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
357 /* Scrivi quello che entra fino alla fine del buffer */
358 memcpy(fb->tail, block, freelen);
365 /* Scrivi tutto il blocco */
366 memcpy(fb->tail, block, len);
374 /** \} */ /* defgroup fifobuf */
376 #endif /* STRUCT_FIFO_H */