Как я могу реализовать этот псевдокод очереди без блокировки в 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;
}
_t, зарезервированы в некоторых стандартах (POSIX, не уверен насчет фактического стандарта) и не должны использоваться в вашем коде. Вы должны использовать другое соглашение об именах. - person Chris Lutz schedule 23.05.2011