Linux环形队列

1 环形队列

    环形队列，分配固定大小空间，循环记录信息，当超过固定大小限制，进行覆盖。

2 实现方式

2.1  存储结构

typedef struct {
  char *buffer;             //分配的缓存区
  unsigned int in;         //存入数据计数
  unsigned int out;       //取出数据计数
  unsigned int size;      //缓存区总大小
} cfifo_t;

2.2  初始化

static unsigned int is_power_of_2(unsigned int n)
{
  return (n != 0 && (n & (n-1)) == 0);
}

static unsigned int roundup_power_of_2(unsigned int a)
{
  if(a == 0)
    return 0;
  
  unsigned int position = 0;
  unsigned int i;

  for(i=a; i!=0; i>>=1)
    position++;
  return (unsigned int)(1 << position);
}

void cfifo_init(cfifo_t *fifo, unsigned int size)
{
  if(!is_power_of_2(size))
    size = roundup_power_of_2(size);

  fifo->buffer = (char*)(malloc(size * sizeof(char)));
  fifo->in = 0;
  fifo->out = 0;
  fifo->size = size;
}

2.3 队列释放

void cfifo_exit(cfifo_t *fifo)
{
  if(fifo->buffer != NULL)
  {  
    free(fifo->buffer);
    fifo->buffer = NULL;
  }
}

2.4 入队列

unsigned int cfifo_put(cfifo_t *fifo, char *data, unsigned int len)
{
  unsigned int fl;
  unsigned int l;
 
  //get fifo free space
  fl = fifo->size - fifo->in + fifo->out;
  if(fl < len)
  {
    fifo->out += len - fl;
  }
  //len = min(len, fifo->size - fifo->in + fifo->out);
  //get fifo->in to buffer end free space
  l = min(len, fifo->size - (fifo->in & (fifo->size -1)));
  //first  put the data starting from fifo->in to buffer end
  memcpy(fifo->buffer + (fifo->in & (fifo->size -1)), data, l);

  //then put the rest (if any) at the beginning of the buffer
  memcpy(fifo->buffer, data+l, len - l);
  fifo->in += len;
  //zlog_info(o, "fifo->in = %d", fifo->in);
  return len; 
}

2.5 获取队列长度

unsigned int cfifo_get_datalength(cfifo_t *fifo)
{
  unsigned int len = 0;
  len = (fifo->in - fifo->out);
  return len;
}

2.6 出队列

#define min(x, y) ((x) < (y) ? (x) : (y))

unsigned int cfifo_get(cfifo_t *fifo, char *data, unsigned int len)
{
  unsigned int l;
  unsigned int dl;

  //get fifo data length
  dl = fifo->in - fifo->out;
  len = min(len, dl);
 
  //get fifo->out to buffer end data length 
  l = min(len, fifo->size - (fifo->out & (fifo->size -1)));
 
  //first get the data from fifo->out until the end of the buffer
  memcpy(data, fifo->buffer + (fifo->out & (fifo->size -1)), l);
  
  //then get the rest data (if any) from the beginning of the buufer 
  memcpy(data+l, fifo->buffer, len-l);
 
  fifo->out += len;
  //zlog_info(o, "fifo->out = %d", fifo->out);
  return len;
}

2.7 回退数据

void cfifo_rollback_data(cfifo_t *fifo, unsigned int size)
{
  fifo->out -= size;
}