Я построил стек с помощью CAS. Является ли он потокобезопасным?
Я использую std::atomic для создания стека, использующего CAS.
Чтобы решить проблему ABA, я использовал помеченный указатель.
Код показан ниже.
template <typename T>
union tagged_ptr {
struct
{
std::uint64_t tag : 12, ptr : 52;
};
std::uint64_t full;
tagged_ptr(const std::uint64_t &full)
{
this->full = full;
}
tagged_ptr(T *ptr = nullptr, std::uint16_t cnt = 0)
{
tag = cnt;
this->ptr = reinterpret_cast<std::uint64_t>(ptr);
}
T *get()
{
return reinterpret_cast<T *>(ptr);
}
};
template <typename T>
class lfstack
{
struct Node
{
T data;
Node *next;
Node(const T &data, Node *next = nullptr)
{
this->data = data;
this->next = next;
}
};
std::atomic_uint64_t m_top;
std::atomic_size_t m_size;
public:
lfstack()
{
m_top = 0;
m_size = 0;
}
~lfstack()
{
Node *ptr = reinterpret_cast<Node *>(m_top.load(std::memory_order_relaxed)), *next;
while (ptr)
{
next = ptr->next;
delete ptr;
ptr = next;
}
}
size_t size()
{
return m_size.load();
}
bool empty()
{
return !size();
}
const T &top()
{
return tagged_ptr<Node>(m_top.load()).get()->data;
}
std::optional<T> pop()
{
tagged_ptr<Node> local_ptr(m_top.load(std::memory_order_relaxed));
while (true)
{
if (!local_ptr.get())
return std::nullopt;
tagged_ptr<Node> local_next(local_ptr.get()->next, local_ptr.tag);
if (m_top.compare_exchange_weak(local_ptr.full, local_next.full))
{
T ret_val = std::move(local_ptr.get()->data);
delete local_ptr.get();
m_size.fetch_sub(1, std::memory_order_relaxed);
return ret_val;
}
}
}
void push(const T &data)
{
tagged_ptr<Node> local_ptr(m_top.load(std::memory_order_relaxed)), new_ptr(new Node(data));
while (true)
{
new_ptr.get()->next = local_ptr.get();
new_ptr.tag = local_ptr.tag + 1;
if (m_top.compare_exchange_weak(local_ptr.full, new_ptr.full))
{
m_size.fetch_add(1, std::memory_order_relaxed);
break;
}
}
}
};
Я протестировал его в нескольких потоках, и он, кажется, работает нормально.(Я тестировал его на компиляторе MSVC x64.)
Но линияtagged_ptr<Node> local_next(local_ptr.get()->next, local_ptr.tag);
мне это не кажется потокобезопасным, я прав?
Если я сделаюdelete local_ptr.get();
в другом потоке это похоже на ссылку на local_ptr вlocal_ptr.get()->next
будет UB, так следует ли мне в этих случаях откладывать уничтожение объекта?