I wrote an article about this implementation

[schneems]

Thanks for putting this on github. I wrote an article about it.

https://schneems.com/2017/06/28/how-to-write-a-lock-free-queue/

[darkautism]

Hello schneems, Thanks for your article.

I notice the reddit have some comment. ABA problem can be resolve by __sync_bool_compare_and_swap check

    do {
        p = ctx->head;
    } while(p==0 || !__sync_bool_compare_and_swap(&ctx->head,p,0));

    if( p->next==0) {
        ctx->head=p;
        return 0;
    }

The code not perfect because it like a very very mini spin lock. Maybe ring buffer (Next version?) version can resolve this issue.

[schneems]

I was thinking about eventually writing a ring buffer article eventually. That would solve the ABA issue (since we're presumably comparing indexes instead of elements).

As is I think this queue is still useful if you know you're not going to be putting the same element in twice. The code I was using (queues in my first article for) was used for passing in a struct with a unique pointer every time, the usage of the queue can also mitigate ABA as well.

It was very useful for an introduction to lock free data structures.

[Globik]

How can I unlock my imagination with this?

[darkautism]

@Globik What?

[darkautism]

@schneems I write Hazard Pointers version. Hope you like it. Update: Still crashing... try to fix it.

[schneems]

Cool, thank you for making this code open source. I would love to learn more about hazard pointers.

I see it is still crashing. Before you updated this I took a look at the code and don't see where HP is defined

https://github.com/darkautism/lfqueue/blob/d8f03e29ccca055b826a21feb770b6623f5059c1/lfq.h#L18

[darkautism]

This line is a pointer array. HP means these pointer is hazard which freeer couldn't free this pointer.