Invariants:
-Consumer moves head
-Producer moves tail
-Producer handles all memory allocation and removal
This comment was marked helpful 0 times.
lazyplus
The trick here is that we have another 'head pointer', the 'reclaim' pointer. Consumer drops elements from pointer 'head' by move the 'head' pointer forward. Then the dropped elements will be hidden from consumer. But they can still be accessed via the 'reclaim' pointer. So, the producer can know which element is deleted and do both allocation and deletion.
This comment was marked helpful 0 times.
bottie
The reclaim node pointer in queue is the key of implementing this lock free queue data structure. The producer takes advantage of the reclaim pointer to issue the allocation and deletion in the queue.
Invariants: -Consumer moves head -Producer moves tail -Producer handles all memory allocation and removal
This comment was marked helpful 0 times.
The trick here is that we have another 'head pointer', the 'reclaim' pointer. Consumer drops elements from pointer 'head' by move the 'head' pointer forward. Then the dropped elements will be hidden from consumer. But they can still be accessed via the 'reclaim' pointer. So, the producer can know which element is deleted and do both allocation and deletion.
This comment was marked helpful 0 times.
The reclaim node pointer in queue is the key of implementing this lock free queue data structure. The producer takes advantage of the reclaim pointer to issue the allocation and deletion in the queue.
This comment was marked helpful 0 times.