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.jikesrvm.scheduler;
014
015 import org.jikesrvm.VM;
016 import org.vmmagic.pragma.NonMoving;
017 import org.vmmagic.pragma.Uninterruptible;
018 import org.vmmagic.pragma.Untraced;
019 import org.jikesrvm.runtime.Magic;
020
021 /**
022 * An unsynchronized queue data structure for Threads. The current uses are all
023 * where there is some other lock that already protects the queue.
024 */
025 @Uninterruptible
026 @NonMoving
027 public class ThreadQueue {
028 protected static final boolean trace = false;
029
030 @Untraced RVMThread head;
031
032 @Untraced RVMThread tail;
033
034 public ThreadQueue() {
035 }
036
037 public boolean isEmpty() {
038 return head == null;
039 }
040
041 public void enqueue(RVMThread t) {
042 if (trace) {
043 VM.sysWriteln("enqueueing ", t.getThreadSlot(), " onto ",
044 Magic.objectAsAddress(this));
045 }
046 if (VM.VerifyAssertions)
047 VM._assert(t.queuedOn == null);
048 t.next = null;
049 if (tail == null) {
050 head = t;
051 } else {
052 tail.next = t;
053 }
054 tail = t;
055 t.queuedOn = this;
056 }
057
058 public RVMThread peek() {
059 return head;
060 }
061
062 public RVMThread dequeue() {
063 RVMThread result = head;
064 if (result != null) {
065 head = result.next;
066 if (head == null) {
067 tail = null;
068 }
069 if (VM.VerifyAssertions)
070 VM._assert(result.queuedOn == this);
071 result.next = null;
072 result.queuedOn = null;
073 }
074 if (trace) {
075 if (result == null) {
076 VM.sysWriteln("dequeueing null from ", Magic.objectAsAddress(this));
077 } else {
078 VM.sysWriteln("dequeueing ", result.getThreadSlot(), " from ",
079 Magic.objectAsAddress(this));
080 }
081 }
082 return result;
083 }
084
085 /**
086 * Private helper. Gets the next pointer of cur unless cur is {@code null}, in which
087 * case it returns head.
088 */
089 private RVMThread getNext(RVMThread cur) {
090 if (cur == null) {
091 return head;
092 } else {
093 return cur.next;
094 }
095 }
096
097 /**
098 * Private helper. Sets the next pointer of cur to value unless cur is {@code null},
099 * in which case it sets head. Also sets tail as appropriate.
100 */
101 private void setNext(RVMThread cur, RVMThread value) {
102 if (cur == null) {
103 if (tail == head) {
104 tail = value;
105 }
106 head = value;
107 } else {
108 if (cur == tail) {
109 tail = value;
110 }
111 cur.next = value;
112 }
113 }
114
115 /**
116 * Remove the given thread from the queue if the thread is still on the queue.
117 * Does nothing (and returns in O(1)) if the thread is not on the queue. Also
118 * does nothing (and returns in O(1)) if the thread is on a different queue.
119 */
120 public boolean remove(RVMThread t) {
121 if (t.queuedOn != this)
122 return false;
123 if (trace) {
124 VM.sysWriteln("removing ", t.getThreadSlot(), " from ",
125 Magic.objectAsAddress(this));
126 }
127 for (RVMThread cur = null; cur != tail; cur = getNext(cur)) {
128 if (getNext(cur) == t) {
129 if (trace) {
130 VM.sysWriteln("found! before:");
131 dump();
132 }
133 setNext(cur, t.next);
134 if (tail == t) {
135 tail = cur;
136 }
137 if (trace) {
138 VM.sysWriteln("after:");
139 dump();
140 }
141 t.next = null;
142 t.queuedOn = null;
143 return true;
144 }
145 }
146 VM.sysWriteln("Could not remove Thread #", t.getThreadSlot(),
147 " from queue!");
148 dump();
149 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
150 return false; // make javac happy
151 }
152
153 public boolean isQueued(RVMThread t) {
154 return t.queuedOn == this;
155 }
156
157 public void dump() {
158 boolean pastFirst = false;
159 for (RVMThread t = head; t != null; t = t.next) {
160 if (pastFirst) {
161 VM.sysWrite(" ");
162 }
163 t.dump();
164 pastFirst = true;
165 }
166 VM.sysWrite("\n");
167 if (head != null) {
168 VM.sysWriteln("head: ", head.getThreadSlot());
169 } else {
170 VM.sysWriteln("head: null");
171 }
172 if (tail != null) {
173 VM.sysWriteln("tail: ", tail.getThreadSlot());
174 } else {
175 VM.sysWriteln("tail: null");
176 }
177 }
178 }