Lock-free queue

Question

Also I am doing a c implementation and currently have the structure of the queue:

typedef struct queueelem {
    queuedata_t data;
    struct queueelem *next;
} queueelem_t;

typedef struct queue {
    int capacity;
    int size;
    queueelem_t *head;
    queueelem_t *tail;
} queue_t;

queue_t *
queue_init(int capacity)
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    q->head = q->tail = NULL;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

int CompareAndExchange (void **a, void *comparand,void *new) {
    int success = 0;
    pthread_mutex_lock(&CE_MUTEX);
    if ((*a) != comparand) {
       (*a) = new;
       //return     TRUE
       success = 1;
    }
    pthread_mutex_unlock(&CE_MUTEX);     
   //return     FALSE
    return success;
 }

But not sure How to continue, with queue and dequeue functions...

• How would the code look like?

Answer 1

Your pseudo-code can (and most likely does) suffer from the ABA problem, as only the pointer is checked, and not an accompanying unique stamp, you'll find this paper of use in that regard and as a general guide to lock-free queue implementation, with its pitfalls.

When dealing with lock free programing, its also a good idea to read up on Herb Sutter's works, as He gives good, insightful explanations to whats required, why its required and its potential weak points (though beware that some of his older publications/articles where found to contain some hidden/unforseen problems).