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.jikesrvm.scheduler;
014
015import org.jikesrvm.VM;
016import org.vmmagic.pragma.NonMoving;
017import org.vmmagic.pragma.Uninterruptible;
018import org.vmmagic.pragma.Untraced;
019import 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
027public 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   * @param cur a thread
087   * @return the next pointer of cur unless cur is {@code null}, in which
088   * case it returns head.
089   */
090  private RVMThread getNext(RVMThread cur) {
091    if (cur == null) {
092      return head;
093    } else {
094      return cur.next;
095    }
096  }
097
098  /**
099   * Sets the next pointer of cur to value unless cur is {@code null},
100   * in which case it sets head. Also sets tail as appropriate.
101   *
102   * @param cur a thread
103   * @param value a value for the next pointer of the given thread
104   */
105  private void setNext(RVMThread cur, RVMThread value) {
106    if (cur == null) {
107      if (tail == head) {
108        tail = value;
109      }
110      head = value;
111    } else {
112      if (cur == tail) {
113        tail = value;
114      }
115      cur.next = value;
116    }
117  }
118
119  /**
120   * Removes the given thread from the queue if the thread is still on the queue.
121   * Does nothing (and returns in O(1)) if the thread is not on the queue. Also
122   * does nothing (and returns in O(1)) if the thread is on a different queue.
123   *
124   * @param t thread to remove from the queue
125   * @return whether the given thread was removed from the queue
126   */
127  public boolean remove(RVMThread t) {
128    if (t.queuedOn != this)
129      return false;
130    if (trace) {
131      VM.sysWriteln("removing ", t.getThreadSlot(), " from ",
132          Magic.objectAsAddress(this));
133    }
134    for (RVMThread cur = null; cur != tail; cur = getNext(cur)) {
135      if (getNext(cur) == t) {
136        if (trace) {
137          VM.sysWriteln("found!  before:");
138          dump();
139        }
140        setNext(cur, t.next);
141        if (tail == t) {
142          tail = cur;
143        }
144        if (trace) {
145          VM.sysWriteln("after:");
146          dump();
147        }
148        t.next = null;
149        t.queuedOn = null;
150        return true;
151      }
152    }
153    VM.sysWriteln("Could not remove Thread #", t.getThreadSlot(),
154        " from queue!");
155    dump();
156    if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED);
157    return false;
158  }
159
160  public boolean isQueued(RVMThread t) {
161    return t.queuedOn == this;
162  }
163
164  public void dump() {
165    boolean pastFirst = false;
166    for (RVMThread t = head; t != null; t = t.next) {
167      if (pastFirst) {
168        VM.sysWrite(" ");
169      }
170      t.dump();
171      pastFirst = true;
172    }
173    VM.sysWrite("\n");
174    if (head != null) {
175      VM.sysWriteln("head: ", head.getThreadSlot());
176    } else {
177      VM.sysWriteln("head: null");
178    }
179    if (tail != null) {
180      VM.sysWriteln("tail: ", tail.getThreadSlot());
181    } else {
182      VM.sysWriteln("tail: null");
183    }
184  }
185}