circbuf.h

Go to the documentation of this file.

/** \file circbuf.h
                                                                                                                 
  \brief Circular buffer data structures

******************************************************************************/

#ifndef _CIRCBUF
#define _CIRCBUF

#ifdef __cplusplus
extern "C" {
#endif

#include "util.h"
#include "array.h"

/**
  * \brief  Structure for keeping a generic circular buffer
  * 
  */

struct Circbuf_t
{
  int N;
  int numEntries;
  int head;
  int tail;
  array_t *entries;
};

typedef struct Circbuf_t Circbuf_t;


/**
  * \brief  Types of errors when manipulating a Circbuf.
  * 
  */

typedef enum
{
  CircbufDeleteEmpty_c,
  CircbufInsertFull_c
} CircbufErrorType_t;


/**
  * \brief  Macro for a working mod - C does not guarantee -1 % 3 = 2
  * 
  * Macro for a working mod - C does not guarantee -1 % 3 = 2.
  * Assume that a is not less than (-b), and b is positive. 
  * 
  * Assumes that a is always in the closed interval \[-1,b+1\] 
  * 
  */

static inline int
Circbuf_Mod (int a, int b)
{
  // return ( ( (a) >= 0 ) ? ( ( a )  % ( b ) ) : ( ( ( a ) + ( b ) ) % ( b ) ) );
  // assert( ( -1 <= a ) && ( a <= b + 1 ) );
  if (0 <= a)
    {
      if (a < b)
    {
      return a;
    }
      else if (a == b)
    {
      return 0;
    }
      else
    {
      // must be that a is b + 1
      return 1;
    }
    }
  else
    {
      // a is -1
      return (b - 1);
    }
}


/**
  * \brief  Initialize the buffer
  * 
  */

#define Circbuf_Init( type, N ) \
    Circbuf_DoAlloc( sizeof( type ), ( (N) + 1) )

/**
  * \brief  Test to see if a circular buffer is empty
  * 
  */

static inline int
Circbuf_IsEmpty (Circbuf_t * cb)
{
  return (cb->tail == cb->head);
}

/**
  * \brief  Test to see if a circular buffer is full
  * 
  * 
  */

static inline int
Circbuf_IsFull (Circbuf_t * cb)
{
  // try to replace the expensive mod call
  // return ( cb->head == Circbuf_Mod( ( cb->tail + 1 ) , cb->N ) ) ;
  if (cb->head > 0)
    {
      return (cb->head == cb->tail + 1);
    }
  else
    {
      return (cb->tail == (cb->N - 1));
    }
}


/**
  * \brief  Insert an entry into the buffer; return 1 on succ completion,
  * 0 otherwise.
  * 
  Circbuf_IsFull( cb ) ? \
    ( fail( "CircbufInsertFull_c" ) ) : \
    ( ( array_insert( type, cb->entries, cb->tail, datum ) ), \
      ( cb->numEntries++ ), \
      ( cb->tail = Circbuf_Mod( ( cb->tail + 1 ), cb->N ) ) )

  */

#define Circbuf_Insert( type, cb, datum ) \
    ( assert( !Circbuf_IsFull( cb ) ), \
      ( array_insert( type, cb->entries, cb->tail, datum ) ), \
      ( cb->numEntries++ ), \
      ( cb->tail = Circbuf_Mod( ( cb->tail + 1 ), cb->N ) ) )

/**
  * \brief  Code to delete an entry from a circular buffer;
  * value returned is deleted item.
  * 
  * For some reason we cannot just use fail (maybe because it's a macro?) 
  * so we  print the error, assert 0, and do an array fetch (which will
  * also fail in case we used -O4, removed the assert, and the type of
  * the comma operator works out ok (fetching type)
  * 
  */


#define Circbuf_Delete( type, cb ) \
    ( !Circbuf_IsEmpty( cb  ) ) ? \
        ( ( cb->numEntries-- ) , \
    (  cb->head = ( Circbuf_Mod( ( cb->head + 1 ) , cb->N  ) ) ), \
        ( array_fetch( type, cb->entries, Circbuf_Mod( ( cb->head - 1 ) , cb->N )  ) ) )  \
    : \
    ( ( fprintf( stderr, "CircbufDeleteEmpty_c\n" ), assert(0), ( array_fetch( type, cb->entries, cb->N + 1 ) ) ) )


extern Circbuf_t *Circbuf_DoAlloc (int, int);
extern int Circbuf_Num (Circbuf_t *);
#ifdef __cplusplus
}
#endif

#endif // _CIRCBUF