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
