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 */
013 package org.mmtk.utility.deque;
014
015 import org.mmtk.utility.Constants;
016
017 import org.mmtk.vm.VM;
018
019 import org.vmmagic.unboxed.*;
020 import 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 implements Constants {
031
032 /****************************************************************************
033 *
034 * Public instance methods
035 */
036
037 /**
038 * Constructor
039 *
040 * @param queue The shared deque to which this local deque will append
041 * its buffers (when full or flushed).
042 */
043 LocalDeque(SharedDeque queue) {
044 super(queue);
045 }
046
047 @Override
048 public final void flushLocal() {
049 super.flushLocal();
050 if (head.NE(Deque.HEAD_INITIAL_VALUE)) {
051 closeAndInsertHead(queue.getArity());
052 head = Deque.HEAD_INITIAL_VALUE;
053 }
054 }
055
056 /****************************************************************************
057 *
058 * Protected instance methods
059 */
060
061 /**
062 * Check whether there is space in the buffer for a pending insert.
063 * If there is not sufficient space, allocate a new buffer
064 * (dispatching the full buffer to the shared deque if not null).
065 *
066 * @param arity The arity of the values stored in this deque: the
067 * buffer must contain enough space for this many words.
068 */
069 @Inline
070 protected final void checkHeadInsert(int arity) {
071 if (bufferOffset(head).EQ(bufferSentinel(arity)) ||
072 head.EQ(HEAD_INITIAL_VALUE))
073 headOverflow(arity);
074 else if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bufferOffset(head).sLE(bufferLastOffset(arity)));
075 }
076
077 /**
078 * Insert a value at the front of the deque (and buffer). This is
079 * <i>unchecked</i>. The caller must first call
080 * <code>checkHeadInsert()</code> to ensure the buffer can accommodate
081 * the insertion.
082 *
083 * @param value the value to be inserted.
084 */
085 @Inline
086 protected final void uncheckedHeadInsert(Address value) {
087 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bufferOffset(head).sLT(bufferSentinel(queue.getArity())));
088 head.store(value);
089 head = head.plus(BYTES_IN_ADDRESS);
090 // if (Interface.VerifyAssertions) enqueued++;
091 }
092
093 /****************************************************************************
094 *
095 * Private instance methods and fields
096 */
097
098 /**
099 * Buffer space has been exhausted, allocate a new buffer and enqueue
100 * the existing buffer (if any).
101 *
102 * @param arity The arity of this buffer (used for sanity test only).
103 */
104 private void headOverflow(int arity) {
105 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(arity == queue.getArity());
106 if (head.NE(Deque.HEAD_INITIAL_VALUE))
107 closeAndInsertHead(arity);
108
109 head = queue.alloc();
110 }
111
112 /**
113 * Close the head buffer and enqueue it at the front of the
114 * shared buffer deque.
115 *
116 * @param arity The arity of this buffer.
117 */
118 @Inline
119 private void closeAndInsertHead(int arity) {
120 queue.enqueue(head, arity, false);
121 }
122
123 /**
124 * The tail is empty (or {@code null}), and the shared deque has no buffers
125 * available. If the head has sufficient entries, consume the head.
126 * Otherwise try wait on the shared deque until either all other
127 * clients of the reach exhaustion or a buffer becomes
128 * available.
129 *
130 * @param arity The arity of this buffer
131 * @return {@code true} if the consumer has eaten all of the entries
132 */
133 @SuppressWarnings("unused")
134 private boolean tailStarved(int arity) {
135 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(arity == queue.getArity());
136 // entries in tail, so consume tail
137 if (!bufferOffset(head).isZero()) {
138 tailBufferEnd = head;
139 tail = bufferStart(tailBufferEnd);
140 head = Deque.HEAD_INITIAL_VALUE;
141 return false;
142 }
143
144 // Wait for another entry to materialize...
145 tailBufferEnd = queue.dequeueAndWait(arity, true);
146 tail = bufferStart(tail);
147
148 // return true if a) there is not a tail buffer or b) it is empty
149 return (tail.EQ(Deque.TAIL_INITIAL_VALUE) || tail.EQ(tailBufferEnd));
150 }
151 }