How to set size of circular queue

Question

I am trying to implement a generic circular buffer (queue) in C. Here is my code so far:

#include <stdio.h>
#include <stdlib.h>
#include <sys/queue.h>

CIRCLEQ_HEAD(circleq, entry) head;
struct circleq *headp;              /* Circular queue head. */
struct entry {
  CIRCLEQ_ENTRY(entry) entries;   /* Circular queue. */
  int number;
};

int main() 
{
  CIRCLEQ_INIT(&head); 

  // Add some numbers to the queue
  int i;
  for (i = 0; i < 10; i++) {
    struct entry* n = malloc(sizeof(struct entry));
    n->number = i;
    CIRCLEQ_INSERT_HEAD(&head, n, entries);
    printf("Added %d to the queue\n", n->number);
  }

  // Remove a number from the queue
  struct entry *n;
  n = CIRCLEQ_FIRST(&head);
  CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
  printf("Removed %d from the queue\n", n->number);

  return 0;
}

Which produces the following output:

Added 0 to the queue
Added 1 to the queue
Added 2 to the queue
Added 3 to the queue
Added 4 to the queue
Added 5 to the queue
Added 6 to the queue
Added 7 to the queue
Added 8 to the queue
Added 9 to the queue
Removed 9 from the queue

I am not very experienced with C, and my questions are:

1. How can I set a limit on the queue, so, for example, only 5 numbers can fit into the buffer at a time? If another item is attempted to be added after this, I should be able to detect it and do something about it (ignore it, wait, exit program, etc.).

2. It seems my code removed the last item from the buffer - how can I make it remove items from the tail (number 0 instead of 9, in my example)?

I've read through http://linux.die.net/man/3/queue, but it doesn't seem clear how I can accomplish the above two things.

Answer 1

1. If you look at the description of circular-buffer, one of the main benefits of this kind of buffer is that it uses a single fixed allocation, whereas yours is basically just a circularly linked list. The fixed size used at creation specifies the limit of the number of elements the ring buffer can hold.

2. If you have a properly implemented circular buffer, removing an item involves simply advancing the tail pointer, wrapping back to the front if necessary.

An example struct representing a circular buffer might look like the following:

struct circleq
{
    int* buf;
    int head;
    int tail;
    int size;
};

void init(struct circleq* q, int size)
{
    q->buf = malloc(sizeof(int) * size);
    q->head = 0;
    q->tail = size - 1;
    q->size = size;
}

void insert(struct circleq* q, int val)
{
    if(q->head == q->tail) { } // queue full, error
    else
    {
        q->buf[q->head] = val;
        q->head = (q->head + 1) % q->size;
    }
}

int remove(struct circleq* q)
{
    if((q->tail + 1) % q->size == q->head) { return 0; } // queue empty, error
    else
    {
        int val = q->buf[q->tail];
        q->tail = (q->tail + 1) % q->size;
        return val;
    }
}

void destroy(struct circleq* q)
{
    free(q->buf);
}