Ring buffer difficulties

Question

I've tried implementing a ring buffer/cyclical queue in C.

It is supposed to take all of the arguments via argv, push them onto the queue one by one, and then pop them off of the queue in the same fashion, printing them on the way out.

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <errno.h>

struct buffer
{
    int32_t front, rear, capacity, *array;
};

__attribute__ ((noreturn)) void prog_error(const char* str)
{
    perror(str);
    exit(1);
}

struct buffer *init_queue(int32_t size)
{
    struct buffer *queue = malloc(sizeof(struct buffer));

    if (!queue)
        return NULL;

    queue->capacity = size;
    queue->front = -1;
    queue->rear = -1;
    queue->array = malloc(queue->capacity * sizeof(int32_t));

    if (!queue->array)
        return NULL;

    return queue;
}


void enqueue(struct buffer *queue, int32_t x)
{
    if (((queue->rear + 1) % queue->capacity == queue->rear))
        prog_error("Queue overflow");

    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = x;

    if (queue->front == -1)
        queue->front = queue->rear;
}

int32_t dequeue(struct buffer *queue)
{
    int32_t data = 0;

    if (queue->front == -1)
        prog_error("Queue underflow");

    data = queue->array[queue->front];

    if (queue->front == queue->rear)
        queue->front = queue->rear = -1;

    queue->front = (queue->front + 1) % queue->capacity;

    return data;
}

int main(int argc, char **argv)
{
    if (argc < 2)
        prog_error("Too few arguments");

    int32_t size = (int32_t) argc - 1;

    struct buffer *queue;

    if (!(queue = init_queue(size)))
        prog_error("Allocation error");

    for (int32_t i = 1; i < size; ++i)
        enqueue(queue, (int32_t) atoi(argv[i]));

    for (int32_t i = 0; i < size; ++i)
        printf("%" PRId32 "\n", dequeue(queue));

    free(queue);
}

But the last value is always replaced by a 1.

And also, if I give it exactly 1 value then it underflows (or is that normal behavior for a ring buffer?). How can I fix this?

Answer 1

I think you've got some of your indexing wrong. In your implementation:

• the front describes the next item that should be dequeued;
• the rear describes the index at which the next item is enqueued;
• the queue is empty when both front and rear have the special value −1; this is necessary to distinguish the empty queue from a full queue.

When you enqueue, you should do the steps in the following order:

• Check for overflow;
• Adjust the special values −1 to sensible values when enyuqueing to an empty queue;
• place item at position rear;
• increment rear, possibly wrapping around.

You increment the rear first, then store the value and then adjust the front. You also have a one-off error when you check for overflow.Here's the corrected version:

void enqueue(struct buffer *queue, int32_t x)
{
    if (queue->rear >= 0 && (queue->rear) % queue->capacity == queue->front)
        prog_error("Queue overflow");

    if (queue->front == -1)
        queue->front = queue->rear = 0;

    queue->array[queue->rear] = x;
    queue->rear = (queue->rear + 1) % queue->capacity;
}

Similarly for dequeueing:

• Check for underflow;
• Save the data at the current front as result;
• Increment the front, taking care of wrap-around and;
• Adjust the front and rear to the special values −1 when the front meets the rear.

You have the last two points mixed up. (The queue can only be empty after removing an item.) So:

int32_t dequeue(struct buffer *queue)
{
    int32_t data = 0;

    if (queue->front == -1)
        prog_error("Queue underflow");

    data = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;

    if (queue->front == queue->rear)
        queue->front = queue->rear = -1;

    return data;
}

Your use of the queue is awkward. Usually, stuff is enqueued somewhere and dequeued somewhere else. The code that dequeues usually doesn't know how many items are in the queue. Therefore, a queue has a means of telling whether it is empty or not. Dequeueing an empty queue leads to underflow.

You could check (queue->front directly, but here's a wrapper function for this:

int isempty(struct buffer *queue)
{
    return (queue->front < 0);
}

This leads to client code like so:

int main(int argc, char **argv)
{
    if (argc < 2)
        prog_error("Too few arguments");

    int32_t size = (int32_t) argc - 1;
    struct buffer *queue = init_queue(size);

    if (queue == NULL)
        prog_error("Allocation error");

    for (int32_t i = 0; i < size; ++i)
        enqueue(queue, (int32_t) atoi(argv[i + 1]));

    while (!isempty(queue))
        printf("%" PRId32 "\n", dequeue(queue));

    free(queue);
}

Finally, he business with the −1s leads to some code clutter. Maybe the queue is better represented as front and length:

struct buffer
{
    int32_t front;
    int32_t length;
    int32_t capacity;
    int32_t *array;
};

struct buffer *init_queue(int32_t size)
{
    struct buffer *queue = malloc(sizeof(struct buffer));

    if (!queue) return NULL;

    queue->capacity = size;
    queue->front = 0;
    queue->length = 0;
    queue->array = malloc(queue->capacity * sizeof(*queue->array));

    if (!queue->array) return NULL;

    return queue;
}

int isempty(struct buffer *queue)
{
    return (queue->length == 0);
}

void enqueue(struct buffer *queue, int32_t x)
{
    if (queue->length == queue->capacity) prog_error("Queue overflow");

    queue->array[queue->front + queue->length++] = x;
}

int32_t dequeue(struct buffer *queue)
{
    int32_t data = 0;

    if (queue->length == 0) prog_error("Queue underflow");

    data = queue->array[queue->front++];
    if (queue->front > queue->capacity) queue->front = 0;
    queue->length--;

    return data;
}

And, but then I'll stop :), you should not only free the memory for the queue struct itself, but also for the array member. It's a good idea to create a queue_destroy function for this.