环形缓冲区(ringbuffer)

环形缓冲区(ringbuffer)

环形缓冲区是嵌入式系统中十分重要的一种数据结构,比如在串口处理中,串口中断接收数据直接往环形缓冲区丢数据,而应用可以从环形缓冲区取数据进行处理,这样数据在读取和写入的时候都可以在这个缓冲区里循环进行,程序员可以根据自己需要的数据大小来决定自己使用的缓冲区大小。

环形缓冲区,顾名思义这个缓冲区是环形的,那么何谓环形这个意思也很好理解,就是用一个指针去访问该缓冲区的最后一个内存位置的的后一位置时回到环形缓冲区的起点。类似一个环一样

在此之前,我们来回顾一下队列的基本概念:队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。

环形缓冲区是队列的一个应用,环形缓冲区(环形队列)的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。

 

                                                                环形缓冲区(ringbuffer)

下面是环形缓冲区的一些数据结构定义

1.环形缓冲区控制块定义

/* 环形缓冲区控制块 */
struct rt_ringbuffer
{
    rt_uint8_t *buffer_ptr;			//缓冲区指针
    rt_uint16_t read_mirror : 1;	//读取镜像
    rt_uint16_t read_index : 15;	//读取位置
    rt_uint16_t write_mirror : 1;	//写入位置
    rt_uint16_t write_index : 15;	//写入位置
    rt_int16_t buffer_size;			//缓冲区大小
};

2.环形缓冲区状态定义

/* 环形缓冲区状态 */
enum rt_ringbuffer_state
{
    RT_RINGBUFFER_EMPTY,			//环形缓冲区空	
    RT_RINGBUFFER_FULL,				//环形缓冲区满
    RT_RINGBUFFER_HALFFULL,			//环形缓冲区半满
};

环形缓冲区实现方式

1.初始化环形缓冲区,使用静态环形缓冲区前,需要调用该函数进行初始化。该函数将把用户指定的缓冲区空间的指针传递给环形缓冲区控制块,并初始化环形缓冲区控制块的参数。

参数 :

rb ringbuffer 环形缓冲区句柄

pool 缓冲区指针

size 缓冲区大小

void rt_ringbuffer_init(struct rt_ringbuffer *rb,
                        rt_uint8_t           *pool,
                        rt_int16_t            size)
{
   
    /* 初始化读写位置及读写镜像 */
    rb->read_mirror = rb->read_index = 0;
    rb->write_mirror = rb->write_index = 0;

    /* 缓冲区空间及大小初始化赋值 */
    rb->buffer_ptr = pool;
    rb->buffer_size = RT_ALIGN_DOWN(size, RT_ALIGN_SIZE);
}

2.往环形缓冲区中写入数据,调用此函数可以往指定环形缓冲区中写入指定长度的数据,如果剩余空间不足将丢弃剩余数据。

参数:

 rb ringbuffer 环形缓冲区句柄

ptr 待写入数据的指针

length 待写入数据的大小,如果 length 大于剩余空间将丢弃剩余的数据 

返回:实际写入字节数。

rt_size_t rt_ringbuffer_put(struct rt_ringbuffer *rb,
                            const rt_uint8_t     *ptr,
                            rt_uint16_t           length)
{
    rt_uint16_t size;

    /* 获取环形缓冲区剩余空间 */
    size = rt_ringbuffer_space_len(rb);

    /* 写入有效长度数据,超过长度则丢弃 */
    if (size < length)
        length = size;

	/* 缓冲区尾部还能存储写入数据长度数据 */
    if (rb->buffer_size - rb->write_index > length)
    {
        /* 将写入数据拷贝到环形缓冲区中 
		 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
		 * | 0 | 1 |   |   |   |   |   |   |   |   |   |   |   |   |
		 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
		 *			write_index
		 */
        memcpy(&rb->buffer_ptr[rb->write_index], ptr, length);
        rb->write_index += length;
        return length;
    }
	/* 将写入数据拷贝到环形缓冲区中,需要分成两段计算 
	 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
	 * |   |   |   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |   |   |   |
	 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
	 *			                                    write_index
	 */
    memcpy(&rb->buffer_ptr[rb->write_index],
           &ptr[0],
           rb->buffer_size - rb->write_index);
    memcpy(&rb->buffer_ptr[0],
           &ptr[rb->buffer_size - rb->write_index],
           length - (rb->buffer_size - rb->write_index));

    /* 写入镜像翻转 */
    rb->write_mirror = ~rb->write_mirror;
    rb->write_index = length - (rb->buffer_size - rb->write_index);

    return length;
}

3.往环形缓冲区中强制压入数据,调用此函数可以往指定环形缓冲区中强制写入指定长度的数据,如果剩余空间不足将覆盖原有数据。

参数 :

rb ringbuffer 环形缓冲区句柄

ptr 待压入数据的指针 length 待压入数据的大小,如果 length 大于剩余空间将丢弃剩余的数据

返回 :实际写入字节数。

rt_size_t rt_ringbuffer_put_force(struct rt_ringbuffer *rb,
                                  const rt_uint8_t     *ptr,
                                  rt_uint16_t           length)
{
    rt_uint16_t space_length;

	/* 获取环形缓冲区剩余空间 */
    space_length = rt_ringbuffer_space_len(rb);

    if (length > rb->buffer_size)
    {
        ptr = &ptr[length - rb->buffer_size];
        length = rb->buffer_size;
    }

    if (rb->buffer_size - rb->write_index > length)
    {
        /* 将写入数据拷贝到环形缓冲区中 
		 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
		 * | 0 | 1 |   |   |   |   |   |   |   |   |   |   |   |   |
		 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
		 *			write_index
		 */
        memcpy(&rb->buffer_ptr[rb->write_index], ptr, length);
        /* this should not cause overflow because there is enough space for
         * length of data in current mirror */
        rb->write_index += length;

        if (length > space_length)
            rb->read_index = rb->write_index;

        return length;
    }
	/* 将写入数据拷贝到环形缓冲区中 
	 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
	 * |   |   |   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |   |   |   |
	 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
	 *			                                    write_index
	 */
    memcpy(&rb->buffer_ptr[rb->write_index],
           &ptr[0],
           rb->buffer_size - rb->write_index);
    memcpy(&rb->buffer_ptr[0],
           &ptr[rb->buffer_size - rb->write_index],
           length - (rb->buffer_size - rb->write_index));

	/* 写入镜像翻转 */
    rb->write_mirror = ~rb->write_mirror;
    rb->write_index = length - (rb->buffer_size - rb->write_index);

    if (length > space_length)
    {
        rb->read_mirror = ~rb->read_mirror;
        rb->read_index = rb->write_index;
    }

    return length;
}

4.从环形缓冲区中取出数据,调用此函数可以从环形缓冲区中读取指定长度的数据。

参数 :

rb ringbuffer 环形缓冲区句柄

ptr 取出数据的写入地址 length 待取出数据的大小

返回 :实际取出数据的字节数

rt_size_t rt_ringbuffer_get(struct rt_ringbuffer *rb,
                            rt_uint8_t           *ptr,
                            rt_uint16_t           length)
{
    rt_size_t size;

    RT_ASSERT(rb != RT_NULL);

    /* 获取环形缓冲区中数据长度 */
    size = rt_ringbuffer_data_len(rb);

	/* 拷贝环形缓冲区中数据  */
    if (rb->buffer_size - rb->read_index > length)
    {
		 /* 从环形缓冲区中读取数据
		 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
		 * | 0 | 1 | 2 | 3 |   |   |   |   |   |   |   |   |   |   |
		 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
		 *  read_index
		 */
        memcpy(ptr, &rb->buffer_ptr[rb->read_index], length);
        rb->read_index += length;
        return length;
    }
	/* 从环形缓冲区中读取数据 
	 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
	 * | 0 | 1 | 2 |   |   |   |   |   |   |   |   | 3 | 4 | 5 |
	 * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
	 *			                                    read_index
	 */
    memcpy(&ptr[0],
           &rb->buffer_ptr[rb->read_index],
           rb->buffer_size - rb->read_index);
    memcpy(&ptr[rb->buffer_size - rb->read_index],
           &rb->buffer_ptr[0],
           length - (rb->buffer_size - rb->read_index));

    /* 读取镜像翻转 */
    rb->read_mirror = ~rb->read_mirror;
    rb->read_index = length - (rb->buffer_size - rb->read_index);

    return length;
}

5.往环形缓冲区中写入一个字节,调用此函数可以往指定环形缓冲区中写入一个字节的数据,如果剩余空间不足将写入失败。

参数:

rb ringbuffer 环形缓冲区句柄

ch 待写入数据

返回 :写入成功返回1;环形缓冲区已满,写入失败则返回0。

rt_size_t rt_ringbuffer_putchar(struct rt_ringbuffer *rb, const rt_uint8_t ch)
{


    rb->buffer_ptr[rb->write_index] = ch;

    if (rb->write_index == rb->buffer_size - 1)
    {
        rb->write_mirror = ~rb->write_mirror;
        rb->write_index = 0;
    }
    else
    {
        rb->write_index++;
    }

    return 1;
}

6.往环形缓冲区中强制写入一个字节,调用此函数可以往指定环形缓冲区中强制写入一个字节的数据,如果剩余空间不足将覆盖原有数据。

参数 :

rb ringbuffer 环形缓冲区句柄

ch 待写入数据

返回 :写入成功返回1,如果缓冲区已满将覆盖已有数据

rt_size_t rt_ringbuffer_putchar_force(struct rt_ringbuffer *rb, const rt_uint8_t ch)
{
    enum rt_ringbuffer_state old_state;

   

    old_state = rt_ringbuffer_status(rb);

    rb->buffer_ptr[rb->write_index] = ch;


    if (rb->write_index == rb->buffer_size - 1)
    {
        rb->write_mirror = ~rb->write_mirror;
        rb->write_index = 0;
        if (old_state == RT_RINGBUFFER_FULL)
        {
            rb->read_mirror = ~rb->read_mirror;
            rb->read_index = rb->write_index;
        }
    }
    else
    {
        rb->write_index++;
        if (old_state == RT_RINGBUFFER_FULL)
            rb->read_index = rb->write_index;
    }

    return 1;
}

7.从环形缓冲区中取出一个字节的数据,调用此函数可以从环形缓冲区中读取一个字节的数据。

参数:

rb ringbuffer 环形缓冲区句柄

ch 存储待取出字节的变量

返回 :0 环形缓冲区已空,取出失败;1 成功取出

rt_size_t rt_ringbuffer_getchar(struct rt_ringbuffer *rb, rt_uint8_t *ch)
{
    RT_ASSERT(rb != RT_NULL);

    /* ringbuffer is empty */
    if (!rt_ringbuffer_data_len(rb))
        return 0;

    /* put character */
    *ch = rb->buffer_ptr[rb->read_index];

    if (rb->read_index == rb->buffer_size - 1)
    {
        rb->read_mirror = ~rb->read_mirror;
        rb->read_index = 0;
    }
    else
    {
        rb->read_index++;
    }

    return 1;
}

8.获取环形缓冲区中已使用的空间大小,调用此函数可以获取环形缓冲区中已被使用的字节数。

参数: rb 环形缓冲区句柄

返回 :已使用的大小;0 则表示环形缓冲区已空

rt_size_t rt_ringbuffer_data_len(struct rt_ringbuffer *rb)
{
    switch (rt_ringbuffer_status(rb))
    {
        case RT_RINGBUFFER_EMPTY:
            return 0;
        case RT_RINGBUFFER_FULL:
            return rb->buffer_size;
        case RT_RINGBUFFER_HALFFULL:
        default:
            if (rb->write_index > rb->read_index)
                return rb->write_index - rb->read_index;
            else
                return rb->buffer_size - (rb->read_index - rb->write_index);
    };
}

9.复位环形缓冲区,调用此函数将复位环形缓冲区,环形缓冲区控制块中的读写指针被置0。

参数 :rb ringbuffer 环形缓冲区句柄

void rt_ringbuffer_reset(struct rt_ringbuffer *rb)
{
    RT_ASSERT(rb != RT_NULL);

    rb->read_mirror = 0;
    rb->read_index = 0;
    rb->write_mirror = 0;
    rb->write_index = 0;
}

10.创建环形缓冲区对象,调用该函数将释放缓冲区和唤醒缓冲区控制块所占的内存空间。

参数 :size 环形缓冲区大小

struct rt_ringbuffer *rt_ringbuffer_create(rt_uint16_t size)
{
    struct rt_ringbuffer *rb;
    rt_uint8_t *pool;


	/* 申请环形缓冲区对象*/
    size = RT_ALIGN_DOWN(size, RT_ALIGN_SIZE);

    rb = (struct rt_ringbuffer *)rt_malloc(sizeof(struct rt_ringbuffer));
    if (rb == RT_NULL)
        goto exit;
	/* 申请环形缓冲区空间 */
    pool = (rt_uint8_t *)rt_malloc(size);
    if (pool == RT_NULL)
    {
        rt_free(rb);
        rb = RT_NULL;
        goto exit;
    }
	/* 初始化环形缓冲区 */
    rt_ringbuffer_init(rb, pool, size);

exit:
    return rb;
}

11.销毁环形缓冲区,调用该函数将释放缓冲区和唤醒缓冲区控制块所占的内存空间。

参数 :rb ringbuffer 环形缓冲区句柄

void rt_ringbuffer_destroy(struct rt_ringbuffer *rb)
{
    RT_ASSERT(rb != RT_NULL);

    rt_free(rb->buffer_ptr);
    rt_free(rb);
}

 

 

上一篇:Python CSV模块使用实例


下一篇:gif——攻防世界