Skip to content

Instantly share code, notes, and snippets.

@ryankurte
Last active April 13, 2024 07:50
Show Gist options
  • Save ryankurte/61f95dc71133561ed055ff62b33585f8 to your computer and use it in GitHub Desktop.
Save ryankurte/61f95dc71133561ed055ff62b33585f8 to your computer and use it in GitHub Desktop.
Simple C FIFO Queues (aka Ring Buffers)
#define QUEUE_SIZE 16
int main(int argc, char** argv) {
queue_t example = {0, 0, QUEUE_SIZE, malloc(sizeof(void*) * QUEUE_SIZE)};
// Write until queue is full
for (int i=0; i<QUEUE_SIZE; i++) {
int res = queue_write(&example, (void*)(i+1));
assert((i == QUEUE_SIZE - 1) ? res == -1: res == 0);
}
// Read until queue is empty
for (int i=0; i<QUEUE_SIZE; i++) {
void* handle = queue_read(&example);
assert((i == QUEUE_SIZE - 1) ? handle == NULL: handle == (i+1));
}
}
// A simple fifo queue (or ring buffer) in c.
// This implementation \should be\ "thread safe" for single producer/consumer with atomic writes of size_t.
// This is because the head and tail "pointers" are only written by the producer and consumer respectively.
// Demonstrated with void pointers and no memory management.
// Note that empty is head==tail, thus only QUEUE_SIZE-1 entries may be used.
#include <stdlib.h>
#include <assert.h>
typedef struct {
size_t head;
size_t tail;
size_t size;
void** data;
} queue_t;
void* queue_read(queue_t *queue) {
if (queue->tail == queue->head) {
return NULL;
}
void* handle = queue->data[queue->tail];
queue->data[queue->tail] = NULL;
queue->tail = (queue->tail + 1) % queue->size;
return handle;
}
int queue_write(queue_t *queue, void* handle) {
if (((queue->head + 1) % queue->size) == queue->tail) {
return -1;
}
queue->data[queue->head] = handle;
queue->head = (queue->head + 1) % queue->size;
return 0;
}
// A simple and terrifying fifo queue in C.
// This is "thread safe" in the same manner as the previous example.
// It's also an "optimisation" to add length, save space and improve speed.
// Don't let the head/tail "pointers" overflow.
#include <stdlib.h>
#include <assert.h>
typedef struct {
size_t head;
size_t tail;
void** data;
} queue_t;
size_t queue_count(queue_t *queue) {
return queue->head - queue->tail;
}
void* queue_read(queue_t *queue) {
if (queue->head == queue->tail) {
return NULL;
}
void* handle = queue->data[queue->tail % queue->size];
queue->tail ++;
return handle;
}
int queue_write(queue_t *queue, void* handle) {
if ((queue->head - queue->tail) == queue->size) {
return -1;
}
queue->data[queue->head % queue->size] = handle;
queue->head ++;
}
Copy link

ghost commented Dec 7, 2021

Hi.
// Don't let the head/tail "pointers" overflow.
Just funny, but it will be happened anyway. But, in case:
(max value queue->head + 1) % queue->size == 0,
head/tail "pointers" may overflow.
Let assume, that size_t is uint8_t and queue->size = 4. So, (255 + 1) % 4 = 0. In this case, overflowing of head/tail "pointers" has no side effects.

@18521344596
Copy link

What if write faster than read,I suppose in this case It would causes overwrite memory that has not yet read

@yishengjiang99
Copy link

typedef struct {
size_t head;
size_t tail; //missing size_t size?
void** data;
} queue_t;

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment