typedef struct _Node Node;
|
typedef struct _Queue Queue;
|
|
struct _Node {
|
void *data;
|
Node *next;
|
};
|
|
struct _Queue {
|
Node *head;
|
Node *tail;
|
};
|
|
Queue*
|
queue_new(void)
|
{
|
Queue *q = g_slice_new(sizeof(Queue));
|
q->head = q->tail = g_slice_new0(sizeof(Node));
|
return q;
|
}
|
|
void
|
queue_enqueue(Queue *q, gpointer data)
|
{
|
Node *node, *tail, *next;
|
|
node = g_slice_new(Node);
|
node->data = data;
|
node->next = NULL;
|
|
while (TRUE) {
|
tail = q->tail;
|
next = tail->next;
|
if (tail != q->tail)
|
continue;
|
|
if (next != NULL) {
|
CAS(&q->tail, tail, next);
|
continue;
|
}
|
|
if (CAS(&tail->next, null, node)
|
break;
|
}
|
|
CAS(&q->tail, tail, node);
|
}
|
|
gpointer
|
queue_dequeue(Queue *q)
|
{
|
Node *node, *tail, *next;
|
|
while (TRUE) {
|
head = q->head;
|
tail = q->tail;
|
next = head->next;
|
if (head != q->head)
|
continue;
|
|
if (next == NULL)
|
return NULL; // Empty
|
|
if (head == tail) {
|
CAS(&q->tail, tail, next);
|
continue;
|
}
|
|
data = next->data;
|
if (CAS(&q->head, head, next))
|
break;
|
}
|
|
g_slice_free(Node, head); // This isn't safe
|
return data;
|
}
|
