环形缓冲区
用镜像指示法构造环形缓冲区,读写线程可以分别设计专用算法策略,能实现精致的并发控制。如果缓冲区长度是2的幂,则本方法可以省略镜像指示位。如果读写指针的值相等,则缓冲区为空;如果读写指针相差n,则缓冲区为满,
这可以用条件表达式(写指针 == (读指针 异或 缓冲区长度))来判断。(这个条件表达式不怎么懂,是怎么判断出来的)
// This approach adds one bit to end and start pointers
// Circular buffer object
typedef struct {
int size; // maximum number of elements
int start; // index of oldest element
int end; // index at which to write new element
ElemType *elems; // vector of elements
} CircularBuffer;
void cbInit(CircularBuffer *cb, int size) {
cb->size = size;
cb->start = 0;
cb->end = 0;
cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));
}
void cbPrint(CircularBuffer *cb) {
printf("size = 0x%x, start = %d, end = %d\n", cb->size, cb->start, cb->end);
}
int cbIsFull(CircularBuffer *cb) {
// This inverts the most significant bit of start before comparison
return cb->end == (cb->start ^ cb->size);
int cbIsEmpty(CircularBuffer *cb) {
return cb->end == cb->start;
}
int cbIncr(CircularBuffer *cb, int p) {
// start and end pointers incrementation is done modulo 2*size
return (p + 1) & (2 * cb->size - 1);
void cbWrite(CircularBuffer *cb, ElemType *elem) {
cb->elems[cb->end & (cb->size - 1)] = *elem;
if (cbIsFull(cb)) // full, overwrite moves start pointer
cb->start = cbIncr(cb, cb->start);
cb->end = cbIncr(cb, cb->end);
}
void cbRead(CircularBuffer *cb, ElemType *elem) {
*elem = cb->elems[cb->start & (cb->size - 1)];
cb->start = cbIncr(cb, cb->start);
}