Custom concurrent stack implementation in Java

Question

I don't want to use synchronized for sizeof method, any suggestion to implement the method thread safe?

package com.r.collection.adt;
import java.util.concurrent.atomic.AtomicReference;
public class ConcurrentStack<E> implements Stack<E>{
 @SuppressWarnings("hiding")
 private class Node<E>{
 public E item;
 public Node<E> next;
 public Node(E item){
 this.item=item;
 }
 }
 @SuppressWarnings("rawtypes")
 private AtomicReference<Node> head;
 @SuppressWarnings("rawtypes")
 ConcurrentStack(){
 head = new AtomicReference<Node>();
 }
 @SuppressWarnings("unchecked")
 @Override
 public void push(E item) {
 Node<E> newHead = new Node<E>(item);
 Node<E> headNode = null;
 do
 {
 headNode = head.get();
 newHead.next = headNode;
 }while(!head.compareAndSet(headNode, newHead));
 }
 @SuppressWarnings("unchecked")
 @Override
 public E pop() {
 Node<E> headNode = head.get();
 do
 {
 headNode = head.get();
 if(headNode == null)
 return null;
 }while(!head.compareAndSet(headNode, headNode.next));
 return headNode.item;
 }
 @SuppressWarnings("unchecked")
 @Override
 public E peek() {
 Node<E> headNode = head.get();
 if(headNode == null){
 return null;
 }
 return headNode.item;
 }
 @Override
 public boolean isEmpty() {
 return head.get() == null;
 }
 @SuppressWarnings("unchecked")
 @Override
 public synchronized int sizeOf() {
 int size=0;
 for(Node<E> node=head.get();node != null; node=node.next){
 size++;
 }
 return size;
 }
}

Answer 1

The synchronization you are currently using is not even working the way you intend to: as nothing else is synchronizing on this (like the sizeOf() method) you might as well not make the method synchronized.

You could stick a size field into your Node which gets set on inserting, something along the lines of this:

do {
 headNode = head.get();
 newHead.next = headNode;
 newHead.size = (headNode == null) ? 1 : headNode.size + 1;
} while (!head.compareAndSet(headNode, newHead));

This should allow reduction of the sizeOf() method to:

public int sizeOf() {
 return head.get().size;
}

• ganesh r: yes we can use size in Node class but it would be available in every node(every item) and occupy space.
• Bombe: Well, you haven’t mentioned that particular requirement. If you keep changing what you want nobody can help you. You either need to invest the space to save time, or you need to invest time to save space.
• ganesh r: am not changing my requirement. i want to implement size of method thread safe in better way.
• Bombe: And I just showed you how to do that.

Answer 2

Monitor

I suggest to think about your monitor.

As every method is working with the "head" variable every method should be synchronized. Either you make all methods "synchronized" or you introduce an internal lock object and use the "synchronized-block" construct in each method. If you do so you do not even need an "AtomicReference".

Synchronisation micro management

For the sake of clarity: Of course there may be several solutions with "micro-managed concurrency mechanisms" (volatile, several implementations of sets, maps, lists, stacks and queues) and they may be faster. But my way is to have the monitor clearly and transparently defined. And this transparency omits any concurrency elements that are different to the synchronized keyword. You should only left this path if you really need whatever you want to achieve (mostly performance). If you do so then you will open Pandora's box and you have to handle it. And what is even worse your collegues have to handle and maintain it too.

size-method

Your size-method is good. Either you are iterating or you formulate a recursive algorithm. As Java has no "tail recursion optimisation" and the stack count can exceed the JVM stack I would go for the iteration.

Generics

Try to get your Generics right and do not suppress "raw type warnings" as they are important indicators of design flaws.

Code

public class ConcurrentStack<E> implements Stack<E>{
 private class Node<T>{
 public T item;
 public Node<T> next;
 public Node(T item){
 this.item=item;
 }
 }
 private AtomicReference<Node<E>> head;
 ConcurrentStack(){
 head = new AtomicReference<Node<E>>();
 }
 @Override
 public synchronized void push(E item) {
 Node<E> newHead = new Node<E>(item);
 Node<E> headNode = null;
 do
 {
 headNode = head.get();
 newHead.next = headNode;
 }while(!head.compareAndSet(headNode, newHead));
 }
 @Override
 public synchronized E pop() {
 Node<E> headNode = head.get();
 do
 {
 headNode = head.get();
 if(headNode == null)
 return null;
 }while(!head.compareAndSet(headNode, headNode.next));
 return headNode.item;
 }
 @Override
 public synchronized E peek() {
 Node<E> headNode = head.get();
 if(headNode == null){
 return null;
 }
 return headNode.item;
 }
 @Override
 public synchronized boolean isEmpty() {
 return head.get() == null;
 }
 @Override
 public synchronized int sizeOf() {
 int size=0;
 for(Node<E> node=head.get();node != null; node=node.next){
 size++;
 }
 return size;
 }
}

The final step would be to get rid of the "AtomicReference".