D language book errata + chapter 13. SharedList code listing confusion

[monarch_dodra]

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(&currentNode._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.