Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11673
Последний выпуск: 19.06.2015

lock-free linked list

359
05 января 2016 года
KIV
432 / / 20.01.2009
Я реализовал lock-free добавление и удаление в односвязный кольцевой список:
Код:
#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;
            }
        }
    }
}
Я не уверен, что этот код полностью thread-safe. Особенно беспокоит функция удаления (цикл поиска prev). Помогите разобраться, пожалуйста.
P.S.: Вопрос освобождения памяти после удаления элемента меня сейчас не интересует. У меня есть возможность убедиться, что элемент больше никто не попытается добавить в список перед его уничтожением.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог