我怎样才能实现这个无锁队列伪代码C？
ENQUEUE(x)
q ← new record
q^.value ← x
q^.next ← NULL
repeat
p ← tail
succ ← COMPARE&SWAP(p^.next, NULL, q)
if succ ≠ TRUE
COMPARE&SWAP(tail, p, p^.next)
until succ = TRUE
COMPARE&SWAP(tail,p,q)
end
DEQUEUE()
repeat
p ← head
if p^.next = NULL
error queue empty
until COMPARE&SWAP(head, p, p^.next)
return p^.next^.value
end
如何使用内置函数进行原子内存访问
__sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
我目前有
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;
}