练习44：环形缓冲区
译者：飞龙
环形缓冲区在处理异步IO时非常实用。它们可以在一端接收随机长度和区间的数据，在另一端以相同长度和区间提供密致的数据块。它们是Queue数据结构的变体，但是它针对于字节块而不是一系列指针。这个练习中我打算向你展示RingBuffer的代码，并且之后你需要对它执行完整的单元测试。
#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，所以当数据到达缓冲区末尾时还可以继续“循环”。这样就会给人一种在固定空间内无限读取的“幻觉”。接下来我创建了一些宏来基于它执行各种计算。
下面是它的实现，它是对工作原理更好的解释：
#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运行结果：
$ ./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的代码基本上没有做我教给你的防御型编程检查。我将它们留给你，便于你熟悉使用这些额外的检查来改进代码。
例如，这个环形缓冲区并没有过多检查每次访问是否实际上都在缓冲区内。
如果你阅读环形缓冲区的维基百科页面，你会看到“优化的POSIX实现”，它使用POSIX特定的调用来创建一块无限的区域。研究并且在附加题中尝试实现它。
附加题
- 创建
RingBuffer的替代版本，使用POSIX的技巧并为其执行单元测试。 - 为二者添加一个性能对比测试，通过带有随机数据和随机读写操作的模糊测试来比较两个版本。确保你你对每个版本进行了相同的操作，便于你在操作之间比较二者。
- 使用
callgrind和cachegrind比较二者的性能。