I have a following problem and despite many approached all fail to satisfy my needs:
Having a circular buffer where index is size_t
and underlying buffer may be anything I please, I need to iterate both forward and backwards like so:
from head to tail and from tail to head (in other words I need to be able to iterate over all cells in this buffer).
I have following functions:
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;
}
Small description:
sizeWithGuard
is size plus tail 'guard' element (tail is empty).
And while next works fine, previous always fails to iterate from head to tail when idx == head (it always results in capacity - 1
). I am looking for a clue on how to change this algorithm to work always.
What is crucial for me is that index needs to be of size_t
type and there are no branches in the code (otherwise this problem would be non-existent :)
The trick is that there are two types of indexes: list indexes, ranging from 0 to size - 1 (or, in your case, 0 to size with the tail guard) and buffer indexes ranging from 0 to capacity - 1. I propose changing the code a bit to clarify this.
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;
}
So what I changed was:
What is the difference? Here is an example:
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]
My version of the code does:
In contrast, your code does: