Snippets:Atomic linked list addition

The following code snippet adds an element to the beginning of a linked list. It is safe to call from multiple threads and no locks are required (beyond those used by malloc):

struct ll_node {
    int val;
    struct ll_node *next;
};
static volatile struct ll_node *ll_head = NULL;
static void ll_add_node(int val) {
    struct ll_node *new_elem = malloc(sizeof(struct ll_node));
    new_elem->val = val;
    while (1) {
        struct ll_node *current_value = ll_head;
        new_elem->next = current_value;
        if (__sync_bool_compare_and_swap(&ll_head, current_value, new_elem)) break;
    }
}

On x86, __sync_bool_compare_and_swap compiles into a lock cmpxchg assembly instruction.