环形缓冲区

背景：

        循环存储大量数据，实现新的数据自动覆盖老的数据，最简单方法。

实现代码：

定义类型:

        包括一个用来指向存储数据的数组指针buffer，记录头部的位置head，记录尾部的位置tail，开辟缓存的容量capacity，以及数据满的标志位full。

typedef struct{
    int *buffer;
    size_t head;
    size_t tail;
    size_t capacity;
    bool full;
}CircularBuffer;

创建:

        一个环形缓存区,初始化结构体的相关参数，开辟相应capacity的buffer。

CircularBuffer * create(size_t capacity)
{
    CircularBuffer *cb = (CircularBuffer *)malloc(sizeof(CircularBuffer));
    if(!cb)
        return NULL;
    cb->buffer = (int *)malloc(capacity *sizeof(int));
    if(!cb->buffer){
        free(cb);
        return NULL;
    }
    cb->head = 0;
    cb->tail = 0;
    cb->capacity = capacity;
    cb->full = false;
    return cb;
}

释放:

        释放环形缓冲区的内存。

void destroy(CircularBuffer  *cb)
{
    if(cb){
        free(cb->buffer);
        free(cb);
    }
}

读取：

        从缓冲区读取元素，若为空则返回错误值。

int get(CircularBuffer  *cb)
{
    if(isEmpty(cb))
        return -1;
    int item = cb->buffer[cb->head];
    cb->full = false;
    cb->head = (cb->head + 1) % cb->capacity;
    return item;
}

判空满：

        检测缓冲区是否为空或已满。

bool isEmpty(CircularBuffer  *cb)
{
    return (!cb->full && cb->tail == cb->head);
}

bool isFull(CircularBuffer  *cb)
{
    return cb->full;
}

获取容量和大小：

        获取缓冲区的容量和当前大小。

size_t capacity(CircularBuffer  *cb)
{
    return cb->capacity;
}

size_t size(CircularBuffer  *cb)
{
    if(cb->full)
        return cb->capacity;
    if(cb->tail >= cb->head)
        return cb->tail - cb->head;
    return cb->capacity + cb->tail - cb->head;
}

写入：

        向缓冲区添加新元素。如果缓冲区已满，覆盖最早的数据。

void put(CircularBuffer *cb, int item)
{
    cb->buffer[cb->tail] = item;
    if(cb->full){
        cb->head = (cb->head + 1) % cb->capacity;
    }
    cb->tail = (cb->tail + 1) % cb->capcity;
    cb->full = cb->tail == cb->head;
}

使用解释：

int main()
{
    CircularBuffer  *buf = create(5);
    
    put(buf,1);
    put(buf,2);
    put(buf,3);

    while (!sEmpty(buf)) {
        int item = get(buf);
        printf("%d\n", item);
    }

    destroy(buf);
    return 0;
}

        理解环形缓冲区的关键在于理解 tail 指针的更新方式。cb->tail = (cb->tail + 1) % cb->capacity; 这一行代码的作用是将 tail 指针移动到下一个写入位置，并确保 tail 指针在缓冲区范围内循环。

tail 指针的作用

• tail 指针：指向缓冲区中下一个要写入的位置。
• head 指针：指向缓冲区中下一个要读取的位置。

为什么需要 (cb->tail + 1) % cb->capacity

• cb->tail + 1：将 tail 指针向前移动一位。
• % cb->capacity：使用模运算确保 tail 指针在缓冲区范围内循环。

为什么需要模运算

• 模运算：确保 tail 指针在缓冲区范围内循环。
• 当 tail 指针达到缓冲区的末尾时，tail = (tail + 1) % capacity 会将 tail 指针重置为 0，从而实现循环写入。

示例：

        假设缓冲区的容量为 capacity = 5，初始状态为空（head = 0, tail = 0, full = false），依次插入元素 1, 2, 3, 4, 5：

1. 插入 1：

   • 写入位置：buffer[0] = 1
   • 更新 tail：tail = (0 + 1) % 5 = 1
   • 状态：head = 0, tail = 1, full = false

2. 插入 2：

   • 写入位置：buffer[1] = 2
   • 更新 tail：tail = (1 + 1) % 5 = 2
   • 状态：head = 0, tail = 2, full = false

3. 插入 3：

   • 写入位置：buffer[2] = 3
   • 更新 tail：tail = (2 + 1) % 5 = 3
   • 状态：head = 0, tail = 3, full = false

4. 插入 4：

   • 写入位置：buffer[3] = 4
   • 更新 tail：tail = (3 + 1) % 5 = 4
   • 状态：head = 0, tail = 4, full = false

5. 插入 5：

   • 写入位置：buffer[4] = 5
   • 更新 tail：tail = (4 + 1) % 5 = 0
   • 状态：head = 0, tail = 0, full = true（缓冲区已满）

这时缓冲区已满（head = 0, tail = 0, full = true），再插入一个元素 6：

1. 写入位置：buffer[0] = 6（覆盖最早的元素 1）
2. 更新 tail：tail = (0 + 1) % 5 = 1
3. 更新 head：head = (0 + 1) % 5 = 1（因为缓冲区已满，需要移动 head 指针）
4. 状态：head = 1, tail = 1, full = true

最后：

        通过这种方式，环形缓冲区可以有效地循环利用固定大小的数组空间，避免数据溢出。