#define CAS(var, oldValue, newValue) __sync_bool_compare_and_swap(&(var), oldValue, newValue)
typedef struct Item Item;
struct Item {
Item * volatile next;
...
};
Item * volatile head = NULL;
void addToList(Item *item) {
while (true) {
item->next = listHead;
if (item->next == NULL) {
item->next = item;
if (CAS(listHead, NULL, item)) {
break;
}
} else {
if (CAS(listHead, item->next, item)) {
break;
}
}
}
}
void removeFromList(Item *item) {
while (true) {
Item *prev = listHead;
while (prev->next != item) {
prev = prev->next;
}
if (CAS(prev->next, item, item->next)) {
if (CAS(head, item, item->next)) {
CAS(head, item, NULL);
}
break;
}
}
}
}
lock-free linked list
Код:
P.S.: Вопрос освобождения памяти после удаления элемента меня сейчас не интересует. У меня есть возможность убедиться, что элемент больше никто не попытается добавить в список перед его уничтожением.