Re: atomic-free spsc-lifo-stack 2

On 23 фев, 19:37, "Dmitriy V'jukov" <dvyu...@xxxxxxxxx> wrote:
atomic-free spsc-lifo-stack version 2
Here is implementation:

template<typename T>
class spsc_lifo_stack2
{
public:
struct node
{
node* link_;

When producer push node, links constitute fifo-order. Then consumer
change direction of links to lifo (cycle in pop() function).
So actually stack consists of 2 parts. First part is fifo. Second is
lifo.

T data_;
};

spsc_lifo_stack2()
{
head_ = new node();
head_->link_ = 0;
tail_ = head_;
prev_ = 0;

First node (pointed by head_) always contains fake data.
head_ points to last node in fifo part.
tail_ points to first node in fifo part.
prev_ points to first node in lifo part.

}

~spsc_lifo_stack2()
{
ASSERT(0 == head_->link_);
ASSERT(head_ == tail_);
ASSERT(0 == prev_);
delete head_;
}

void push(node* n, T const& v)
{
n->link_ = 0;
head_->data_ = v;
_ReadWriteBarrier();
head_->link_ = n;
_ReadWriteBarrier();
head_ = n;

Nothing unusual here. Except that producer establish fifo order, not
lifo.

}

bool pop(node*& n, T& v)
{

This cycle moves nodes from fifo part to lifo part.

if (node* next = tail_->link_)
{
node* cur = tail_;
node* prev = prev_;
do
{
cur->link_ = prev;
prev = cur;
cur = next;
next = cur->link_;
}
while (next);
tail_ = cur;
prev_ = prev;
}
if (0 == prev_)
return false;
n = prev_;
v = n->data_;
prev_ = n->link_;
return true;
}

private:
char pad1_ [128];
node* head_;

head_ used solely by producer

char pad2_ [128];
node* tail_;
node* prev_;

tail_ and prev_ used solely by consumer

char pad3_ [128];

};



Dmitriy V'jukov
.

Relevant Pages