LUFA/Drivers/Misc/RingBuffer.h

   1 /*
   2              LUFA Library
   3      Copyright (C) Dean Camera, 2010.
   4
   5   dean [at] fourwalledcubicle [dot] com
   6            www.lufa-lib.org
   7 */
   8
   9 /*
  10   Copyright 2010  Dean Camera (dean [at] fourwalledcubicle [dot] com)
  11
  12   Permission to use, copy, modify, distribute, and sell this
  13   software and its documentation for any purpose is hereby granted
  14   without fee, provided that the above copyright notice appear in
  15   all copies and that both that the copyright notice and this
  16   permission notice and warranty disclaimer appear in supporting
  17   documentation, and that the name of the author not be used in
  18   advertising or publicity pertaining to distribution of the
  19   software without specific, written prior permission.
  20
  21   The author disclaim all warranties with regard to this
  22   software, including all implied warranties of merchantability
  23   and fitness.  In no event shall the author be liable for any
  24   special, indirect or consequential damages or any damages
  25   whatsoever resulting from loss of use, data or profits, whether
  26   in an action of contract, negligence or other tortious action,
  27   arising out of or in connection with the use or performance of
  28   this software.
  29 */
  30
  31 /** \file
  32  *  \brief Lightweight ring buffer, for fast insertion/deletion.
  33  *
  34  *  Lightweight ring buffer, for fast insertion/deletion. Multiple buffers can be created of
  35  *  different sizes to suit different needs.
  36  *
  37  *  Note that for each buffer, insertion and removal operations may occur at the same time (via
  38  *  a multithreaded ISR based system) however the same kind of operation (two or more insertions
  39  *  or deletions) must not overlap. If there is possibility of two or more of the same kind of
  40  *  operating occuring at the same point in time, atomic (mutex) locking should be used.
  41  */
  42
  43 /** \ingroup Group_MiscDrivers
  44  *  @defgroup Group_RingBuff Generic Byte Ring Buffer - LUFA/Drivers/Misc/RingBuffer.h
  45  *
  46  *  \section Sec_Dependencies Module Source Dependencies
  47  *  The following files must be built with any user project that uses this module:
  48  *    - None
  49  *
  50  *  \section Module Description
  51  *  Lightweight ring buffer, for fast insertion/deletion. Multiple buffers can be created of
  52  *  different sizes to suit different needs.
  53  *
  54  *  Note that for each buffer, insertion and removal operations may occur at the same time (via
  55  *  a multithreaded ISR based system) however the same kind of operation (two or more insertions
  56  *  or deletions) must not overlap. If there is possibility of two or more of the same kind of
  57  *  operating occuring at the same point in time, atomic (mutex) locking should be used.
  58  *
  59  *  <b>Example Usage:</b>
  60  *  \code
  61  *      // Create the buffer structure and its underlying storage array
  62  *      RingBuff_t Buffer;
  63  *      uint8_t    BufferData[128];
  64  *
  65  *      // Initialise the buffer with the created storage array
  66  *      RingBuffer_InitBuffer(&Buffer, BufferData, sizeof(BufferData));
  67  *
  68  *      // Insert some data into the buffer
  69  *      RingBuffer_Insert(Buffer, 'H');
  70  *      RingBuffer_Insert(Buffer, 'E');
  71  *      RingBuffer_Insert(Buffer, 'L');
  72  *      RingBuffer_Insert(Buffer, 'L');
  73  *      RingBuffer_Insert(Buffer, 'O');
  74  *
  75  *      // Cache the number of stored bytes in the buffer
  76  *      uint16_t BufferCount = RingBuffer_GetCount(&Buffer);
  77  *
  78  *      // Printer stored data length
  79  *      printf("Buffer Length: %d, Buffer Data: \r\n", BufferCount);
  80  *
  81  *      // Print contents of the buffer one character at a time
  82  *      while (BufferCount--)
  83  *        putc(RingBuffer_Remove(&Buffer));
  84  *  \endcode
  85  *
  86  *  @{
  87  */
  88
  89 #ifndef __RING_BUFF_H__
  90 #define __RING_BUFF_H__
  91
  92         /* Includes: */
  93                 #include <util/atomic.h>
  94                 #include <stdint.h>
  95                 #include <stdbool.h>
  96
  97                 #include <LUFA/Common/Common.h>
  98
  99         /* Type Defines: */
 100                 /** Type define for a new ring buffer object. Buffers should be initialized via a call to
 101                  *  \ref RingBuffer_InitBuffer() before use.
 102                  */
 103                 typedef struct
 104                 {
 105                         uint8_t* In; /**< Current storage location in the circular buffer */
 106                         uint8_t* Out; /**< Current retrieval location in the circular buffer */
 107                         uint8_t* Start; /** Pointer to the start of the buffer's underlying storage array */
 108                         uint8_t* End; /** Pointer to the end of the buffer's underlying storage array */
 109                         uint8_t  Size; /** Size of the buffer's underlying storage array */
 110                         uint16_t Count; /** Number of bytes currently stored in the buffer */
 111                 } RingBuff_t;
 112
 113         /* Inline Functions: */
 114                 /** Initializes a ring buffer ready for use. Buffers must be initialized via this function
 115                  *  before any operations are called upon them. Already initialized buffers may be reset
 116                  *  by re-initializing them using this function.
 117                  *
 118                  *  \param[out] Buffer   Pointer to a ring buffer structure to initialize
 119                  *  \param[out] DataPtr  Pointer to a global array that will hold the data stored into the ring buffer
 120                  *  \param[out] Size     Maximum number of bytes that can be stored in the underlying data array
 121                  */
 122                 static inline void RingBuffer_InitBuffer(RingBuff_t* Buffer, uint8_t* const DataPtr, const uint16_t Size)
 123                 {
 124                         ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
 125                         {
 126                                 GCC_FORCE_POINTER_ACCESS(Buffer);
 127
 128                                 Buffer->In     = DataPtr;
 129                                 Buffer->Out    = DataPtr;
 130                                 Buffer->Start  = &DataPtr[0];
 131                                 Buffer->End    = &DataPtr[Size];
 132                                 Buffer->Size   = Size;
 133                                 Buffer->Count  = 0;
 134                         }
 135                 }
 136
 137                 /** Retrieves the minimum number of bytes stored in a particular buffer. This value is computed
 138                  *  by entering an atomic lock on the buffer while the IN and OUT locations are fetched, so that
 139                  *  the buffer cannot be modified while the computation takes place. This value should be cached
 140                  *  when reading out the contents of the buffer, so that as small a time as possible is spent
 141                  *  in an atomic lock.
 142                  *
 143                  *  \note The value returned by this function is guaranteed to only be the minimum number of bytes
 144                  *        stored in the given buffer; this value may change as other threads write new data and so
 145                  *        the returned number should be used only to determine how many successive reads may safely
 146                  *        be performed on the buffer.
 147                  *
 148                  *  \param[in] Buffer  Pointer to a ring buffer structure whose count is to be computed
 149                  */
 150                 static inline uint16_t RingBuffer_GetCount(RingBuff_t* const Buffer)
 151                 {
 152                         uint16_t Count;
 153
 154                         ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
 155                         {
 156                                 Count = Buffer->Count;
 157                         }
 158
 159                         return Count;
 160                 }
 161
 162                 /** Atomically determines if the specified ring buffer contains any free space. This should
 163                  *  be tested before storing data to the buffer, to ensure that no data is lost due to a
 164                  *  buffer overrun.
 165                  *
 166                  *  \param[in,out] Buffer  Pointer to a ring buffer structure to insert into
 167                  *
 168                  *  \return Boolean true if the buffer contains no free space, false otherwise
 169                  */
 170                 static inline bool RingBuffer_IsFull(RingBuff_t* const Buffer)
 171                 {
 172                         return (RingBuffer_GetCount(Buffer) == Buffer->Size);
 173                 }
 174
 175                 /** Atomically determines if the specified ring buffer contains any data. This should
 176                  *  be tested before removing data from the buffer, to ensure that the buffer does not
 177                  *  underflow.
 178                  *
 179                  *  If the data is to be removed in a loop, store the total number of bytes stored in the
 180                  *  buffer (via a call to the \ref RingBuffer_GetCount() function) in a temporary variable
 181                  *  to reduce the time spent in atomicity locks.
 182                  *
 183                  *  \param[in,out] Buffer  Pointer to a ring buffer structure to insert into
 184                  *
 185                  *  \return Boolean true if the buffer contains no free space, false otherwise
 186                  */
 187                 static inline bool RingBuffer_IsEmpty(RingBuff_t* const Buffer)
 188                 {
 189                         return (RingBuffer_GetCount(Buffer) == 0);
 190                 }
 191
 192                 /** Inserts an element into the ring buffer.
 193                  *
 194                  *  \note Only one execution thread (main program thread or an ISR) may insert into a single buffer
 195                  *        otherwise data corruption may occur. Insertion and removal may occur from different execution
 196                  *        threads.
 197                  *
 198                  *  \param[in,out] Buffer  Pointer to a ring buffer structure to insert into
 199                  *  \param[in]     Data    Data element to insert into the buffer
 200                  */
 201                 static inline void RingBuffer_Insert(RingBuff_t* const Buffer,
 202                                                      const uint8_t Data)
 203                 {
 204                         *Buffer->In = Data;
 205
 206                         if (++Buffer->In == Buffer->End)
 207                           Buffer->In = Buffer->Start;
 208
 209                         ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
 210                         {
 211                                 Buffer->Count++;
 212                         }
 213                 }
 214
 215                 /** Removes an element from the ring buffer.
 216                  *
 217                  *  \note Only one execution thread (main program thread or an ISR) may remove from a single buffer
 218                  *        otherwise data corruption may occur. Insertion and removal may occur from different execution
 219                  *        threads.
 220                  *
 221                  *  \param[in,out] Buffer  Pointer to a ring buffer structure to retrieve from
 222                  *
 223                  *  \return Next data element stored in the buffer
 224                  */
 225                 static inline uint8_t RingBuffer_Remove(RingBuff_t* const Buffer)
 226                 {
 227                         uint8_t Data = *Buffer->Out;
 228
 229                         if (++Buffer->Out == Buffer->End)
 230                           Buffer->Out = Buffer->Start;
 231
 232                         ATOMIC_BLOCK(ATOMIC_RESTORESTATE)
 233                         {
 234                                 Buffer->Count--;
 235                         }
 236
 237                         return Data;
 238                 }
 239
 240                 /** Returns the next element stored in the ring buffer, without removing it.
 241                  *
 242                  *  \param[in,out] Buffer  Pointer to a ring buffer structure to retrieve from
 243                  *
 244                  *  \return Next data element stored in the buffer
 245                  */
 246                 static inline uint8_t RingBuffer_Peek(RingBuff_t* const Buffer)
 247                 {
 248                         return *Buffer->Out;
 249                 }
 250
 251 #endif
 252
 253 /** @} */
 254