Исправление KivApple, (текущая версия) :
#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;
}
}
}
}
Переписал код более-менее абстрактно, чтобы конкретизировать вопрос. Меня сейчас интересует в первую очередь корректность реализации этих двух функций (без учёта вопроса освобождения памяти после удаления элемента - будем считать, что я могу гарантировать, что элемент никто не добавит перед его уничтожением).
А вот полный код - http://pastebin.com/UqsFYGbV
Так лучше?
Исходная версия KivApple, :
#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;
}
}
}
}
Переписал код более-менее абстрактно, чтобы конкретизировать вопрос. Меня сейчас интересует в первую очередь корректность реализации этих двух функций (без учёта вопроса освобождения памяти после удаления элемента - будем считать, что я могу гарантировать, что элемент никто не добавит перед его уничтожением).
А вот полный код - http://pastebin.com/UqsFYGbV