Linux下循环缓存区（fifo）的实现

    循环缓冲区在一些竞争问题上提供了一种免锁的机制，免锁的前提是，生产者和消费都只有一个的情况下，否则也要加锁。下面是循环缓存区的代码示例：
fifo.h

#ifndef  FIFO_H
#define  FIFO_H

typedef unsigned char uchar;
typedef unsigned int uint;


struct _pfifo
{
    uchar *buffer;
    uint size;
    uint in;
    uint out;
};
typedef struct _pfifo Pfifo;

#define min(a,b) ((a) < (b) ? (a):(b))

void pfifo_reset(Pfifo *p);
uint pfifo_len(Pfifo *p);
uint pfifo_get(Pfifo *fifo, uchar *buffer, uint len);
uint pfifo_put(Pfifo *fifo, uchar *buffer, uint len);
/* size must be 2^n */
Pfifo * pfifo_alloc(uint size);
void pfifo_free(Pfifo *p);

#endif /*FIFO_H*/

fifo.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#include "fifo.h"

void pfifo_reset(Pfifo *p)
{
    p->in = p->out = 0;
}
uint pfifo_len(Pfifo *p)
{
    return p->in - p->out;
}

uint pfifo_get(Pfifo *fifo, uchar *buffer, uint len)
{
    uint l;

    len = min(len, fifo->in - fifo->out);

     /* first get the data from fifo->out until the end of the buffer */
    l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
    memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

     /* then get the rest (if any) from the beginning of the buffer */
    memcpy(buffer + l, fifo->buffer, len - l);

    fifo->out += len;
    return len;
}

uint pfifo_put(Pfifo *fifo, uchar *buffer, uint len)
{
    uint l;

    len = min(len, fifo->size - fifo->in + fifo->out);
    /* first put the data starting from fifo->in to buffer end */
    l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
    memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

    /* then put the rest (if any) at the beginning of the buffer */
    memcpy(fifo->buffer, buffer + l, len - l);

    fifo->in += len;
    return len;
}

Pfifo * pfifo_alloc(uint size)
{
    Pfifo *fifo = NULL;
    uchar *buffer;

    buffer = malloc(size);
    if (!buffer ) {
        printf("failed to malloc buffer!\n");
        goto err1;
    }

    fifo = malloc(sizeof(Pfifo));
    if (!fifo) {
        printf("failed to malloc Pfifo!\n");
        goto err2;
    }
    fifo->buffer = buffer;
    fifo->size = size;
    fifo->in = fifo->out = 0;

    return fifo;

err2:
    free(buffer);
err1:
    return NULL;
}

void pfifo_free(Pfifo *p)
{
    free(p->buffer);
    p->buffer = NULL;
    free(p);
    p = NULL;
}

Pfifo * fifo;

void test(void)
{
    uchar buf[256] ;
    uint last, this;
    int ret, i;

    while (1) {
        ret = pfifo_get(fifo, buf,256);
        if (ret == 0 ) {
            usleep(1000);
            continue;
        }

        for (i = 0 ; i < ret ; i++ ) {
           this = buf[i];
           if (this != ((last + 1)%127)) {
               printf("this %d last %d\n");
           }
           last = this;
        }
        last = this;
    }
}

int main(int argc, char *argv[])
{
    uchar buf[127];
    int i, ret;
    pthread_t id;

    for (i = 0 ; i <127 ; i++ )
        buf[i] = i;

    fifo = pfifo_alloc(1024);

    ret = pthread_create(&id,NULL,test,NULL);
    if (ret < 0) {
        printf("pthread create failed !\n");
    }

    while (1 ) {
        ret = pfifo_put(fifo,buf,127);
        if (ret < 127 ) {
            usleep(5000);
            pfifo_put(fifo,buf + ret,127 - ret);
        }
    }

    pfifo_free(fifo);
    return 0;
}

    这两个读写结构才是循环缓冲区的重点。在fifo结构中，size是缓冲区的大小，是由用户自己定义的，但是在这个设计当中要求它的大小必须是2的幂次。当in==out时，表明缓冲区为空的，当(in-out)==size 时，说明缓冲区已满。
    我们看fifo->in &(fifo->size-1) 这个表达式是什么意思呢？我们知道size是2的幂次项，那么它减1即表示其值的二进制所有位都为1，与in相与的最终结果是in%size,比size要小，所以看in及out的值都是不断地增加，但再相与操作后，它们即是以size为周期的一个循环。 l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));就是比较要写入的数据应该是多少，如果缓冲区后面的还有足够的空间可写，那么把全部的值写到后面，否则写满后面，再写到前面去memcpy(fifo->buffer, buffer + l, len - l);。读数据也可以作类似的分析，len = min(len, fifo->in - fifo->out);表示请求的数据要比缓冲区的数据要大时，只读取缓冲区中可用的数据。