001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.mmtk.utility.deque;
014
015import static org.mmtk.utility.Constants.*;
016
017import org.mmtk.vm.VM;
018
019import org.vmmagic.unboxed.*;
020import org.vmmagic.pragma.*;
021
022/**
023 * Note this may perform poorly when being used as a FIFO structure with
024 * insertHead and pop operations operating on the same buffer.  This
025 * only uses the fields inherited from <code>LocalQueue</code>, but adds
026 * the ability for entries to be added to the head of the deque and popped
027 * from the rear.
028 */
029@Uninterruptible public class LocalDeque extends LocalQueue {
030
031  /****************************************************************************
032   *
033   * Public instance methods
034   */
035
036  /**
037   * Constructor
038   *
039   * @param queue The shared deque to which this local deque will append
040   * its buffers (when full or flushed).
041   */
042  LocalDeque(SharedDeque queue) {
043    super(queue);
044  }
045
046  @Override
047  public final void flushLocal() {
048    super.flushLocal();
049    if (head.NE(Deque.HEAD_INITIAL_VALUE)) {
050      closeAndInsertHead(queue.getArity());
051      head = Deque.HEAD_INITIAL_VALUE;
052    }
053  }
054
055  /****************************************************************************
056   *
057   * Protected instance methods
058   */
059
060  /**
061   * Check whether there is space in the buffer for a pending insert.
062   * If there is not sufficient space, allocate a new buffer
063   * (dispatching the full buffer to the shared deque if not null).
064   *
065   * @param arity The arity of the values stored in this deque: the
066   * buffer must contain enough space for this many words.
067   */
068  @Inline
069  protected final void checkHeadInsert(int arity) {
070    if (bufferOffset(head).EQ(bufferSentinel(arity)) ||
071        head.EQ(HEAD_INITIAL_VALUE))
072      headOverflow(arity);
073    else if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bufferOffset(head).sLE(bufferLastOffset(arity)));
074  }
075
076  /**
077   * Insert a value at the front of the deque (and buffer).  This is
078   * <i>unchecked</i>.  The caller must first call
079   * <code>checkHeadInsert()</code> to ensure the buffer can accommodate
080   * the insertion.
081   *
082   * @param value the value to be inserted.
083   */
084  @Inline
085  protected final void uncheckedHeadInsert(Address value) {
086      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bufferOffset(head).sLT(bufferSentinel(queue.getArity())));
087    head.store(value);
088    head = head.plus(BYTES_IN_ADDRESS);
089    // if (Interface.VerifyAssertions) enqueued++;
090  }
091
092  /****************************************************************************
093   *
094   * Private instance methods and fields
095   */
096
097  /**
098   * Buffer space has been exhausted, allocate a new buffer and enqueue
099   * the existing buffer (if any).
100   *
101   * @param arity The arity of this buffer (used for sanity test only).
102   */
103  private void headOverflow(int arity) {
104    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(arity == queue.getArity());
105    if (head.NE(Deque.HEAD_INITIAL_VALUE))
106      closeAndInsertHead(arity);
107
108    head = queue.alloc();
109  }
110
111  /**
112   * Close the head buffer and enqueue it at the front of the
113   * shared buffer deque.
114   *
115   *  @param arity The arity of this buffer.
116   */
117  @Inline
118  private void closeAndInsertHead(int arity) {
119    queue.enqueue(head, arity, false);
120  }
121
122  /**
123   * The tail is empty (or {@code null}), and the shared deque has no buffers
124   * available.  If the head has sufficient entries, consume the head.
125   * Otherwise try wait on the shared deque until either all other
126   * clients of the reach exhaustion or a buffer becomes
127   * available.
128   *
129   * @param arity The arity of this buffer
130   * @return {@code true} if the consumer has eaten all of the entries
131   */
132  @SuppressWarnings("unused")
133  private boolean tailStarved(int arity) {
134    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(arity == queue.getArity());
135    // entries in tail, so consume tail
136    if (!bufferOffset(head).isZero()) {
137      tailBufferEnd = head;
138      tail = bufferStart(tailBufferEnd);
139      head = Deque.HEAD_INITIAL_VALUE;
140      return false;
141    }
142
143    // Wait for another entry to materialize...
144    tailBufferEnd = queue.dequeueAndWait(arity, true);
145    tail = bufferStart(tail);
146
147    // return true if a) there is not a tail buffer or b) it is empty
148    return (tail.EQ(Deque.TAIL_INITIAL_VALUE) || tail.EQ(tailBufferEnd));
149  }
150}