#define CAS(var, oldValue, newValue) __sync_bool_compare_and_swap(&(var), oldValue, newValue)

typedef struct ListItem;
struct ListItem {
    ListItem * volatile next;
    bool locked;
    bool removed;
};

typedef struct List {
    ListItem * volatile head;
    ListItem * volatile current;
} List;

List list;

void insertListItem(ListItem *item) {
    if (!CAS(item->locked, false, true)) return;
    if (item->removed == true) {
        item->removed = false;
        while (true) {
            ListItem *head = list.head;
            assert(item != head);
            item->next = head;
            if (CAS(list.head, item->next, item)) {
                break;
            }
        }
    }
    item->locked = false;
}

void removeListItem(ListItem *item) {
    if (!CAS(item->locked, false, true)) return;
    if (item->removed == false) {
        item->removed = true;
        while (true) {
            ListItem *prev = list.head;
            if (prev == item) {
                ListItem *next = item->next;
                if (CAS(list.head, item, next)) {
                    break;
                } else {
                    continue;
                }
            }
            while (prev->next != item) {
                ListItem *next = prev->next;
                prev = next;
            }
            if (CAS(prev->next, item, item->next)) {
                ListItem *next = item->next;
                CAS(list.head, item, next);
                break;
            }
        }
    }
    item->locked = false;
}