A Weekly Rust🦀 Pill #1

A Weekly Rust🦀 Pill is a post series where on a weekly base, I share some implementations of the most popular algorithms and data structures to share my learnings on Rust 🦀.

Circular Buffer

A circular buffer, or a circular queue or ring buffer, is a data structure that manages and stores a fixed-size collection of items circularly and efficiently. It is a type of queue where the elements are stored in a circular arrangement, and the buffer wraps around when it reaches its maximum capacity. This design allows for constant-time access and efficient memory utilisation compared to traditional linear buffers.
The circular buffer has two primary components:

1. Buffer Array: An array or a fixed-size memory block holds the elements of the circular buffer. The elements are stored in a linear sequence, but the logical order of the items forms a circular loop.

2. Front and Rear Pointers: The circular buffer maintains a front (or head) pointer and a rear (or tail) pointer. These pointers indicate the current position of the buffer's earliest (front) and the latest (rear) elements.

Implementation

Here our Rust implementations using generic type:

use std::string;

#[derive(Debug)]
struct CircularBuffer<T> {
    capacity: usize,
    buff: Vec<Option<T>>,
    wrt_ptr: usize,
    rd_ptr: usize,
}

impl<T: Clone> CircularBuffer<T> {
    pub fn new(size: usize) -> CircularBuffer<T> {
        CircularBuffer {
            capacity: size,
            buff: vec![None; size],
            wrt_ptr: 0,
            rd_ptr: 0,
        }
    }

    pub fn is_full(&self) -> bool {
        (self.wrt_ptr - self.rd_ptr) == self.capacity
    }

    pub fn len(&self) -> usize {
        if self.is_full() {
            return self.capacity;
        }

        if self.wrt_ptr > self.rd_ptr {
            self.wrt_ptr - self.rd_ptr
        } else if self.wrt_ptr == self.rd_ptr {
            0
        } else {
            self.capacity - self.rd_ptr + self.wrt_ptr
        }
    }

    pub fn push(&mut self, item: T) -> bool {
        if self.is_full() {
            return false;
        }

        self.buff[self.wrt_ptr] = Some(item);
        self.wrt_ptr = (self.wrt_ptr + 1) % self.capacity;

        return true;
    }

    pub fn pop(&mut self) -> Result<T, String> {
        match self.buff[self.rd_ptr].take() {
            Some(value) => {
                self.rd_ptr = (self.rd_ptr + 1) % self.capacity;
                Ok(value)
            }
            None => Err("EmptyBuffer".to_string()),
        }
    }
}

The structure contains four fields:

capacity: which is the size of our buffer

buff: which is a Vector of generic type T

wrt_ptr: is the pointer to the head of our buffer

rd_ptr: is the pointer to the tail of

To manage our circular buffer, we implement the following methods:
is_full(&self): that checks if our buffer has an empty memory slot
len(&self): which returns the actual buffer size
push(&self, T): which inserts a new element into our buffer at the position pointed by wrt_ptr
pop(&self): which gets the element pointed by rd_ptr

Enqueuing and dequeuing elements from the front and rear of the circular buffer are typically constant time operations, O(1), since the front and rear pointers directly indicate the following positions for insertion and removal.

This example code was written to learn and share knowledge on algorithms and Rust. For production-ready implementations of Circular Buffer, you can refer to the following:

• Module vec_deque
• Crate circbuf