View mode: basic / threaded / horizontal-split · Log in · Help
August 21, 2012
D language book errata + chapter 13. SharedList code listing confusion
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
  }
}
August 21, 2012
Re: D language book errata + chapter 13. SharedList code listing confusion
Could you remove this double repost please?

Thanks.

Ondrej
August 21, 2012
Re: D language book errata + chapter 13. SharedList code listing confusion
Ignore this doulbe post, please.

Ondrej
Top | Discussion index | About this forum | D home