A lock-free stack can use split reference counts to keep nodes alive while threads access them. Its head pairs a node pointer with an external count; each node also has an internal count. Once the head pairing is no longer shared, its count is transferred to the node’s internal count. The node can be deleted when that count reaches zero. section 7.2.4
The stack uses atomic updates to coordinate its operations:
- push creates a node and uses compare-and-swap to add it to the head. section 7.2.4
- pop increases the head’s external count before accessing its node, then updates the head atomically. section 7.2.4
- The implementation is lock-free only if the atomic counted pointer is lock-free on the target platform; otherwise std::atomic may use a mutex. section 7.2.4
Listing 7.11. Pushing a node on a lock-free stack using split reference counts
template<typename T>
class lock_free_stack
{
private:
struct node;
struct counted_node_ptr #1
{
int external_count;
node* ptr;
};
struct node
{
std::shared_ptr<T> data;
std::atomic<int> internal_count; #2
counted_node_ptr next; #3
node(T const& data_):
data(std::make_shared<T>(data_)),
internal_count(0)
{}
};
std::atomic<counted_node_ptr> head; #4
public:
~lock_free_stack()
{
while(pop());
}
void push(T const& data) #5
{
counted_node_ptr new_node;
new_node.ptr=new node(data);
new_node.external_count=1;
new_node.ptr->next=head.load();
while(!head.compare_exchange_weak(new_node.ptr->next,new_node));
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":5,\"ch\":45},{\"line\":5,\"ch\":47}],[{\"line\":13,\"ch\":45},{\"line\":13,\"ch\":47}],[{\"line\":14,\"ch\":45},{\"line\":14,\"ch\":47}],[{\"line\":20,\"ch\":45},{\"line\":20,\"ch\":47}],[{\"line\":26,\"ch\":45},{\"line\":26,\"ch\":47}]]"}
!@%STYLE%@!
Inspect the counted-pointer structure and push implementation. section 7.2.4
Listing 7.12. Popping a node from a lock-free stack using split reference counts
template<typename T>
class lock_free_stack
{
private:
// other parts as in listing 7.11
void increase_head_count(counted_node_ptr& old_counter)
{
counted_node_ptr new_counter;
do
{
new_counter=old_counter;
++new_counter.external_count;
}
while(!head.compare_exchange_strong(old_counter,new_counter)); #1
old_counter.external_count=new_counter.external_count;
}
public:
std::shared_ptr<T> pop()#
{
counted_node_ptr old_head=head.load();
for(;;)
{
increase_head_count(old_head);
node* const ptr=old_head.ptr; #2
if(!ptr)
{
return std::shared_ptr<T>();
}
if(head.compare_exchange_strong(old_head,ptr->next)) #3
{
std::shared_ptr<T> res;
res.swap(ptr->data); #4
int const count_increase=old_head.external_count-2; #5
if(ptr->internal_count.fetch_add(count_increase)== #6
-count_increase)
{
delete ptr;
}
return res; #7
}
else if(ptr->internal_count.fetch_sub(1)==1)
{
delete ptr; #8
}
}
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":13,\"ch\":72},{\"line\":13,\"ch\":74}],[{\"line\":23,\"ch\":72},{\"line\":23,\"ch\":74}],[{\"line\":28,\"ch\":72},{\"line\":28,\"ch\":74}],[{\"line\":31,\"ch\":72},{\"line\":31,\"ch\":74}],[{\"line\":32,\"ch\":72},{\"line\":32,\"ch\":74}],[{\"line\":33,\"ch\":72},{\"line\":33,\"ch\":74}],[{\"line\":38,\"ch\":72},{\"line\":38,\"ch\":74}],[{\"line\":42,\"ch\":72},{\"line\":42,\"ch\":74}]]"}
!@%STYLE%@!
Inspect how pop acquires a reference before accessing the head node. section 7.2.4
