Ring buffer — counter pointers and mirror indexing

Contents

  1. 1. Counter-based implementation
  2. 2. Mirror index implementation

A ring buffer (circular queue) joins head and tail: read/write cursors advance around a fixed slice instead of shifting elements on every dequeue.

The payoff: after a dequeue you do not slide the rest of the queue forward; the next enqueue overwrites the freed slot.

Below is a common pattern—separate read/write counters—with a diagram-friendly walkthrough. Code is adapted from chanx ringbuffer.

Counter-based implementation

Skim the code first; a picture afterward makes the flow obvious.

Data layout:

1
2
3
4
5
6
7
8
type T interface{}
type RingBuffer struct {
buf []T // backing store
initialSize int // initial capacity
size int // current capacity
r int // read cursor
w int // write cursor
}

Reads:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Empty when read and write cursors meet
func (r *RingBuffer) IsEmpty() bool {
return r.r == r.w
}

func (r *RingBuffer) Read() (T, error) {
if r.IsEmpty() {
return nil, ErrIsEmpty
}

// Take slot at read cursor, then advance
v := r.buf[r.r]
r.r++
// Wrap to zero after one lap
if r.r == r.size {
r.r = 0
}

return v, nil
}

Writes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (r *RingBuffer) Write(v T) {
// Store at write cursor and advance
r.buf[r.w] = v
r.w++
// Wrap to zero after one lap
if r.w == r.size {
r.w = 0
}

// After write, write cursor catches read cursor => full
if r.w == r.r {
// Grow in place
r.grow()
}
}

Growth:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (r *RingBuffer) grow() {
var size int
if r.size < 1024 {
// Double
size = r.size * 2
} else {
// Grow by 25%
size = r.size + r.size/4
}

buf := make([]T, size)

// Copy unread data after read cursor
copy(buf[0:], r.buf[r.r:])
// Copy unread data before read cursor
copy(buf[r.size-r.r:], r.buf[0:r.r])

// Read cursor at front after compacting
r.r = 0
// Write cursor at old length
r.w = r.size
r.size = size
r.buf = buf
}

The figure below walks through a concrete example:

Ring buffer read/write cursors advancing around the slice

Another classic approach uses mirror index bits instead of growing.

Mirror index implementation

If the buffer length is n, logical indices are 0…n−1; indices n…2n−1 mirror that space. Read and write pointers live in 0…2n−1: the low half is the real buffer, the high half is the mirror. When a pointer reaches ≥2n, wrap with ptr − 2n. One bit records whether the pointer is in the mirror region.
From Wikipedia — circular buffer (mirror solution)

Counters may lap the buffer twice (up to 2n−1). “Full” used to mean r == w after wrap-to-zero; with mirroring, full is w == r + n before resetting.

Illustration:

Mirror-index circular buffer full and empty states

When capacity is a power of two, a bitwise test checks whether the gap is exactly n:

1
2
3
4
5
func (r *RingBuffer) IsFull() bool {
// r.r > size: r.r-size
// r.r < size: r.r+size
return (r.r ^ r.size) == r.w
}

Index and advance can use masks instead of %:

1
2
3
4
5
6
7
// Index
v := r.buf[r.r&(r.size-1)]
r.buf[r.w&(r.size-1)] = v
// Advance
func (r *RingBuffer) incrCursor(p *int) {
*p = (*p + 1) & (2*r.size - 1)
}

Full code: ringbuffer-mirror.

Questions? Leave a comment below or email: newbvirgil@gmail.com