Обратите внимание, что внешний счетчик хранится вместе с указателем на узел в структуре counted_node_ptr (1). Эта структура затем используется для представления указателя next в структуре node (3), где хранится также внешний счетчик (2). Поскольку counted_node_ptr определена как struct, то ее можно использовать в шаблоне std::atomic<> для представления головы списка head (4).
На платформах, где поддерживается операция сравнения и обмена двойного слова, размер этой структуры достаточно мал для того, чтобы тип данных std::atomic был свободен от блокировок. Если вы работаете на другой платформе, то лучше пользоваться вариантом std::shared_ptr<>, приведенным в листинге 7.9, потому что в std::atomic<> для гарантирования атомарности используется мьютекс, когда тип слишком велик и с помощью машинных команд обеспечить атомарность невозможно (а, следовательно, ваш алгоритм, якобы «свободный от блокировок», на самом теле таковым не является). Можно поступить и по-другому — если вы готовы ограничить размер счетчика и знаете, что на данной платформе в указателе есть неиспользуемые биты (например, потому что адресное пространство представлено 48 битами, а под указатель отводится 64 бита), то счетчик можно хранить в незанятых битах указателя, и тогда оба поля поместятся в одно машинное слово. Но для таких трюков нужно хорошо знать особенности платформы, так что в этой книге мы их обсуждать не будем.
Функция push() относительно проста (5). Мы конструируем объект counted_node_ptr, ссылающийся на только что выделенный узел node с ассоциированными данными, и в поле next узла node записываем текущее значение head. Затем с помощью compare_exchange_weak() устанавливаем новое значение head, как и раньше. Внутренний счетчик internal_count инициализируется нулем, а внешний external_count — единицей. Поскольку узел новый, на него пока существует только одна внешняя ссылка (из самого указателя head).
Как обычно, все сложности сосредоточены в реализации pop(), показанной в следующем листинге.
Листинг 7.11. Выталкивание узла из свободного от блокировок стека с разделённым счётчиком ссылок
template
class lock_free_stack {
private:
void increase_head_count(counted_node_ptr& old_counter) {
counted_node_ptr new_counter;
do {
new_counter = old_counter;
++new_counter.external_count;
}
while (
!head.compare_exchange_strong(old_counter, new_counter));←(1)
old_counter.external_count = new_counter.external_count;
}
public:
std::shared_ptr
counted_node_ptr old_head = head.load();
for (;;) {
increase_head_count(old_head);
node* const ptr = old_head.ptr;←(2)
if (!ptr) {
return std::shared_ptr
}
if (head.compare_exchange_strong(old_head, ptr->next)) {←(3)
std::shared_ptr
res.swap(ptr->data); ←(4)
int const count_increase = old_head.external_count - 2;←(5)
if (ptr->internal_count.fetch_add(count_increase) ==
-count_increase) { ←(6)
delete ptr;
}
return res; ←(7)
} else if (ptr->internal_count.fetch_sub(1) == 1) {
delete ptr; ←(8)
}
}
}
};
Теперь, загрузив значение head, мы должны сначала увеличить счетчик внешних ссылок на узел head, показав, что ссылаемся на него, — только тогда его можно безопасно будет разыменовывать. Если попытаться разыменовать указатель compare_exchange_strong() (1), где устанавливаются все поля структуры, чтобы быть уверенным, что другой поток не изменил в промежутке указатель.
