练习44：环形缓冲区

原文：Exercise 44: Ring Buffer

译者：飞龙

环形缓冲区在处理异步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比较二者的性能。