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