練習44：環形緩沖區 · 笨辦法學C

# 練習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`比較二者的性能。