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

Ondrej Pokorny pokorny.ondrej at gmail.com
Tue Aug 21 00:21:31 PDT 2012


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




More information about the Digitalmars-d mailing list