Untitled

 avatar
unknown
plain_text
6 months ago
2.2 kB
2
Indexable
#include <atomic>
#include <memory>

template<typename T>
class LockFreeQueue {
public:
    struct Node {
        std::shared_ptr<T> data;
        std::atomic<Node*> next;

        Node(T value) : data(std::make_shared<T>(value)), next(nullptr) {}
    };

    LockFreeQueue() : head(new Node(T())), tail(head.load()) {}

    ~LockFreeQueue() {
        while (Node* old_head = head.load()) {
            head.store(old_head->next);
            delete old_head;
        }
    }

    // Метод push для добавления элемента в очередь
    void push(T value) {
        Node* new_node = new Node(value);
        Node* old_tail;

        while (true) {
            old_tail = tail.load();
            Node* next = old_tail->next.load();

            if (old_tail == tail.load()) {
                if (next == nullptr) {
                    if (old_tail->next.compare_exchange_weak(next, new_node)) {
                        break;
                    }
                } else {
                    tail.compare_exchange_weak(old_tail, next);
                }
            }
        }
        tail.compare_exchange_weak(old_tail, new_node);
    }

    // Метод pop для извлечения элемента из очереди
    bool pop(T& result) {
        Node* old_head;

        while (true) {
            old_head = head.load();
            Node* tail_node = tail.load();
            Node* next = old_head->next.load();

            if (old_head == head.load()) {
                if (old_head == tail_node) {
                    if (next == nullptr) {
                        return false; // Очередь пуста
                    }
                    tail.compare_exchange_weak(tail_node, next);
                } else {
                    if (head.compare_exchange_weak(old_head, next)) {
                        break;
                    }
                }
            }
        }
        result = *(old_head->next.load()->data);
        delete old_head;
        return true;
    }

private:
    std::atomic<Node*> head;
    std::atomic<Node*> tail;
};
Editor is loading...
Leave a Comment