精华内容
下载资源
问答
  • 环形缓冲区

    2017-11-07 20:49:56
    环形缓冲区的优点就不赘述了,此VS2015工程封装好环形缓冲区的接口,Boost库的二次封装,有测试示例。如果有编译问题,选择x86编译,记得要配置boost库环境。PS:如果可以的话,大量使用boost库,用起来很方便。
  • 基于环形缓冲区的CAN驱动模块、电子技术,开发板制作交流
  • 打包环提供了环形缓冲区的简单实现。 用法 var DefaultCapacity int = 10 未初始化的环形缓冲区的DefaultCapacity。 更改此值只会影响更改后创建的环形缓冲区。 环型 type Ring struct { sync. Mutex } 类型...
  • C语言环形缓冲区

    2017-03-10 20:29:31
    C语言实现环形缓冲区,可供多线程读写操作
  • Go中的线程安全循环缓冲区(环形缓冲区),实现了io.ReaderWriter接口
  • 该工程包含了整个实现代码,并添加了注释,提供了软件计时器多任务创建及调度接口函数,以及环形缓冲区完整接口函数。
  • STM32进阶之串口环形缓冲区实现 FIFO,代码精简,易实现。
  • 使用Go(golang.org)编写的简化的无锁环形缓冲区实现的高性能极简队列 当使用2个或更多goroutine进行操作时,GOMAXPROCS> = goroutine的数量,并且有足够的CPU内核来并行服务goroutine,这相当于使用通道构建的等效...
  • 本文主要是介绍 C语言实现环形缓冲区,并附有详细实现代码,具有一定的参考价值,希望能帮助有需要的小伙伴
  • 环形缓冲区-易语言

    2021-06-12 00:49:48
    这俩天用hp写中转服务器,考虑到分包,组包的时间消耗,就研究了下环形缓冲区。发现没有相关的e源码。只用e写了write,没写read,read 需要结合自己的xx包结构写
  • 这种处理方式是没有缓冲区的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据, 那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的...
  • 环形缓冲区实现原理

    2013-08-27 09:15:25
    在通信程序中,经常使用环形缓冲区作为数据结构来存放通信中发送和接收的数据。环形缓冲区是一个先进先出的循环缓冲区,可以向通信程序提供对缓冲区的互斥访问。
  • 一种为嵌入式系统设计的简单环形缓冲区(环形缓冲区)。- AndersKaloer /环缓冲区-源码
  • 环形缓冲区实现类(RingBuffer)
  • STM32串口接收,环形缓冲区方式实现串口接收
  • 环形缓冲区是嵌入式系统中十分重要的一种数据结构,比如在串口处理中,串口中断接收数据直接往环形缓冲区丢数据,而应用可以从环形缓冲区取数据进行处理,这样数据在读取和写入的时候都可以在这个缓冲区里循环进行,...

    环形缓冲区(ringbuffer)

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

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

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

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

     

     

                                                                    

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

    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);
            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);
    
        if (!rt_ringbuffer_data_len(rb))
            return 0;
    
        *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);
    }

     

     

    展开全文
  • 环形缓冲区 Go中的循环缓冲区(环形缓冲区),已实现io.ReaderWriter接口 rb := New ( 1024 ) // write rb . Write ([] byte ( "abcd" )) fmt . Println ( rb . Length ()) fmt . Println ( rb . Free ()) //...
  • Web的线程安全免等待单消费者单生产者环形缓冲区以及一些实用程序。 该库的主要文件: js/ringbuf.js :基本数据结构,实现环形缓冲区。 有意对此发表了强烈评论。 js/audioqueue.js :包装音频数据流,而不使用...
  • 队列1-环形缓冲区

    千次阅读 2019-01-27 16:58:34
    本篇为队列的第一篇文章,介绍基于数组结构的一个环形缓冲区队列。我觉得没有必要再从数组来写起,毕竟对于数组本身来说,我觉得是没有太多可说的,但是基于数组的数据结构就有的说了。 什么是环形缓冲区 环形缓冲...

    本篇为队列的第一篇文章,介绍基于数组结构的一个环形缓冲区队列。我觉得没有必要再从数组来写起,毕竟对于数组本身来说,我觉得是没有太多可说的,但是基于数组的数据结构就有的说了。

    什么是环形缓冲区

    • 环形缓冲区,顾名思义就是一个环状的存储数据的区域,其空间使用数组进行构造(链表也可以)。环形缓冲区特点是读和写可以是分开的,写入数据之后可以先不去读取,等到需要读取的时候再去读取,并且数据一经读取之后就做丢弃处理(当然也可以实现重复读取的效果,不过大多用作一次性读取),等于说是一次性的读取。
    • 假设一个长度为256字节的数组,构建出一个环形缓冲区,当写操作进行到数组的第256项之后,再一次写入就会回到第0个进行写入;同样读操作是读取到数组的第256项时,再一次进行读取就会回到数组的第一项。是谓环形缓冲

    可以看到,环形缓冲区是一种先进先出的队列类型结构,通常情况下会用于一个符合生产着消费者模型的场景。比如说视频帧数据的管理、消息队列的管理等等。

    队列类型的数据结构还有链表形式,只不过对于环形缓冲区来说,使用数组更加的高效。本文就基于 Linux 内核里面的 kfifo 队列实现一个高效、自定义功能并且以面向对象模式组织的环形缓冲区模块,不是照抄,理会精髓,自己实现,然后加入一些扩展。

    基本结构

    一个环形缓冲区包括以下元素:

    1. 读指针、写指针。
    2. 数组类型的存储空间(有链表类型的,但是这里只说数组类型)。
    3. 缓冲区是否满标志、锁。

    用图形化的描述就如下图所示:

    上面一个是它的直观存储方式,也就是一个数组类型的结构,其中 r 代表读指针,用于指示下一个应该读取的环形缓冲区元素。w 代表写指针,用于指示下一个该写入的位置。黑色的一列小方框就是用于存储环形缓冲区数据的存储空间。锁在单生产者、单消费者的情况下是不需要的,原因后面讲。其中 r,w 指针其实很容易看出来,它就是个数组的下标索引。

    下面一个圆形的图就是形象化的环形缓冲区,其实把直线棍状的数组给它折叠起来了而已,看起来没头没尾的一个自交型贪吃蛇结构。这个图更接近环形缓冲区的本身的抽象化形象,在代码实现上其实就是把读写指针取一个模完成"环形化"。

    这里要提一下的是关于缓冲区的满与空的标志,首先说结论:

    1. rw 相等的时候,就说明这个环形缓冲区队列空了。
    2. r == (w + 1)%size 的时候就说明这个环形缓冲区满了。

    上面两个断言似乎有冲突的地方,比如写指针绕过一圈子之后如果 wr 相等也能够说这个环形缓冲区是满的,并且上面第二条看起来会空余一个元素没有用到啊。第一个我们在代码实现的时候就会在出队列的时候才会判断这个缓冲区是否为空,第二个为了方便起见,环形缓冲区始终会空出一个元素的位置来明确的区分队列空与队列满的标记。所以第一个冲突的情况就不会发生。

    如果希望能够充分利用存储空间的话就需要一个额外的变量来存储目前缓冲区里面已经存放好的元素有多少个,然后与环形缓冲区创建之初指定的元素总数进行比较,这样就可以充分利用所有缓冲区里面的存储空间,因为大多数时候环形缓冲区的元素都是大于一个字节的。

    代码实现

    保留之前的习惯,在文章里面会尽可能少的贴代码,我觉得贴的代码过多会导致整篇文章很难看,并且使得文章显得冗长并且有用的部分还不多,代码我贴到 github 上面在文末给出链接。

    首先我这里的代码实现提出了几个要求:

    1. 能够自定义环形缓冲区的元素个数、自定义每个元素的字节数。
    2. 能够支持多线程安全的方式进行读取或者写入。
    3. 模块化,使用者只需要初始化一个环形缓冲区对象,然后可以很方便地使用它。
    4. 可以很方便、快速地初始化多个环形缓冲区实例。

    这里我会先规定一个环形缓冲区的抽象化结构体,在需要使用的时候就实例化一个环形缓冲区结构体,我把它的结构写成下面这种:

    struct ring_buffer {
        int (*rb_in)(struct ring_buffer *rb_hd,
                void *buf_in, uint32_t elem_num);
        int (*rb_out)(struct ring_buffer *rb_hd,
                void *buf_out, uint32_t elem_num);
        void (*rb_reset)(struct ring_buffer *rb_hd);
    
        uint32_t (*rb_g_bufsize)(struct ring_buffer *rb_hd);
        uint32_t (*rb_g_validnum)(struct ring_buffer *rb_hd);
        uint32_t (*rb_g_elemsize)(struct ring_buffer *rb_hd);
    
        void *private;
    };
    

    里面的前面大部分项都不去解释了,很容易可以知道它们每个值的意义。最后一个 private 需要特别解释下,这个是用于模块内部的自用结构的索引。仔细看一下上面的结构体里面缺少了哪些元素?

    可以看到少了环形缓冲区的总大小、元素大小、锁、读指针、写指针等等。而这些东西对于使用者来讲是不需要用到的数据,不需要关心,而这部分数据我就放在另外一个内部的结构体里面了,它的定义如下所示:

    struct ring_buffer_entity {
        pthread_mutex_t rb_lock;
        uint32_t rb_in;
        uint32_t rb_out;
    
        uint32_t elem_size;
        uint32_t elem_cnt;
        bool rb_full;
    
        unsigned char *rb_buf;
    
        struct ring_buffer_attr rb_attr;
        struct ring_buffer rb_handle;
    };
    

    在使用的时候我通常会做以下的转换:struct ring_buffer_entity *entity = (struct ring_buffer_entity *)ring_buffer->private;。这样就达到了封装的目的,在 C++ 里面封装是不需要用得到那个 private 的,但是在 C 里面就不得不用这种方式实现封装的目的。

    扯多了,回到代码中与环形缓冲区相关的地方。

    临界判断

    在上面的第二个结构体里面,读写指针都是32位的无符号整形,这个是有特殊作用的,因为这种情况下可以直接使用 rb_in - rb_out 来表示目前环形缓冲区里面有效的数据个数,不用取模,在写入之后 rb_in 尽管加上写入元素的个数即可,也不用在写入结束的时候把 rb_in 取模。

    想象一下无符号整形数的特点,就是在溢出的时候会恢复到0值,也就是 0xFFFFFFFF+1 会等于 0,在没有溢出的情况下 rb_in - rb_out 用于表示目前已写入的元素个数很好理解,那么一旦当 rb_in 溢出了,rb_in - rb_out 还是可以满足计算要求。

    用一个实例套入计算即可,比如说现在环形缓冲区里面有三个元素,正常情况下 rb_inrb_out 的关系是类似 3与0,116与113 的关系,直接减去没有问题,但是如果这个时候 rb_in 已经超了,比如此时 rb_out == 0xFFFFFFFE, 呢么 rb_in 就是 0xFFFFFFFE+3,这个值在无符号的时候是2,因为溢出了,那么无符号的 2-0xFFFFFFFE 在内部计算的时候就是一个很大的负数,而这个负数重新转化为无符号类型就是 3.

    目前代码里面没有只用了一个已写入元素的个数计数和整个环形缓冲区的可存储元素总数来进行比较,没有使用 r,w 指针本身来进行判断,这样会充分利用环形缓冲区里面的每一个存储空间。

    读写的实现

    写入的核心代码有下面几个步骤:

    uint32_t cp_cnt   = min(要写入的元素个数, 剩余的元素个数);
    uint32_t cp_step1 = min(cp_cnt, 数组右侧剩余的可存储元素空间个数);
    memcpy(写指针在的位置, 输入buffer地址, cp_step1乘以元素的大小);
    memcpy(数组起始地址, 输入buffer剩下的数据起始地址, (cp_cnt-cp_step1)乘以元素大小);
    rb_ent->rb_in += cp_cnt; /* 写指针后移 */
    

    读取的核心代码有下面几个步骤:

    uint32_t cp_cnt   = min(要读出的元素个数, 有效元素个数);
    uint32_t cp_step1 = min(cp_cnt, 数组右侧剩余的有效元素个数);
    
    if (NULL == buf_out)
        goto copy_end;
    
    memcpy(输出buffer地址, 读指针在的位置, cp_step1乘以元素大小);
    memcpy(输出buffer剩余空间起始地址, 数组零下标起始地址, (cp_cnt-cp_step1)乘以元素大小);
    
    copy_end:
    rb_ent->rb_out += cp_cnt; /* 读指针后移 */
    

    这里读写指针不必每次后移的时候都取模,只用在索引数组下标的时候对其取模即可,原因在上一条里面描述过了。

    如果在单生产者单消费者的情况下,这个读写的过程是不用加锁的,唯一需要担心的也就是指令重排了,但是这种情况发生的概率也是极小的,一般情况下在嵌入式的场景里面基本是不用担心的。

    那么如果在写的时候被打断,看下会发生什么情况,由于写过程中用到的会时刻变化的共享变量也就是 rb_out 了,如果在取到了 rb_out 的值之后它的值被别人改变了,也就是环形缓冲区中的存储空间又被释放出了一部分,此时顶多会导致本来可以写入的部分由于缓冲区被判定为满而写不进去了,稍等片刻再写或者干脆丢掉也不影响,整体上不会导致读写错乱。

    而读的过程也是类似,顶多是有些已经写入的东西被误判为还没有写入,那下次再去读取就好,无非是多耗费了一点时间,况且加锁的话这部分时间也是无法省去的。这也是代码里面为什么要在数据拷贝完成之后在改变 rb_inrb_out 的一个考虑,因为如果在拷贝之前改变它的值就有可能读出来非法的值或者写入值把原来的值给覆盖了。

    所以单生产者但消费者的情况下,基本上是不用考虑锁的问题的。从另一种角度来讲,这种队列模式其实不太可能用于多个消费者的情况,原因是因为通常情况下消费者是不能够错过队列中的任何一个消息的,或者说必须获取连续的队列内容。

    想象一下多消费者的实现,我这里有一种思路:提前确定好消费者的数量,然后为每一个队列项添加一个引用计数,一旦有一个消费者取用就将引用计数减一,到0才真正从队列里面删掉这个数据。这样会有几个问题:

    1. 一旦有任何一个消费者阻塞,其它的都会阻塞。
    2. 必须确定每一个元素的引用计数,需要添加一个成员,这样会导致一次性的多个元素拷贝变得很困难,因为可能有的读得多,有的读的少,这样会导致引用计数无法保持一致性的减少。

    所以,多个消费者一般是不会使用同一个队列对象的,多个生产者却是可能的,因为生产元素有很多时候无需满足十分有序的输入,比如命令分发、消息分发队列,这个时候可以只在生产者那一端也就是队列写入操作那里加上锁,读出就不需要加锁了。

    代码设计

    在代码里面我添加了一些属性,比如线程安全属性,与普通情况不同的是它加了一把锁,但是表现在使用者那里就对应的是同一个回调函数成员,只不过其指向的函数实现不一样而已。

    代码采用了面向对象的方式进行编写,可以非常方便的初始化一个环形缓冲区,并且使用实例化对象结构体内部的成员就可以完成整个的环形缓冲区的操作,十分方便。

    代码参考了内核里面的 kfifo 的实现,力求尽量地精简,但是为了使用的便捷,加入了不少的自定义内容,并且加入了一些可能会用得到的特性,比如线程安全属性等等。

    环形缓冲区内部不区分你想存入的数据结构类型,它只管按照当初约定好的元素长度以及你传递给它的读写 buffer 地址来进行指定长度的拷贝或者读取,数据类型的一致性要靠使用者自己来保证。

    利用 void* 指针的特性来屏蔽一些用户不需要的细节,比如上面说到的两个结构体,一个作为模块内部使用,一个作为用户与模块内部交互的接口使用。

    End

    这是队列的第一篇,主要介绍下环形缓冲区这个队列,下一篇文章会介绍一下链表类型的队列,会先写一下链表队列的实现,然后再结合一个实际的链表类型的应用进行辅助,风格与这个类似,力求使用方便,代码清晰易懂。

    需要注意的是代码里面肯定会不可避免的有一些 bug,要实现一个无 bug 的小模块显然比我想象当中的更困难,这一点在工作当中已经无数次验证过,所以当你使用我的代码遇到一些操蛋的问题,那一定不是用法的问题,我觉得大概率是我的代码 bug。那么为什么会有 bug 呢,主要还是我没有精力与动力去搞大规模测试,代码精确 review 这些,领会精髓吧,如果后续有必要,比如有人提了 issue 或者啥的我可能才会去修一修,不然凭我自己的主观能动性怕是比较玄学了。

    这篇其实是比较浅显易懂的,不过不要怪我水,因为写一篇技术类的文章太难了,要有代码要有文章,要有调试要尽量少错误,由浅及深,后续估计进度会越来越慢的(逃。

    Github 代码链接:链接


    想做的事情就去做吧
    展开全文
  • 环形缓冲区实现

    2016-01-29 20:24:22
    两种方式实现环形缓冲区,很实用,希望对你有帮助!
  • 环形缓冲区的实现

    千次阅读 2019-05-18 20:55:37
    1/** 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author 杰杰 6* @date 2018 7* @version v1.0 8* @note 初始化环形缓冲区 9*/10void RingBuff_Init(void)11{12 //初始化相关信息13 ringBuff....

    队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。


    队列的特点

    640?wx_fmt=png


    640?wx_fmt=png类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票

    640?wx_fmt=png 队列的常见两种形式

    640?wx_fmt=png

    640?wx_fmt=png 普通队列


    640?wx_fmt=png


    在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。


    当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。

    640?wx_fmt=png 环形队列

    640?wx_fmt=png


    它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。


    队列头 (Head) :允许进行删除的一端称为队首。队列尾 (Tail) :允许进行插入的一端称为队尾。

     

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


    实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。

    640?wx_fmt=png

    看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。

    640?wx_fmt=png


    640?wx_fmt=png 从队列到串口缓冲区的实现


    串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。

     

    那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:

     

    ①定义一个结构体:

    
     
    1typedef struct2{3    u16 Head;           4    u16 Tail;5    u16 Lenght;6    u8 Ring_Buff[RINGBUFF_LEN];7}RingBuff_t;8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区typedef struct
    2{

    3    u16 Head;          
    4    u16 Tail;
    5    u16 Lenght;
    6    u8 Ring_Buff[RINGBUFF_LEN];
    7}RingBuff_t;
    8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区


    ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。

    
     
     1/** 2* @brief  RingBuff_Init 3* @param  void 4* @return void 5* @author 杰杰 6* @date   2018 7* @version v1.0 8* @note   初始化环形缓冲区 9*/10void RingBuff_Init(void)11{12   //初始化相关信息13   ringBuff.Head = 0;14   ringBuff.Tail = 0;15   ringBuff.Lenght = 0;16}/**
    2* @brief  RingBuff_Init
    3* @param  void
    4* @return void
    5* @author 杰杰
    6* @date   2018
    7* @version v1.0
    8* @note   初始化环形缓冲区
    9*/

    10void RingBuff_Init(void)
    11
    {
    12   //初始化相关信息
    13   ringBuff.Head = 0;
    14   ringBuff.Tail = 0;
    15   ringBuff.Lenght = 0;
    16}


    初始化效果如下:

    640?wx_fmt=png


    写入环形缓冲区的代码实现:

    
     
     1/** 2* @brief  Write_RingBuff 3* @param  u8 data 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰 6* @date   2018 7* @version v1.0 8* @note   往环形缓冲区写入u8类型的数据 9*/10u8 Write_RingBuff(u8 data)11{12   if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满13    {14      return FLASE;15    }16    ringBuff.Ring_Buff[ringBuff.Tail]=data;17//    ringBuff.Tail++;18    ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问19    ringBuff.Lenght++;20    return TRUE;21}/**
    2* @brief  Write_RingBuff
    3* @param  u8 data
    4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功
    5* @author 杰杰
    6* @date   2018
    7* @version v1.0
    8* @note   往环形缓冲区写入u8类型的数据
    9*/

    10u8 Write_RingBuff(u8 data)
    11{
    12   if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满
    13    {
    14      return FLASE;
    15    }
    16    ringBuff.Ring_Buff[ringBuff.Tail]=data;
    17//    ringBuff.Tail++;
    18    ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问
    19    ringBuff.Lenght++;
    20    return TRUE;
    21}

     

    读取缓冲区的数据的代码实现:

    
     
     1/** 2* @brief  Read_RingBuff 3* @param  u8 *rData,用于保存读取的数据 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰 6* @date   2018 7* @version v1.0 8* @note   从环形缓冲区读取一个u8类型的数据 9*/10u8 Read_RingBuff(u8 *rData)11{12   if(ringBuff.Lenght == 0)//判断非空13    {14       return FLASE;15    }16   *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出17//   ringBuff.Head++;18   ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问19   ringBuff.Lenght--;20   return TRUE;21}/**
    2* @brief  Read_RingBuff
    3* @param  u8 *rData,用于保存读取的数据
    4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功
    5* @author 杰杰
    6* @date   2018
    7* @version v1.0
    8* @note   从环形缓冲区读取一个u8类型的数据
    9*/

    10u8 Read_RingBuff(u8 *rData)
    11{
    12   if(ringBuff.Lenght == 0)//判断非空
    13    {
    14       return FLASE;
    15    }
    16   *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出
    17//   ringBuff.Head++;
    18   ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问
    19   ringBuff.Lenght--;
    20   return TRUE;
    21}
    640?wx_fmt=png

    对于读写操作需要注意的地方有两个:

    1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。

    2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。

    640?wx_fmt=png

    那么在串口接收函数中:

    
     
    1void USART1_IRQHandler(void)   2{3   if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)  //接收中断4                   {5           USART_ClearITPendingBit(USART1,USART_IT_RXNE);       //清楚标志位6           Write_RingBuff(USART_ReceiveData(USART1));      //读取接收到的数据7       }8}void USART1_IRQHandler(void)   
    2
    {
    3   if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)  //接收中断
    4                   {
    5           USART_ClearITPendingBit(USART1,USART_IT_RXNE);       //清楚标志位
    6           Write_RingBuff(USART_ReceiveData(USART1));      //读取接收到的数据
    7       }
    8}

    640?wx_fmt=png 测试效果

    640?wx_fmt=png

    测试数据没有发生丢包现象。

    补充

      对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。

     1#define USER_RINGBUFF  1  //使用环形缓冲区形式接收数据 2#if  USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/ 4#define  RINGBUFF_LEN          200     //定义最大接收字节数 200 5#define  FLASE   1  6#define  TRUE    0  7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData);10#endif#define USER_RINGBUFF  1  //使用环形缓冲区形式接收数据
    2#if  USER_RINGBUFF
    3/**如果使用环形缓冲形式接收串口数据***/
    4#define  RINGBUFF_LEN          200     //定义最大接收字节数 200
    5#define  FLASE   1
    6#define  TRUE    0
    7void RingBuff_Init(void);
    8u8 Write_RingBuff(u8 data);
    9u8 Read_RingBuff(u8 *rData);
    10#endif


    当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。


    轻轻一扫  欢迎关注~

    640?wx_fmt=jpeg

    640?wx_fmt=gif


    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,894
精华内容 7,957
关键字:

环形缓冲区