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 Bernardo Innocenti <bernie@develer.com>
36 * \author Bernardo Innocenti <bernie@develer.com>
38 * \brief General pourpose FIFO buffer implemented with a ring buffer
40 * \li \c begin points to the first buffer element;
41 * \li \c end points to the last buffer element (unlike the STL convention);
42 * \li \c head points to the element to be extracted next;
43 * \li \c tail points to the location following the last insertion;
44 * \li when any of the pointers advances beyond \c end, it is reset
49 * +-----------------------------------+
50 * | empty | valid data | empty |
51 * +-----------------------------------+
57 * The buffer is EMPTY when \c head and \c tail point to the same location:
58 * \code head == tail \endcode
60 * The buffer is FULL when \c tail points to the location immediately
62 * \code tail == head - 1 \endcode
64 * The buffer is also FULL when \c tail points to the last buffer
65 * location and head points to the first one:
66 * \code head == begin && tail == end \endcode
71 *#* Revision 1.22 2006/07/19 12:56:27 bernie
72 *#* Convert to new Doxygen style.
74 *#* Revision 1.21 2005/11/04 16:20:02 bernie
75 *#* Fix reference to README.devlib in header.
77 *#* Revision 1.20 2005/04/11 19:10:28 bernie
78 *#* Include top-level headers from cfg/ subdir.
80 *#* Revision 1.19 2004/12/08 08:30:12 bernie
81 *#* Add missing header.
83 *#* Revision 1.18 2004/11/16 21:55:12 bernie
84 *#* Workaround for a known fifobuf bug.
86 *#* Revision 1.17 2004/09/14 20:57:00 bernie
87 *#* Use debug.h instead of kdebug.h.
89 *#* Revision 1.16 2004/09/06 21:39:08 bernie
90 *#* Simplify code using ATOMIC().
92 *#* Revision 1.15 2004/08/29 22:05:16 bernie
93 *#* Rename BITS_PER_PTR to CPU_BITS_PER_PTR.
95 *#* Revision 1.14 2004/08/25 14:12:09 rasky
96 *#* Aggiornato il comment block dei log RCS
98 *#* Revision 1.13 2004/08/24 13:16:11 bernie
99 *#* Add type-size definitions for preprocessor.
101 *#* Revision 1.12 2004/08/02 20:20:29 aleph
102 *#* Merge from project_ks
104 *#* Revision 1.11 2004/07/30 14:15:53 rasky
105 *#* Nuovo supporto unificato per detect della CPU
107 *#* Revision 1.10 2004/07/29 22:57:09 bernie
110 *#* Revision 1.9 2004/07/20 23:54:27 bernie
111 *#* fifo_flush_locked(): New function;
112 *#* Revamp documentation.
114 *#* Revision 1.8 2004/07/20 23:47:39 bernie
115 *#* Finally remove redundant protos.
117 *#* Revision 1.7 2004/07/20 23:46:29 bernie
118 *#* Finally remove redundant protos.
120 *#* Revision 1.6 2004/06/06 17:18:04 bernie
121 *#* Remove redundant declaration of fifo_isempty_locked().
123 *#* Revision 1.5 2004/06/06 16:50:35 bernie
124 *#* Import fixes for race conditions from project_ks.
126 *#* Revision 1.4 2004/06/06 16:11:17 bernie
127 *#* Protect MetroWerks specific pragmas with #ifdef's
134 #include <cfg/debug.h>
136 typedef struct FIFOBuffer
138 unsigned char * volatile head;
139 unsigned char * volatile tail;
140 unsigned char *begin;
145 #define ASSERT_VALID_FIFO(fifo) \
147 ASSERT((fifo)->head >= (fifo)->begin); \
148 ASSERT((fifo)->head <= (fifo)->end); \
149 ASSERT((fifo)->tail >= (fifo)->begin); \
150 ASSERT((fifo)->tail <= (fifo)->end); \
155 * Check whether the fifo is empty
157 * \note Calling fifo_isempty() is safe while a concurrent
158 * execution context is calling fifo_push() or fifo_pop()
159 * only if the CPU can atomically update a pointer
160 * (which the AVR and other 8-bit processors can't do).
162 * \sa fifo_isempty_locked
164 INLINE bool fifo_isempty(const FIFOBuffer *fb)
166 //ASSERT_VALID_FIFO(fb);
167 return fb->head == fb->tail;
172 * Check whether the fifo is full
174 * \note Calling fifo_isfull() is safe while a concurrent
175 * execution context is calling fifo_pop() and the
176 * CPU can update a pointer atomically.
177 * It is NOT safe when the other context calls
179 * This limitation is not usually problematic in a
180 * consumer/producer scenario because the
181 * fifo_isfull() and fifo_push() are usually called
182 * in the producer context.
184 INLINE bool fifo_isfull(const FIFOBuffer *fb)
186 //ASSERT_VALID_FIFO(fb);
188 ((fb->head == fb->begin) && (fb->tail == fb->end))
189 || (fb->tail == fb->head - 1);
194 * Pop a character from the fifo buffer.
196 * \note Calling \c fifo_push() on a full buffer is undefined.
197 * The caller must make sure the buffer has at least
198 * one free slot before calling this function.
200 * \note It is safe to call fifo_pop() and fifo_push() from
201 * concurrent contexts, unless the CPU can't update
202 * a pointer atomically (which the AVR and other 8-bit
203 * processors can't do).
205 * \sa fifo_push_locked
207 INLINE void fifo_push(FIFOBuffer *fb, unsigned char c)
210 #pragma interrupt called
212 //ASSERT_VALID_FIFO(fb);
214 /* Write at tail position */
217 if (UNLIKELY(fb->tail == fb->end))
218 /* wrap tail around */
219 fb->tail = fb->begin;
221 /* Move tail forward */
227 * Pop a character from the fifo buffer.
229 * \note Calling \c fifo_pop() on an empty buffer is undefined.
230 * The caller must make sure the buffer contains at least
231 * one character before calling this function.
233 * \note It is safe to call fifo_pop() and fifo_push() from
234 * concurrent contexts.
236 INLINE unsigned char fifo_pop(FIFOBuffer *fb)
239 #pragma interrupt called
241 //ASSERT_VALID_FIFO(fb);
243 if (UNLIKELY(fb->head == fb->end))
245 /* wrap head around */
246 fb->head = fb->begin;
250 /* move head forward */
251 return *(fb->head++);
256 * Make the fifo empty, discarding all its current contents.
258 INLINE void fifo_flush(FIFOBuffer *fb)
260 //ASSERT_VALID_FIFO(fb);
265 #if CPU_REG_BITS >= CPU_BITS_PER_PTR
268 * 16/32bit CPUs that can update a pointer with a single write
269 * operation, no need to disable interrupts.
271 #define fifo_isempty_locked(fb) fifo_isempty((fb))
272 #define fifo_push_locked(fb, c) fifo_push((fb), (c))
273 #define fifo_pop_locked(fb) fifo_pop((fb))
274 #define fifo_flush_locked(fb) fifo_flush((fb))
276 #else /* CPU_REG_BITS < CPU_BITS_PER_PTR */
279 * Similar to fifo_isempty(), but with stronger guarantees for
280 * concurrent access between user and interrupt code.
282 * \note This is actually only needed for 8-bit processors.
286 INLINE bool fifo_isempty_locked(const FIFOBuffer *fb)
289 ATOMIC(result = fifo_isempty(fb));
295 * Similar to fifo_push(), but with stronger guarantees for
296 * concurrent access between user and interrupt code.
298 * \note This is actually only needed for 8-bit processors.
302 INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c)
304 ATOMIC(fifo_push(fb, c));
307 /* Probably not really needed, but hard to prove. */
308 INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb)
311 ATOMIC(c = fifo_pop(fb));
316 * Similar to fifo_flush(), but with stronger guarantees for
317 * concurrent access between user and interrupt code.
319 * \note This is actually only needed for 8-bit processors.
323 INLINE void fifo_flush_locked(FIFOBuffer *fb)
325 ATOMIC(fifo_flush(fb));
328 #endif /* CPU_REG_BITS < BITS_PER_PTR */
332 * Thread safe version of fifo_isfull()
334 INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb)
337 ATOMIC(result = fifo_isfull(_fb));
343 * FIFO Initialization.
345 INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size)
347 /* FIFO buffers have a known bug with 1-byte buffers. */
350 fb->head = fb->tail = fb->begin = buf;
351 fb->end = buf + size - 1;
358 * UNTESTED: if uncommented, to be moved in fifobuf.c
360 void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len)
364 /* Se c'e' spazio da tail alla fine del buffer */
365 if (fb->tail >= fb->head)
367 freelen = fb->end - fb->tail + 1;
369 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
372 /* Scrivi quello che entra fino alla fine del buffer */
373 memcpy(fb->tail, block, freelen);
376 fb->tail = fb->begin;
380 /* Scrivi tutto il blocco */
381 memcpy(fb->tail, block, len);
389 while (!(freelen = fb->head - fb->tail - 1))
390 Delay(FIFO_POLLDELAY);
392 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
395 /* Scrivi quello che entra fino alla fine del buffer */
396 memcpy(fb->tail, block, freelen);
403 /* Scrivi tutto il blocco */
404 memcpy(fb->tail, block, len);
412 #endif /* MWARE_FIFO_H */