In function pop, I guess *value = q->head->next->data should be *value = q->head->next->value?

NOTE: Now fixed.

Can you explain to me more specifically what the reclaim does?

@418_touhenying reclaim points to the first element in the queue that is popped but not freed.

Also, I can't understand why the memory needs to be freed from the same thread. I believe malloc/free are thread safe operations. Could someone explain this?

Ref: http://stackoverflow.com/questions/15995831/freeing-memory-across-threads

Adding a reclaim pointer is to prevent "pop" from accessing a null node. For example, without reclaim, if a thread is pushing, it get the tail node and ready to push. Then another thread comes and pop all the nodes from queue. After that, the tail node that first thread got is NULL. With reclaim, we can prevent it.

@momoda I couldn't follow how the tail will be null? pop fails if head == tail, and in init(), both head and tail are initialized to new Node (some random addr). Failing pop when head == tail prevents the thread from deleting all the nodes in the queue.

The only reason for transferring the delete to push instead of pop is to prevent having to make malloc() thread safe or is there any other reason?

@harboric. Fixed. Thanks.

@mrrobot. I agree with you.

if there is only one thread executing pop(), why it could be problematic if we do deletion in pop()?

@yanguw I think for single thread it's ok to do deletion in pop(). Only when multi threads present, allocation and free should be done by the same thread, though I don't fully understand why.

@yangwu In this case, both allocation and free operation is done by the pusher thread. If we put delete in the poper thread, we may lost a push value since the pop will delete tail Node where push just linked the value to that Node->next.

@leis1 But then couldn't a deleting pop just check that head != tail before doing the same thing as the slide's pop and deleting the old head? If deleting the tail node is the only problem, pop should be able to check for that.

@Josephus a head!=tail check would not work.Consider the situation where in push
tail->next = n has executed but tail pointer has not been updated to n. Now if we pop the value at tail, head->next will point to n and tail will become null.

@rajul But in that case, shouldn't the head!=tail check prevent pops until the tail pointer updates? I don't see how that case would bypass the check on q's head and tail.

How do we make sure push and pop is done by the same thread, and why do we need this?

@cyl, push and pop are not done by the same thread. Addition and deletion is.

Producer will call push, and execute the the reclaim logic.

Consumer will just call pop.