LINUX.ORG.RU

История изменений

Исправление 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