При инициализации структуры node в поле internal_count записывается 0, а в поле external_counters — 2 (4), потому что сразу после добавления нового узла в очередь на него есть две ссылки: из tail и из указателя next в предыдущем узле. Код самой функции push() похож на приведенный в листинге 7.14 с тем отличием, что перед тем как разыменовывать загруженное из tail значение, чтобы вызвать compare_exchange_strong() для члена узла data (6), мы вызываем новую функцию increase_external_count() которая увеличивает счетчик (5), а затем функцию free_external_counter() для старого хвоста old_tail (7).
Разобравшись с push(), обратим наши взоры на pop(). В ее коде (см. листинг 7.16) логика подсчета ссылок из реализации pop() в листинге 7.11 комбинируется с логикой извлечения из очереди в листинге 7.13.
Листинг 7.16. Извлечение узла из очереди без блокировок с подсчётом ссылок на tail
template
class lock_free_queue {
private:
struct node {
void release_ref();
};
public:
std::unique_ptr
counted_node_ptr old_head =
head.load(std::memory_order_relaxed); ←(1)
for (;;) {
increase_external_count(head, old_head);←(2)
node* const ptr = old_head.ptr;
if (ptr == tail.load().ptr) {
ptr->release_ref();←(3)
return std::unique_ptr
}
if (head.compare_exchange_strong(old_head, ptr->next)) {←(4)
T* const res = ptr->data.exchange(nullptr);
free_external_counter(old_head);←(5)
return std::unique_ptr
}
ptr->release_ref();
}
}
};
Все начинается с загрузки значения old_head перед входом в цикл (1) и до увеличения внешнего счетчика в загруженном значении (2). Если узел head совпадает с tail, то можно освободить ссылку (3) и вернуть нулевой указатель, потому что очередь пуста. Если же в очереди есть данные, то мы пытаемся заявить на них свои права с помощью compare_exchange_strong() (4). Как и в случае стека в листинге 7.11, мы при этом сравниваем внешний счетчик и указатель как единое целое; если хотя бы один из них изменился, то мы должны вернуться в начало цикла, освободив предварительно ссылку 6. Если обмен завершился удачно, то мы получили в свое распоряжение данные в узле, поэтому можем вернуть их вызывающей программе, освободив предварительно внешний счетчик ссылок на извлеченный узел (5). После того как оба внешних счетчика освобождены, а внутренний счетчик обратился в нуль, сам узел можно удалять. Вспомогательные функции подсчета ссылок приведены в листингах 7.17, 7.18 и 7.19.
Листинг 7.17. Освобождение ссылки на узел в очереди без блокировок
template
class lock_free_queue {
private:
struct node {
void release_ref() {
node_counter old_counter =
count.load(std::memory_order_relaxed);
node_counter new_counter;
do {
new_counter = old_counter;
--new_counter.internal_count; ←(1)
}
while (!count.compare_exchange_strong(←(2)
old_counter, new_counter,
std::memory_order_acquire, std::memory_order_relaxed));
if (
!new_counter.internal_count &&
!new_counter.external_counters) {
delete this; ←(3)
}
}
};
};
Реализация node::release_ref() лишь немногим отличается от аналогичного кода в lock_free_stack::pop() (см. листинг 7.11). Там мы работали с единственным внешним счетчиком, поэтому достаточно было вызвать fetch_sub. Здесь же необходимо атомарно обновить всю структуру count, хотя в действительности мы хотим модифицировать только поле internal_count (1). Поэтому никуда не деться от цикла сравнения с обменом (2). Если после уменьшения internal_count оказалось, что и внутренний, и внешний счетчик равны нулю, то это была последняя ссылка, и мы можем удалять узел (3).
Листинг 7.18. Получение новой ссылки на узел в очереди без блокировок
template
class lock_free_queue {
private:
static void increase_external_count(
std::atomic
