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;
}