练习44：环形缓冲区

原文：Exercise 44: Ring Buffer

译者：飞龙

环形缓冲区在处理异步IO时非常实用。它们可以在一端接收随机长度和区间的数据，在另一端以相同长度和区间提供密致的数据块。它们是Queue数据结构的变体，但是它针对于字节块而不是一系列指针。这个练习中我打算向你展示RingBuffer的代码，并且之后你需要对它执行完整的单元测试。

  1. #ifndef _lcthw_RingBuffer_h
  2. #define _lcthw_RingBuffer_h
  4. #include <lcthw/bstrlib.h>
  6. typedef struct {
  7.     char *buffer;
  8.     int length;
  9.     int start;
  10.     int end;
  11. } RingBuffer;
  13. RingBuffer *RingBuffer_create(int length);
  15. void RingBuffer_destroy(RingBuffer *buffer);
  17. int RingBuffer_read(RingBuffer *buffer, char *target, int amount);
  19. int RingBuffer_write(RingBuffer *buffer, char *data, int length);
  21. int RingBuffer_empty(RingBuffer *buffer);
  23. int RingBuffer_full(RingBuffer *buffer);
  25. int RingBuffer_available_data(RingBuffer *buffer);
  27. int RingBuffer_available_space(RingBuffer *buffer);
  29. bstring RingBuffer_gets(RingBuffer *buffer, int amount);
  31. #define RingBuffer_available_data(B) (((B)->end + 1) % (B)->length - (B)->start - 1)
  33. #define RingBuffer_available_space(B) ((B)->length - (B)->end - 1)
  35. #define RingBuffer_full(B) (RingBuffer_available_data((B)) - (B)->length == 0)
  37. #define RingBuffer_empty(B) (RingBuffer_available_data((B)) == 0)
  39. #define RingBuffer_puts(B, D) RingBuffer_write((B), bdata((D)), blength((D)))
  41. #define RingBuffer_get_all(B) RingBuffer_gets((B), RingBuffer_available_data((B)))
  43. #define RingBuffer_starts_at(B) ((B)->buffer + (B)->start)
  45. #define RingBuffer_ends_at(B) ((B)->buffer + (B)->end)
  47. #define RingBuffer_commit_read(B, A) ((B)->start = ((B)->start + (A)) % (B)->length)
  49. #define RingBuffer_commit_write(B, A) ((B)->end = ((B)->end + (A)) % (B)->length)
  51. #endif

观察这个数据结构，你会看到它含有buffer、start 和 end。RingBuffer的所做的事情只是在buffer中移动start和end，所以当数据到达缓冲区末尾时还可以继续“循环”。这样就会给人一种在固定空间内无限读取的“幻觉”。接下来我创建了一些宏来基于它执行各种计算。

下面是它的实现，它是对工作原理更好的解释：

  1. #undef NDEBUG
  2. #include <assert.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <lcthw/dbg.h>
  7. #include <lcthw/ringbuffer.h>
  9. RingBuffer *RingBuffer_create(int length)
  10. {
  11.     RingBuffer *buffer = calloc(1, sizeof(RingBuffer));
  12.     buffer->length  = length + 1;
  13.     buffer->start = 0;
  14.     buffer->end = 0;
  15.     buffer->buffer = calloc(buffer->length, 1);
  17.     return buffer;
  18. }
  20. void RingBuffer_destroy(RingBuffer *buffer)
  21. {
  22.     if(buffer) {
  23.         free(buffer->buffer);
  24.         free(buffer);
  25.     }
  26. }
  28. int RingBuffer_write(RingBuffer *buffer, char *data, int length)
  29. {
  30.     if(RingBuffer_available_data(buffer) == 0) {
  31.         buffer->start = buffer->end = 0;
  32.     }
  34.     check(length <= RingBuffer_available_space(buffer),
  35.             "Not enough space: %d request, %d available",
  36.             RingBuffer_available_data(buffer), length);
  38.     void *result = memcpy(RingBuffer_ends_at(buffer), data, length);
  39.     check(result != NULL, "Failed to write data into buffer.");
  41.     RingBuffer_commit_write(buffer, length);
  43.     return length;
  44. error:
  45.     return -1;
  46. }
  48. int RingBuffer_read(RingBuffer *buffer, char *target, int amount)
  49. {
  50.     check_debug(amount <= RingBuffer_available_data(buffer),
  51.             "Not enough in the buffer: has %d, needs %d",
  52.             RingBuffer_available_data(buffer), amount);
  54.     void *result = memcpy(target, RingBuffer_starts_at(buffer), amount);
  55.     check(result != NULL, "Failed to write buffer into data.");
  57.     RingBuffer_commit_read(buffer, amount);
  59.     if(buffer->end == buffer->start) {
  60.         buffer->start = buffer->end = 0;
  61.     }
  63.     return amount;
  64. error:
  65.     return -1;
  66. }
  68. bstring RingBuffer_gets(RingBuffer *buffer, int amount)
  69. {
  70.     check(amount > 0, "Need more than 0 for gets, you gave: %d ", amount);
  71.     check_debug(amount <= RingBuffer_available_data(buffer),
  72.             "Not enough in the buffer.");
  74.     bstring result = blk2bstr(RingBuffer_starts_at(buffer), amount);
  75.     check(result != NULL, "Failed to create gets result.");
  76.     check(blength(result) == amount, "Wrong result length.");
  78.     RingBuffer_commit_read(buffer, amount);
  79.     assert(RingBuffer_available_data(buffer) >= 0 && "Error in read commit.");
  81.     return result;
  82. error:
  83.     return NULL;
  84. }

这些就是一个基本的RingBuffer实现的全部了。你可以从中读取和写入数据，获得它的大小和容量。也有一些缓冲区使用OS中的技巧来创建虚拟的无限存储，但它们不可移植。

由于我的RingBuffer处理读取和写入内存块，我要保证任何end == start出现的时候我都要将它们重置为0，使它们从退回缓冲区头部。在维基百科上的版本中，它并不可以写入数据块，所以只能移动end和start来转圈。为了更好地处理数据块，你需要在数据为空时移动到内部缓冲区的开头。

单元测试

对于你的单元测试，你需要测试尽可能多的情况。最简单的方法就是预构造不同的RingBuffer结构，之后手动检查函数和算数是否有效。例如，你可以构造end在缓冲区末尾的右边，而start在缓冲区范围内的RingBuffer，来看看它是否执行成功。

你会看到什么

下面是我的ringbuffer_tests运行结果：

  1. $ ./tests/ringbuffer_tests
  2. DEBUG tests/ringbuffer_tests.c:60: ----- RUNNING: ./tests/ringbuffer_tests
  3. ----
  4. RUNNING: ./tests/ringbuffer_tests
  5. DEBUG tests/ringbuffer_tests.c:53:
  6. ----- test_create
  7. DEBUG tests/ringbuffer_tests.c:54:
  8. ----- test_read_write
  9. DEBUG tests/ringbuffer_tests.c:55:
  10. ----- test_destroy
  11. ALL TESTS PASSED
  12. Tests run: 3
  13. $

你应该测试至少三次来确保所有基本操作有效，并且看看在我完成之前你能测试到额外的多少东西。

如何改进

像往常一样，你应该为这个练习做防御性编程检查。我希望你这样做，是因为liblcthw的代码基本上没有做我教给你的防御型编程检查。我将它们留给你，便于你熟悉使用这些额外的检查来改进代码。

例如，这个环形缓冲区并没有过多检查每次访问是否实际上都在缓冲区内。

如果你阅读环形缓冲区的维基百科页面，你会看到“优化的POSIX实现”，它使用POSIX特定的调用来创建一块无限的区域。研究并且在附加题中尝试实现它。

附加题

  • 创建RingBuffer的替代版本，使用POSIX的技巧并为其执行单元测试。
  • 为二者添加一个性能对比测试，通过带有随机数据和随机读写操作的模糊测试来比较两个版本。确保你你对每个版本进行了相同的操作，便于你在操作之间比较二者。
  • 使用callgrind 和 cachegrind比较二者的性能。