4 * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
5 * Copyright 2001 Bernardo Innocenti <bernie@develer.com>
6 * This file is part of DevLib - See README.devlib for information.
11 * \author Bernardo Innocenti <bernie@develer.com>
13 * \brief General pourpose FIFO buffer implemented with a ring buffer
15 * \li \c begin points to the first buffer element;
16 * \li \c end points to the last buffer element (unlike the STL convention);
17 * \li \c head points to the element to be extracted next;
18 * \li \c tail points to the location following the last insertion;
19 * \li when any of the pointers advances beyond \c end, it is reset
24 * +-----------------------------------+
25 * | empty | valid data | empty |
26 * +-----------------------------------+
32 * The buffer is EMPTY when \c head and \c tail point to the same location:
33 * \code head == tail \endcode
35 * The buffer is FULL when \c tail points to the location immediately
37 * \code tail == head - 1 \endcode
39 * The buffer is also FULL when \c tail points to the last buffer
40 * location and head points to the first one:
41 * \code head == begin && tail == end \endcode
46 *#* Revision 1.22 2006/07/19 12:56:27 bernie
47 *#* Convert to new Doxygen style.
49 *#* Revision 1.21 2005/11/04 16:20:02 bernie
50 *#* Fix reference to README.devlib in header.
52 *#* Revision 1.20 2005/04/11 19:10:28 bernie
53 *#* Include top-level headers from cfg/ subdir.
55 *#* Revision 1.19 2004/12/08 08:30:12 bernie
56 *#* Add missing header.
58 *#* Revision 1.18 2004/11/16 21:55:12 bernie
59 *#* Workaround for a known fifobuf bug.
61 *#* Revision 1.17 2004/09/14 20:57:00 bernie
62 *#* Use debug.h instead of kdebug.h.
64 *#* Revision 1.16 2004/09/06 21:39:08 bernie
65 *#* Simplify code using ATOMIC().
67 *#* Revision 1.15 2004/08/29 22:05:16 bernie
68 *#* Rename BITS_PER_PTR to CPU_BITS_PER_PTR.
70 *#* Revision 1.14 2004/08/25 14:12:09 rasky
71 *#* Aggiornato il comment block dei log RCS
73 *#* Revision 1.13 2004/08/24 13:16:11 bernie
74 *#* Add type-size definitions for preprocessor.
76 *#* Revision 1.12 2004/08/02 20:20:29 aleph
77 *#* Merge from project_ks
79 *#* Revision 1.11 2004/07/30 14:15:53 rasky
80 *#* Nuovo supporto unificato per detect della CPU
82 *#* Revision 1.10 2004/07/29 22:57:09 bernie
85 *#* Revision 1.9 2004/07/20 23:54:27 bernie
86 *#* fifo_flush_locked(): New function;
87 *#* Revamp documentation.
89 *#* Revision 1.8 2004/07/20 23:47:39 bernie
90 *#* Finally remove redundant protos.
92 *#* Revision 1.7 2004/07/20 23:46:29 bernie
93 *#* Finally remove redundant protos.
95 *#* Revision 1.6 2004/06/06 17:18:04 bernie
96 *#* Remove redundant declaration of fifo_isempty_locked().
98 *#* Revision 1.5 2004/06/06 16:50:35 bernie
99 *#* Import fixes for race conditions from project_ks.
101 *#* Revision 1.4 2004/06/06 16:11:17 bernie
102 *#* Protect MetroWerks specific pragmas with #ifdef's
109 #include <cfg/debug.h>
111 typedef struct FIFOBuffer
113 unsigned char * volatile head;
114 unsigned char * volatile tail;
115 unsigned char *begin;
120 #define ASSERT_VALID_FIFO(fifo) \
122 ASSERT((fifo)->head >= (fifo)->begin); \
123 ASSERT((fifo)->head <= (fifo)->end); \
124 ASSERT((fifo)->tail >= (fifo)->begin); \
125 ASSERT((fifo)->tail <= (fifo)->end); \
130 * Check whether the fifo is empty
132 * \note Calling fifo_isempty() is safe while a concurrent
133 * execution context is calling fifo_push() or fifo_pop()
134 * only if the CPU can atomically update a pointer
135 * (which the AVR and other 8-bit processors can't do).
137 * \sa fifo_isempty_locked
139 INLINE bool fifo_isempty(const FIFOBuffer *fb)
141 //ASSERT_VALID_FIFO(fb);
142 return fb->head == fb->tail;
147 * Check whether the fifo is full
149 * \note Calling fifo_isfull() is safe while a concurrent
150 * execution context is calling fifo_pop() and the
151 * CPU can update a pointer atomically.
152 * It is NOT safe when the other context calls
154 * This limitation is not usually problematic in a
155 * consumer/producer scenario because the
156 * fifo_isfull() and fifo_push() are usually called
157 * in the producer context.
159 INLINE bool fifo_isfull(const FIFOBuffer *fb)
161 //ASSERT_VALID_FIFO(fb);
163 ((fb->head == fb->begin) && (fb->tail == fb->end))
164 || (fb->tail == fb->head - 1);
169 * Pop a character from the fifo buffer.
171 * \note Calling \c fifo_push() on a full buffer is undefined.
172 * The caller must make sure the buffer has at least
173 * one free slot before calling this function.
175 * \note It is safe to call fifo_pop() and fifo_push() from
176 * concurrent contexts, unless the CPU can't update
177 * a pointer atomically (which the AVR and other 8-bit
178 * processors can't do).
180 * \sa fifo_push_locked
182 INLINE void fifo_push(FIFOBuffer *fb, unsigned char c)
185 #pragma interrupt called
187 //ASSERT_VALID_FIFO(fb);
189 /* Write at tail position */
192 if (UNLIKELY(fb->tail == fb->end))
193 /* wrap tail around */
194 fb->tail = fb->begin;
196 /* Move tail forward */
202 * Pop a character from the fifo buffer.
204 * \note Calling \c fifo_pop() on an empty buffer is undefined.
205 * The caller must make sure the buffer contains at least
206 * one character before calling this function.
208 * \note It is safe to call fifo_pop() and fifo_push() from
209 * concurrent contexts.
211 INLINE unsigned char fifo_pop(FIFOBuffer *fb)
214 #pragma interrupt called
216 //ASSERT_VALID_FIFO(fb);
218 if (UNLIKELY(fb->head == fb->end))
220 /* wrap head around */
221 fb->head = fb->begin;
225 /* move head forward */
226 return *(fb->head++);
231 * Make the fifo empty, discarding all its current contents.
233 INLINE void fifo_flush(FIFOBuffer *fb)
235 //ASSERT_VALID_FIFO(fb);
240 #if CPU_REG_BITS >= CPU_BITS_PER_PTR
243 * 16/32bit CPUs that can update a pointer with a single write
244 * operation, no need to disable interrupts.
246 #define fifo_isempty_locked(fb) fifo_isempty((fb))
247 #define fifo_push_locked(fb, c) fifo_push((fb), (c))
248 #define fifo_pop_locked(fb) fifo_pop((fb))
249 #define fifo_flush_locked(fb) fifo_flush((fb))
251 #else /* CPU_REG_BITS < CPU_BITS_PER_PTR */
254 * Similar to fifo_isempty(), but with stronger guarantees for
255 * concurrent access between user and interrupt code.
257 * \note This is actually only needed for 8-bit processors.
261 INLINE bool fifo_isempty_locked(const FIFOBuffer *fb)
264 ATOMIC(result = fifo_isempty(fb));
270 * Similar to fifo_push(), 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_push_locked(FIFOBuffer *fb, unsigned char c)
279 ATOMIC(fifo_push(fb, c));
282 /* Probably not really needed, but hard to prove. */
283 INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb)
286 ATOMIC(c = fifo_pop(fb));
291 * Similar to fifo_flush(), but with stronger guarantees for
292 * concurrent access between user and interrupt code.
294 * \note This is actually only needed for 8-bit processors.
298 INLINE void fifo_flush_locked(FIFOBuffer *fb)
300 ATOMIC(fifo_flush(fb));
303 #endif /* CPU_REG_BITS < BITS_PER_PTR */
307 * Thread safe version of fifo_isfull()
309 INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb)
312 ATOMIC(result = fifo_isfull(_fb));
318 * FIFO Initialization.
320 INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size)
322 /* FIFO buffers have a known bug with 1-byte buffers. */
325 fb->head = fb->tail = fb->begin = buf;
326 fb->end = buf + size - 1;
333 * UNTESTED: if uncommented, to be moved in fifobuf.c
335 void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len)
339 /* Se c'e' spazio da tail alla fine del buffer */
340 if (fb->tail >= fb->head)
342 freelen = fb->end - fb->tail + 1;
344 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
347 /* Scrivi quello che entra fino alla fine del buffer */
348 memcpy(fb->tail, block, freelen);
351 fb->tail = fb->begin;
355 /* Scrivi tutto il blocco */
356 memcpy(fb->tail, block, len);
364 while (!(freelen = fb->head - fb->tail - 1))
365 Delay(FIFO_POLLDELAY);
367 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
370 /* Scrivi quello che entra fino alla fine del buffer */
371 memcpy(fb->tail, block, freelen);
378 /* Scrivi tutto il blocco */
379 memcpy(fb->tail, block, len);
387 #endif /* MWARE_FIFO_H */