Code Understanding Issues

Question

I read the source code this morning when I came across a sample C # code that I don't understand:

public bool Dequeue(out T value) { Node head; Node tail; Node next; while (true) { // read head head = this.head; tail = this.tail; next = head.Next; // Are head, tail, and next consistent? if (Object.ReferenceEquals(this.head, head)) { // Source code continues here... } // And here... } } 

On line, I have a problem with what Object.ReferenceEquals() contains.

If I understand well, the author of the source code wants to compare this.head and head , but in the lines above, he simply wrote head = this.head .

Based on the background of C++ , this statement makes no sense to me. Moreover, on some events, it seems that the Object.ReferenceEquals() throws a System.NullReferenceException , so it is doing something, I just can’t understand that.

Can you help me understand what this line does and maybe why?

If you need it, here is the definition of the Node class (I think this is the "template" class, not sure about the wording for C #):

 private class Node { public T Value; public Node Next; public Node(T value) { this.Value = value; } } 

Thanks.

Edit: the rest of the method for those who asked

  public void Enqueue(T value) { // Allocate a new node from the free list Node valueNode = new Node(value); while (true) { Node tail = this.tail; Node next = tail.Next; // are tail and next consistent if (Object.ReferenceEquals(tail, this.tail)) { // was tail pointing to the last node? if (Object.ReferenceEquals(next, null)) { if (Object.ReferenceEquals( Interlocked.CompareExchange(ref tail.Next, valueNode, next), next ) ) { Interlocked.CompareExchange(ref this.tail, valueNode, tail); break; } } else // tail was not pointing to last node { // try to swing Tail to the next node Interlocked.CompareExchange<Node>(ref this.tail, next, tail); } } } } 

Answer 1

he just wrote head = this.head

This is the purpose, and it is related to their comparison. Note that this is about the head field and the local var this.head .

if (Object.ReferenceEquals (this.head, head))

Here, the author wants to compare this.head and head , making sure that equality is based on their links (addresses), and not on any (possible) overload == and Equals()

I assume that the local var head changes inside the loop, which makes it a controversial naming convention.

Answer 2

Looks like a linked list. Dequeue looks like a recursive function. Thus, either the “Next” does something with the “head” part of the node, or works in parallel, and it tries to check if everything is somewhere where it is before continuing. The last part is not executed correctly, since you must use the semaphore when entering the critical section, otherwise you will encounter the conditions of the race, and this will work sooner or later.

Answer 3

If this.head and this.tail are publicly available, they can be changed while the loop is running. Object.ReferenceEquals checks if they are the same as when executing the method.

It is difficult to give a more complete answer without the whole class / context.

Answer 4

ReferenceEquals is a function that is used to verify that two instances of an object are the same object, not just two objects that have the same value. Documentation can be found here ( http://msdn.microsoft.com/en-us/library/system.object.referenceequals.aspx ). As for the purpose of this statement, if this code is executed in a multi-threaded context, it may try to ensure that no one is bothering with it because it is (very dangerous), or worried that someone passed the value type (dangerous, but better to check).

EDIT: With further code submitted, this is similar to the first. He uses ReferenceEquals to try and catch his race conditions when there are multiple threads (if he was not multi-threaded, he would not have to worry about InterlockedExchange). The code seems to be basically trying to perform the operation, and if someone changed the horses on it in the middle of the stream, just try again (while (true)). Perhaps it would be more elegant to use a critical section or semaphore so that no one changes your values, but just hopes that you can check if they have any. The reason for this is AFTER IF, but BEFORE InterlockedExchange, someone may change your values, which leads to an error.

Answer 5

The Interlocked.CompareExchange method is used to provide stream comparisons and replacements - this means that this method should be able to handle cases when the queue is modified by external threads. The if tries to handle cases where the list has been modified by other threads.