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
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions