simqueu2.java

public E dequeue(final int tid) {
    DeqState<E> lstate = deqState;
    // Start by checking if the queue is empty
    if (lstate.head.next == null) return null;
    // Publish dequeue request
    final int newrequest = (lstate.applied[tid]+1) % 2;
    dequeuers.set(tid, newrequest);
    for (int iter = 0; iter < 2; iter++) {
        lstate = deqState;
        if (lstate.applied[tid] == newrequest) break;
        // Help opened dequeue requests, starting from turn+1
        Node<E> newHead = lstate.head;
        int newTurn = lstate.turn;
        E[] items = lstate.items.clone();
        int[] applied = lstate.applied.clone();
        Node<E> node = lstate.head;            
        for (int j = 1; j < maxThreads+1; j++) {
            final int i = (j + lstate.turn) % maxThreads;
            // Check if it is an open request
            if (dequeuers.get(i) == applied[i]) continue;
            applied[i] = (applied[i]+1) % 2;
            final Node<E> lnext = node.next;
            if (lnext == null) {
                items[i] = null;
            } else {
                node = lnext;
                items[i] = node.item;
                newHead = node;
                newTurn = i;
            }
            if (lstate != deqState) break;
        }
        if (lstate != deqState) continue;
        if (casDeqState(lstate, new DeqState<E>(newHead, newTurn, items, applied))) break; 
    }
    return deqState.items[tid];
}