# 练习44：环形缓冲区
> 原文：[Exercise 44: Ring Buffer](http://c.learncodethehardway.org/book/ex44.html)
> 译者：[飞龙](https://github.com/wizardforcel)
环形缓冲区在处理异步IO时非常实用。它们可以在一端接收随机长度和区间的数据，在另一端以相同长度和区间提供密致的数据块。它们是`Queue`数据结构的变体，但是它针对于字节块而不是一系列指针。这个练习中我打算向你展示`RingBuffer`的代码，并且之后你需要对它执行完整的单元测试。
```c
#ifndef _lcthw_RingBuffer_h
#define _lcthw_RingBuffer_h
#include <lcthw/bstrlib.h>
typedef struct {
char *buffer;
int length;
int start;
int end;
} RingBuffer;
RingBuffer *RingBuffer_create(int length);
void RingBuffer_destroy(RingBuffer *buffer);
int RingBuffer_read(RingBuffer *buffer, char *target, int amount);
int RingBuffer_write(RingBuffer *buffer, char *data, int length);
int RingBuffer_empty(RingBuffer *buffer);
int RingBuffer_full(RingBuffer *buffer);
int RingBuffer_available_data(RingBuffer *buffer);
int RingBuffer_available_space(RingBuffer *buffer);
bstring RingBuffer_gets(RingBuffer *buffer, int amount);
#define RingBuffer_available_data(B) (((B)->end + 1) % (B)->length - (B)->start - 1)
#define RingBuffer_available_space(B) ((B)->length - (B)->end - 1)
#define RingBuffer_full(B) (RingBuffer_available_data((B)) - (B)->length == 0)
#define RingBuffer_empty(B) (RingBuffer_available_data((B)) == 0)
#define RingBuffer_puts(B, D) RingBuffer_write((B), bdata((D)), blength((D)))
#define RingBuffer_get_all(B) RingBuffer_gets((B), RingBuffer_available_data((B)))
#define RingBuffer_starts_at(B) ((B)->buffer + (B)->start)
#define RingBuffer_ends_at(B) ((B)->buffer + (B)->end)
#define RingBuffer_commit_read(B, A) ((B)->start = ((B)->start + (A)) % (B)->length)
#define RingBuffer_commit_write(B, A) ((B)->end = ((B)->end + (A)) % (B)->length)
#endif
```
观察这个数据结构，你会看到它含有`buffer`、`start` 和 `end`。`RingBuffer`的所做的事情只是在`buffer`中移动`start`和`end`，所以当数据到达缓冲区末尾时还可以继续“循环”。这样就会给人一种在固定空间内无限读取的“幻觉”。接下来我创建了一些宏来基于它执行各种计算。
下面是它的实现，它是对工作原理更好的解释：
```c
#undef NDEBUG
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <lcthw/dbg.h>
#include <lcthw/ringbuffer.h>
RingBuffer *RingBuffer_create(int length)
{
RingBuffer *buffer = calloc(1, sizeof(RingBuffer));
buffer->length = length + 1;
buffer->start = 0;
buffer->end = 0;
buffer->buffer = calloc(buffer->length, 1);
return buffer;
}
void RingBuffer_destroy(RingBuffer *buffer)
{
if(buffer) {
free(buffer->buffer);
free(buffer);
}
}
int RingBuffer_write(RingBuffer *buffer, char *data, int length)
{
if(RingBuffer_available_data(buffer) == 0) {
buffer->start = buffer->end = 0;
}
check(length <= RingBuffer_available_space(buffer),
"Not enough space: %d request, %d available",
RingBuffer_available_data(buffer), length);
void *result = memcpy(RingBuffer_ends_at(buffer), data, length);
check(result != NULL, "Failed to write data into buffer.");
RingBuffer_commit_write(buffer, length);
return length;
error:
return -1;
}
int RingBuffer_read(RingBuffer *buffer, char *target, int amount)
{
check_debug(amount <= RingBuffer_available_data(buffer),
"Not enough in the buffer: has %d, needs %d",
RingBuffer_available_data(buffer), amount);
void *result = memcpy(target, RingBuffer_starts_at(buffer), amount);
check(result != NULL, "Failed to write buffer into data.");
RingBuffer_commit_read(buffer, amount);
if(buffer->end == buffer->start) {
buffer->start = buffer->end = 0;
}
return amount;
error:
return -1;
}
bstring RingBuffer_gets(RingBuffer *buffer, int amount)
{
check(amount > 0, "Need more than 0 for gets, you gave: %d ", amount);
check_debug(amount <= RingBuffer_available_data(buffer),
"Not enough in the buffer.");
bstring result = blk2bstr(RingBuffer_starts_at(buffer), amount);
check(result != NULL, "Failed to create gets result.");
check(blength(result) == amount, "Wrong result length.");
RingBuffer_commit_read(buffer, amount);
assert(RingBuffer_available_data(buffer) >= 0 && "Error in read commit.");
return result;
error:
return NULL;
}
```
这些就是一个基本的`RingBuffer`实现的全部了。你可以从中读取和写入数据，获得它的大小和容量。也有一些缓冲区使用OS中的技巧来创建虚拟的无限存储，但它们不可移植。
由于我的`RingBuffer`处理读取和写入内存块，我要保证任何`end == start`出现的时候我都要将它们重置为0，使它们从退回缓冲区头部。在维基百科上的版本中，它并不可以写入数据块，所以只能移动`end`和`start`来转圈。为了更好地处理数据块，你需要在数据为空时移动到内部缓冲区的开头。
## 单元测试
对于你的单元测试，你需要测试尽可能多的情况。最简单的方法就是预构造不同的`RingBuffer`结构，之后手动检查函数和算数是否有效。例如，你可以构造`end`在缓冲区末尾的右边，而`start`在缓冲区范围内的`RingBuffer`，来看看它是否执行成功。
## 你会看到什么
下面是我的`ringbuffer_tests`运行结果：
```sh
$ ./tests/ringbuffer_tests
DEBUG tests/ringbuffer_tests.c:60: ----- RUNNING: ./tests/ringbuffer_tests
----
RUNNING: ./tests/ringbuffer_tests
DEBUG tests/ringbuffer_tests.c:53:
----- test_create
DEBUG tests/ringbuffer_tests.c:54:
----- test_read_write
DEBUG tests/ringbuffer_tests.c:55:
----- test_destroy
ALL TESTS PASSED
Tests run: 3
$
```
你应该测试至少三次来确保所有基本操作有效，并且看看在我完成之前你能测试到额外的多少东西。
## 如何改进
像往常一样，你应该为这个练习做防御性编程检查。我希望你这样做，是因为` liblcthw`的代码基本上没有做我教给你的防御型编程检查。我将它们留给你，便于你熟悉使用这些额外的检查来改进代码。
例如，这个环形缓冲区并没有过多检查每次访问是否实际上都在缓冲区内。
如果你阅读[环形缓冲区的维基百科页面](http://en.wikipedia.org/wiki/Ring_buffer)，你会看到“优化的POSIX实现”，它使用POSIX特定的调用来创建一块无限的区域。研究并且在附加题中尝试实现它。
## 附加题
+ 创建`RingBuffer`的替代版本，使用POSIX的技巧并为其执行单元测试。
+ 为二者添加一个性能对比测试，通过带有随机数据和随机读写操作的模糊测试来比较两个版本。确保你你对每个版本进行了相同的操作，便于你在操作之间比较二者。
+ 使用`callgrind` 和 `cachegrind`比较二者的性能。
- 笨办法学C 中文版
- 前言
- 导言：C的笛卡尔之梦
- 练习0：准备
- 练习1：启用编译器
- 练习2：用Make来代替Python
- 练习3：格式化输出
- 练习4：Valgrind 介绍
- 练习5：一个C程序的结构
- 练习6：变量类型
- 练习7：更多变量和一些算术
- 练习8：大小和数组
- 练习9：数组和字符串
- 练习10：字符串数组和循环
- 练习11：While循环和布尔表达式
- 练习12：If，Else If，Else
- 练习13：Switch语句
- 练习14：编写并使用函数
- 练习15：指针，可怕的指针
- 练习16：结构体和指向它们的指针
- 练习17：堆和栈的内存分配
- 练习18：函数指针
- 练习19：一个简单的对象系统
- 练习20：Zed的强大的调试宏
- 练习21：高级数据类型和控制结构
- 练习22：栈、作用域和全局
- 练习23：认识达夫设备
- 练习24：输入输出和文件
- 练习25：变参函数
- 练习26：编写第一个真正的程序
- 练习27：创造性和防御性编程
- 练习28：Makefile 进阶
- 练习29：库和链接
- 练习30：自动化测试
- 练习31：代码调试
- 练习32：双向链表
- 练习33：链表算法
- 练习34：动态数组
- 练习35：排序和搜索
- 练习36：更安全的字符串
- 练习37：哈希表
- 练习38：哈希算法
- 练习39：字符串算法
- 练习40：二叉搜索树
- 练习41：将 Cachegrind 和 Callgrind 用于性能调优
- 练习42：栈和队列
- 练习43：一个简单的统计引擎
- 练习44：环形缓冲区
- 练习45：一个简单的TCP/IP客户端
- 练习46：三叉搜索树
- 练习47：一个快速的URL路由
- 后记：“解构 K&R C” 已死
- 捐赠名单