/**
 * Copyright (C) 2012 - present by OpenGamma Inc. and the OpenGamma group of companies
 *
 * Please see distribution for license.
 */
package com.opengamma.engine.depgraph;

import java.util.Iterator;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Run queue implementation based on a stack. This is a LIFO queue which may give good performance as computation targets often end up grouped together.
 */
/* package */final class StackRunQueue implements RunQueue {

  private static final class Element {

    private volatile ContextRunnable _runnable;
    private volatile Element _next;

    private Element(final ContextRunnable runnable, final Element next) {
      _runnable = runnable;
      _next = next;
    }

  }

  private final AtomicReference<Element> _head = new AtomicReference<Element>();
  private final AtomicReference<Element> _free = new AtomicReference<Element>();

  @Override
  public boolean isEmpty() {
    return _head.get() == null;
  }

  @Override
  public int size() {
    Element e = _head.get();
    int count = 0;
    while (e != null) {
      count++;
      e = e._next;
    }
    return count;
  }

  @Override
  public Iterator<ContextRunnable> iterator() {
    return new Iterator<ContextRunnable>() {

      private Element _ptr = _head.get();

      @Override
      public boolean hasNext() {
        return _ptr != null;
      }

      @Override
      public ContextRunnable next() {
        Element ptr = _ptr;
        _ptr = ptr._next;
        return ptr._runnable;
      }

      @Override
      public void remove() {
        throw new UnsupportedOperationException();
      }

    };
  }

  @Override
  public void add(final ContextRunnable runnable) {
    Element e = _free.get();
    if (e != null) {
      if (_free.compareAndSet(e, e._next)) {
        e._next = _head.get();
        e._runnable = runnable;
      } else {
        e = new Element(runnable, _head.get());
      }
    } else {
      e = new Element(runnable, _head.get());
    }
    while (!_head.compareAndSet(e._next, e)) {
      e._next = _head.get();
    }
  }

  @Override
  public ContextRunnable take() {
    Element e;
    do {
      e = _head.get();
      if (e == null) {
        return null;
      }
    } while (!_head.compareAndSet(e, e._next));
    final ContextRunnable runnable = e._runnable;
    e._runnable = null;
    e._next = _free.get();
    _free.compareAndSet(e._next, e);
    return runnable;
  }
}

@@ -171,16 +171,40 @@
 graph;%0A%0A
+import java.util.Deque;%0A
 import j
@@ -254,29 +254,28 @@
 ent.
-atomic.AtomicReferenc
+ConcurrentLinkedDequ
 e;%0A%0A
@@ -511,59 +511,20 @@
 ate 
-static final class Element %7B%0A%0A    private volatile 
+final Deque%3C
 Cont
@@ -538,348 +538,60 @@
 able
+%3E
  _
-runnable;%0A    private volatile Element _next;%0A%0A    private Element(final ContextRunnable runnable, final Element next) %7B%0A      _runnable = runnable;%0A      _next = next;%0A    %7D%0A%0A  %7D%0A%0A  private final AtomicReference%3CElement%3E _head = new AtomicReference%3CElement%3E();%0A  private final AtomicReference%3CElement%3E _free = new AtomicReference%3CElement
+deque = new ConcurrentLinkedDeque%3CContextRunnable
 %3E();
@@ -649,26 +649,23 @@
 rn _
-head.get() == null
+deque.isEmpty()
 ;%0A  
@@ -709,1434 +709,303 @@
     
-Element e = _head.get();%0A    int count = 0;%0A    while (e != null) %7B%0A      count++;%0A      e = e._next;%0A    %7D%0A    return count;%0A  %7D%0A%0A  @Override%0A  public Iterator%3CContextRunnable%3E iterator() %7B%0A    return new Iterator%3CContextRunnable%3E() %7B%0A%0A      private Element _ptr = _head.get();%0A%0A      @Override%0A      public boolean hasNext() %7B%0A        return _ptr != null;%0A      %7D%0A%0A      @Override%0A      public ContextRunnable next() %7B%0A        Element ptr = _ptr;%0A        _ptr = ptr._next;%0A        return ptr._runnable;%0A      %7D%0A%0A      @Override%0A      public void remove() %7B%0A        throw new UnsupportedOperationException();%0A      %7D%0A%0A    %7D;%0A  %7D%0A%0A  @Override%0A  public void add(final ContextRunnable runnable) %7B%0A    Element e = _free.get();%0A    if (e != null) %7B%0A      if (_free.compareAndSet(e, e._next)) %7B%0A        e._next = _head.get();%0A        e._runnable = runnable;%0A      %7D else %7B%0A        e = new Element(runnable, _head.get());%0A      %7D%0A    %7D else %7B%0A      e = new Element(runnable, _head.get());%0A    %7D%0A    while (!_head.compareAndSet(e._next, e)) %7B%0A      e._next = _head.get();%0A    %7D%0A  %7D%0A%0A  @Override%0A  public ContextRunnable take() %7B%0A    Element e;%0A    do %7B%0A      e = _head.get();%0A      if (e == null) %7B%0A        return null;%0A      %7D%0A    %7D while (!_head.compareAndSet(e, e._next));%0A    final ContextRunnable runnable = e._runnable;%0A    e._runnable = null;%0A    e._next = _free.get();%0A    _free.compareAndSet(e._next, e);%0A    return runnable
+return _deque.size();%0A  %7D%0A%0A  @Override%0A  public Iterator%3CContextRunnable%3E iterator() %7B%0A    return _deque.iterator();%0A  %7D%0A%0A  @Override%0A  public void add(final ContextRunnable runnable) %7B%0A    _deque.addLast(runnable);%0A  %7D%0A%0A  @Override%0A  public ContextRunnable take() %7B%0A    return _deque.pollLast()
 ;%0A  

Use slower, but correct, linked list to support the stack. Previous method does not handle ABA case.