| |
| Posted by Ondrej Pokorny | PermalinkReply |
|
Ondrej Pokorny
| 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
}
}
|