Experimental mostly lock-free atomic lifo experiment...

[Chris M. Thomasson]

Some context: read all

https://groups.google.com/forum/#!original/comp.arch/k1Qr520dcDk/4vl_jiVRBQAJ

within the following thread:

https://groups.google.com/d/topic/comp.arch/k1Qr520dcDk/discussion


I need to find an older post I made that has a test for this using
threads. Remember coding it up in Relacy. Anyway, here is a _highly_
_crude_ little implementation. It should compile right up.
_____________________________
#include <iostream>
#include <atomic>
#include <thread>


struct user_payload
{
int m_foo;

user_payload(int foo) : m_foo(foo) {}

user_payload(const user_payload& rhs) : m_foo(rhs.m_foo) {}

void process()
{
std::cout << this << "->user_payload::process() " << m_foo << "\n";
std::this_thread::yield();
}
};


namespace ct
{

static struct node* node_wait_next(node*);

struct node
{
std::atomic<node*> m_next;
user_payload m_payload;


node(user_payload const& payload) : m_next(nullptr),
m_payload(payload)
{
std::cout << this << "->node::node()" << "\n";
}

~node()
{
std::cout << this << "->node::~node()" << "\n";
}


static void process(node* head)
{
node* cur = head;

while (cur)
{
// user processing first!
cur->m_payload.process();

// now, we see if we need to wait...
node* next = node_wait_next(cur);

delete cur;

cur = next;
}
}
};


static node g_special_wait_node(0);


#define CT_SPECIAL (&ct::g_special_wait_node)


node* node_wait_next(node* n)
{
node* next = nullptr;
while ((next = n->m_next.load(std::memory_order_relaxed))
== CT_SPECIAL) std::this_thread::yield();
return next;
}

struct stack
{
std::atomic<node*> m_head;

stack() : m_head(nullptr) {}

void push(node* n)
{
n->m_next.store(CT_SPECIAL, std::memory_order_relaxed);
node* prev = m_head.exchange(n, std::memory_order_release);
n->m_next.store(prev, std::memory_order_relaxed);
}


node* flush()
{
return m_head.exchange(nullptr, std::memory_order_acquire);
}
};
}


int main()
{
std::cout << "\nCT_SPECIAL = " << CT_SPECIAL << "\n\n";

{
ct::stack alist;

alist.push(new ct::node(789));
alist.push(new ct::node(456));
alist.push(new ct::node(123));

ct::node* work = alist.flush();

ct::node::process(work);


alist.push(new ct::node(321));
alist.push(new ct::node(654));
alist.push(new ct::node(987));

work = alist.flush();

ct::node::process(work);
}

return 0;
}
_____________________________


Can you get it to work? Fwiw, I get the following output:
_____________________________
0x6021c0->node::node()

CT_SPECIAL = 0x6021c0

0x17a0280->node::node()
0x17a02a0->node::node()
0x17a02c0->node::node()
0x17a02c8->user_payload::process() 123
0x17a02c0->node::~node()
0x17a02a8->user_payload::process() 456
0x17a02a0->node::~node()
0x17a0288->user_payload::process() 789
0x17a0280->node::~node()
0x17a0280->node::node()
0x17a02a0->node::node()
0x17a02c0->node::node()
0x17a02c8->user_payload::process() 987
0x17a02c0->node::~node()
0x17a02a8->user_payload::process() 654
0x17a02a0->node::~node()
0x17a0288->user_payload::process() 321
0x17a0280->node::~node()
0x6021c0->node::~node()
_____________________________