数据结构-环形缓冲区-- Circular Buffer（Ring Buffer）

环形缓冲区-- Circular Buffer（Ring Buffer）C/C++ 可用

什么是循环缓冲区

循环缓冲区(也称为环形缓冲区)是固定大小的缓冲区，工作原理就像内存是连续的且可循环的一样。在生成和使用内存时，不需将原来的数据全部重新清理掉，只要调整head/tail 指针即可。当添加数据时，head 指针前进。当使用数据时，tail 指针向前移动。当到达缓冲区的尾部时，指针又回到缓冲区的起始位置。

为什么使用循环缓冲区

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

引用 Ring buffer basics 文章如下

The ring buffer's first-in first-out data structure is useful tool for transmitting data between asynchronous processes. Here's how to bit bang one in C without C++'s Standard Template Library.

The ring buffer is a circular software queue. This queue has a first-in-first-out (FIFO) data characteristic. These buffers are quite common and are found in many embedded systems. Usually, most developers write these constructs from scratch on an as-needed basis.

The C++ language has the Standard Template Library (STL), which has a very easy-to-use set of class templates. This library enables the developer to create the queue and other lists relatively easily. For the purposes of this article, however, I am assuming that we do not have access to the C++ language.

The ring buffer usually has two indices to the elements within the buffer. The distance between the indices can range from zero (0) to the total number of elements within the buffer. The use of the dual indices means the queue length can shrink to zero, (empty), to the total number of elements, (full). Figure 1 shows the ring structure of the ring buffer, (FIFO) queue.

img

Figure 1: Structure of a ring buffer.

The data gets PUT at the head index, and the data is read from the tail index. In essence, the newest data “grows” from the head index. The oldest data gets retrieved from the tail index. Figure 2 shows how the head and tail index varies in time using a linear array of elements for the buffer.

img

Figure 2: Linear buffer implementation of the ring buffer.

Use cases Single process to single process In general, the queue is used to serialize data from one process to another process. The serialization allows some elasticity in time between the processes. In many cases, the queue is used as a data buffer in some hardware interrupt service routine. This buffer will collect the data so that at some later time another process can fetch the data for further processing. This use case is the single process to process buffering case.

This use case is typically found as an interface between some very high priority hardware service buffering data to some lower priority service running in some background loop. This simple buffering use case is shown in Figure 3 .

img

Figure 3: A single process to process buffer use case

In many cases, there will be a need for two queues for a single interrupt service. Using multiple queues is quite common for device drivers for serial devices such as RS-232, I2C or USB drivers. Multiple processes to single process A little less common is the requirement to serialize many data streams into one receiving streams. These use cases are quite common in multi-threaded operating systems. In this case, there are many client threads requesting some type of serialization from some server or broker thread. The requests or messages are serialized into a single queue which is received by a single process. Figure 4 shows this use case.

img

Figure 4: Multiple processes to process use case.

Single process to multiple processes The least common use case is the single process to multiple processes case. The difficulty here is to determine where to steer the output in real time. Usually, this is done by tagging the data elements in such a way that a broker can steer the data in some meaningful way. Figure 5 shows the single process to multiple processes use case. Since queues can be readily created, it is usually better to create multiple queues to solve this use case than it would be to use a single queue.

img

Figure 5: Single process to multiple processes use case.

Figure 6 shows how to reorganize the single process to multiple process use case using a set of cascaded queues. In this case, we have inserted an Rx / Tx Broker Dispatcher service, which will parse the incoming requests to each of the individual process queues.

img

Figure 6: Single process to multiple process use case using a dispatcher and multiple queues.

Managing overflow One must be able to handle the case where the queue is full and there is still incoming data. This case is known as the overflow condition. There are two methods which handle this case. They are to drop the latest data or to overwrite the oldest data. Either style may be implemented.

缓冲区实现

数据结构

  • 基础数据缓冲区
  • 缓冲区的最大范围
  • “head”指针的当前位置（添加元素时增加）
  • “tail”指针的当前位置（读取元素后增加）
  • 一个标志位来指示缓冲区是否已满
// The hidden definition of our circular buffer structure
typedef struct circular_buf_t
{
    uint8_t *buffer;
    size_t head;
    size_t tail;
    size_t max; //of the buffer
    bool full;
} *cbuf_handle_t;

确认缓冲区是否已满

当head == tail， 循环缓冲区的 “full” 和 “empty” 看起来是相同的：head 和 tail 指针是相等的。有两种方法区分 full 和 empty：

使用缓冲区中的一个数据位：

  • Full：tail + 1 == head
  • Empty：head == tail

使用一个bool标志位和其他逻辑来区分：

  • Full：full
  • Empty：(head == tail) && (!full)

从上面的数据结构看到我们使用的是通过标志位来判断，那么就需要在get /set 操作方法中更新该标志位

初始化和复位

/// Pass in a storage buffer and size 
/// Returns a circular buffer handle
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;
}

/// Reset the circular buffer to empty, head == tail
void circular_buf_reset(cbuf_handle_t cbuf)
{
    assert(cbuf);

    cbuf->head = 0;
    cbuf->tail = 0;
    cbuf->full = false;
}

/// Free a circular buffer structure.
/// Does not free data buffer; owner is responsible for that
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;
}
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;
}
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;
}

数据填充删除

从缓冲区读取数据后删除，即取出 tail 指针位置的值并更新 tail 指针。如果缓冲区是空的，不修改指针值并且返回 error=-1。
从缓冲区读取数据后删除，即取出 tail 指针位置的值并更新 tail 指针。如果缓冲区是空的，不修改指针值并且返回 error=-1。

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];
        // 当删除数据时，full 标志置为 flase ，tail 指针向前移一位
        cbuf->full = false;
        cbuf->tail = (cbuf->tail + 1) % cbuf->max;
        r = 0;
    }

    return r;
}

当读跟不上写速度的时候有两种方法，一种是覆盖旧数据，一种是不做处理，阻塞或者丢弃新数据

阻塞或者丢弃新数据

以丢弃新数据为例， 如果buff 已满了（circular_buf_full = true），则不做任何处理

int circular_buf_put_block(cbuf_handle_t cbuf, uint8_t data)
{
    int r = -1;

    assert(cbuf && cbuf->buffer);

    if(!circular_buf_full(cbuf))
    {
        cbuf->buffer[cbuf->head] = data;
        //  将写指针位置往前移动
        cbuf->head = (cbuf->head + 1) % cbuf->max;
        cbuf->full = (cbuf->head == cbuf->tail);
        r = 0;
    }

    return r;
}

以Demo为例

100ms 写一次，而400ms 读一次，buff 大小为16B，所以其阻塞住了，并且丢弃了新来写的数据，只有buff 有缓冲的时候才能写

void *read_thread(void *arg)
{
    uint8_t data;;
    printf("%s %d\n", __FUNCTION__, __LINE__);
    while (1)
    {
        pthread_mutex_lock(&rw_mutex);
        circular_buf_get(arg, &data);
        pthread_mutex_unlock(&rw_mutex);
        printf("%s %d ===>data:0x%x\n", __FUNCTION__, __LINE__, data);

        usleep(400*1000);
    }

    return NULL;
}

int main()
{
    pthread_t ntid;
    uint8_t data;
    uint8_t buff[16] = {0};
    cbuf_handle_t handle = circular_buf_init(buff, sizeof(buff));
    int ret;
    pthread_create(&ntid, NULL, read_thread, handle);
    printf("%s %d data:0x%x\n", __FUNCTION__, __LINE__, data);
    while (1)
    {
        usleep(100*1000);
        data = rand()%0xff;
        pthread_mutex_lock(&rw_mutex);
        ret = circular_buf_put_block(handle, data);
        pthread_mutex_unlock(&rw_mutex);
        if(!ret)
            printf("%s %d write data:0x%x\n", __FUNCTION__, __LINE__, data);
    }
    free(buff);
    circular_buf_free(handle);
    return 0;
}

打印输出：

main 201 data:0x0
read_thread 179
read_thread 185 ===>data:0x0
main 210 write data:0x29
main 210 write data:0x6b
main 210 write data:0xd6
read_thread 185 ===>data:0x29
main 210 write data:0xeb
main 210 write data:0x2c
main 210 write data:0xa9
main 210 write data:0x3
read_thread 185 ===>data:0x6b
main 210 write data:0x21
main 210 write data:0xbb
main 210 write data:0xef
main 210 write data:0x5f
read_thread 185 ===>data:0xd6
main 210 write data:0x5f
main 210 write data:0x4c
main 210 write data:0xfc
main 210 write data:0x10
read_thread 185 ===>data:0xeb
main 210 write data:0xec
main 210 write data:0xbe
main 210 write data:0xd4
main 210 write data:0xed
read_thread 185 ===>data:0x2c
main 210 write data:0x51
main 210 write data:0x6
read_thread 185 ===>data:0xa9
main 210 write data:0x99
read_thread 185 ===>data:0x3
main 210 write data:0x65
read_thread 185 ===>data:0x21
main 210 write data:0x33

覆盖旧数据

int circular_buf_put_overwrite(cbuf_handle_t cbuf, uint8_t data)
{
    assert(cbuf && cbuf->buffer);

    cbuf->buffer[cbuf->head] = data;

    // 如果buff 满了需要复写读到的数据，那么需要将读位置往前移动
    if (cbuf->full)
    {
        cbuf->tail = (cbuf->tail + 1) % cbuf->max;
    }

    cbuf->head = (cbuf->head + 1) % cbuf->max;
    cbuf->full = (cbuf->head == cbuf->tail);
    return 0;
}

同样以该Demo为例

100ms 写一次，而400ms 读一次，buff 大小为16B，将写替换为 circular_buf_put_overwrite 来覆盖旧数据

int main()
{
    pthread_t ntid;
    uint8_t data;
    uint8_t buff[16] = {0};
    cbuf_handle_t handle = circular_buf_init(buff, sizeof(buff));
    int ret;
    pthread_create(&ntid, NULL, read_thread, handle);
    printf("%s %d data:0x%x\n", __FUNCTION__, __LINE__, data);
    while (1)
    {
        usleep(100*1000);
        data = rand()%0xff;
        pthread_mutex_lock(&rw_mutex);
        ret = circular_buf_put_overwrite(handle, data);
        pthread_mutex_unlock(&rw_mutex);
        if(!ret)
            printf("%s %d write data:0x%x\n", __FUNCTION__, __LINE__, data);
    }
    free(buff);
    circular_buf_free(handle);
    return 0;
}

100ms 写一次，而400ms 读一次，buff 大小为16B，因为复写了，所以buffer满了之后，读到的数据总是16B写之前写的首次数据

输出

main 227 write data:0x33
main 227 write data:0xec
main 227 write data:0x3f
main 227 write data:0x54
read_thread 202 ===>data:0x51
main 227 write data:0x16
main 227 write data:0xa7
main 227 write data:0x22
main 227 write data:0xcd
read_thread 202 ===>data:0x99
main 227 write data:0xcc
main 227 write data:0x8f
main 227 write data:0x60
main 227 write data:0xd4
read_thread 202 ===>data:0x65
main 227 write data:0xf3
main 227 write data:0x4e
main 227 write data:0x4a
main 227 write data:0x60
read_thread 202 ===>data:0x33   // 读到这个数据位置与之前的写位置正好相差16
main 227 write data:0x3d

参考自 https://www.cnblogs.com/youngjum/p/12188780.html

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,189评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,577评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,857评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,703评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,705评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,620评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,995评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,656评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,898评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,395评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,982评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2赞 342