一种不需要%的环形缓冲队列的实现

在做练习44的时候，在维基百科上面看到了一种不需要取模运算，而是利用异或、与实现的环形缓冲队列，比较有意思。

一般来说环形队列的写法都会疯狂取模%，比如判断环形队列是否队满，会写类似这样的代码：

cb->size-1 == ((cb->end - cb->beg + cb->size) % cb->size)

但是，取模运算%比较耗时，特别是对于Linux kernel这样的基础设施而言，所以Linux kernel采用了类似下面这样的实现：

// 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) {
    return cb->end == (cb->start ^ cb->size); // This inverts the most significant bit of start before comparison
}

int cbIsEmpty(CircularBuffer *cb) {
    return cb->end == cb->start;
}

int cbIncr(CircularBuffer *cb, int p) {
    return (p + 1) & (2 * cb->size - 1); // start and end pointers incrementation is done modulo 2*size
}

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

值得注意的是，其中这个环形队列的大小一定是2的幂次，这一点非常重要，是之后一切的前提。

可以看到，它是通过 头指针 异或 队列大小 == 尾指针 来判断队列是否已满，这里利用了异或是不进位二进制加法的性质，本该进位但没进位的那一位一定是队列大小为1的那一位（因为保证了队列大小一定是2的幂次，所以只有唯一一个1），因为没进位所以相当于原数加上队列长度再减去了队列大小的两倍，这里相当于做了一次对队列大小的两倍取模的操作，很巧妙。

至于为什么要取模队列长度*2，为什么指针的范围维护在[0,队列大小*2)，这是为了区分队满和队空的情况。如果指针范围为[0,队列大小)并且不保持一个存储单元为空的话，队满和队空都会导致头指针等于尾指针。一般的方案是保持一个存储单元为空，队空就是头指针等于尾指针，而队满就是头指针距离尾指针=队列大小-1。这样比较方便，但是浪费了一个空间，另外一个方案是将整个队列镜像复制到对尾拼在一起，比如abc|abc这样，实际数据还是只有abc，但是指针的范围扩大到abcabc，此时队空就是头指针等于尾指针，而队满就是头指针距离尾指针=队列大小，没有浪费空间而且解决了区别队空、队尾的难题。

然后再来看cbInc，这是用于前移指针的函数，& (2 * cb->size - 1)的效果也相当于是对指针做了一次对队列大小的两倍取模的操作（所以其实可以将上面判断队满改写为((cb->beg + cb->size) & (2*cb->size-1)) == cb->end）。

对环形队列的写入和读取时，指针还要记得& (cb->size - 1)，相当于对队列长度取模，（为什么还要取模？因为指针虽然在abc|abc，但是实际数据还是只在abc中）。值得注意的是，当队满仍要写入时，直接让头指针向前，让新的数据覆盖队首即可。