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

[Ondrej Pokorny]

> 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.

Inserting after last node can be checked against
haslsb(last._next) with _next as null pointer in this case (in
removeAfter() it would be needed to call setlsb(null)? -->
0x00..01). This way insertAfter() obtain at least an information
about that, that something went wrong and return false or
something.

Robust solution would be do this in similar manner like in
mentioned article e.g. by searching from beginning of the list
(which is possible) every time and by comparing pointers with
second search started from "this" pointer and on clearlsb(_next),
as you wrote in case of Y type list this will find common valid
node, if not, new element should be inserted at the end. If this
fails, then start search again.

Adding new node immediately after "this" node can be possible, if
cas() return false and pointer invalidates we need to start
search for first valid element that is shared with "main" branch
of Y.

> 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.

This will work if there is new node inserted between nextNode and
"this", but it won't work if "this" is being removed and its
haslsb(this._next) == true.
e.g.:

A ---> B ---> C ---> D

call to removeAfter(B) in thread 1
thread1 is interrupted before call to if(!cas(&_next, thisNext,
afterExcise))

A ---> B ---> C xxxx> D   (xxxx> is setlsb (invalid) pointer)

call to removeAter(A) in thread 2
A ---> B xxxx> C xxxx> D
thread 2 interrupts at same place as thread 1
thread 1 continues

if(!cas()) // == true step inside
currentNode = this;
while(currentNode.next != thisNext) // is false, cleared lsb is
same as thisNext, cycle skipped
{}
}while (!cas(&currentNode._next, thisNext,
> afterExcise)) // is true and cycle will run forever because 
> currentNode._next has already set lsb, while thisNext don't.

Another scenario to consider:
beginning is same as before except that thread 2 is not
interrupted and removes node B completely (Y list scenario).
RemoveAfter in thread 2 should be able to recognize that C is
invalid too and  set this._next to first valid element (which is
D).