I have written a lock free MPMC FIFO in C based on a ring buffer. It uses gcc's atomic built-ins to achieve thread safety. The queue is designed to return -1 if it's full on enqueue or empty on dequeue.
After some feedback, I've changed by design. I have tested this code to work, but testing multithreaded code is hardly enough to prove it's correct.
struct queue
{
void** buf;
size_t num;
uint64_t writePos;
uint64_t readPos;
};
queue_t* createQueue(size_t num)
{
struct queue* new = xmalloc(sizeof(*new));
new->buf = xmalloc(sizeof(void*) * num);
memset(new->buf, 0, sizeof(void*)*num);
new->readPos = 0;
new->writePos = 0;
new->num = num;
return new;
}
void destroyQueue(queue_t* queue)
{
if(queue)
{
xfree(queue->buf);
xfree(queue);
}
}
int enqueue(queue_t* queue, void* item)
{
for(int i = 0; i < kNumTries; i++)
{
if(__sync_bool_compare_and_swap(&queue->buf[queue->writePos % queue->num], NULL, item))
{
__sync_fetch_and_add(&queue->writePos, 1);
return 0;
}
}
return -1;
}
void* dequeue(queue_t* queue)
{
for(int i = 0; i < kNumTries; i++)
{
void* value = queue->buf[queue->readPos % queue->num];
if(value && __sync_bool_compare_and_swap(&queue->buf[queue->readPos % queue->num], value, NULL))
{
__sync_fetch_and_add(&queue->readPos, 1);
return value;
}
}
return NULL;
}
(link to the previous iteration)
