On Tuesday, 21 August 2012 at 07:21:34 UTC, Ondrej Pokorny wrote:
Hi,
[snip]
Ondrej
What you bring up are valid issues. They are already brought up
in the comments section of the article you linked. I re-read the
totality of Harris' paper, and the algorithm in TDPL is different
from Harris', hence the issues. Harris' list does not give a
direct view of the nodes, and instead implements a sorted list.
This is the reason for the difference of implementation to begin
with.
For the first issue, I think a bug fix would be:
------------------------------------------------
// Attempt to find an insertion point
auto n = _next;
while (n && haslsb(n)) {
n = clearlsb(n)._next; //Here
}
if(!n) continue; //Should also check this
// Found a possible insertion point, attempt insert
------------------------------------------------
Another one of the issues here is that TDPL makes the insertion
after-after the current node (It find the first valid insertion
point *after* the node "_next"). This means:
a) The function lies about what it is actually doing
b) you cannot insert after the last node :/
Doing an insertion right after "this" would also not be correct:
If "this" was previously removed, then you would be creating a
threaded linked list: A list that looks like a Y: multiple start
points, single end point.
Honestly, I do not know if there is a "correct" solution. To this
issue.
Regarding the second issue, I think it was just lazy coding due
to the fatigue of working with lock-free sharing :D. Issues are:
a) The list is not walked properly (afterNext is not updated).
b) The code is not cas correct anyways.
Here is a correct (I think) but bulkier implementation:
------------------------------------------------
// Step 2: excise the node to delete
if(!cas(&_next, thisNext, afterExcise)) {
// Step 3: Failed to remove: A node was inserted between
this and thisNext.
// We need to walk the list at re-attempt the deletion
until successful.
// Note that we are garanteed that thisNext still exists,
so no need to check null.
Node* currentNode;
do {
currentNode = this;
while(currentNode.next != thisNext)
currentNode = currentNode.next;
} while (!cas(¤tNode._next, thisNext, afterExcise))
}
------------------------------------------------
Can I get a second opinion on these? If I can get a proof read,
I'll submit to Andrei's errata page.
