chapter 10 source code LockFreeQueue.java

Showing 1-1 of 1 messages
chapter 10 source code LockFreeQueue.java Paolo Bonzini 8/2/09 2:58 PM
The file in the chapter 10 zip file is a copy of DCASQueue.  Here is
what I put together by removing stamping from LockFreeQueueRecycle
(I'm travelling and don't have the book with me).

/*
 * LockFreeQueue.java
 *
 * Created on March 10, 2006, 9:05 AM
 *
 * From "Multiprocessor Synchronization and Concurrent Data
Structures",
 * by Maurice Herlihy and Nir Shavit.
 * Copyright 2006 Elsevier Inc. All rights reserved.
 */

package queue;

import java.util.concurrent.atomic.AtomicReference;
/**
 * Lock-free queue.
 * Based on Michael and Scott http://doi.acm.org/10.1145/248052.248106
 * @author Maurice Herlihy
 */
public class LockFreeQueue<T> {
  private AtomicReference<Node> head;
  private AtomicReference<Node> tail;

  /**
   * Create a new object of this class.
   */
  public LockFreeQueue() {
    Node sentinel = new Node(null);
    head = new AtomicReference<Node>(sentinel);
    tail = new AtomicReference<Node>(sentinel);
  }
  /**
   * Enqueue an item.
   * @param value Item to enqueue.
   */
  public void enq(T value) {
    // try to allocate new node from local pool
    Node node = new Node(value);
    while (true) {                 // keep trying
      Node last = tail.get();    // read tail
      Node next = last.next.get(); // read next
      // are they consistent?
      if (last == tail.get()) {
        if (next == null) {        // was tail the last node?
          // try to link node to end of list
          if (last.next.compareAndSet(next, node) {
            // enq done, try to advance tail
            tail.compareAndSet(last, node);
            return;
          }
        } else {                // tail was not the last node
          // try to swing tail to next node
          tail.compareAndSet(last, next);
        }
      }
    }
  }
  /**
   * Dequeue an item.
   * @throws queue.EmptyException The queue is empty.
   * @return Item at the head of the queue.
   */
  public T deq() throws EmptyException {
    while (true) {
      Node first = head.get();
      Node last = tail.get();
      Node next = first.next.get();
      // are they consistent?
      if (first == head.get()) {
        if (first == last) {        // is queue empty or tail falling behind?
          if (next == null) {        // is queue empty?
            throw new EmptyException();
          }
          // tail is behind, try to advance
          tail.compareAndSet(last, next);
        } else {
          T value = next.value; // read value before dequeuing
          if (head.compareAndSet(first, next)) {
            return value;
          }
        }
      }
    }
  }
  /**
   * Items are kept in a list of nodes.
   */
  public class Node {
    /**
     * Item kept by this node.
     */
    public T value;
    /**
     * Next node in the queue.
     */
    public AtomicReference<Node> next;

    /**
     * Create a new node.
     */
    public Node(T value) {
      this.next  = new AtomicReference<Node>(null);
      this.value = value;
    }
  }
}