Я построил стек с помощью 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, так следует ли мне в этих случаях откладывать уничтожение объекта?

0 ответов

Другие вопросы по тегам