[Ready] William's queue - SPSC and MPMC

[dudovlad]

[dudovlad]

Добавлена очередь SPSC, вместе с unit и stress тестами. Исправлена ошибка сборки stress тестов очереди MPMC. Однако некоторый stress тесты не проходят, по причине SegFault.

SegFault появляется в строке 426 в классе WilliamsQueue. Это происходит, потому что переменная old_head равна nullptr.

[khizmax]

Переменная old_head не может быть равной nullptr, так как она - не указатель.

[dudovlad]

Ошибка не в 425, а в 426 строке.

counted_node_ptr next = p->m_next.load();

Там p = nullptr. Соответственно old_head = nullptr.

[khizmax]

Если я нигде не наврал, то вот usecase:

bool dequeue_with(Func f)
{
    // Предположим,  очередь пуста.
    counted_node_ptr old_head = m_Head.load(atomics::memory_order_relaxed);
    // Раз очередь пуста, то m_Head.ptr ==  m_Tail.ptr
    // и old_head.ptr->m_next == nullptr
     while (true) {
	increase_external_count(m_Head, old_head);
	node_type * const p = old_head.ptr;
       // Thread preempted. Другой поток вставляет элемент в очередь
       // Раз вставляет - m_Tail изменился
       // Тогда сравнение с m_Tail не пройдет
	if (p == m_Tail.load().ptr) 	{
		release_ref(p);
		return false;
	}
       // а здесь у нас p->m_next == nullptr !!!
	counted_node_ptr next = p->m_next.load();
	if (m_Head.compare_exchange_strong(old_head, next))
	{
		scoped_value_ptr res(p->m_value.load());
		free_external_counter(old_head); 
		--m_ItemCounter;
		f(*res.get());
		return true;
	}
	release_ref(p);
   }
}