Stack.hpp

Go to the documentation of this file.

#pragma once
#include <Core/Core.hpp>
#include <Core/Allocator.hpp>
#include "Atomic.hpp"
namespace Foundation::Atomics
{
    using namespace Foundation::Core;
    template <typename T>
    class Stack
    {
        struct Node;
        struct alignas(2 * sizeof(Node*)) PTag
        {
            Node* p{ nullptr };
            uintptr_t tag{};
        };
        struct Node
        {
            PTag next{};
            T data{};
        };
        Atomic<PTag> mTop{};
        Allocator* mAlloc;
    public:
        Stack(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
                }
                old_top = mTop.load(std::memory_order_relaxed); // Retry later
            }
        }
        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
                }
                old_top = mTop.load(std::memory_order_relaxed); // Retry later
            }
            return false; // Empty
        }
    };
}