Easy peasy lock-free queue

lock_free_queue.hpp

#pragma once

#include <atomic>
#include <optional>

template <typename T>
class lock_free_queue {
public:
    using value_type = T;

    struct list_node {
        value_type value;
        list_node* next;
    };

    lock_free_queue() :
        _first(nullptr),
        _free_list(nullptr),
        _before_next(nullptr),
        _last(nullptr) {}

    void push(T t) {
        auto node = [&]{
            if (auto node = _free_list) {
                _free_list = node->next;
                node->value = std::move(t);
                return node;
            } else {
                return new list_node{std::move(t), nullptr};
            }
        }();

        auto last = _last.load(std::memory_order_acquire);

        if (!last) {
            _first = new list_node{{}, node};
            _before_next.store(_first, std::memory_order_relaxed);
            _last.store(node, std::memory_order_release);
        } else {
            last->next = node;
            _last.store(node, std::memory_order_release);
        }

        // cleanup
        auto before_next = _before_next.load(std::memory_order_acquire);
        while (_first != before_next) {
            auto node = _first;
            _first = node->next;
            node->next = _free_list;
            _free_list = node;
        }
    }

    auto pop() -> std::optional<T> {
        auto last = _last.load(std::memory_order_acquire);

        if (!last) {
            return std::nullopt;
        }

        auto before_next = _before_next.load(std::memory_order_relaxed);

        if (before_next == last) {
            return std::nullopt;
        }

        auto value = std::move(before_next->next->value);

        _before_next.store(before_next->next, std::memory_order_release);

        return value;
    }

private:
    list_node* _first;
    list_node* _free_list;
    std::atomic<list_node*> _before_next;
    std::atomic<list_node*> _last;
};