Ring buffer

Sometime tech interviewers asked about implementing known concept. Like RingBuffer.
Lets have short definition of that:

Technopedia says

https://www.techopedia.com/definition/18301/ring-buffer

A ring buffer is a data structure that is treated as circular although it its implementation is linear. A circular buffer is typically used as a data queue. A circular buffer is a popular way to implement a data stream because the code can be compact.
A ring buffer is also known as a circular buffer, circular queue or cyclic buffer.

A ring buffer is a common implementation of a queue. It is popular because circular queues are easy to implement. While a ring buffer is represented as a circle, in the underlying code, a ring buffer is linear. A ring buffer exists as a fixed-length array with two pointers: one that represents the head of a queue, and another that represents the tail. In a queue, elements are added to the tail of the queue in a “FIFO” (first in-first out) fashion. The first elements of the queue are removed from the head in the order they were added. When the head pointer gets to the end of the array, it wraps around to the first element in the array. Any data in the buffer is overwritten. The head of the queue is different from the first element in the actual array and both pointers move as elements are added and removed.
One disadvantage of a ring buffer is its fixed size. For queues where elements need to be added and removed in the middle, not just at the start and end of a buffer, an implementation as a linked list is the preferred approach.

Naive interface

Lets create different imlementations, so for tests we will use this interface. It is as simple as is - put and get, parametrised
with any type, I plan to use String, eg.
package algos;

interface RingBuffer<T> {
int DEFAULT_CAPACITY = 100;

void put(T item);

T get();
}

Testing it with such ring buffer client

I would write couple stupid runnables for checking - one will put values into RingBuffer, another will get value from that RingBuffer.
And two threads for writing, two threads for getting items.

package algos;

public class Client {
public static void main(String... a) throws Exception {
int capacity = 3;
new Client().runTest(new RingBufferArray<>(String.class, capacity));
new Client().runTest(new RingBufferLinked<>(capacity));
}

private void runTest(RingBuffer<String> ringBuffer) throws Exception {
Runnable writer = () -> {
for (int i = 0; i < 5; i++) {
ringBuffer.put(Thread.currentThread().getName() + "-" + i);
System.out.println("/put " + ringBuffer);
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Runnable reader = () -> {
for (int i = 0; i < 5; i++) {
String s = ringBuffer.get();
System.out.println("/get " + s + " / " + ringBuffer);
try {
Thread.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};

Thread writer1 = new Thread(writer, "writer-1");
Thread reader1 = new Thread(reader, "reader-1");
Thread writer2 = new Thread(writer, "writer-2");
Thread reader2 = new Thread(reader, "reader-2");

writer1.start();
reader1.start();
writer2.start();
reader2.start();

writer1.join();
reader1.join();
writer2.join();
reader2.join();
}
}

Implementation in a way of Linked List

Linked list style seems more organic way, since we could only handle references, taking into accound just two things -
keeping the size and using locks for thread safety.
Below code is quite straightforward, so no need to comment generally.

package algos;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class RingBufferLinked<T> implements RingBuffer<T> {

private int size, capacity;
private Node head = null, tail = null;

private final ReadWriteLock lock = new ReentrantReadWriteLock();
private final Lock readLock = lock.readLock();
private final Lock writeLock = lock.writeLock();

RingBufferLinked() {
this(DEFAULT_CAPACITY);
}

RingBufferLinked(int capacity) {
this.capacity = capacity;
}

@Override
public void put(T item) {
writeLock.lock();
try {
Node oldTail = null;
if (tail != null) {
oldTail = tail;
}
tail = new Node(item);
if (oldTail != null) {
oldTail.next = tail;
}
if (head == null) {
head = tail;
}
if (size < capacity) {
size++;
} else {
head = head.next;
}
} finally {
writeLock.unlock();
}
}

@Override
public T get() {
writeLock.lock();
try {
if (size == 0) {
return null;
}
T item = head.item;
size--;
head = head.next;
return item;
} finally {
writeLock.unlock();
}
}

@Override
public String toString() {
readLock.lock();
try {
StringBuilder sb = new StringBuilder("[ ");
Node node = head;
while (node != null) {
sb.append(node).append(" ");
node = node.next;
}
sb.append("] s=").append(size);
return sb.toString();
} finally {
readLock.unlock();
}
}

private class Node {
T item;
Node next;

Node(T item) {
this.item = item;
}

@Override
public String toString() {
return item.toString();
}
}
}

Testing linked way

One of possible outputs. Get always gets first item, the head of RingBuffer, put always puts item at the end of buffer.

/put [ writer-1-0 ] s=1
/get writer-1-0 / [ ] s=0
/put [ writer-2-0 ] s=1
/put [ writer-2-0 writer-2-1 ] s=2
/get writer-2-0 / [ writer-2-1 ] s=1
/put [ writer-2-1 writer-2-2 ] s=2
/get writer-2-1 / [ writer-2-2 ] s=1
/get writer-2-2 / [ ] s=0
/put [ writer-1-1 ] s=1
/put [ writer-1-1 writer-2-3 ] s=2
/put [ writer-1-1 writer-2-3 writer-1-2 ] s=3
/get writer-2-3 / [ writer-1-2 ] s=1
/get writer-1-1 / [ writer-1-2 ] s=1
/put [ writer-1-2 writer-2-4 ] s=2
/put [ writer-1-2 writer-2-4 writer-1-3 ] s=3
/get writer-1-2 / [ writer-2-4 writer-1-3 ] s=2
/get writer-2-4 / [ writer-1-3 ] s=1
/put [ writer-1-3 writer-1-4 ] s=2
/get writer-1-3 / [ writer-1-4 ] s=1
/get writer-1-4 / [ ] s=0

Implementation in a way of Array

Array way is using array buffer with two "pointers" to head and tail.
Get method is simple - if size is zero, then return null;
otherwise get element from buffer at head index and increase it and align to size.
then decrease size, since one less element now.

Put is a bit trikier in terms of indicies.

package algos;

import java.lang.reflect.Array;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class RingBufferArray<T> implements RingBuffer<T> {

private int head, tail, size, capacity;
private T[] buffer;
private final ReadWriteLock lock = new ReentrantReadWriteLock();
private final Lock readLock = lock.readLock();
private final Lock writeLock = lock.writeLock();

RingBufferArray(Class<T> cls) {
this(cls, DEFAULT_CAPACITY);
}

RingBufferArray(Class<T> cls, int capacity) {
buffer = (T[]) Array.newInstance(cls, capacity);
this.capacity = capacity;
}

@Override
public void put(T item) {
writeLock.lock();
try {
boolean replaced = buffer[tail] != null;
buffer[tail++] = item;
if (tail == capacity) {
tail = 0;
if (replaced && head + 1 == capacity) {
head = 0;
}
}
if (0 < tail && tail > head && size == capacity) {
head = tail;
}
if (size < capacity) {
size++;
}
} finally {
writeLock.unlock();
}
}

@Override
public T get() {
writeLock.lock();
try {
if (size == 0) {
return null;
}
T item = buffer[head];
buffer[head] = null;
head++;
if (head == capacity) {
head = 0;
}
size--;
return item;
} finally {
writeLock.unlock();
}
}

@Override
public String toString() {
readLock.lock();
try {
StringBuilder sb = new StringBuilder("[ ");
for (T item : buffer) {
sb.append(item != null ? item : "_").append(" ");
}
sb.append("] s=").append(size)
.append(", h=").append(head)
.append(", t=").append(tail);
return sb.toString();
} finally {
readLock.unlock();
}
}
}

Testing array way

This output differs a bit from previous, because we have fixed size array. So empty places in buffer marked by underscores.
For better understanding whats going on - here are indices head (h) and tail (t) printed alongside with content and size.
This is more natural look, representing how pointers circularly shifted through array.

/put [ writer-1-0 _ _ ] s=1, h=0, t=1
/get writer-1-0 / [ _ _ _ ] s=0, h=1, t=1 // here array is empty, but indices points to the middle
/put [ _ writer-2-0 _ ] s=1, h=1, t=2
/get writer-2-0 / [ _ _ _ ] s=0, h=2, t=2 // here indices points to the end
/put [ _ _ writer-1-1 ] s=1, h=2, t=0
/put [ writer-2-1 _ writer-1-1 ] s=2, h=2, t=1 // here head is "after" tail
/get writer-1-1 / [ writer-2-1 _ _ ] s=1, h=0, t=1
/put [ writer-2-1 writer-1-2 _ ] s=2, h=0, t=2
/put [ _ writer-1-2 writer-2-2 ] s=2, h=1, t=0
/get writer-2-1 / [ _ writer-1-2 writer-2-2 ] s=2, h=1, t=0
/put [ writer-2-3 writer-1-2 writer-2-2 ] s=3, h=1, t=1
/put [ writer-2-3 writer-1-3 writer-2-2 ] s=3, h=2, t=2 // here second item was just overwritten, tail and head shifter later by array index
/get writer-2-2 / [ writer-2-3 writer-1-3 _ ] s=2, h=0, t=2
/put [ writer-2-3 writer-1-3 writer-2-4 ] s=3, h=0, t=0
/get writer-2-3 / [ _ writer-1-3 writer-2-4 ] s=2, h=1, t=0
/put [ writer-1-4 writer-1-3 writer-2-4 ] s=3, h=1, t=1
/get writer-1-3 / [ writer-1-4 _ writer-2-4 ] s=2, h=2, t=1
/get writer-2-4 / [ writer-1-4 _ _ ] s=1, h=0, t=1
/get writer-1-4 / [ _ _ _ ] s=0, h=1, t=1
/get null / [ _ _ _ ] s=0, h=1, t=1

Popular Posts