圆形缓冲区(circular buffer),也称作圆形队列(circular queue),循环缓冲区(cyclic buffer),环形缓冲区(ring buffer),是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构,适合缓存数据流。
圆形缓冲区的一个有用特性是:当一个数据元素被用掉后,其余数据元素不需要移动其存储位置。相反,一个非圆形缓冲区(例如一个普通的队列)在用掉一个数据元素后,其余数据元素需要向前搬移。换句话说,圆形缓冲区适合实现先进先出缓冲区,而非圆形缓冲区适合后进先出缓冲区。
圆形缓冲区适合于事先明确了缓冲区的最大容量的情形。扩展一个圆形缓冲区的容量,需要搬移其中的数据。因此一个缓冲区如果需要经常调整其容量,用链表实现更为合适。
写操作覆盖圆形缓冲区中未被处理的数据在某些情况下是允许的。特别是在多媒体处理时。例如,音频的生产者可以覆盖掉声卡尚未来得及处理的音频数据。
一个圆形缓冲区最初为空并有预定的长度。例如,这是一个具有七个元素空间的圆形缓冲区,其中底部的单线与箭头表示“头尾相接”形成一个圆形地址空间:
假定1被写入缓冲区中部(对于圆形缓冲区来说,最初的写入位置在哪里是无关紧要的):
再写入2个元素,分别是2 & 3 — 被追加在1之后:
如果两个元素被处理,那么是缓冲区中最老的两个元素被移除。在本例中,1 & 2被移除,缓冲区中只剩下3:
如果缓冲区中有7个元素,则是满的:
如果缓冲区是满的,又要写入新的数据,一种策略是覆盖掉最老的数据。此例中,2个新数据— A & B — 写入,覆盖了3 & 4:
也可以采取其他策略,禁止覆盖缓冲区的数据,采取返回一个错误码或者抛出异常。
最终,如果从缓冲区中移除2个数据,不是3 & 4 而是 5 & 6 。因为 A & B 已经覆盖了3 & 4:
由于计算机内存是线性地址空间,因此圆形缓冲区需要特别的设计才可以从逻辑上实现。
一般的,圆形缓冲区需要4个指针:
读指针、写指针可以用整型值来表示。
下例为一个未满的缓冲区的读写指针:
下例为一个满的缓冲区的读写指针:
缓冲区是满、或是空,都有可能出现读指针与写指针指向同一位置:
有多种策略用于检测缓冲区是满、或是空.
缓冲区中总是有一个存储单元保持未使用状态。缓冲区最多存入个数据。如果读写指针指向同一位置,则缓冲区为空。如果写指针位于读指针的相邻后一个位置,则缓冲区为满。这种策略的优点是简单、粗暴;缺点是语义上实际可存数据量与缓冲区容量不一致,测试缓冲区是否满需要做取余数计算。
这种策略不使用显式的写指针,而是保持着缓冲区内存储的数据的计数。因此测试缓冲区是空是满非常简单;对性能影响可以忽略。缺点是读写操作都需要修改这个存储数据计数,对于多线程访问缓冲区需要并发控制。
缓冲区的长度如果是n,逻辑地址空间则为0至n-1;那么,规定n至2n-1为镜像逻辑地址空间。本策略规定读写指针的地址空间为0至2n-1,其中低半部分对应于常规的逻辑地址空间,高半部分对应于镜像逻辑地址空间。当指针值大于等于2n时,使其折返(wrapped)到ptr-2n。使用一位表示写指针或读指针是否进入了虚拟的镜像存储区:置位表示进入,不置位表示没进入还在基本存储区。
在读写指针的值相同情况下,如果二者的指示位相同,说明缓冲区为空;如果二者的指示位不同,说明缓冲区为满。这种方法优点是测试缓冲区满/空很简单;不需要做取余数操作;读写线程可以分别设计专用算法策略,能实现精致的并发控制。 缺点是读写指针各需要额外的一位作为指示位。
如果缓冲区长度是2的幂,则本方法可以省略镜像指示位。如果读写指针的值相等,则缓冲区为空;如果读写指针相差n,则缓冲区为满,这可以用条件表达式(写指针 == (读指针 异或 缓冲区长度))来判断。
1 // This approach adds one bit to end and start pointers 2 // Circular buffer object 3 typedef struct { 4 int size; // maximum number of elements 5 int start; // index of oldest element 6 int end; // index at which to write new element 7 ElemType *elems; // vector of elements 8 } CircularBuffer; 9 10 void cbInit(CircularBuffer *cb, int size) {11 cb->size = size;12 cb->start = 0;13 cb->end = 0;14 cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));15 }16 17 void cbPrint(CircularBuffer *cb) {18 printf("size = 0x%x, start = %d, end = %d\n", cb->size, cb->start, cb->end);19 }20 21 int cbIsFull(CircularBuffer *cb) {22 return cb->end == (cb->start ^ cb->size); // This inverts the most significant bit of start before comparison23 }24 25 int cbIsEmpty(CircularBuffer *cb) {26 return cb->end == cb->start;27 }28 29 int cbIncr(CircularBuffer *cb, int p) {30 return (p + 1) & (2 * cb->size - 1); // start and end pointers incrementation is done modulo 2*size31 }32 33 void cbWrite(CircularBuffer *cb, ElemType *elem) {34 cb->elems = *elem;35 if (cbIsFull(cb)) // full, overwrite moves start pointer36 cb->start = cbIncr(cb, cb->start);37 cb->end = cbIncr(cb, cb->end);38 }39 40 void cbRead(CircularBuffer *cb, ElemType *elem) {41 *elem = cb->elems;42 cb->start = cbIncr(cb, cb->start);43 }