Azinix

circbuf.h

Go to the documentation of this file.
00001 /** \file circbuf.h
00002                                                                                                                  
00003   \brief Circular buffer data structures
00004 
00005 ******************************************************************************/
00006 
00007 #ifndef _CIRCBUF
00008 #define _CIRCBUF
00009 
00010 #ifdef __cplusplus
00011 extern "C" {
00012 #endif
00013 
00014 #include "util.h"
00015 #include "array.h"
00016 
00017 /**
00018   * \brief  Structure for keeping a generic circular buffer
00019   * 
00020   */
00021 
00022 struct Circbuf_t
00023 {
00024   int N;
00025   int numEntries;
00026   int head;
00027   int tail;
00028   array_t *entries;
00029 };
00030 
00031 typedef struct Circbuf_t Circbuf_t;
00032 
00033 
00034 /**
00035   * \brief  Types of errors when manipulating a Circbuf.
00036   * 
00037   */
00038 
00039 typedef enum
00040 {
00041   CircbufDeleteEmpty_c,
00042   CircbufInsertFull_c
00043 } CircbufErrorType_t;
00044 
00045 
00046 /**
00047   * \brief  Macro for a working mod - C does not guarantee -1 % 3 = 2
00048   * 
00049   * Macro for a working mod - C does not guarantee -1 % 3 = 2.
00050   * Assume that a is not less than (-b), and b is positive. 
00051   * 
00052   * Assumes that a is always in the closed interval \[-1,b+1\] 
00053   * 
00054   */
00055 
00056 static inline int
00057 Circbuf_Mod (int a, int b)
00058 {
00059   // return ( ( (a) >= 0 ) ? ( ( a )  % ( b ) ) : ( ( ( a ) + ( b ) ) % ( b ) ) );
00060   // assert( ( -1 <= a ) && ( a <= b + 1 ) );
00061   if (0 <= a)
00062     {
00063       if (a < b)
00064     {
00065       return a;
00066     }
00067       else if (a == b)
00068     {
00069       return 0;
00070     }
00071       else
00072     {
00073       // must be that a is b + 1
00074       return 1;
00075     }
00076     }
00077   else
00078     {
00079       // a is -1
00080       return (b - 1);
00081     }
00082 }
00083 
00084 
00085 /**
00086   * \brief  Initialize the buffer
00087   * 
00088   */
00089 
00090 #define Circbuf_Init( type, N ) \
00091     Circbuf_DoAlloc( sizeof( type ), ( (N) + 1) )
00092 
00093 /**
00094   * \brief  Test to see if a circular buffer is empty
00095   * 
00096   */
00097 
00098 static inline int
00099 Circbuf_IsEmpty (Circbuf_t * cb)
00100 {
00101   return (cb->tail == cb->head);
00102 }
00103 
00104 /**
00105   * \brief  Test to see if a circular buffer is full
00106   * 
00107   * 
00108   */
00109 
00110 static inline int
00111 Circbuf_IsFull (Circbuf_t * cb)
00112 {
00113   // try to replace the expensive mod call
00114   // return ( cb->head == Circbuf_Mod( ( cb->tail + 1 ) , cb->N ) ) ;
00115   if (cb->head > 0)
00116     {
00117       return (cb->head == cb->tail + 1);
00118     }
00119   else
00120     {
00121       return (cb->tail == (cb->N - 1));
00122     }
00123 }
00124 
00125 
00126 /**
00127   * \brief  Insert an entry into the buffer; return 1 on succ completion,
00128   * 0 otherwise.
00129   * 
00130   Circbuf_IsFull( cb ) ? \
00131     ( fail( "CircbufInsertFull_c" ) ) : \
00132     ( ( array_insert( type, cb->entries, cb->tail, datum ) ), \
00133       ( cb->numEntries++ ), \
00134       ( cb->tail = Circbuf_Mod( ( cb->tail + 1 ), cb->N ) ) )
00135 
00136   */
00137 
00138 #define Circbuf_Insert( type, cb, datum ) \
00139     ( assert( !Circbuf_IsFull( cb ) ), \
00140       ( array_insert( type, cb->entries, cb->tail, datum ) ), \
00141       ( cb->numEntries++ ), \
00142       ( cb->tail = Circbuf_Mod( ( cb->tail + 1 ), cb->N ) ) )
00143 
00144 /**
00145   * \brief  Code to delete an entry from a circular buffer;
00146   * value returned is deleted item.
00147   * 
00148   * For some reason we cannot just use fail (maybe because it's a macro?) 
00149   * so we  print the error, assert 0, and do an array fetch (which will
00150   * also fail in case we used -O4, removed the assert, and the type of
00151   * the comma operator works out ok (fetching type)
00152   * 
00153   */
00154 
00155 
00156 #define Circbuf_Delete( type, cb ) \
00157     ( !Circbuf_IsEmpty( cb  ) ) ? \
00158         ( ( cb->numEntries-- ) , \
00159     (  cb->head = ( Circbuf_Mod( ( cb->head + 1 ) , cb->N  ) ) ), \
00160         ( array_fetch( type, cb->entries, Circbuf_Mod( ( cb->head - 1 ) , cb->N )  ) ) )  \
00161     : \
00162     ( ( fprintf( stderr, "CircbufDeleteEmpty_c\n" ), assert(0), ( array_fetch( type, cb->entries, cb->N + 1 ) ) ) )
00163 
00164 
00165 extern Circbuf_t *Circbuf_DoAlloc (int, int);
00166 extern int Circbuf_Num (Circbuf_t *);
00167 #ifdef __cplusplus
00168 }
00169 #endif
00170 
00171 #endif // _CIRCBUF