AtomicStack.hpp

Go to the documentation of this file.

#pragma once
#include "Allocator.hpp"
#include "Atomic.hpp"
namespace Foundation::Core
{
    template <typename T>
    class AtomicStack
    {
    public:
        struct Node;
        struct alignas(2 * sizeof(Node*)) PTag
        {
            Node* p{nullptr};
            uintptr_t tag{};
        };
        struct Node
        {
            PTag next{};
            T data{};
        };
 
    private:
        Atomic<PTag> mTop{};
        Allocator* mAlloc;
 
    public:
        AtomicStack(Allocator* alloc) : mAlloc(alloc) {}
        template <typename U>
        void Push(U&& value)
        {
            Node* node = static_cast<Node*>(mAlloc->Allocate(sizeof(Node), alignof(Node)));
            node->data = std::forward<U>(value);
            // Node* old_top = m_top.load(std::memory_order_relaxed);
            // -> Doesn't avoid https://en.wikipedia.org/wiki/ABA_problem - a pushes and a pop then a push
            //    effectively make the new pointer the same again on linear allocators, but it's a different node.
            //    CAS later won't solve this. We need to tag the pointer.
            PTag old_top = mTop.load(std::memory_order_relaxed);
            node->next = old_top;
            // -> Tag is incremented on every modification of the head pointer.
            while (true)
            {
                PTag new_top{node, old_top.tag + 1};
                if (mTop.compare_exchange_weak(old_top, new_top, std::memory_order_acquire, std::memory_order_relaxed))
                {
                    node->next = old_top;
                    return; // OK. Acquired the head and we're in
                }
            }
        }
        bool Pop(T& out)
        {
            PTag old_top = mTop.load(std::memory_order_relaxed);
            while (old_top.p != nullptr)
            {
                // Same as above
                PTag new_top{old_top.p->next.p, old_top.tag + 1};
                if (mTop.compare_exchange_weak(old_top, new_top, std::memory_order_acquire, std::memory_order_relaxed))
                {
                    out = std::move(old_top.p->data);
                    old_top.p->~Node();
                    mAlloc->Deallocate(old_top.p);
                    return true; // OK. Acquired the head and we're out
                }
            }
            return false; // Empty
        }
        ~AtomicStack()
        {
            T val;
            while (Pop(val))
                ;
        }
    };
} // namespace Foundation::Core