digitalmars.D - D language book errata + chapter 13. SharedList code listing confusion
- Ondrej Pokorny (64/64) Aug 21 2012 Hi,
- Ondrej Pokorny (3/3) Aug 21 2012 Could you remove this double repost please?
- Ondrej Pokorny (2/2) Aug 21 2012 Ignore this doulbe post, please.
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. Could possibly someone give me a hand and helps 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; } } } } private Node * _root; void pushFront(T value) { ... // Same as for Stack.push } shared(T)* popFront() { ... // Same as for Stack.pop } }
Aug 21 2012
Could you remove this double repost please? Thanks. Ondrej
Aug 21 2012
Ignore this doulbe post, please. Ondrej
Aug 21 2012