Java Vyukov MPSC

gistfile1.java

class MpscQueue<T> {
  // This song and dance is required to get field offset which we need for getAndSet
  private static final long HEAD_FIELD_OFFSET;
  static {
    try {
      HEAD_FIELD_OFFSET = UNSAFE.objectFieldOffset(MpscQueue.class.getDeclaredField("head"));
    } catch (NoSuchFieldException e) {
      throw new RuntimeException(e);
    }
  }
  static class Node<T> {
    T val;
    // C 'volatile' is not the same as Java 'volatile', but in this case they happen to
    // apply to the same fields.
    volatile Node<T> next;
  }
  
  volatile Node<T> head;
  Node<T> tail;

  MpscQueue() {
    head = tail = new Node<T>();
  }

  public boolean offer(T val) {
    if (val == null) throw new IllegalArgumentException("You bastard!!!");
    Node<T> n = new Node<T>();
    n.val = val;
    // getAndSet acts as an effective StoreLoad[0]
    // see https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/package-summary.html
    // The LOCK XCHG mechanics create the ordering between producers, hence Vyukov comment on
    // serialization.
    Node<T> prev = (Node<T>) UNSAFE.getAndSetObject(this, HEAD_FIELD_OFFSET, n); 
    // StoreLoad[1] (StoreStore would do we can weaken this write to a lazySet/putOrdered)
    prev.next = n;
    return true;
  }

  public T poll() {
    // LoadLoad matching StoreLoad[1]
    Node<T> next = tail.next;
    // this establishes the HB relationship between producer and consumer
    if (next != null) {
      T val = next.val;
      next.val = null;
      tail = next;
      return val;
    }
    return null;
  }
}