Skip to content

Instantly share code, notes, and snippets.

@M0nteCarl0
Created December 27, 2023 12:17
Show Gist options
  • Save M0nteCarl0/811e1458afad8814341c03508944e339 to your computer and use it in GitHub Desktop.
Save M0nteCarl0/811e1458afad8814341c03508944e339 to your computer and use it in GitHub Desktop.
C++ lock-free structures
#include <atomic>
#include <memory>
template <typename T>
class LockFreeFIFO {
private:
struct Node {
std::shared_ptr<T> data;
Node* next;
Node(const T& value)
: data(std::make_shared<T>(value)), next(nullptr) {}
};
std::atomic<Node*> head;
std::atomic<Node*> tail;
public:
LockFreeFIFO()
: head(nullptr), tail(nullptr) {}
void enqueue(const T& value) {
Node* newNode = new Node(value);
newNode->next = nullptr;
Node* prevTail = tail.exchange(newNode);
prevTail->next = newNode;
}
std::shared_ptr<T> dequeue() {
Node* oldHead = head.load();
Node* newHead = oldHead->next;
if (newHead == nullptr) {
return nullptr;
}
std::shared_ptr<T> value = newHead->data;
head.store(newHead);
delete oldHead;
return value;
}
};
#include <atomic>
#include <vector>
template <typename T>
class LockFreeRingBuffer {
private:
std::vector<T> buffer;
std::atomic<size_t> head;
std::atomic<size_t> tail;
const size_t capacity;
public:
LockFreeRingBuffer(size_t capacity)
: buffer(capacity), head(0), tail(0), capacity(capacity) {}
bool enqueue(const T& value) {
size_t currentTail = tail.load(std::memory_order_relaxed);
size_t nextTail = (currentTail + 1) % capacity;
if (nextTail == head.load(std::memory_order_acquire)) {
return false; // Buffer is full
}
buffer[currentTail] = value;
tail.store(nextTail, std::memory_order_release);
return true;
}
bool dequeue(T& value) {
size_t currentHead = head.load(std::memory_order_relaxed);
if (currentHead == tail.load(std::memory_order_acquire)) {
return false; // Buffer is empty
}
value = buffer[currentHead];
head.store((currentHead + 1) % capacity, std::memory_order_release);
return true;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment