如何在没有分支的情况下在循环缓冲区中从头到尾迭代

Question

我有以下问题，尽管有很多方法都无法满足我的需求：有一个索引为 size_t 的循环缓冲区，底层缓冲区可能是我喜欢的任何东西，我需要像这样向前和向后迭代：从头到尾和从尾到头（换句话说，我需要能够遍历此缓冲区中的所有单元格）。

我有以下功能：

size_t prevIdxCircularBuffer(size_t head, size_t size, size_t capacity, size_t idx)
{
    const size_t sizeWithGuard = size + 1;
    const size_t prevOffset = (idx + capacity - 1 - head) % capacity;
    const size_t sizeCorrectedPrevOffset = prevOffset % sizeWithGuard;
    return (head + sizeCorrectedPrevOffset) % capacity;
}

size_t nextIdxCircularBuffer(size_t head, size_t size, size_t capacity, size_t idx)
{
    const size_t sizeWithGuard = size + 1;
    const size_t nextOffset = (idx + capacity + 1 - head) % capacity;
    const size_t sizeCorrectedNextOffset = nextOffset % sizeWithGuard;
    return (head + sizeCorrectedNextOffset) % capacity;
}

小说明： sizeWithGuard 是 size 加上 tail 'guard' 元素（tail 为空）。

虽然 next 工作正常，但当 idx == head 时，previous 总是无法从头到尾迭代（它总是导致 capacity - 1）。我正在寻找有关如何更改此算法以使其始终有效的线索。

对我来说很关键的是索引需要是size_t类型并且代码中没有分支（否则这个问题就不存在了:)

Answer 1

诀窍在于有两种类型的索引：list indexes，范围从 0 到 size - 1（或者，在你的情况，0 到 size with the tail guard) and buffer indexes range from 0 to capacity - 1. 我建议稍微修改一下代码来澄清这一点。

size_t prevIdxCircularBuffer(size_t head, size_t size, size_t capacity, size_t idx) {
    // at the beginning, idx is a buffer index
    const size_t sizeWithGuard = size + 1;

    // listIdx is the same index, just translated to a list index
    const size_t listIdx = (idx + capacity - head) % capacity;

    // sizeCorrectedPrevOffset is the list index of the previous element
    // (ranging from 0 to size inclusively)
    const size_t sizeCorrectedPrevOffset = (prevOffset + sizeWithGuard - 1) % sizeWithGuard;

    // finally convert sizeCorrectedPrevOffset back to a buffer index
    // and return it
    return (head + sizeCorrectedPrevOffset) % capacity;
}

所以我改变的是：

从 prevOffset 中删除了 -1 减法。将该变量重命名为 listIdx 因为它不再是 "previous".
在 sizeCorrectedPrevOffset 中包含 -1 减法（还添加了 sizeWithGuard，因此我们保持在范围内）。

有什么区别？这是一个例子：

        tail                               head=idx
+-----------+-----------------------------+---------------+
|           |                             |               |
+-----------+-----------------------------+---------------+
 0         8                               20           36

capacity=37
head=20
idx=20
size=25+1 guard element, spanning positions [20-36] and [0-8]

我的代码版本：

listIdx = (20 + 37 - 20) % 27 = 0：它正确地意识到它的列表索引是0（头部）；
sizeCorrectedPrevOffset = (0 + 26 - 1) % 26 = 25：新的列表索引应该是25（尾部）；
returns (20 + 25) % 37 = 8:尾元素的缓冲区索引

相比之下，您的代码：

prevOffset = (20 + 37 - 1 - 20) % 37 = 36 % 37 = 36 从这里开始偏离轨道。

如何在没有分支的情况下在循环缓冲区中从头到尾迭代

How to iterate from head to tail in circular buffer without branching

iteration

algorithm

circular-buffer

data-structures