練習(xí)44：環(huán)形緩沖區(qū)

原文：Exercise 44: Ring Buffer

譯者：飛龍

環(huán)形緩沖區(qū)在處理異步IO時(shí)非常實(shí)用。它們可以在一段接收隨機(jī)長度和區(qū)間的數(shù)據(jù)拂苹，在另一端以相同長度和區(qū)間提供密致的數(shù)據(jù)塊栅组。它們是Queue數(shù)據(jù)結(jié)構(gòu)的變體榆俺，但是它針對于字節(jié)塊而不是一系列指針谒臼。這個(gè)練習(xí)中我打算想你展示RingBuffer的代碼艇挨，并且之后你需要對它執(zhí)行完整的單元測試会烙。

#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

觀察這個(gè)數(shù)據(jù)結(jié)構(gòu)负懦，你會(huì)看到它含有buffer、start 和 end柏腻。RingBuffer的所做的事情只是在buffer中移動(dòng)start和end纸厉，所以當(dāng)數(shù)據(jù)到達(dá)緩沖區(qū)末尾時(shí)還可以繼續(xù)“循環(huán)”。這樣就會(huì)給人一種在固定空間內(nèi)無限讀取的“幻覺”五嫂。接下來我創(chuàng)建了一些宏來基于它執(zhí)行各種計(jì)算颗品。

下面是它的實(shí)現(xiàn)，它是對工作原理更好的解釋：

#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;
}

這些就是一個(gè)基本的RingBuffer實(shí)現(xiàn)的全部了沃缘。你可以從中讀取和寫入數(shù)據(jù)躯枢，獲得它的大小和容量。也有一些緩沖區(qū)使用OS中的技巧來創(chuàng)建虛擬的無限存儲(chǔ)槐臀，但它們不可移植闺金。

由于我的RingBuffer處理讀取和寫入內(nèi)存塊，我要保證任何end == start出現(xiàn)的時(shí)候我都要將它們重置為0峰档，使它們從退回緩沖區(qū)頭部败匹。在維基百科上的版本中寨昙，它并不可以寫入數(shù)據(jù)塊，所以只能移動(dòng)end和start來轉(zhuǎn)圈掀亩。為了更好地處理數(shù)據(jù)塊舔哪，你需要在數(shù)據(jù)為空時(shí)移動(dòng)到內(nèi)部緩沖區(qū)的開頭。

單元測試

對于你的單元測試槽棍，你需要測試盡可能多的情況捉蚤。最簡單的方法就是預(yù)構(gòu)造不同的RingBuffer結(jié)構(gòu)，之后手動(dòng)檢查函數(shù)和算數(shù)是否有效炼七。例如缆巧，你可以構(gòu)造end在緩沖區(qū)末尾的右邊，而start在緩沖區(qū)范圍內(nèi)的RingBuffer豌拙，來看看它是否執(zhí)行成功陕悬。

你會(huì)看到什么

下面是我的ringbuffer_tests運(yùn)行結(jié)果：

$ ./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
$

你應(yīng)該測試至少三次來確保所有基本操作有效，并且看看在我完成之前你能測試到額外的多少東西按傅。

如何改進(jìn)

像往常一樣捉超，你應(yīng)該為這個(gè)練習(xí)做防御性編程檢查。我希望你這樣做唯绍，是因?yàn)?code>liblcthw的代碼基本上沒有做我教給你的防御型編程檢查拼岳。我將它們留給你，便于你熟悉使用這些額外的檢查來改進(jìn)代碼况芒。

例如惜纸，這個(gè)環(huán)形緩沖區(qū)并沒有過多檢查每次訪問是否實(shí)際上都在緩沖區(qū)內(nèi)。

如果你閱讀環(huán)形緩沖區(qū)的維基百科頁面绝骚，你會(huì)看到“優(yōu)化的POSIX實(shí)現(xiàn)”耐版，它使用POSIX特定的調(diào)用來創(chuàng)建一塊無限的區(qū)域。研究并且在附加題中嘗試實(shí)現(xiàn)它皮壁。

附加題

• 創(chuàng)建RingBuffer的替代版本椭更，使用POSIX的技巧并為其執(zhí)行單元測試。
• 為二者添加一個(gè)性能對比測試蛾魄，通過帶有隨機(jī)數(shù)據(jù)和隨機(jī)讀寫操作的模糊測試來比較兩個(gè)版本虑瀑。確保你你對每個(gè)版本進(jìn)行了相同的操作，便于你在操作之間比較二者滴须。
• 使用callgrind 和 cachegrind比較二者的性能舌狗。