bertos/struct/fifobuf.h

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   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.
  10  *
  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.
  15  *
  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
  19  *
  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.
  28  *
  29  * Copyright 2003, 2004 Develer S.r.l. (http://www.develer.com/)
  30  * Copyright 2001, 2008 Bernie Innocenti <bernie@codewiz.org>
  31  * -->
  32  *
  33  * \defgroup fifobuf FIFO buffer
  34  * \ingroup struct
  35  * \{
  36  *
  37  * \brief General pourpose FIFO buffer implemented with a ring buffer
  38  *
  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
  44  *     back to \c begin.
  45  *
  46  * \code
  47  *
  48  *  +-----------------------------------+
  49  *  |  empty  |   valid data   |  empty |
  50  *  +-----------------------------------+
  51  *  ^         ^                ^        ^
  52  *  begin    head             tail     end
  53  *
  54  * \endcode
  55  *
  56  * The buffer is EMPTY when \c head and \c tail point to the same location:
  57  *              \code head == tail \endcode
  58  *
  59  * The buffer is FULL when \c tail points to the location immediately
  60  * after \c head:
  61  *              \code tail == head - 1 \endcode
  62  *
  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
  66  *
  67  * \author Bernie Innocenti <bernie@codewiz.org>
  68  */
  69
  70 #ifndef STRUCT_FIFO_H
  71 #define STRUCT_FIFO_H
  72
  73 #include <cpu/types.h>
  74 #include <cpu/irq.h>
  75 #include <cfg/debug.h>
  76
  77 typedef struct FIFOBuffer
  78 {
  79         unsigned char * volatile head;
  80         unsigned char * volatile tail;
  81         unsigned char *begin;
  82         unsigned char *end;
  83 } FIFOBuffer;
  84
  85
  86 #define ASSERT_VALID_FIFO(fifo) \
  87         ATOMIC( \
  88                 ASSERT((fifo)->head >= (fifo)->begin); \
  89                 ASSERT((fifo)->head <= (fifo)->end); \
  90                 ASSERT((fifo)->tail >= (fifo)->begin); \
  91                 ASSERT((fifo)->tail <= (fifo)->end); \
  92         )
  93
  94
  95 /**
  96  * Check whether the fifo is empty
  97  *
  98  * \note Calling fifo_isempty() is safe while a concurrent
  99  *       execution context is calling fifo_push() or fifo_pop()
 100  *       only if the CPU can atomically update a pointer
 101  *       (which the AVR and other 8-bit processors can't do).
 102  *
 103  * \sa fifo_isempty_locked
 104  */
 105 INLINE bool fifo_isempty(const FIFOBuffer *fb)
 106 {
 107         //ASSERT_VALID_FIFO(fb);
 108         return fb->head == fb->tail;
 109 }
 110
 111
 112 /**
 113  * Check whether the fifo is full
 114  *
 115  * \note Calling fifo_isfull() is safe while a concurrent
 116  *       execution context is calling fifo_pop() and the
 117  *       CPU can update a pointer atomically.
 118  *       It is NOT safe when the other context calls
 119  *       fifo_push().
 120  *       This limitation is not usually problematic in a
 121  *       consumer/producer scenario because the
 122  *       fifo_isfull() and fifo_push() are usually called
 123  *       in the producer context.
 124  */
 125 INLINE bool fifo_isfull(const FIFOBuffer *fb)
 126 {
 127         //ASSERT_VALID_FIFO(fb);
 128         return
 129                 ((fb->head == fb->begin) && (fb->tail == fb->end))
 130                 || (fb->tail == fb->head - 1);
 131 }
 132
 133
 134 /**
 135  * Push a character on the fifo buffer.
 136  *
 137  * \note Calling \c fifo_push() on a full buffer is undefined.
 138  *       The caller must make sure the buffer has at least
 139  *       one free slot before calling this function.
 140  *
 141  * \note It is safe to call fifo_pop() and fifo_push() from
 142  *       concurrent contexts, unless the CPU can't update
 143  *       a pointer atomically (which the AVR and other 8-bit
 144  *       processors can't do).
 145  *
 146  * \sa fifo_push_locked
 147  */
 148 INLINE void fifo_push(FIFOBuffer *fb, unsigned char c)
 149 {
 150 #ifdef __MWERKS__
 151 #pragma interrupt called
 152 #endif
 153         //ASSERT_VALID_FIFO(fb);
 154
 155         /* Write at tail position */
 156         *(fb->tail) = c;
 157
 158         if (UNLIKELY(fb->tail == fb->end))
 159                 /* wrap tail around */
 160                 fb->tail = fb->begin;
 161         else
 162                 /* Move tail forward */
 163                 fb->tail++;
 164 }
 165
 166
 167 /**
 168  * Pop a character from the fifo buffer.
 169  *
 170  * \note Calling \c fifo_pop() on an empty buffer is undefined.
 171  *       The caller must make sure the buffer contains at least
 172  *       one character before calling this function.
 173  *
 174  * \note It is safe to call fifo_pop() and fifo_push() from
 175  *       concurrent contexts.
 176  */
 177 INLINE unsigned char fifo_pop(FIFOBuffer *fb)
 178 {
 179 #ifdef __MWERKS__
 180 #pragma interrupt called
 181 #endif
 182         //ASSERT_VALID_FIFO(fb);
 183
 184         if (UNLIKELY(fb->head == fb->end))
 185         {
 186                 /* wrap head around */
 187                 fb->head = fb->begin;
 188                 return *(fb->end);
 189         }
 190         else
 191                 /* move head forward */
 192                 return *(fb->head++);
 193 }
 194
 195
 196 /**
 197  * Make the fifo empty, discarding all its current contents.
 198  */
 199 INLINE void fifo_flush(FIFOBuffer *fb)
 200 {
 201         //ASSERT_VALID_FIFO(fb);
 202         fb->head = fb->tail;
 203 }
 204
 205
 206 #if CPU_REG_BITS >= CPU_BITS_PER_PTR
 207
 208         /*
 209          * 16/32bit CPUs that can update a pointer with a single write
 210          * operation, no need to disable interrupts.
 211          */
 212         #define fifo_isempty_locked(fb) fifo_isempty((fb))
 213         #define fifo_push_locked(fb, c) fifo_push((fb), (c))
 214         #define fifo_pop_locked(fb)     fifo_pop((fb))
 215         #define fifo_flush_locked(fb)   fifo_flush((fb))
 216
 217 #else /* CPU_REG_BITS < CPU_BITS_PER_PTR */
 218
 219         /**
 220          * Similar to fifo_isempty(), but with stronger guarantees for
 221          * concurrent access between user and interrupt code.
 222          *
 223          * \note This is actually only needed for 8-bit processors.
 224          *
 225          * \sa fifo_isempty()
 226          */
 227         INLINE bool fifo_isempty_locked(const FIFOBuffer *fb)
 228         {
 229                 bool result;
 230                 ATOMIC(result = fifo_isempty(fb));
 231                 return result;
 232         }
 233
 234
 235         /**
 236          * Similar to fifo_push(), but with stronger guarantees for
 237          * concurrent access between user and interrupt code.
 238          *
 239          * \note This is actually only needed for 8-bit processors.
 240          *
 241          * \sa fifo_push()
 242          */
 243         INLINE void fifo_push_locked(FIFOBuffer *fb, unsigned char c)
 244         {
 245                 ATOMIC(fifo_push(fb, c));
 246         }
 247
 248         /* Probably not really needed, but hard to prove. */
 249         INLINE unsigned char fifo_pop_locked(FIFOBuffer *fb)
 250         {
 251                 unsigned char c;
 252                 ATOMIC(c = fifo_pop(fb));
 253                 return c;
 254         }
 255
 256         /**
 257          * Similar to fifo_flush(), but with stronger guarantees for
 258          * concurrent access between user and interrupt code.
 259          *
 260          * \note This is actually only needed for 8-bit processors.
 261          *
 262          * \sa fifo_flush()
 263          */
 264         INLINE void fifo_flush_locked(FIFOBuffer *fb)
 265         {
 266                 ATOMIC(fifo_flush(fb));
 267         }
 268
 269 #endif /* CPU_REG_BITS < BITS_PER_PTR */
 270
 271
 272 /**
 273  * Thread safe version of fifo_isfull()
 274  */
 275 INLINE bool fifo_isfull_locked(const FIFOBuffer *_fb)
 276 {
 277         bool result;
 278         ATOMIC(result = fifo_isfull(_fb));
 279         return result;
 280 }
 281
 282
 283 /**
 284  * FIFO Initialization.
 285  */
 286 INLINE void fifo_init(FIFOBuffer *fb, unsigned char *buf, size_t size)
 287 {
 288         /* FIFO buffers have a known bug with 1-byte buffers. */
 289         ASSERT(size > 1);
 290
 291         fb->head = fb->tail = fb->begin = buf;
 292         fb->end = buf + size - 1;
 293 }
 294
 295 /**
 296  * \return Lenght of the FIFOBuffer \a fb.
 297  */
 298 INLINE size_t fifo_len(FIFOBuffer *fb)
 299 {
 300         return fb->end - fb->begin;
 301 }
 302
 303
 304 #if 0
 305
 306 /*
 307  * UNTESTED: if uncommented, to be moved in fifobuf.c
 308  */
 309 void fifo_pushblock(FIFOBuffer *fb, unsigned char *block, size_t len)
 310 {
 311         size_t freelen;
 312
 313         /* Se c'e' spazio da tail alla fine del buffer */
 314         if (fb->tail >= fb->head)
 315         {
 316                 freelen = fb->end - fb->tail + 1;
 317
 318                 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
 319                 if (freelen < len)
 320                 {
 321                         /* Scrivi quello che entra fino alla fine del buffer */
 322                         memcpy(fb->tail, block, freelen);
 323                         block += freelen;
 324                         len -= freelen;
 325                         fb->tail = fb->begin;
 326                 }
 327                 else
 328                 {
 329                         /* Scrivi tutto il blocco */
 330                         memcpy(fb->tail, block, len);
 331                         fb->tail += len;
 332                         return;
 333                 }
 334         }
 335
 336         for(;;)
 337         {
 338                 while (!(freelen = fb->head - fb->tail - 1))
 339                         Delay(FIFO_POLLDELAY);
 340
 341                 /* C'e' abbastanza spazio per scrivere tutto il blocco? */
 342                 if (freelen < len)
 343                 {
 344                         /* Scrivi quello che entra fino alla fine del buffer */
 345                         memcpy(fb->tail, block, freelen);
 346                         block += freelen;
 347                         len -= freelen;
 348                         fb->tail += freelen;
 349                 }
 350                 else
 351                 {
 352                         /* Scrivi tutto il blocco */
 353                         memcpy(fb->tail, block, len);
 354                         fb->tail += len;
 355                         return;
 356                 }
 357         }
 358 }
 359 #endif
 360
 361 /** \} */ /* defgroup fifobuf */
 362
 363 #endif /* STRUCT_FIFO_H */