Skip to content

redundant next_ptr == 0 check in queue? #108

@copyrat90

Description

@copyrat90

I really don't see why this check is required:

if ( next_ptr == 0 )
/* this check is not part of the original algorithm as published by michael and scott
*
* however we reuse the tagged_ptr part for the freelist and clear the next part during node
* allocation. we can observe a null-pointer here.
* */
continue;

The comment says it clears the next part during allocation, however looking at queue::node's constructor, it seems that it doesn't clear the tag;
Rather, it increases the tag to avoid ABA problem.

node( T const& v, handle_type null_handle ) :
data( v )
{
/* increment tag to avoid ABA problem */
tagged_node_handle old_next = next.load( memory_order_relaxed );
tagged_node_handle new_next( null_handle, old_next.get_next_tag() );
next.store( new_next, memory_order_release );
}

By the time next_ptr == 0 check is performed, it is already guaranteed that head == head2, so the next_ptr must have set to the correct next pointer to the head's next node.
And it is guaranteed that pool.get_handle( head ) != pool.get_handle( tail ), so the next_ptr can't be nullptr.

Even if the head has been reused by the time when the check performs, the next_ptr should hold the previous next node value instead of nullptr.

Am I missing something here?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions