www.digitalmars.com         C & C++   DMDScript  

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

reply "Ondrej Pokorny" <pokorny.ondrej gmail.com> writes:
Hi,

there is in chapter 13.16.2 in last paragraph before SharedList
code listing:
... The idea is first to mark that pointer as “logically
deleted” by setting its bit to zero, and then ...

and later:

T* setlsb(T)(T* p) {
     return cast(T*) (cast(size_t) p | 1);
}

Now to SharedList source code itself. Could possibly someone give 
me a
hand and explain me this algorithm?
I hope nobody will be offended if i repost it from here
(http://www.informit.com/articles/article.aspx?p=1609144&seqNum=16)
in my book is same version:

shared struct SharedList(T) {
     shared struct Node {
        private T _payload;
        private Node * _next;

         property shared(Node)* next() {
           return clearlsb(_next);
        }

        bool removeAfter() {
           shared(Node)* thisNext, afterNext;
           // Step 1: set the lsb of _next for the node to delete
           do {
              thisNext = next;
              if (!thisNext) return false;
              afterNext = thisNext.next;
           } while (!cas(&thisNext._next, afterNext, 
setlsb(afterNext)));
           // Step 2: excise the node to delete
           if (!cas(&_next, thisNext, afterNext)) {
              afterNext = thisNext._next;
              while (!haslsb(afterNext))
              {
                 thisNext._next = thisNext._next.next;
              }
             _next = afterNext;
        }
     }

     void insertAfter(T value) {
        auto newNode = new Node(value);
        for (;;) {
           // Attempt to find an insertion point
           auto n = _next;
           while (n && haslsb(n)) {
              n = n._next;
           }
           // Found a possible insertion point, attempt insert
           auto afterN = n._next;
           newNode._next = afterN;
           if (cas(&n._next, afterN, newNode)) {
              break;
           }
        }
      }
    }

}

In insertAfter() method there is:

auto n = _next;
while (n && haslsb(n)) {
    n = n._next;
}
isn't this accessing member ._next of the invalid pointer 
(haslsb(n) == true)?

but what particularly I do not understand is in

//Step 2:
in removeAfter() method:

afterNext = thisNext._next;
while (!haslsb(afterNext))
{
     thisNext._next = thisNext._next.next;
}

it seems for me, that while cycle, if entered, will cycle 
forever... or is there a way how can be afterNext variable 
changed?

I think I understand rest of the code except these two parts.

Thanks a lot.

Ondrej
Aug 21 2012
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Aug 21 2012
prev sibling parent "Ondrej Pokorny" <pokorny.ondrej gmail.com> writes:
 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).
Aug 21 2012