Differences

This shows you the differences between two versions of the page.

--- stack [2007/10/28 15:28] – created franck
+++ stack [2007/10/28 16:43] (current) – franck
@@ Line 160: / Line 160: @@
 </code>
+The third implementation does not use any locking.  We exploit the class AtomicReference.
+<code java>
+import java.util.concurrent.atomic.*;
+public class Stack3 implements Stack
+{
+  private volatile AtomicReference<Node> top;
+  /**
+   * Creates an empty stack.
+   */
+  public Stack3()
+  {
+    this.top = new AtomicReference<Node>();
+  }
+  public Integer pop() throws EmptyException
+  {
+    Node node;
+    do
+    {
+      node = this.top.get();
+      if (node == null)
+      {
+        throw new EmptyException();
+      }
+    }
+    while (!this.top.compareAndSet(node, node.getNext()));
+    return node.getElement();
+  }
+  public void push(Integer element)
+  {
+    Node node = new Node(element, null);
+    do
+    {
+      node.setNext(this.top.get());
+    }
+    while (!this.top.compareAndSet(node.getNext(), node));
+  }
+}
+</code>
+Also the fourth implementation does not use any locking.  This time we exploit the class AtomicReferenceFieldUpdater.
+<code java>
+import java.util.concurrent.atomic.*;
+public class Stack4 implements Stack
+{
+  private volatile Node top;
+  private static final AtomicReferenceFieldUpdater<Stack4, Node> topUpdater = AtomicReferenceFieldUpdater.newUpdater(Stack\
+.class, Node.class, "top");
+  /**
+   * Creates an empty stack.
+   */
+  public Stack4()
+  {
+    this.top = null;
+  }
+  public Integer pop() throws EmptyException
+  {
+    Node node;
+    do
+    {
+      node = this.top;
+      if (node == null)
+      {
+        throw new EmptyException();
+      }
+    } while (!Stack4.topUpdater.compareAndSet(this, node, node.getNext()));
+    return node.getElement();
+  }
+  public void push(Integer element)
+  {
+    Node node = new Node(element, null);
+    do
+    {
+        node.setNext(this.top);
+    }
+    while (!Stack4.topUpdater.compareAndSet(this, node.getNext(), node));
+  }
+}
+</code>