精华内容
下载资源
问答
  • 循环缓冲区
    千次阅读
    2018-07-26 09:55:46

    这次需要记录之前了解到的参考自linux内核循环队列kfifo的循环缓冲区实现方法。

    1、循环缓冲区的实现依靠队列来实现,也就是分配一个数组来存储实际数据。

    2、对于一个循环缓冲区来说,我们需要关注的点有:

    ①缓冲区大小应该设置多少?

    ②缓冲区队头(in)、队尾(out)初始值?

    ③缓冲区什么时候为空,什么时候为满?

    ④如何表示缓冲区长度?

    ⑤如何入队,如何出队?

    ⑥如何处理索引值溢出问题?

     

    3、要实现循环缓冲区,我们当然可以用我们数据结构课学过的循环队列来实现,也就是:

    设队列大小为M;in和out为下标值。

    ①循环缓冲区的大小设置为M(没有限制)

    ②初始化队头 in=0 ,队尾 out = 0

    ③out == in的时候缓冲区为空,(in+1)%M == out 的时候为满

    ④缓冲区长度len =(in - out + M)% M

    ⑤入队:a[in] = data ;  in = (in+1) % M;

        出队:data = a[out] ;  out = (out+1)%M;

    ⑥索引溢出通过对缓冲区长度进行求余来实现。

     

    4、我们也可以通过另一种更好的方法来实现

    同样设队列大小为M;in和out为下标值,但是他们的数据类型都是unsigned int(无符号整型)!!!

    ①循环缓冲区的大小M设置为2的幂(举例M=2^4=16)

    ②初始化队头 in=0 ,队尾 out = 0

    ③out == in的时候缓冲区为空,(in - out ) == M的时候缓冲区为满。

    ④缓冲区的长度len = (in - out)

    ⑤入队:a[ in & (M-1) ] = data ; in = ++in;

        出对:data = a[ out & (M-1) ] ; out = ++out;

    ⑥因为我们缓冲区的大小M设置为2的幂,而unsigned int 型的溢出值肯定是M的2的幂次倍,也就是我们的unsigned int 能表示的数值范围就是2的幂数倍个M。所以,当我们需要得到当前in或者out对应于实际分配到内存的那块循环缓冲区的哪个位置时,可以让in或者out跟(M-1)相与;而更新in和out时,只需要++in和++out。

     

    下面举例说明:

    M = 10000;(M设置为16)

    (M-1) = 01111; 

    由于in和out都是unsigned int数据类型,所以in和out能表示的数值范围为maxof(unsigned_int)=2^32-1 = 4294967295

    a、当out在[0,M-1]范围内,就设out = 6(0110),out & (M-1) = 0110,也就是6。嗯,这个简单。

    b、当out 在[M,4294967295]范围内,设out = 28(11100),out & (M-1) = 11100 & 01111 = 01100,也就是out等于28时对应的循环缓冲区的位置下标为12。

    c、分析一下最极端的情况当out等于unsigned int的最大值4294967295,

        out&(M-1)= 01111,也就是循环缓冲区的最后一个位置。

        而out+1就溢出了,由于unsigned int溢出时变为0,又从最后一个位置加到第一个位置了。

       

    总结:

    关键字:unsigned int 、按位与运算、2的次幂

    a、必须要将M设置为2的次幂。

    b、用这种方法不必让in和out对M取余,通过与运算,可以提升速度。

    b、unsigned int 溢出时自动变为0,更新in和out时只需要加1即可,方便。

    更多相关内容
  • 这段代码是关于使用线性缓冲区(FIFO)、双缓冲区、循环缓冲区和双循环缓冲区实现卷积
  • 循环缓冲区 在C#中简单实现循环缓冲区。 这是单个文件的实现,这意味着您只需要将CircularBuffer.cs文件复制到您的项目中并使用它即可。 什么是循环缓冲区循环缓冲区循环缓冲区或环形缓冲区是一种数据结构,...
  • 将字符的循环/环形缓冲区实现为 C 扩展的 python 扩展。 它无声地覆盖。 可用性 目前,pyringbuf 可在或通过pip install pyringbuf 。 因为这是一个 C 扩展,所以有一个编译步骤,所以你的系统需要能够为 python ...
  • Go中的线程安全循环缓冲区(环形缓冲区),实现了io.ReaderWriter接口
  • 使用链表在 golang 中实现循环缓冲区 #####安装 go get github.com/pravj/cqueue 一个循环缓冲区结构 // CQueue represents a circular buffer data structure type CQueue struct { // size limit of the ...
  • 循环缓冲区 这几乎是循环缓冲区的高级版本,它遵循std :: queue,deque,vector等的STL命名约定。 它支持创建多个循环缓冲区,而无需使用重新分配,new或malloc。 系统使用模板来配置该类的缓冲区。 循环缓冲区和...
  • 循环缓冲区用于缓冲实时流媒体数据,以不定长度的数据块为存取单位,符合FIFO规则。 特征: 1、封装成了一个类,便于代码重用; 2、采用Mutex作为读取同步机制; 3、可设置缓冲区内的最多块的数量;
  • 循环缓冲区C++

    2015-04-30 00:00:15
    循环缓冲区,采用C++开发。 实现了数据的读写操作。
  • 在C和C ++中创建循环缓冲区

    千次阅读 2021-03-12 10:02:52
    由于嵌入式系统的资源限制,在大多数项目中都可以找到循环缓冲区数据结构。 循环缓冲区(也称为环形缓冲区)是固定大小的缓冲区,其工作方式就像内存是连续的且本质上是循环的。随着内存的生成和消耗,不需要重新...

    概述

            由于嵌入式系统的资源限制,在大多数项目中都可以找到循环缓冲区数据结构

    循环缓冲区(也称为环形缓冲区)是固定大小的缓冲区,其工作方式就像内存是连续的且本质上是循环的。随着内存的生成和消耗,不需要重新整理数据–而是调整了头/尾指针。添加数据后,头指针前进。当数据被消耗时,尾指针前进。如果到达缓冲区的末尾,指针将简单地绕到起始位置。

    有关循环缓冲区操作的更详细的摘要,请参阅Wikipedia文章。本文的其余部分假定您已了解循环缓冲区的工作方式。

    目录:

    1. 为什么要使用循环缓冲区?
    2. C实施
      1. 使用封装
      2. API设计
      3. 确定缓冲区是否已满
      4. 循环缓冲容器类型
      5. 执行
      6. 用法
      7. 删除full标志的修改
    3. C ++实现
      1. 类定义
      2. 执行
      3. 用法
      4. C ++ 17的更新
    4. 放在一起
    5. 进一步阅读

    为什么要使用循环缓冲区?

    循环缓冲区通常用作固定大小的队列。固定大小对于嵌入式系统是有益的,因为开发人员经常尝试使用静态数据存储方法而不是动态分配。

    循环缓冲区对于数据产生和使用以不同速率发生的情况也是有用的结构:最新数据始终可用。如果消费者无法跟上生产速度,则过时的数据将被更新的数据覆盖。通过使用循环缓冲区,我们可以确保始终使用最新数据。

    有关其他用例,请查看Embedded.com上的“环形缓冲区基础知识” 。

    C实施

    我们将从C实现开始,因为这在创建循环缓冲区库时使我们面临一些设计挑战和折衷。

    使用封装

    由于我们正在创建循环缓冲区库,因此我们希望确保用户使用我们的库API,而不是直接修改结构。我们还希望将实现保留在我们的库中,以便我们可以根据需要对其进行更改,而无需最终用户更新其代码。用户不需要知道关于我们结构的任何细节,只需知道它存在即可。

    在我们的库头中,我们将向前声明结构:

    // Opaque circular buffer structure
    typedef struct circular_buf_t circular_buf_t;
    

    我们不希望用户circular_but_t直接使用指针,因为他们可能会感到可以取消引用该值。我们将创建一个可以使用的句柄类型。

    对于我们的句柄,最简单的方法是typedefcbuf_handle_t用作循环缓冲区的指针。这将避免我们需要在函数实现中强制转换指针。

    // Handle type, the way users interact with the API
    typedef circular_buf_t* cbuf_handle_t;
    

    另一种方法是使句柄为auintptr_tvoid*value。在接口内部,我们将处理转换为适当的指针类型。我们将圆形缓冲区类型保持对用户隐藏,并且与数据进行交互的唯一方法是通过句柄。

    我们将坚持使用简单的句柄实现,以使示例代码保持简单明了。

    API设计

    首先,我们应该考虑用户如何与循环缓冲区交互:

    • 他们需要使用缓冲区和大小来初始化循环缓冲区容器
    • 他们需要破坏一个圆形的缓冲容器
    • 他们需要重置循环缓冲区容器
    • 他们需要能够将数据添加到缓冲区
    • 他们需要能够从缓冲区中获取下一个值
    • 他们需要知道缓冲区是满还是空
    • 他们需要知道缓冲区中当前的元素数量
    • 他们需要知道缓冲区的最大容量

    使用此列表,我们可以为我们的库提供一个API。用户将使用我们在初始化期间创建的不透明句柄类型与循环缓冲区库进行交互。

    我已选择uint8_t此实现中的基础数据类型。您可以使用任何喜欢的特定类型-请小心处理底层缓冲区和适当的字节数。

    /// Pass in a storage buffer and size 
    /// Returns a circular buffer handle
    cbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size);
    
    /// Free a circular buffer structure.
    /// Does not free data buffer; owner is responsible for that
    void circular_buf_free(cbuf_handle_t cbuf);
    
    /// Reset the circular buffer to empty, head == tail
    void circular_buf_reset(cbuf_handle_t cbuf);
    
    /// Put version 1 continues to add data if the buffer is full
    /// Old data is overwritten
    void circular_buf_put(cbuf_handle_t cbuf, uint8_t data);
    
    /// Put Version 2 rejects new data if the buffer is full
    /// Returns 0 on success, -1 if buffer is full
    int circular_buf_put2(cbuf_handle_t cbuf, uint8_t data);
    
    /// Retrieve a value from the buffer
    /// Returns 0 on success, -1 if the buffer is empty
    int circular_buf_get(cbuf_handle_t cbuf, uint8_t * data);
    
    /// Returns true if the buffer is empty
    bool circular_buf_empty(cbuf_handle_t cbuf);
    
    /// Returns true if the buffer is full
    bool circular_buf_full(cbuf_handle_t cbuf);
    
    /// Returns the maximum capacity of the buffer
    size_t circular_buf_capacity(cbuf_handle_t cbuf);
    
    /// Returns the current number of elements in the buffer
    size_t circular_buf_size(cbuf_handle_t cbuf);
    

    确定缓冲区是否已满

    在继续之前,我们应该花一点时间来讨论用于确定缓冲区是满还是空的方法。

    循环缓冲区的“满”和“空”情况看起来相同:head并且tail指针相等。有两种区分满和空的方法:

    1. “浪费”缓冲区中的一个插槽:
      • 完整状态为 head + 1 == tail
      • 空状态为 head == tail
    2. 使用bool标志和其他逻辑来区分状态:
      • 完整状态为 full
      • 空状态为 (head == tail) && !full

    我们还应该考虑线程安全性。通过使用单个空单元格来检测“已满”情况,我们可以无锁地支持单个生产者和单个消费者(只要put并且get不修改相同的变量)。该队列是线程安全的,因为生产者将仅修改head索引,而使用者将仅修改tail索引。尽管两个索引在给定的上下文中可能都有些过时,但这不会影响队列的线程安全性。full但是,使用该标志会产生相互排斥的要求。这是因为该full标志由生产者和消费者共享。

    当然,该决定需要权衡。如果缓冲区元素具有较大的内存占用空间(例如,为相机i帧调整大小的缓冲区),则在系统上浪费插槽可能是不合理的。如果您有多个生产者/消费者与一个队列进行交互,那么无论如何您都将需要一个锁,因此浪费插槽是没有意义的。如果您没有互斥功能(例如,因为您没有使用OS),但是您正在使用中断,那么您将要使用非full标记版本。系统上使用的内存模型也可能会影响您决定不加锁

    下面的实现使用该bool标志。使用标志需要在getput例程中附加逻辑以更新标志。我还将描述如何对不使用该full标志的单个生产者/消费者进行修改。

    循环缓冲容器类型

    既然我们已经掌握了需要支持的操作,那么我们就可以设计循环缓冲区容器了。

    我们使用容器结构来管理缓冲区的状态。为了保留封装,容器结构是在我们的库.c文件中定义的,而不是在标头中定义的。

    我们将需要跟踪:

    • 基础数据缓冲区
    • 缓冲区的最大大小
    • 当前的“头部”位置(添加元素时增加)
    • 当前的“尾巴”(当元素被删除时增加)
    • 指示缓冲区是否已满的标志
    // The hidden definition of our circular buffer structure
    struct circular_buf_t {
    	uint8_t * buffer;
    	size_t head;
    	size_t tail;
    	size_t max; //of the buffer
    	bool full;
    };
    

    既然我们的容器已经设计好了,我们就可以实现库函数了。

    执行

    需要注意的一个重要细节是,我们的每个API都需要一个初始化的缓冲区句柄。我们不会使用条件语句来填充我们的代码,而是将使用断言来以“按合同设计”样式来强制执行我们的API要求。

    如果接口使用不当,程序将立即失败,而不是要求用户检查和处理错误代码。

    例如:

    circular_buf_reset(NULL);
    

    产生:

    === C Circular Buffer Check ===
    Assertion failed: (cbuf), function circular_buf_reset, file ../../circular_buffer.c, line 35.
    Abort trap: 6
    

    另一个重要的注意事项是,下面显示的实现不是线程安全的。没有将锁添加到基础循环缓冲区库中。

    初始化和重置

    让我们从头开始:初始化循环缓冲区。我们的API让客户端提供了底层缓冲区和缓冲区大小,并且我们向它们返回了循环缓冲区句柄。

    我们需要在库侧创建循环缓冲区容器。malloc为了简单起见,我已经使用过。不能使用动态内存的系统只需修改init功能以使用其他方法,例如从循环缓冲区容器的静态池中进行分配。

    另一种方法是破坏封装,允许用户静态声明循环缓冲区容器结构。在这种情况下,circular_buf_init需要更新以采用结构指针,或者init可以在堆栈上创建容器结构并将其返回。但是,由于封装被破坏,因此用户将可以在不使用库例程的情况下修改结构。

    // User provides struct
    void circular_buf_init(circular_buf_t* cbuf, uint8_t* buffer, 
    	size_t size);
    
    // Return a struct
    circular_buf_t circular_buf_init(uint8_t* buffer, size_t size)
    

    创建容器后,我们需要填充值并对其进行调用reset。从返回之前init,请确保缓冲区容器已创建为空状态。

    cbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size)
    {
    	assert(buffer && size);
    
    	cbuf_handle_t cbuf = malloc(sizeof(circular_buf_t));
    	assert(cbuf);
    
    	cbuf->buffer = buffer;
    	cbuf->max = size;
    	circular_buf_reset(cbuf);
    
    	assert(circular_buf_empty(cbuf));
    
    	return cbuf;
    }
    

    复位功能的目的是把缓冲到一个“空”的状态,这需要更新headtailfull

    void circular_buf_reset(cbuf_handle_t cbuf)
    {
        assert(cbuf);
    
        cbuf->head = 0;
        cbuf->tail = 0;
        cbuf->full = false;
    }
    

    由于我们有创建圆形缓冲区容器的方法,因此我们需要使用等效的方法来销毁该容器。在这种情况下,我们调用free容器。我们不尝试释放底层缓冲区,因为我们不拥有它。

    void circular_buf_free(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    	free(cbuf);
    }
    

    状态检查

    接下来,我们将实现与缓冲区容器状态有关的功能。

    完整功能最容易实现,因为我们有一个表示状态的标志:

    bool circular_buf_full(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
        return cbuf->full;
    }
    

    由于我们具有full区分完整状态或空状态的标志,因此我们将标志与以下检查结合起来head == tail

    bool circular_buf_empty(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
        return (!cbuf->full && (cbuf->head == cbuf->tail));
    }
    

    缓冲区的容量是在初始化期间提供的,因此我们只将该值返回给用户:

    size_t circular_buf_capacity(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
    	return cbuf->max;
    }
    

    计算缓冲区中元素的数量是一个比我预期的棘手的问题。许多建议的尺寸计算使用模,但是在测试时遇到了奇怪的极端情况。我选择使用条件语句进行简化的计算。

    如果缓冲区已满,我们知道我们的容量最大。如果head大于或等于tail,则只需将两个值相减即可得出大小。如果tail大于head,则需要用来抵消差值,max以获取正确的大小。

    size_t circular_buf_size(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
    	size_t size = cbuf->max;
    
    	if(!cbuf->full)
    	{
    		if(cbuf->head >= cbuf->tail)
    		{
    			size = (cbuf->head - cbuf->tail);
    		}
    		else
    		{
    			size = (cbuf->max + cbuf->head - cbuf->tail);
    		}
    	}
    
    	return size;
    }
    

    添加和删​​除数据

    随着簿记功能的完成,现在该深入探讨一下:从队列中添加和删除数据。

    要从循环缓冲区中添加和删除数据,需要对headtail指针进行操作。将数据添加到缓冲区时,我们在当前head位置插入新值,然后前进head。当我们从缓冲区中删除数据时,我们将获取当前tail指针的值,然后前进tail

    但是,将数据添加到缓冲区需要更多的考虑。如果缓冲区是缓冲区full,我们需要将tail指针和都向前推进head。我们还需要检查是否插入值会触发full条件。

    我们将实现该put函数的两个版本,因此让我们将指针提升逻辑提取到一个辅助函数中。如果缓冲区已满,则前进tail。我们总是前进head一个。指针前进后,我们full通过检查是否填充来标记head == tail

    请注意%以下模运算符()的使用。达到最大大小时,模将导致headtail值重置为0。这保证了headtail总是底层数据缓冲区的有效指标。

    static void advance_pointer(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
    	if(cbuf->full)
       	{
    		cbuf->tail = (cbuf->tail + 1) % cbuf->max;
    	}
    
    	cbuf->head = (cbuf->head + 1) % cbuf->max;
    	cbuf->full = (cbuf->head == cbuf->tail);
    }
    

    正如Miro Samek有益地指出的那样,这是一个昂贵的计算操作。相反,我们可以使用条件逻辑来减少指令总数。Miro推荐的方法是:

    if (++(cbuf->head) == cbuf->max) 
    { 
    	cbuf->head = 0;
    }
    

    现在,advance_pointer将如下所示:

    static void advance_pointer(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
    	if(cbuf->full)
       	{
    		if (++(cbuf->tail) == max_size_) 
    		{ 
    			cbuf->tail = 0;
    		}
    	}
    
    	if (++(cbuf->head) == cbuf->max) 
    	{ 
    		cbuf->head = 0;
    	}
    	cbuf->full = (cbuf->head == cbuf->tail);
    }
    

    我们可以创建一个类似的帮助器函数,当从缓冲区中删除一个值时会调用该函数。当我们删除一个值时,该full标志设置为false,并且尾指针前进。

    static void retreat_pointer(cbuf_handle_t cbuf)
    {
    	assert(cbuf);
    
    	cbuf->full = false;
    	if (++(cbuf->tail) == cbuf->max) 
    	{ 
    		cbuf->tail = 0;
    	}
    }
    

    我们将创建该put函数的两个版本。第一个版本将一个值插入缓冲区并前进指针。如果缓冲区已满,则最早的值将被覆盖。这是循环缓冲区的标准用例

    void circular_buf_put(cbuf_handle_t cbuf, uint8_t data)
    {
    	assert(cbuf && cbuf->buffer);
    
        cbuf->buffer[cbuf->head] = data;
    
        advance_pointer(cbuf);
    }
    

    put如果缓冲区已满,则该函数的第二个版本将返回错误。提供此代码是出于演示目的,但是我们在系统中未使用此变体。

    int circular_buf_put2(cbuf_handle_t cbuf, uint8_t data)
    {
        int r = -1;
    
        assert(cbuf && cbuf->buffer);
    
        if(!circular_buf_full(cbuf))
        {
            cbuf->buffer[cbuf->head] = data;
            advance_pointer(cbuf);
            r = 0;
        }
    
        return r;
    }
    

    要从缓冲区中删除数据,我们访问处的值,tail然后更新tail指针。如果缓冲区为空,则不返回值或修改指针。相反,我们将错误返回给用户。

    int circular_buf_get(cbuf_handle_t cbuf, uint8_t * data)
    {
        assert(cbuf && data && cbuf->buffer);
    
        int r = -1;
    
        if(!circular_buf_empty(cbuf))
        {
            *data = cbuf->buffer[cbuf->tail];
            retreat_pointer(cbuf);
    
            r = 0;
        }
    
        return r;
    }
    

    这样就完成了我们的循环缓冲区库的实现。

    用法

    使用该库时,客户端负责为创建基础数据缓冲区circular_buf_init,并cbuf_handle_t返回a:

    uint8_t * buffer  = malloc(EXAMPLE_BUFFER_SIZE * sizeof(uint8_t));
    cbuf_handle_t cbuf = circular_buf_init(buffer, 
    	EXAMPLE_BUFFER_SIZE);
    

    该句柄用于与所有剩余的库函数进行交互:

    bool full = circular_buf_full(cbuf);
    bool empty = circular_buf_empty(cbuf);
    printf("Current buffer size: %zu\n", circular_buf_size(cbuf);
    

    完成后,不要忘记释放基础数据缓冲区和容器:

    free(buffer);
    circular_buf_free(cbuf);
    

    的测试程序,它使用循环缓冲器库可以在找到嵌入式资源库

    删除full标志的修改

    如果要抛弃该full标志,则应检查head尾是否位于后面一个位置,以确定缓冲区是否已满:

    bool circular_buf_full(circular_buf_t* cbuf)
    {
    	// We determine "full" case by head being one position behind the tail
    	// Note that this means we are wasting one space in the buffer
        return ((cbuf->head + 1) % cbuf->size) == cbuf->tail;
    }
    

    现在,如果我们想避免取模运算,可以改为使用条件逻辑:

    bool circular_buf_full(circular_buf_t* cbuf)
    {
    	
    	// We need to handle the wraparound case
        size_t head = cbuf->head + 1;
        if(head == cbuf->max)
       {
    	head = 0;
       }
    
    	return head == cbuf->tail;
    }
    

    空的情况就是这样,head并且tail是相同的:

    bool circular_buf_empty(circular_buf_t* cbuf)
    {
    	// We define empty as head == tail
        return (cbuf->head == cbuf->tail);
    }
    

    当从缓冲区中获取数据时,我们将尾部指针前进,如有必要,将其环绕:

    int circular_buf_get(circular_buf_t * cbuf, uint8_t * data)
    {
        int r = -1;
    
        if(cbuf && data && !circular_buf_empty(cbuf))
        {
            *data = cbuf->buffer[cbuf->tail];
            cbuf->tail = (cbuf->tail + 1) % cbuf->size;
    
            r = 0;
        }
    
        return r;
    }
    

    在将数据添加到缓冲区时,我们将存储数据并前进头指针,如果需要的话,将其环绕:

    int circular_buf_put(circular_buf_t * cbuf, uint8_t data)
    {
        int r = -1;
    
        if(cbuf && !circular_nuf_full(cbuf))
        {
            cbuf->buffer[cbuf->head] = data;
            cbuf->head = (cbuf->head + 1) % cbuf->size;
    
            r = 0;
        }
    
        return r;
    }
    

    full可以省略对的其他引用。

    C ++

    C ++C语言更适合使用循环缓冲区实现。

    类定义

    我们将从定义我们的C ++类开始。我们希望我们的C ++实现支持任何类型的数据,因此我们将其设为模板化类。

    我们的API将类似于C的实现。我们的课程将提供以下接口:

    • 将缓冲区重置为空
    • 新增资料
    • 删除数据
    • 检查满/空状态
    • 检查缓冲区中的当前元素数
    • 检查缓冲区的总容量

    我们还将利用C ++智能指针来确保一旦破坏了缓冲区,我们就不会留下任何数据。这意味着我们可以为用户管理缓冲区。

    C ++的另一个好处是使该类成为线程安全的琐事:我们可以依靠std::mutex类型(假设为您的平台定义了该类型)。

    这是我们的类定义:

    template <class T>
    class circular_buffer {
    public:
    	explicit circular_buffer(size_t size) :
    		buf_(std::unique_ptr<T[]>(new T[size])),
    		max_size_(size)
    	{ // empty }
    
    	void put(T item);
    	T get();
    	void reset();
    	bool empty() const;
    	bool full() const;
    	size_t capacity() const;
    	size_t size() const;
    
    private:
    	std::mutex mutex_;
    	std::unique_ptr<T[]> buf_;
    	size_t head_ = 0;
    	size_t tail_ = 0;
    	const size_t max_size_;
    	bool full_ = 0;
    };
    

    C ++实现

    我们的C ++循环缓冲区模仿了C实现中的许多逻辑,但是却导致了更简洁,更可重用的设计。同样,C ++缓冲区std::mutex用于提供线程安全的实现。

    注意:可以在C ++实现中进行相同的逻辑更改,以通过“浪费”一个插槽来支持单个生产者和使用者的线程安全。有关更多信息,请参见C实现中调整

    初始化

    在构造类时,我们为基础缓冲区分配数据并设置缓冲区大小。这消除了C实现所需的开销。

    与C实现不同,C ++构造函数不会调用reset。因为我们为成员变量指定了初始值,所以循环缓冲区以正确的状态开始。

    explicit circular_buffer(size_t size) :
    	buf_(std::unique_ptr<T[]>(new T[size])),
    	max_size_(size)
    {
    	//empty constructor
    }
    

    我们的重置行为会将缓冲区恢复为空状态(head == tail && !full_)。

    void reset()
    {
    	std::lock_guard<std::mutex> lock(mutex_);
    	head_ = tail_;
    	full_ = false;
    }
    

    状态追踪

    的逻辑emptyfull的情况下是相同的C例如:

    bool empty() const
    {
    	//if head and tail are equal, we are empty
    	return (!full_ && (head_ == tail_));
    }
    
    bool full() const
    {
    	//If tail is ahead the head by 1, we are full
    	return full_;
    }
    

    在C ++循环缓冲器实现,sizecapacity报告在队列中,而不是在字节大小的元素数。这使我们与该类型的基本细节无关。

    size_t capacity() const
    {
    	return max_size_;
    }
    
    size_t size() const
    {
    	size_t size = max_size_;
    
    	if(!full_)
    	{
    		if(head_ >= tail_)
    		{
    			size = head_ - tail_;
    		}
    		else
    		{
    			size = max_size_ + head_ - tail_;
    		}
    	}
    
    	return size;
    }
    

    新增资料

    put匹配C实现的逻辑。此实现使用“覆盖最旧的值”行为模式。

    void put(T item)
    {
    	std::lock_guard<std::mutex> lock(mutex_);
    
    	buf_[head_] = item;
    
    	if(full_)
    	{
    		tail_ = (tail_ + 1) % max_size_;
    	}
    
    	head_ = (head_ + 1) % max_size_;
    
    	full_ = head_ == tail_;
    }
    

    注意:为简单起见,我省略了避免模运算的选项。您可以在C部分中找到该逻辑。

    检索数据

    后面的逻辑get与C实现匹配。与C实现不同,如果缓冲区为空,则返回空值。

    T get()
    {
    	std::lock_guard<std::mutex> lock(mutex_);
    
    	if(empty())
    	{
    		return T();
    	}
    
    	//Read data and advance the tail (we now have a free space)
    	auto val = buf_[tail_];
    	full_ = false;
    	tail_ = (tail_ + 1) % max_size_;
    
    	return val;
    }
    

    注意: return T()将返回给定类型的默认构造值。产生的实际值取决于类型或构造函数。另外,为简单起见,我省略了避免模运算的选项。您可以在C部分中找到该逻辑。

    用法

    C ++循环缓冲区比C实现要简单得多。

    要实例化循环缓冲区,我们只需要声明一个对象并为缓冲区指定模板化类型。这是一个使用10uint32_t个条目的缓冲区的示例:

    circular_buffer<uint32_t> circle(10);
    

    添加数据很容易:

    uint32_t x = 100;
    circle.put(x);
    

    同样,获取数据也很容易:

    x = circle.get()
    

    请记住,由于这是模板化类,因此您可以创建所需的任何类型的循环缓冲区。

    C ++ 17的更新

    在C ++ 17中,我们可以访问std::optional,这使我们能够表示可能存在或可能不存在的值。我们的get函数将返回std::optional<T>。如果队列为空,我们也将返回std::nullopt而不是默认构造T的。

    std::optional<T> get()
    {
    	std::lock_guard<std::mutex> lock(mutex_);
    
    	if(empty())
    	{
    		return std::nullopt;
    	}
    
    	//Read data and advance the tail (we now have a free space)
    	auto val = buf_[tail_];
    	full_ = false;
    	tail_ = (tail_ + 1) % max_size_;
    
    	return val;
    }
    

    注意:为简单起见,我省略了避免模运算的选项。您可以在C部分中找到该逻辑。

    在调用代码中,可以使用布尔运算符或has_value成员函数检查有效值。如果存在有效值,则可以使用->*运算符(使用value()成员函数ur)对其进行访问。

    
    // Returns an optional
    auto item = cbuf.get();
    
    // Check if the optional is valid
    if(item)
    {
    	process_data(*item); // access the value
    }
    

    放在一起

    示例实现中可以找到embedded-resourcesGithub的存储库

    如果要扩展此库,一个有用的练习是添加其他API,以使用户可以通过单个操作添加/删除多个元素。您还可以使C实现线程安全。

    前瞻方法的线程安全

    没有互斥量的一种线程安全方法是“超前”方法。该方法支持单个生产者线程和单个消费者线程。多个生产者或消费者将需要锁。

    不必使用布尔值标志来区分完全用例和空用例,我们总是将一个单元格留空。通过使用单个空单元格来检测“已满”情况,我们可以无锁地支持单个生产者和单个消费者(只要put并且get不修改相同的变量)。

    您可能会担心浪费插槽,但是这种权衡通常比使用OS锁定原语的成本便宜得多。

    进一步阅读

    以下是其他循环缓冲区的实现:

    有关循环缓冲区的更多信息:

    建议将循环缓冲区类型添加到C ++标准库:

    变更记录

    • 20200301
      • 解决了Miro关于避免模运算的反馈
    • 20200213
      • 添加了其他链接
      • 增加了有关在全标志与使用“浪费”时隙之间权衡的进一步讨论
      • 显示单个生产者/消费者对线程安全性的修改
      • 添加有关std::optional在C ++ 17上使用的注释
    • 20191016
      • 更新了变更日志部分的格式,以确保整个站点的一致性
      • 降级的标题可确保整个网站的一致性
      • 修复了破碎的目录链接
      • 从目录中删除了更改日志
    • 20190627
    • 20190604
      • 修复了拼写错误(感谢Chris Svec!),并更改了一些与不透明类型有关的措词。
    • 20181219
      • 添加了有关避免使用空插槽的单个生产者和单个消费者的并发问题的注释。
    • 20180804
      • 文章进行了重组和重写。感谢在此过程中提供反馈的每个人。这些示例已更新为:
      • 删除防御性编程
      • 使用断言
      • 使用不透明结构创建独立库
      • 扩展API,包括计算当前循环缓冲区的大小
      • 更新库,这样就不会浪费时间

    参考文章:https://embeddedartistry.com/blog/2017/05/17/creating-a-circular-buffer-in-c-and-c/

    展开全文
  • 利用C语言实现了一个循环缓冲区,一个线程向缓冲区里写数据,另一个线程从缓冲区中读取数据,同时保证数据的读取写入操作正确无误。
  • 循环缓冲区的 Nim 实现 循环缓冲区循环缓冲区或环形缓冲区是一种数据结构,它使用单个固定大小的缓冲区,就像端到端连接一样。 这种结构很容易缓冲数据流。 用法 var b = newRingBuffer [ int ]( 5 ) b. add ([ 1...
  • Go中的循环缓冲区(环形缓冲区),已实现io.ReaderWriter接口 rb := New ( 1024 ) // write rb . Write ([] byte ( "abcd" )) fmt . Println ( rb . Length ()) fmt . Println ( rb . Free ()) // read buf ...
  • 循环缓冲区的实现(纯C)

    千次阅读 2019-08-11 21:26:25
    循环缓冲区的用途 循环缓冲区主要用在文件系统中,和FIFO队列进行互补,特点是读写指针互不干扰,适用于经典的生产者消费者问题,相关原理已有相关博主解释。 循环缓冲区的定义 struct TRingBuf { char *buf; char ...

    循环缓冲区的用途

    循环缓冲区主要用在文件系统中,和FIFO队列进行互补,特点是读写指针互不干扰,适用于经典的生产者消费者问题,相关原理已有相关博主解释。

    循环缓冲区的定义

    struct TRingBuf {
        char *buf;
        char *end_pos_;
        char *read_pos_;
        char *write_pos_;
        //int data_size_;
        int data_write_size_;
        int data_read_size_;
    };
    void TRingBufCreate(struct TRingBuf *self, void *buf, int buf_size);//construct
    void TRingBufWrite(struct TRingBuf *self, void *data, int data_size);
    void TRingBufRead(struct TRingBuf *self, void *buf, int buf_size);
    void TRingBufClear(struct TRingBuf *self);//destruct
    int TRingBufSize(struct TRingBuf *self);
    int TRingBufFreeSize(struct TRingBuf *self);
    int TRingBufDataSize(struct TRingBuf *self);
    

    需要的头文件如下:

    #include <string.h>
    #include <stdlib.h>
    #include <unistd.h>
    

    循环缓冲区的实现

    #include "c_cache.h"
    
    
    void TRingBufCreate(struct TRingBuf *self, void *buf, int buf_size) {
        self->buf = (char*)buf;
        self->write_pos_ = (char*)buf;
        self->read_pos_ = (char*)buf;
        self->end_pos_ = (char*)buf + buf_size;
        //self->data_size_ = 0;
        self->data_read_size_ = 0;
        self->data_write_size_ = 0;
    }
    
    void TRingBufClear(struct TRingBuf *self) {
        self->write_pos_ = self->buf;
        self->read_pos_ = self->buf;
    //self->data_size_ = 0;
        self->data_read_size_ = 0;
        self->data_write_size_ = 0;
    }
    
    
    int TRingBufFreeSize(struct TRingBuf *self) {
        return (self->end_pos_ - self->buf) - (self->data_write_size_ - self->data_read_size_);
    }
    
    
    int TRingBufDataSize(struct TRingBuf *self) {
        return self->data_write_size_ - self->data_read_size_;
    }
    
    
    int TRingBufSize(struct TRingBuf *self) {
        return self->end_pos_ - self->buf;
    }
    
    
    void TRingBufWrite(struct TRingBuf *self, void *data, int data_size) {
        int free_size = TRingBufFreeSize(self);
        int result = data_size >= free_size ? free_size : data_size;
        int size = self->end_pos_ - self->write_pos_;
        if(size > result) 
        size = result;
        memmove(self->write_pos_, data, size);
        self->write_pos_ += size;
        if(self->write_pos_ >= self->end_pos_) {
            self->write_pos_ = self->buf;
            data_size = result - size;
            if(data_size > 0) {
            memmove(self->write_pos_, (char *)data + size, data_size);
            self->write_pos_ += data_size;
            }
        }
        self->data_write_size_ += result;
    }
    
    
    void TRingBufRead(struct TRingBuf *self, void *buf, int buf_size) {
        int data_size = TRingBufDataSize(self);
        int result = buf_size >= data_size ? data_size : buf_size;
        int size = self->end_pos_ - self->read_pos_;
        if(size > result) size = result;
        memmove(buf,(const void *)self->read_pos_, size); 
        self->read_pos_ += size;
        if(self->read_pos_ >= self->end_pos_){
            self->read_pos_ = self->buf;
            data_size = result - size;
            if(data_size > 0) {
            memmove((char *)buf + size, self->read_pos_, data_size);
            self->read_pos_ += data_size;
            }
        }
        self->data_read_size_ += result;
    }
    

    多线程读写测试代码

    #include "c_cache.h"
    #include <pthread.h>
    #include <stdio.h>
    struct TRingBuf *Buf = NULL; 
    void* Write(void *reg) {
        char r[] = "qwertyuiopasdfghjklzxcvbnm";
        TRingBufWrite(Buf, r, 26);
        printf("*****************************\n");
        printf("First Write success!!\n");
        printf("The data_size is %d\n",TRingBufDataSize(Buf));
        printf("The free_size is %d\n",TRingBufFreeSize(Buf));
        printf("The data of buf is :%s\n", Buf->buf);
        sleep(1);
        char s[] = "qwertyuiopasdfghjklzxcvbnm";
        TRingBufWrite(Buf, s, 26);
        printf("*****************************\n");
        printf("Second Write success!!\n");
        printf("The data_size is %d\n",TRingBufDataSize(Buf));
        printf("The free_size is %d\n",TRingBufFreeSize(Buf));
        printf("The data of buf is :%s\n", Buf->buf);
        return NULL; 
    }
    void* Read(void *reg) {
        char *buf = (char *)malloc(16*sizeof(char));
        TRingBufRead(Buf, buf, 16);
        printf("*****************************\n");
        printf("The result of reading is :%s\n", buf);
        free(buf);
        buf = NULL;
        printf("The data_size is %d\n",TRingBufDataSize(Buf));
        printf("The free_size is %d\n", TRingBufFreeSize(Buf));
        sleep(0.5);
        buf = (char *)malloc(16*sizeof(char));
        TRingBufRead(Buf, buf, 16);
        printf("*****************************\n");
        printf("The result of reading is :%s\n", buf);
        free(buf);
        buf = NULL;
        return NULL;
    }
    int main() {
        pthread_t tid[2];
        Buf = (struct TRingBuf*)malloc(sizeof(struct TRingBuf));
        char str[] = "12345678901234567890123456789012345";
        TRingBufCreate(Buf, str, 35);
        printf("*****************************\n");
        printf("The circle_cache is created!!\n");
        printf("The data_size is %d\n",TRingBufDataSize(Buf));
        printf("The free_size is %d\n", TRingBufFreeSize(Buf));
        sleep(0.01);
        int ret = pthread_create(&tid[0], NULL, Write, NULL);
        if(ret != 0) printf("pthread create fail\n");
        usleep(0.0001);
        int re = pthread_create(&tid[1], NULL, Read, NULL);
        if(re != 0) printf("pthread create fail\n");
        sleep(3);
        TRingBufClear(Buf);
        free(Buf);
        Buf = NULL;
        return 0;
    }
    
    展开全文
  • 下载Circular-master.zip-14.4 ...,但是没有循环缓冲器或循环队列(“双头”队列)。本课程旨在填补这一空白。 概念化这个混乱 循环缓冲器可从容器的正面和背面快速push和pop。假设没有重新分配,则这些操作的时...

    目录

    介绍

    概念化这个混乱

    使用这个混乱

    兴趣点


    介绍

    微软.NET提供了一些基本的通用数据结构,例如Stack<T>Queue<T>LinkedList<T>,但是没有循环缓冲器或循环队列(双头队列)。本课程旨在填补这一空白。

    概念化这个混乱

    循环缓冲器可从容器的正面和背面快速pushpop。假设没有重新分配,则这些操作的时间复杂度为O(1) ,而其他插入和删除操作的时间复杂度为O(n) 

    这使缓冲区适合作为通用堆栈或队列。尽管Microsoft拥有堆栈或队列,但仍可能希望以这种方式使用这个类的原因是这个类允许按索引访问并完全实现IList<T> 

    使用这个混乱

    该类相对易于使用。大多数IList<T>ICollection<T>接口成员都是显式的,因为它们的大多数操作都是O(n)而不是O(1。这意味着您必须转换为适当的接口才能完全访问其列表或集合成员。这是为了防止对数据结构的随意使用——它并不是主要用作列表类,而可以用作一个列表类。访问修饰符反映了这一点。

    主要APIPushBack()PopBack()PushFront()PopFront()组成 ,分别在容器的后面或前面添加和删除项目。也有一些更多的标准列表/集合成员如Contains()IndexOf()this[] Clear()

    这是演示/测试代码的摘录:

    Console.WriteLine("Adding 10 items");
    for (var i = 0; i < 10; ++i)
        list.PushBack(i + 1);
    
    Console.Write("Enumerating "+ list.Count+" items:");
    foreach (var item in list)
        Console.Write(" " + item.ToString());
    Console.WriteLine();
    
    Console.WriteLine("Removing 1 item");
    list.PopFront();

    兴趣点

    我真的受不了实现Insert(),尤其是在循环缓冲区上,如果有错误,可能在Insert()代码中。我不确定例程是否可以简化。有很多极端的情况。

    展开全文
  • 循环buffer的实现方式多种多样,我这里主要讲一种基于数组的循环buffer实现方式。 循环buffer原理如上图,在数据写满整个数组后将数据放入最开始再次写入。需要保证读指针小于等于写指针。 话不多说,直接上代码: ...
  • 它包括循环缓冲区,timout字典和持久字典。 循环缓冲区 循环缓冲区是固定长度的缓冲区。 当缓冲区已满时,后续的写操作将覆盖并覆盖先前的值。 当您仅对最新值感兴趣时,此功能很有用。 使用范例 为了激发食欲,...
  • C++封装 循环缓冲区

    2017-11-23 06:56:19
    C++ 封装的循环缓冲区类,可扩展,用于视频接收缓存区、消息接收缓冲区、解析数据缓冲区
  • 圆形队列类似于圆形缓冲区的队列容器。 创建具有设置的容量。 当将新项目推入生产能力时,旧项目将被覆盖。 Su Circular-queue圆形缓冲区状队列容器。 创建具有设置的容量。 当将新项目推入生产能力时,旧项目将被...
  • Linux设备驱动程序学习(3-补)-Linux中的循环缓冲区.pdf
  • 内存中的字符串循环缓冲区。 它支持多线程。 要求 铛 GNU Make 编译安装 make sudo make install 在调试模式下构建 make MODE=debug 建立共享库 make SHARED=yes 用消毒剂制作 make MODE=debug SANITIZE=address ...
  • #红衣主教 一种简单的方法来测量流的基数,该方法使用集合的循环缓冲区来进行更智能的异常检测和响应。
  • linux中的kfifo循环缓冲区设计得很精妙,使用循环队列的数据结构。 特点 使用并行无锁编程技术,即当它用于只有一个入队线程和一个出队线程的场景时,两个线程可以并发操作,而不需要任何加锁行为,就可以保证...
  • 报告C ++容器类在各种操作上的性能
  • * 索引 'new' 表示最后附加向量的开始这个循环缓冲区的主要思想是恒定性能(=> 双缓冲)并在程序中使用缓冲区时避免复制操作。 检查屏幕截图以查看,如果缓冲区较大,则此循环缓冲区具有优势,但与简单的复制缓冲区...
  • 循环缓冲区 嵌入式系统的循环缓冲区库 作者:詹姆斯·吴 电子邮件:

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 224,904
精华内容 89,961
关键字:

循环缓冲区