cdata-structuresiterationcircular-bufferbranchless

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


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 :)


Solution

  • 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:

    1. Removed the -1 subtraction from prevOffset. Renamed that variable to listIdx since it is no longer "previous".
    2. Included the -1 subtraction in sizeCorrectedPrevOffset (also added sizeWithGuard so we stay within bounds).

    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:

    • listIdx = (20 + 37 - 20) % 27 = 0: it correctly realizes its list index is 0 (the head);
    • sizeCorrectedPrevOffset = (0 + 26 - 1) % 26 = 25: the new list index should be 25 (the tail);
    • returns (20 + 25) % 37 = 8: the buffer index of the tail element

    In contrast, your code does:

    • prevOffset = (20 + 37 - 1 - 20) % 37 = 36 % 37 = 36 and it goes off-track from here.