How do I implement a circular list (ring buffer) in C?

Question

How do I implement a circular list that overwrites the oldest entry when it's full?

For a little background, I want to use a circular list within GWT; so using a 3rd party lib is not what I want.

Answer 1

Here is a simple template solution for a circular buffer (FIFO). It does leave one storage space empty, but I think this is a small penalty for the performance and simplicity. I included a simple stress-test.

#include <iostream>
#include <string>

using namespace std;

class E: public std::exception {

    const char *_msg;
    E(){}; //no default constructor

public:

    explicit E(const char *msg) throw(): _msg(msg) {};
    const char * what() const throw() {return(_msg);};

};

const int min_size = 2;
const int max_size = 1000;

template<typename T>
class Fifo{

    int _head;
    int _tail;
    int _size;

    T* _storage;

public:

    explicit Fifo(int size = min_size);
    ~Fifo(){ delete [] _storage;};

    bool is_full() const{
        return(((_head+1)%_size) == _tail);
    };
    bool is_empty() const{
        return(_head == _tail);
    };

    void add_item(const T& item);
    const T& get_item();

};

template<typename T>
Fifo<T>::Fifo(int size): _size(size){
    
    if (size < min_size) throw E("Cannot create Fifo less than 2\n");

    _head = _tail = 0;

    try{

        _storage = new T[_size];
    }
    catch (std::bad_alloc &ba)
    {
        char e_string[500];
        sprintf(e_string, "Cannot allocate memory (%s)\n", ba.what());
        throw E(e_string);
    }

    printf("Constructing Fifo of size %d\n", _size);

}

template <typename T>
void Fifo<T>::add_item(const T& item)
{
    if (this->is_full()) throw E("Fifo is full.\n");

    _storage[_head] = item;

    _head = (_head + 1)%_size;
}

template <typename T>
const T& Fifo<T>::get_item()
{
    if (this->is_empty()) throw E("Fifo is empty.\n");

    int temp = _tail; //save the current tail

    _tail = (_tail+1)%_size; //update tail

    return(_storage[temp]);
}

int main()
{
    Fifo<int> my_fifo(3);

    for (int i = 1, item; i < 50; i++)
    {
        my_fifo.add_item(i);
        my_fifo.add_item(i*10);
        item = my_fifo.get_item();
        printf("Item: %d\n", item);
        item = my_fifo.get_item();
        printf("Item: %d\n", item);
    }


    return 0;
}

Answer 2

Here is an elegant way to create dynamically increasing/decreasing circular queue using java.

I have commented most part of the code for easy & fast understanding. Hope it helps :)

    public class CircularQueueDemo {
    public static void main(String[] args) throws Exception {

        CircularQueue queue = new CircularQueue(2);
        /* dynamically increasing/decreasing circular queue */
        System.out.println("--dynamic circular queue--");
        queue.enQueue(1);
        queue.display();
        queue.enQueue(2);
        queue.display();
        queue.enQueue(3);
        queue.display();
        queue.enQueue(4);
        queue.display();
        queue.deQueue();
        queue.deQueue();
        queue.enQueue(5);
        queue.deQueue();    
        queue.display();

    }
}

class CircularQueue {
    private int[] queue;
    public int front;
    public int rear;
    private int capacity;

    public CircularQueue(int cap) {
        front = -1;
        rear = -1;
        capacity = cap;
        queue = new int[capacity];
    }

    public boolean isEmpty() {
        return (rear == -1);
    }

    public boolean isFull() {
        if ((front == 0 && rear == capacity - 1) || (front == rear + 1))
            return true;
        else
            return false;
    }

    public void enQueue(int data) { 
        if (isFull()) {            //if queue is full then expand it dynamically   
            reSize();                    
            enQueue(data);
        } else {                                 //else add the data to the queue
            if (rear == -1)                      //if queue is empty
                rear = front = 0;
            else if (rear == capacity)          //else if rear reached the end of array then place rear to start (circular array)
                rear = 0;
            else
                rear++;                         //else just incement the rear 
            queue[rear] = data;                 //add the data to rear position
        }
    }

    public void reSize() {
        int new_capacity = 2 * capacity;                  //create new array of double the prev size
        int[] new_array = new int[new_capacity];          

        int prev_size = getSize();                        //get prev no of elements present
        int i = 0;                                        //place index to starting of new array

        while (prev_size >= 0) {                          //while elements are present in prev queue
            if (i == 0) {                                 //if i==0 place the first element to the array
                new_array[i] = queue[front++];
            } else if (front == capacity) {               //else if front reached the end of array then place rear to start (circular array) 
                front = 0;
                new_array[i] = queue[front++];
            } else                                        //else just increment the array
                new_array[i] = queue[front++];
            prev_size--;                                  //keep decreasing no of element as you add the elements to the new array
            i++;                                          //increase the index of new array
        }
        front = 0;                                        //assign front to 0
        rear = i-1;                                       //assign rear to the last index of added element
        capacity=new_capacity;                            //assign the new capacity
        queue=new_array;                                  //now queue will point to new array (bigger circular array)
    }

    public int getSize() {
        return (capacity - front + rear) % capacity;                  //formula to get no of elements present in circular queue
    }

    public int deQueue() throws Exception {
        if (isEmpty())                                       //if queue is empty
            throw new Exception("Queue is empty");
        else {
            int item = queue[front];                        //get item from front
            if (front == rear)                              //if only one element
                front = rear = -1;
            else if (front == capacity)                     //front reached the end of array then place rear to start (circular array)
                front = 0;
            else
                front++;                                    //increment front by one
            decreaseSize();                                 //check if size of the queue can be reduced to half
            return item;                                    //return item from front
        }

    }

    public void decreaseSize(){                           //function to decrement size of circular array dynamically
        int prev_size = getSize();
        if(prev_size<capacity/2){                         //if size is less than half of the capacity
            int[] new_array=new int[capacity/2];          //create new array of half of its size
            int index=front;                              //get front index
            int i=0;                                      //place an index to starting of new array (half the size)
            while(prev_size>=0){                          //while no of elements are present in the queue
                if(i==0)                                  //if index==0 place the first element
                    new_array[i]=queue[front++];
                else if(front==capacity){                 //front reached the end of array then place rear to start (circular array)      
                    front=0;
                    new_array[i]=queue[front++];
                }
                else
                    new_array[i]=queue[front++];         //else just add the element present in index of front
                prev_size--;                             //decrease the no of elements after putting to new array 
                i++;                                     //increase the index of i
            }
            front=0;                                     //assign front to 0
            rear=i-1;                                    //assign rear to index of last element present in new array(queue)
            capacity=capacity/2;                         //assign new capacity (half the size of prev)
            queue=new_array;                             //now queue will point to new array (or new queue)
        }
    }

    public void display() {                           //function to display queue
        int size = getSize();
        int index = front;

        while (size >= 0) {
            if (isEmpty())
                System.out.println("Empty queue");
            else if (index == capacity)
                index = 0;
            System.out.print(queue[index++] + "=>");
            size--;
        }
        System.out.println("  Capacity: "+capacity);

    }

}

Output:

--dynamic circular queue--

1=> Capacity: 2

1=>2=> Capacity: 2

1=>2=>3=> Capacity: 4

1=>2=>3=>4=> Capacity: 4

4=>5=> Capacity: 2

Answer 3

I don't think queue is the best way to make a cache. You want to be your cache to be really fast! And doing a linear scan of your queue is not the way to go unless you want your cache to be really small or your memory is really limited.

Assuming that you don't want a very small cache or a slow cache, using a Linked List with a Hash Map of value to node in the linked list is a good way to go. You can always evict the head, and whenever an element is accessed, you can remove it and put it in the head of the list. For accessing you can directly get it or check if it's in the cache in O(1). Evicting an element is also O(1) and so is updating the list.

For an example, look at LinkedHashMap in java.

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

Answer 4

I am using this for my microcontroller. For code simplicity one byte will be unfilled. Aka size - 1 is the full capacity actually.

fifo_t* createFifoToHeap(size_t size)
{
    byte_t* buffer = (byte_t*)malloc(size);

    if (buffer == NULL)
        return NULL;

    fifo_t* fifo = (fifo_t*)malloc(sizeof(fifo_t));

    if (fifo == NULL)
    {
       free(buffer);
       return NULL;
    }

    fifo->buffer = buffer;
    fifo->head = 0;
    fifo->tail = 0;
    fifo->size = size;

    return fifo;
}

#define CHECK_FIFO_NULL(fifo) MAC_FUNC(if (fifo == NULL) return 0;)

size_t fifoPushByte(fifo_t* fifo, byte_t byte)
{
    CHECK_FIFO_NULL(fifo);

    if (fifoIsFull(fifo) == true)
       return 0;

    fifo->buffer[fifo->head] = byte;

    fifo->head++;
    if (fifo->head == fifo->size)
       fifo->head = 0;

    return 1;
}

size_t fifoPushBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
    CHECK_FIFO_NULL(fifo);

    for (uint32_t i = 0; i < count; i++)
    {
        if (fifoPushByte(fifo, bytes[i]) == 0)
            return i;
    }

    return count;
}

size_t fifoPopByte(fifo_t* fifo, byte_t* byte)
{
    CHECK_FIFO_NULL(fifo);

    if (fifoIsEmpty(fifo) == true)
        return 0;

    *byte = fifo->buffer[fifo->tail];

    fifo->tail++;
    if (fifo->tail == fifo->size)
        fifo->tail = 0;

    return 1;
}

size_t fifoPopBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
    CHECK_FIFO_NULL(fifo);

    for (uint32_t i = 0; i < count; i++)
    {
        if (fifoPopByte(fifo, bytes + i) == 0)
            return i;
    }

    return count;
}

bool fifoIsFull(fifo_t* fifo)
{
    if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
        return true;
    else
        return false;
}

bool fifoIsEmpty(fifo_t* fifo)
{
    if (fifo->head == fifo->tail)
        return true;
    else
        return false;
}

size_t fifoBytesFilled(fifo_t* fifo)
{
    if (fifo->head == fifo->tail)
        return 0;
    else if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
        return fifo->size;
    else if (fifo->head < fifo->tail)
        return (fifo->head) + (fifo->size - fifo->tail);
    else
        return fifo->head - fifo->tail; 
}

Answer 5

A very simple implementation, expressed in C. Implements a circular buffer style FIFO queue. Could be made more generic by creating a structure containing the queue size, queue data, and queue indexes (in and out), which would be passed in with the data to add or remove from the queue. These same routines could then handle several queues. Also note that this allows queues of any size, although speedups can be used if you use powers of 2 and customize the code further.

/* Very simple queue
 * These are FIFO queues which discard the new data when full.
 *
 * Queue is empty when in == out.
 * If in != out, then 
 *  - items are placed into in before incrementing in
 *  - items are removed from out before incrementing out
 * Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE;
 *
 * The queue will hold QUEUE_ELEMENTS number of items before the
 * calls to QueuePut fail.
 */

/* Queue structure */
#define QUEUE_ELEMENTS 100
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1)
int Queue[QUEUE_SIZE];
int QueueIn, QueueOut;

void QueueInit(void)
{
    QueueIn = QueueOut = 0;
}

int QueuePut(int new)
{
    if(QueueIn == (( QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE))
    {
        return -1; /* Queue Full*/
    }

    Queue[QueueIn] = new;

    QueueIn = (QueueIn + 1) % QUEUE_SIZE;

    return 0; // No errors
}

int QueueGet(int *old)
{
    if(QueueIn == QueueOut)
    {
        return -1; /* Queue Empty - nothing to get*/
    }

    *old = Queue[QueueOut];

    QueueOut = (QueueOut + 1) % QUEUE_SIZE;

    return 0; // No errors
}

Answer 6

If you want a fixed length circular list. You can use a (dynamic) array. Use two variables for houskeeping. One for the position of the next element, one to count the number of elements.

Put: put element on free place. move the position (modulo length). Add 1 to the count unless count equals the lengtht of the list. Get: only if count>0. move the position to the left (modulo length). Decrement the count.

Answer 7

Use an array and keep a variable P with the first available position.

Increase P every time you add a new element.

To know the equivalent index of P in your array do (P % n) where n is the size of your array.

Answer 8

Use a linked list. Maintain separate pointers for the head and tail. Pop from the head of the list, push onto the tail. If you want it circular, just make sure the new tail always points to the head.

I can understand why you might want to implement a FIFO using a linked list, but why make it a circular list?