Non-blocking queue in Java using AtomicStampedReference

So, I'll start by saying that this will be an assignment and there are several restrictions on the queue I need to build:

• It is unlimited.

• Blocking mechanisms are allowed (no synchronized
  
  , ReentrantLock
  
  etc.) {even to mimic things like CompareAndSet}.

• He must implement Michael and Scott's algorithm .

• Of course, I cannot rip off the Java source code for ConcurrentLinkedQueue
  
  .

Here's what I have so far (dequeue not counted):

public class LockFreeQueue<T> implements MyQueue<T>
{
    private class Node<R>
    {
        public final R value;
        public volatile AtomicReference<Node<R>> next;

        public Node()
        {
            value = null;
            next = new AtomicReference<Node<R>>(null);
        }

        public Node(R v)
        {
            value = v;
            next = new AtomicReference<Node<R>>(null);
        }
    }

    volatile AtomicStampedReference<Node<T>> head = new AtomicStampedReference<Node<T>>(new Node<T>(), 0);
    volatile AtomicStampedReference<Node<T>> tail = head;
    AtomicInteger count = new AtomicInteger(0);

    public boolean enq(T value)
    {
        Node<T> node = new Node<T>(value);

        while (true)
        {
            Node<T> tempTail = tail.getReference();
            int tailCount = tail.getStamp();
            Node<T> next = tempTail.next.get();
            if (tempTail == tail.getReference())
            {
                if (null == next)
                {
                    if(tempTail.next.compareAndSet(null, node))
                    {
                        // Problem on this line:
                        tail.compareAndSet(tempTail, node, tailCount, count.incrementAndGet());
                        return true;
                    }
                }
                else
                {
                    tail.compareAndSet(tempTail, next, tailCount, count.incrementAndGet());
                }
            }
        }
    }
...
}

      

        
        
        
      

    

Now, for the most part, this follows the code found in this IBM article . In particular, it follows the code in Listing 4. Insertion in the Michael-Scott nonblocking queue algorithm

. The problem that shows up in both my code and the code in the article is that when the link for the tail swings into a new tail, it does the same for the head. This does it, of course, because it is the change Node

that is being referenced, not the actual link, and the link that tail

both head

match.

I also found another solution , but the main problem with this code is what it uses synchronized

, although it only does it to simulate the CAS operation.

As far as Java is concerned ConcurrentLinkedQueue

, I noticed what they are using AtomicReferenceUpdater

and this seems to be the only way. The problem here, however, is that my code is starting to look surprisingly close to Java, and I don't want to end up with plagiarism (or worse!).

Is there the AtomicReferenceUpdater

only way for me to move forward, or are there other things I can do?

One final note:

• Node
  
  is a complete property, so it can change to be what it should be.

Edit:

Ben Manes noted that there is no need to worry about the ABA problem in a language with garbage collection. For those interested in this in the future, this article is a pleasant read. An important part:

This is not a problem in garbage collection. What for? Since the memory of a node cannot be reclaimed for a new object until observations containing pointers to the structure are found.