blob: 9fd11f148acfcc1ed1c838c689753b87647058b6 (
plain) (
tree)
|
|
#ifndef _SALTICIDAE_QUEUE_H
#define _SALTICIDAE_QUEUE_H
#include <atomic>
#include <vector>
#include <cassert>
#include <thread>
namespace salticidae {
static size_t const cacheline_size = 64;
class FreeList {
public:
struct Node {
std::atomic<Node *> next;
std::atomic<size_t> refcnt;
std::atomic<bool> freed;
Node(): next(nullptr), refcnt(1), freed(false) {}
virtual ~Node() {}
};
private:
alignas(cacheline_size) std::atomic<Node *> top;
public:
FreeList(): top(nullptr) {}
FreeList(const FreeList &) = delete;
FreeList(FreeList &&) = delete;
void release_ref(Node *u) {
if (u->refcnt.fetch_sub(1, std::memory_order_relaxed) != 1) return;
for (;;)
{
auto t = top.load(std::memory_order_relaxed);
// repair the next pointer before CAS, otherwise u->next == nullptr
// could lead to skipping elements
u->next.store(t
|