I'm implementing a generic (ie. void *) queue in C. I believe I have a working version but I'm looking for two things:
- Do any subtle bugs pop out to the experienced reader?
- Can I implement this in a better way (perhaps using
void **pointers?
queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <stdbool.h>
#include <stdlib.h>
typedef struct Queue Queue;
void queue_free (Queue* queue);
Queue* queue_init (void);
void* queue_dequeue (Queue* queue);
void queue_enqueue (Queue* queue, void* item);
bool queue_is_empty (const Queue* queue);
void queue_iterate (const Queue* queue, void (*fn)(void*));
size_t queue_size (const Queue* queue);
#endif
queue.c
#include "queue.h"
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
struct Queue {
size_t capacity, size;
void** data;
size_t head, tail;
/*
The queue is constructed using a pointer to the data and two integers representing
the head and tail of the queue.
head, tail
|
v
[ ][ ][ ][ ]
When an item is enqueued, we place it at the tail of the list and increment the tail.
head
| tail
v v
[a][ ][ ][ ]
The tail is guaranteed to always point to an empty slot (if it can't point to an empty
slot, the underlying array is resized).
head head
| | tail
v v v
[a][b][c][d] => [a][b][c][d][ ][ ][ ][ ]
If the tail has reached the end of the underlying array (and there is still room), it
wraps around.
tail
| head
v v
[ ][b][c][d]
When an object is dequeued we return the item pointed to by head and increment head. If
the queue is empty, we do _not_ move head.
tail
| head
v v
[ ][ ][c][d]
If, when we resize the array, head is larger than tail, we move all of head's elements to
the end of the new array.
tail
| head
v v
[c][d][ ][ ][ ][ ][a][b]
*/
};
void queue_free(Queue* queue) {
assert(queue);
free(queue->data);
free(queue);
}
Queue* queue_init(void) {
Queue* queue = calloc(1, sizeof *queue);
assert(queue);
queue->capacity = 100;
queue->size = 0;
queue->data = calloc(queue->capacity, sizeof *queue->data);
assert(queue->data);
queue->head = 0;
queue->tail = 0;
return queue;
}
void* queue_dequeue(Queue* queue) {
assert(queue);
if (queue->size == 0) {
return NULL;
}
void* item = queue->data[queue->head];
queue->head = (queue->head + 1) % queue->capacity;
queue->size--;
assert(item);
return item;
}
void queue_enqueue(Queue* queue, void* item) {
assert(queue);
assert(item);
queue->data[queue->tail] = item;
queue->size++;
// Resize the underlying array if we've reached capacity.
if (queue->size == queue->capacity) {
size_t scale = 2;
void** tmp = realloc(queue->data, scale * queue->capacity * sizeof *tmp);
assert(tmp);
if (queue->head > queue->tail) {
for (size_t i = queue->head; i < queue->capacity; ++i) {
tmp[i + queue->capacity] = tmp[i];
tmp[i] = NULL;
}
queue->head += queue->capacity;
}
queue->capacity *= scale;
queue->data = tmp;
}
queue->tail = (queue->tail + 1) % queue->capacity;
}
bool queue_is_empty(const Queue* queue) {
assert(queue);
return queue->size == 0;
}
void queue_iterate(const Queue* queue, void (*fn)(void*)) {
assert(queue);
assert(fn);
if (queue->size == 0) {
return;
}
for (size_t i = 0; i < queue->size; ++i) {
void* x = queue->data[(i + queue->head) % queue->capacity];
fn(x);
}
}
size_t queue_size(const Queue* queue) {
assert(queue);
return queue->size;
}
