Untitled
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