预分配内存fifo实现可变长度字节序列存储

github链接https://github.com/gexin1023/utils/tree/master/fifo

fifo即先进先出队列，可以用链表来实现，在链表头部插入数据，尾部读数据，每次插入新的数据都动态分配一段内存用于数据存储,适用于变长数据的队列实现。也可以用数组实现，用一个数组buf[LEN]作为缓存，用两个整数分别记录写数据和读数据的位置，适用于每次读取相同长度数据的场景。

有的场景中，要避免频繁的malloc/free动态分配释放，与此同时数据长度不定。因此，需要预分配一段空间存储数据，也需要记录每一个数据的长度，方便存取。

fifo数据结构

typedef struct

{

    unsigned int pos;   // position index in buffer

    unsigned int len;   // the length of data

    list_node_t  node;

}pos_t;

typedef struct

{

    unsigned char   *buffer;

    unsigned int    size;

    unsigned int    in;

    unsigned int    out;

    list_node_t     pos_head;

} fifo_t;

设计以上的数据结构，buffer即为fifo的存储空间，开始时根据需要预分配，size表示buffer的长度。in和out分别记录读写数据的位置，pos_t结构组成的链表用于记录每次写入数据的位置及长度。

fifo接口

fifo_t * fifo_init(unsigned char *buf, unsigned int size);

fifo_t *fifo_alloc(unsigned int size);

void fifo_free(fifo_t *fifo);

/* fifo_put, 向fifo加入数据

 * @fifo,   目标fifo

 * @buf,    数据

 * @len,    数据长度

 * 如果空间不够，就删除最旧的数据，新数据覆盖旧数据

 */

unsigned int fifo_put(fifo_t *fifo, unsigned char *buf, unsigned int len);

/* fifo_put_tail

 * 有时会存在优先级比较高的数据需要放在最先出队的位置

 * /

unsigned int fifo_put_tail(fifo_t *fifo, unsigned char *buf, unsigned int len);

/* fifo_get

 * 取数据

 */

int fifo_get(fifo_t *fifo, unsigned char *buf, unsigned int *p_len);

/* fifo_get_len

 * 获取数据长度

 */

int fifo_get_len(fifo_t *fifo);

fifo接口的实现如下：



/* fifo_init:   create a fifo using a preallocated memory

 *

 * buf:     preallocated memory

 * size:    the length of the preallocated memory, 取以2为底的整数

 */

fifo_t * fifo_init(unsigned char *buf, unsigned int size)

{

    fifo_t *fifo = (fifo_t *)malloc(sizeof(fifo_t));

    fifo->buffer = buf;

    fifo->size   = size;

    fifo->in = fifo->out = 0;

    fifo->pos_head.next = &(fifo->pos_head);

    fifo->pos_head.prev = &(fifo->pos_head);

    return fifo;

}

/* fifo_alloc:   create a fifo

 *

 * size: the length of the allocated memory

 */

fifo_t *fifo_alloc(unsigned int size)

{

    unsigned char * buf = (unsigned char *)malloc(size);

    return fifo_init(buf, size);

}

/* fifo_free:

 *

 */

void fifo_free(fifo_t *fifo)

{

    free(fifo->buffer);

    free(fifo);

}

/* fifo_put, 向fifo加入数据

 * @fifo,   目标fifo

 * @buf,    数据

 * @len,    数据长度

 * 如果空间不够，就删除最旧的数据，新数据覆盖旧数据 */

static unsigned int __fifo_put(fifo_t *fifo, unsigned char *buf, unsigned int len)

{

    unsigned int l;

    /* fifo 空间不足时，删除旧内容，直到可以容纳新的数据 */

    while(len>(fifo->size - fifo->in + fifo->out))

    {

        pos_t *pos = list_entry(fifo->pos_head.prev, pos_t, node);

        fifo->out += pos->len;

        list_del(fifo->pos_head.prev);

        free(pos);

    }

    /* 首先复制数据从（ in % buf_size）位置到buffer结尾 */

    l = min(len , fifo->size - (fifo->in & (fifo->size-1)));

    memcpy(fifo->buffer + (fifo->in & (fifo->size-1)), buf ,l);

    /* 然后复制剩下的数据从buffer开头开始 */

    memcpy(fifo->buffer, buf+l, len-l);

    /* 加入新的位置节点 */

    pos_t *pos = (pos_t *)malloc(sizeof(pos_t));

    pos->len=len;

    pos->pos=fifo->in;

    list_add(&(fifo->pos_head), &(pos->node));

    /* 更改写入点索引 */

    fifo->in += len;

    return len;

}

unsigned int fifo_put(fifo_t *fifo, unsigned char *buf, unsigned int len)

{

    return __fifo_put(fifo, buf, len);

}

unsigned int fifo_put_tail(fifo_t *fifo, unsigned char *buf, unsigned int len)

{

    unsigned int l;

    /* fifo 空间不足时，删除旧内容，直到可以容纳新的数据 */

    while(len>(fifo->size - fifo->in + fifo->out))

    {

        pos_t *pos = list_entry(fifo->pos_head.prev, pos_t, node);

        fifo->out += pos->len;

        list_del(fifo->pos_head.prev);

        free(pos);

    }

    fifo->out -= len;

    /* 首先复制数据从（ out % buf_size）位置到buffer结尾 */

    l = min(len , fifo->size - (fifo->out & (fifo->size-1)));

    memcpy(fifo->buffer + (fifo->out & (fifo->size-1)), buf ,l);

    /* 然后复制剩下的数据从buffer开头开始 */

    memcpy(fifo->buffer, buf+l, len-l);

    /* 加入新的位置节点 */

    pos_t *pos = (pos_t *)malloc(sizeof(pos_t));

    pos->len=len;

    pos->pos=fifo->out;

    list_add_tail(&(fifo->pos_head), &(pos->node));

    return len;

}

int fifo_get(fifo_t * fifo, unsigned char * buf, unsigned int * p_len)

{

    if(fifo->pos_head.next == &(fifo->pos_head))

    {

        // fifo is emperty

        return -1;

    }

    pos_t *pos = list_entry(fifo->pos_head.prev, pos_t, node);

    *p_len = pos->len;

    list_del(&(pos->node));

    free(pos);

    int l = min(*p_len, fifo->size - (fifo->out &(fifo->size-1)));

    memcpy(buf, fifo->buffer+(fifo->out & (fifo->size-1)), l);

    memcpy(buf+l, fifo->buffer, *p_len-l);

    fifo->out += *p_len;

    return *p_len;

}

int fifo_get_len(fifo_t * fifo)

{

    if(fifo->pos_head.next == &(fifo->pos_head))

    {

        // fifo is emperty

        return -1;

    }

    pos_t *pos = list_entry(fifo->pos_head.prev, pos_t, node);

    return (int)pos->len;

}

巴特西

预分配内存fifo实现可变长度字节序列存储

预分配内存fifo实现可变长度字节序列存储

fifo数据结构

fifo接口

最新文章

热门文章