Introduction

This article is part of the data structure category

A circular buffer (also known as ring buffers, circular queue, or cyclic buffer) is a data structure that uses a fixed-size buffer to store data.

The buffer is connected end-to-end, which usually leads to visualizing this data structure as a circle.

This detail makes the circular buffer a static data structure, which means its size cannot be adjusted once created.

A circular buffer is efficient when the method used to organize the manipulation of a data structure is a FIFO (first-in, first-out); a well-known implementation of a circular queue is a buffered channel in Go:

ch := make(chan int, 5).

Implementation

The implementation of the circular buffer in this article is a type named Circular, which has five fields:

• r: is the read-position in the buffer
• w: is the write-position in the buffer
• buf: is a fixed-size array (In Go we can use a fixed-size slice) used to store the elements
• isFull: to keep track of the buffer’s status without analyzing it at runtime.
• mutex: to ensure that the doubly is thread-safe.

In Go, an implementation may look like this:

type Circular struct {
	mu     sync.Mutex
	w      uint
	r      uint
	buf    []interface{}
	isFull bool
}

func New(size uint) (*Circular, error) {
	// if size is 0 the buffer can't exist
	if size == 0 {
		return nil, errors.New("buffer: could not use 0 size for circular buffer")
	}

	return &Circular{
		buf: make([]interface{}, size),
	}, nil
}

In this implementation, thanks to an empty interface contract, buf allows storing any data type as a value.

A circular buffer mainly offers two behaviors; write and read. The position from where to start writing/reading in a circular buffer is not relevant as long as the starting positions of both are the same.

Let us go through these behaviors and see how those operations work on a circular buffer.

Write

Writing an element into a buffer is a cheap operation, thanks to the slice (dynamic array) used as a buffer, and the read/write positions kept in sync.

Some data needs to be written in an empty circular buffer with a max capacity of eight elements.

To write an element in the buffer, move the write-position to the next available one and store the element at that index.

In the same way as the previous write, it is possible to write data as long as there is space in the buffer.

When the buffer is full, and a write operation occurs, an error is returned. Some circular buffer implementation may override the data, but this is not the case.

Since there is no loop needed to execute a write on the buffer, the time complexity to execute is a constant O(1).

An implementation in Go of a Write method for the Circular type may look like this:

func (c *Circular) Write(v interface{}) error {
	// lock while the operation is ongoing
	c.mu.Lock()
	defer c.mu.Unlock()

	// if the buffer is full then return a buffer full error
	if c.isFull {
		return errors.New("buffer: buffer full")
	}

	// take the next write position in the buffer
	w := c.next(c.w)

	// write the element and update the write position of the buffer
	c.buf[w], c.w = v, w

	// if the write position reached the read one, mark the buffer as full
	if c.w == c.r {
		c.isFull = true
	}

	return nil
}
// ...
func (c *Circular) next(i uint) uint {
	return (i + 1) % uint(len(c.data))
}

Read

Reading an element from a buffer is a cheap operation for the same reason as the writing method.

Some data needs to be read from a buffer storing seven elements with a capacity of eight.

Reading an element from the buffer moves the read-position to the next available one. Once read, the element can be removed.

Similarly, as in the previous read operation, it is possible to read data as long as there are elements in the buffer.

When the buffer is empty, and a read operation occurs, nothing will be returned and the read-position will not move ahead. Some circular buffer implementation may return an error, but this is not the case.

Since the number of elements in the buf does not influence the operation, this operation's time complexity is an O(1).

func (c *Circular) Read() (interface{}, bool) {
	// lock while the operation is ongoing
	c.mu.Lock()
	defer c.mu.Unlock()

	// if the buffer is empty
	// return false to notify that the operation did not read any element in the buffer
	if c.w == c.r && !c.isFull {
		return nil, false
	}

	// take the next read position in the buffer
	r := c.next(c.r)

	// read the element in the buffer
	v := c.buf[r]

	// update the read position of the buffer and clean up the element from the buffer
	c.r, c.buf[r] = r, nil

	// mark the buffer as not null since it read some data
	c.isFull = false

	// return the found element
	// and true to notify that the operation did read some element from the buffer
	return v, true
}
// ...
func (c *Circular) next(i uint) uint {
	// return the next position of the buffer using `i` as starting point
	return (i + 1) % uint(len(c.buf))
}

Conclusion

A circular buffer is an extremely efficient data structure when the max size is known.

It is also often used to implement a queue data structure, and compared to other possible implementations of queues, it is remarkably memory efficient but with the downside of being unable to increase the buffer size.

There is one more behavior that can be part of a circular buffer implementation, checking if it is full, but since it is a one-line method returning the value of the isFull field of the struct, it has been omitted from this article.

To end the article, here is a recap of the time complexity of the operations a circular buffer can support: