J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1999-2007 Sun Microsystems, Inc. All Rights Reserved. |
| 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 | * |
| 5 | * This code is free software; you can redistribute it and/or modify it |
| 6 | * under the terms of the GNU General Public License version 2 only, as |
| 7 | * published by the Free Software Foundation. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun in the LICENSE file that accompanied this code. |
| 10 | * |
| 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
| 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 14 | * version 2 for more details (a copy is included in the LICENSE file that |
| 15 | * accompanied this code). |
| 16 | * |
| 17 | * You should have received a copy of the GNU General Public License version |
| 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
| 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| 20 | * |
| 21 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any questions. |
| 24 | */ |
| 25 | |
| 26 | package java.util; |
| 27 | import java.util.Date; |
| 28 | |
| 29 | /** |
| 30 | * A facility for threads to schedule tasks for future execution in a |
| 31 | * background thread. Tasks may be scheduled for one-time execution, or for |
| 32 | * repeated execution at regular intervals. |
| 33 | * |
| 34 | * <p>Corresponding to each <tt>Timer</tt> object is a single background |
| 35 | * thread that is used to execute all of the timer's tasks, sequentially. |
| 36 | * Timer tasks should complete quickly. If a timer task takes excessive time |
| 37 | * to complete, it "hogs" the timer's task execution thread. This can, in |
| 38 | * turn, delay the execution of subsequent tasks, which may "bunch up" and |
| 39 | * execute in rapid succession when (and if) the offending task finally |
| 40 | * completes. |
| 41 | * |
| 42 | * <p>After the last live reference to a <tt>Timer</tt> object goes away |
| 43 | * <i>and</i> all outstanding tasks have completed execution, the timer's task |
| 44 | * execution thread terminates gracefully (and becomes subject to garbage |
| 45 | * collection). However, this can take arbitrarily long to occur. By |
| 46 | * default, the task execution thread does not run as a <i>daemon thread</i>, |
| 47 | * so it is capable of keeping an application from terminating. If a caller |
| 48 | * wants to terminate a timer's task execution thread rapidly, the caller |
| 49 | * should invoke the timer's <tt>cancel</tt> method. |
| 50 | * |
| 51 | * <p>If the timer's task execution thread terminates unexpectedly, for |
| 52 | * example, because its <tt>stop</tt> method is invoked, any further |
| 53 | * attempt to schedule a task on the timer will result in an |
| 54 | * <tt>IllegalStateException</tt>, as if the timer's <tt>cancel</tt> |
| 55 | * method had been invoked. |
| 56 | * |
| 57 | * <p>This class is thread-safe: multiple threads can share a single |
| 58 | * <tt>Timer</tt> object without the need for external synchronization. |
| 59 | * |
| 60 | * <p>This class does <i>not</i> offer real-time guarantees: it schedules |
| 61 | * tasks using the <tt>Object.wait(long)</tt> method. |
| 62 | * |
| 63 | * <p>Java 5.0 introduced the {@code java.util.concurrent} package and |
| 64 | * one of the concurrency utilities therein is the {@link |
| 65 | * java.util.concurrent.ScheduledThreadPoolExecutor |
| 66 | * ScheduledThreadPoolExecutor} which is a thread pool for repeatedly |
| 67 | * executing tasks at a given rate or delay. It is effectively a more |
| 68 | * versatile replacement for the {@code Timer}/{@code TimerTask} |
| 69 | * combination, as it allows multiple service threads, accepts various |
| 70 | * time units, and doesn't require subclassing {@code TimerTask} (just |
| 71 | * implement {@code Runnable}). Configuring {@code |
| 72 | * ScheduledThreadPoolExecutor} with one thread makes it equivalent to |
| 73 | * {@code Timer}. |
| 74 | * |
| 75 | * <p>Implementation note: This class scales to large numbers of concurrently |
| 76 | * scheduled tasks (thousands should present no problem). Internally, |
| 77 | * it uses a binary heap to represent its task queue, so the cost to schedule |
| 78 | * a task is O(log n), where n is the number of concurrently scheduled tasks. |
| 79 | * |
| 80 | * <p>Implementation note: All constructors start a timer thread. |
| 81 | * |
| 82 | * @author Josh Bloch |
| 83 | * @see TimerTask |
| 84 | * @see Object#wait(long) |
| 85 | * @since 1.3 |
| 86 | */ |
| 87 | |
| 88 | public class Timer { |
| 89 | /** |
| 90 | * The timer task queue. This data structure is shared with the timer |
| 91 | * thread. The timer produces tasks, via its various schedule calls, |
| 92 | * and the timer thread consumes, executing timer tasks as appropriate, |
| 93 | * and removing them from the queue when they're obsolete. |
| 94 | */ |
| 95 | private TaskQueue queue = new TaskQueue(); |
| 96 | |
| 97 | /** |
| 98 | * The timer thread. |
| 99 | */ |
| 100 | private TimerThread thread = new TimerThread(queue); |
| 101 | |
| 102 | /** |
| 103 | * This object causes the timer's task execution thread to exit |
| 104 | * gracefully when there are no live references to the Timer object and no |
| 105 | * tasks in the timer queue. It is used in preference to a finalizer on |
| 106 | * Timer as such a finalizer would be susceptible to a subclass's |
| 107 | * finalizer forgetting to call it. |
| 108 | */ |
| 109 | private Object threadReaper = new Object() { |
| 110 | protected void finalize() throws Throwable { |
| 111 | synchronized(queue) { |
| 112 | thread.newTasksMayBeScheduled = false; |
| 113 | queue.notify(); // In case queue is empty. |
| 114 | } |
| 115 | } |
| 116 | }; |
| 117 | |
| 118 | /** |
| 119 | * This ID is used to generate thread names. (It could be replaced |
| 120 | * by an AtomicInteger as soon as they become available.) |
| 121 | */ |
| 122 | private static int nextSerialNumber = 0; |
| 123 | private static synchronized int serialNumber() { |
| 124 | return nextSerialNumber++; |
| 125 | } |
| 126 | |
| 127 | /** |
| 128 | * Creates a new timer. The associated thread does <i>not</i> |
| 129 | * {@linkplain Thread#setDaemon run as a daemon}. |
| 130 | */ |
| 131 | public Timer() { |
| 132 | this("Timer-" + serialNumber()); |
| 133 | } |
| 134 | |
| 135 | /** |
| 136 | * Creates a new timer whose associated thread may be specified to |
| 137 | * {@linkplain Thread#setDaemon run as a daemon}. |
| 138 | * A daemon thread is called for if the timer will be used to |
| 139 | * schedule repeating "maintenance activities", which must be |
| 140 | * performed as long as the application is running, but should not |
| 141 | * prolong the lifetime of the application. |
| 142 | * |
| 143 | * @param isDaemon true if the associated thread should run as a daemon. |
| 144 | */ |
| 145 | public Timer(boolean isDaemon) { |
| 146 | this("Timer-" + serialNumber(), isDaemon); |
| 147 | } |
| 148 | |
| 149 | /** |
| 150 | * Creates a new timer whose associated thread has the specified name. |
| 151 | * The associated thread does <i>not</i> |
| 152 | * {@linkplain Thread#setDaemon run as a daemon}. |
| 153 | * |
| 154 | * @param name the name of the associated thread |
| 155 | * @throws NullPointerException if {@code name} is null |
| 156 | * @since 1.5 |
| 157 | */ |
| 158 | public Timer(String name) { |
| 159 | thread.setName(name); |
| 160 | thread.start(); |
| 161 | } |
| 162 | |
| 163 | /** |
| 164 | * Creates a new timer whose associated thread has the specified name, |
| 165 | * and may be specified to |
| 166 | * {@linkplain Thread#setDaemon run as a daemon}. |
| 167 | * |
| 168 | * @param name the name of the associated thread |
| 169 | * @param isDaemon true if the associated thread should run as a daemon |
| 170 | * @throws NullPointerException if {@code name} is null |
| 171 | * @since 1.5 |
| 172 | */ |
| 173 | public Timer(String name, boolean isDaemon) { |
| 174 | thread.setName(name); |
| 175 | thread.setDaemon(isDaemon); |
| 176 | thread.start(); |
| 177 | } |
| 178 | |
| 179 | /** |
| 180 | * Schedules the specified task for execution after the specified delay. |
| 181 | * |
| 182 | * @param task task to be scheduled. |
| 183 | * @param delay delay in milliseconds before task is to be executed. |
| 184 | * @throws IllegalArgumentException if <tt>delay</tt> is negative, or |
| 185 | * <tt>delay + System.currentTimeMillis()</tt> is negative. |
| 186 | * @throws IllegalStateException if task was already scheduled or |
| 187 | * cancelled, timer was cancelled, or timer thread terminated. |
| 188 | * @throws NullPointerException if {@code task} is null |
| 189 | */ |
| 190 | public void schedule(TimerTask task, long delay) { |
| 191 | if (delay < 0) |
| 192 | throw new IllegalArgumentException("Negative delay."); |
| 193 | sched(task, System.currentTimeMillis()+delay, 0); |
| 194 | } |
| 195 | |
| 196 | /** |
| 197 | * Schedules the specified task for execution at the specified time. If |
| 198 | * the time is in the past, the task is scheduled for immediate execution. |
| 199 | * |
| 200 | * @param task task to be scheduled. |
| 201 | * @param time time at which task is to be executed. |
| 202 | * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative. |
| 203 | * @throws IllegalStateException if task was already scheduled or |
| 204 | * cancelled, timer was cancelled, or timer thread terminated. |
| 205 | * @throws NullPointerException if {@code task} or {@code time} is null |
| 206 | */ |
| 207 | public void schedule(TimerTask task, Date time) { |
| 208 | sched(task, time.getTime(), 0); |
| 209 | } |
| 210 | |
| 211 | /** |
| 212 | * Schedules the specified task for repeated <i>fixed-delay execution</i>, |
| 213 | * beginning after the specified delay. Subsequent executions take place |
| 214 | * at approximately regular intervals separated by the specified period. |
| 215 | * |
| 216 | * <p>In fixed-delay execution, each execution is scheduled relative to |
| 217 | * the actual execution time of the previous execution. If an execution |
| 218 | * is delayed for any reason (such as garbage collection or other |
| 219 | * background activity), subsequent executions will be delayed as well. |
| 220 | * In the long run, the frequency of execution will generally be slightly |
| 221 | * lower than the reciprocal of the specified period (assuming the system |
| 222 | * clock underlying <tt>Object.wait(long)</tt> is accurate). |
| 223 | * |
| 224 | * <p>Fixed-delay execution is appropriate for recurring activities |
| 225 | * that require "smoothness." In other words, it is appropriate for |
| 226 | * activities where it is more important to keep the frequency accurate |
| 227 | * in the short run than in the long run. This includes most animation |
| 228 | * tasks, such as blinking a cursor at regular intervals. It also includes |
| 229 | * tasks wherein regular activity is performed in response to human |
| 230 | * input, such as automatically repeating a character as long as a key |
| 231 | * is held down. |
| 232 | * |
| 233 | * @param task task to be scheduled. |
| 234 | * @param delay delay in milliseconds before task is to be executed. |
| 235 | * @param period time in milliseconds between successive task executions. |
| 236 | * @throws IllegalArgumentException if {@code delay < 0}, or |
| 237 | * {@code delay + System.currentTimeMillis() < 0}, or |
| 238 | * {@code period <= 0} |
| 239 | * @throws IllegalStateException if task was already scheduled or |
| 240 | * cancelled, timer was cancelled, or timer thread terminated. |
| 241 | * @throws NullPointerException if {@code task} is null |
| 242 | */ |
| 243 | public void schedule(TimerTask task, long delay, long period) { |
| 244 | if (delay < 0) |
| 245 | throw new IllegalArgumentException("Negative delay."); |
| 246 | if (period <= 0) |
| 247 | throw new IllegalArgumentException("Non-positive period."); |
| 248 | sched(task, System.currentTimeMillis()+delay, -period); |
| 249 | } |
| 250 | |
| 251 | /** |
| 252 | * Schedules the specified task for repeated <i>fixed-delay execution</i>, |
| 253 | * beginning at the specified time. Subsequent executions take place at |
| 254 | * approximately regular intervals, separated by the specified period. |
| 255 | * |
| 256 | * <p>In fixed-delay execution, each execution is scheduled relative to |
| 257 | * the actual execution time of the previous execution. If an execution |
| 258 | * is delayed for any reason (such as garbage collection or other |
| 259 | * background activity), subsequent executions will be delayed as well. |
| 260 | * In the long run, the frequency of execution will generally be slightly |
| 261 | * lower than the reciprocal of the specified period (assuming the system |
| 262 | * clock underlying <tt>Object.wait(long)</tt> is accurate). As a |
| 263 | * consequence of the above, if the scheduled first time is in the past, |
| 264 | * it is scheduled for immediate execution. |
| 265 | * |
| 266 | * <p>Fixed-delay execution is appropriate for recurring activities |
| 267 | * that require "smoothness." In other words, it is appropriate for |
| 268 | * activities where it is more important to keep the frequency accurate |
| 269 | * in the short run than in the long run. This includes most animation |
| 270 | * tasks, such as blinking a cursor at regular intervals. It also includes |
| 271 | * tasks wherein regular activity is performed in response to human |
| 272 | * input, such as automatically repeating a character as long as a key |
| 273 | * is held down. |
| 274 | * |
| 275 | * @param task task to be scheduled. |
| 276 | * @param firstTime First time at which task is to be executed. |
| 277 | * @param period time in milliseconds between successive task executions. |
| 278 | * @throws IllegalArgumentException if {@code firstTime.getTime() < 0}, or |
| 279 | * {@code period <= 0} |
| 280 | * @throws IllegalStateException if task was already scheduled or |
| 281 | * cancelled, timer was cancelled, or timer thread terminated. |
| 282 | * @throws NullPointerException if {@code task} or {@code firstTime} is null |
| 283 | */ |
| 284 | public void schedule(TimerTask task, Date firstTime, long period) { |
| 285 | if (period <= 0) |
| 286 | throw new IllegalArgumentException("Non-positive period."); |
| 287 | sched(task, firstTime.getTime(), -period); |
| 288 | } |
| 289 | |
| 290 | /** |
| 291 | * Schedules the specified task for repeated <i>fixed-rate execution</i>, |
| 292 | * beginning after the specified delay. Subsequent executions take place |
| 293 | * at approximately regular intervals, separated by the specified period. |
| 294 | * |
| 295 | * <p>In fixed-rate execution, each execution is scheduled relative to the |
| 296 | * scheduled execution time of the initial execution. If an execution is |
| 297 | * delayed for any reason (such as garbage collection or other background |
| 298 | * activity), two or more executions will occur in rapid succession to |
| 299 | * "catch up." In the long run, the frequency of execution will be |
| 300 | * exactly the reciprocal of the specified period (assuming the system |
| 301 | * clock underlying <tt>Object.wait(long)</tt> is accurate). |
| 302 | * |
| 303 | * <p>Fixed-rate execution is appropriate for recurring activities that |
| 304 | * are sensitive to <i>absolute</i> time, such as ringing a chime every |
| 305 | * hour on the hour, or running scheduled maintenance every day at a |
| 306 | * particular time. It is also appropriate for recurring activities |
| 307 | * where the total time to perform a fixed number of executions is |
| 308 | * important, such as a countdown timer that ticks once every second for |
| 309 | * ten seconds. Finally, fixed-rate execution is appropriate for |
| 310 | * scheduling multiple repeating timer tasks that must remain synchronized |
| 311 | * with respect to one another. |
| 312 | * |
| 313 | * @param task task to be scheduled. |
| 314 | * @param delay delay in milliseconds before task is to be executed. |
| 315 | * @param period time in milliseconds between successive task executions. |
| 316 | * @throws IllegalArgumentException if {@code delay < 0}, or |
| 317 | * {@code delay + System.currentTimeMillis() < 0}, or |
| 318 | * {@code period <= 0} |
| 319 | * @throws IllegalStateException if task was already scheduled or |
| 320 | * cancelled, timer was cancelled, or timer thread terminated. |
| 321 | * @throws NullPointerException if {@code task} is null |
| 322 | */ |
| 323 | public void scheduleAtFixedRate(TimerTask task, long delay, long period) { |
| 324 | if (delay < 0) |
| 325 | throw new IllegalArgumentException("Negative delay."); |
| 326 | if (period <= 0) |
| 327 | throw new IllegalArgumentException("Non-positive period."); |
| 328 | sched(task, System.currentTimeMillis()+delay, period); |
| 329 | } |
| 330 | |
| 331 | /** |
| 332 | * Schedules the specified task for repeated <i>fixed-rate execution</i>, |
| 333 | * beginning at the specified time. Subsequent executions take place at |
| 334 | * approximately regular intervals, separated by the specified period. |
| 335 | * |
| 336 | * <p>In fixed-rate execution, each execution is scheduled relative to the |
| 337 | * scheduled execution time of the initial execution. If an execution is |
| 338 | * delayed for any reason (such as garbage collection or other background |
| 339 | * activity), two or more executions will occur in rapid succession to |
| 340 | * "catch up." In the long run, the frequency of execution will be |
| 341 | * exactly the reciprocal of the specified period (assuming the system |
| 342 | * clock underlying <tt>Object.wait(long)</tt> is accurate). As a |
| 343 | * consequence of the above, if the scheduled first time is in the past, |
| 344 | * then any "missed" executions will be scheduled for immediate "catch up" |
| 345 | * execution. |
| 346 | * |
| 347 | * <p>Fixed-rate execution is appropriate for recurring activities that |
| 348 | * are sensitive to <i>absolute</i> time, such as ringing a chime every |
| 349 | * hour on the hour, or running scheduled maintenance every day at a |
| 350 | * particular time. It is also appropriate for recurring activities |
| 351 | * where the total time to perform a fixed number of executions is |
| 352 | * important, such as a countdown timer that ticks once every second for |
| 353 | * ten seconds. Finally, fixed-rate execution is appropriate for |
| 354 | * scheduling multiple repeating timer tasks that must remain synchronized |
| 355 | * with respect to one another. |
| 356 | * |
| 357 | * @param task task to be scheduled. |
| 358 | * @param firstTime First time at which task is to be executed. |
| 359 | * @param period time in milliseconds between successive task executions. |
| 360 | * @throws IllegalArgumentException if {@code firstTime.getTime() < 0} or |
| 361 | * {@code period <= 0} |
| 362 | * @throws IllegalStateException if task was already scheduled or |
| 363 | * cancelled, timer was cancelled, or timer thread terminated. |
| 364 | * @throws NullPointerException if {@code task} or {@code firstTime} is null |
| 365 | */ |
| 366 | public void scheduleAtFixedRate(TimerTask task, Date firstTime, |
| 367 | long period) { |
| 368 | if (period <= 0) |
| 369 | throw new IllegalArgumentException("Non-positive period."); |
| 370 | sched(task, firstTime.getTime(), period); |
| 371 | } |
| 372 | |
| 373 | /** |
| 374 | * Schedule the specified timer task for execution at the specified |
| 375 | * time with the specified period, in milliseconds. If period is |
| 376 | * positive, the task is scheduled for repeated execution; if period is |
| 377 | * zero, the task is scheduled for one-time execution. Time is specified |
| 378 | * in Date.getTime() format. This method checks timer state, task state, |
| 379 | * and initial execution time, but not period. |
| 380 | * |
| 381 | * @throws IllegalArgumentException if <tt>time</tt> is negative. |
| 382 | * @throws IllegalStateException if task was already scheduled or |
| 383 | * cancelled, timer was cancelled, or timer thread terminated. |
| 384 | * @throws NullPointerException if {@code task} is null |
| 385 | */ |
| 386 | private void sched(TimerTask task, long time, long period) { |
| 387 | if (time < 0) |
| 388 | throw new IllegalArgumentException("Illegal execution time."); |
| 389 | |
| 390 | synchronized(queue) { |
| 391 | if (!thread.newTasksMayBeScheduled) |
| 392 | throw new IllegalStateException("Timer already cancelled."); |
| 393 | |
| 394 | synchronized(task.lock) { |
| 395 | if (task.state != TimerTask.VIRGIN) |
| 396 | throw new IllegalStateException( |
| 397 | "Task already scheduled or cancelled"); |
| 398 | task.nextExecutionTime = time; |
| 399 | task.period = period; |
| 400 | task.state = TimerTask.SCHEDULED; |
| 401 | } |
| 402 | |
| 403 | queue.add(task); |
| 404 | if (queue.getMin() == task) |
| 405 | queue.notify(); |
| 406 | } |
| 407 | } |
| 408 | |
| 409 | /** |
| 410 | * Terminates this timer, discarding any currently scheduled tasks. |
| 411 | * Does not interfere with a currently executing task (if it exists). |
| 412 | * Once a timer has been terminated, its execution thread terminates |
| 413 | * gracefully, and no more tasks may be scheduled on it. |
| 414 | * |
| 415 | * <p>Note that calling this method from within the run method of a |
| 416 | * timer task that was invoked by this timer absolutely guarantees that |
| 417 | * the ongoing task execution is the last task execution that will ever |
| 418 | * be performed by this timer. |
| 419 | * |
| 420 | * <p>This method may be called repeatedly; the second and subsequent |
| 421 | * calls have no effect. |
| 422 | */ |
| 423 | public void cancel() { |
| 424 | synchronized(queue) { |
| 425 | thread.newTasksMayBeScheduled = false; |
| 426 | queue.clear(); |
| 427 | queue.notify(); // In case queue was already empty. |
| 428 | } |
| 429 | } |
| 430 | |
| 431 | /** |
| 432 | * Removes all cancelled tasks from this timer's task queue. <i>Calling |
| 433 | * this method has no effect on the behavior of the timer</i>, but |
| 434 | * eliminates the references to the cancelled tasks from the queue. |
| 435 | * If there are no external references to these tasks, they become |
| 436 | * eligible for garbage collection. |
| 437 | * |
| 438 | * <p>Most programs will have no need to call this method. |
| 439 | * It is designed for use by the rare application that cancels a large |
| 440 | * number of tasks. Calling this method trades time for space: the |
| 441 | * runtime of the method may be proportional to n + c log n, where n |
| 442 | * is the number of tasks in the queue and c is the number of cancelled |
| 443 | * tasks. |
| 444 | * |
| 445 | * <p>Note that it is permissible to call this method from within a |
| 446 | * a task scheduled on this timer. |
| 447 | * |
| 448 | * @return the number of tasks removed from the queue. |
| 449 | * @since 1.5 |
| 450 | */ |
| 451 | public int purge() { |
| 452 | int result = 0; |
| 453 | |
| 454 | synchronized(queue) { |
| 455 | for (int i = queue.size(); i > 0; i--) { |
| 456 | if (queue.get(i).state == TimerTask.CANCELLED) { |
| 457 | queue.quickRemove(i); |
| 458 | result++; |
| 459 | } |
| 460 | } |
| 461 | |
| 462 | if (result != 0) |
| 463 | queue.heapify(); |
| 464 | } |
| 465 | |
| 466 | return result; |
| 467 | } |
| 468 | } |
| 469 | |
| 470 | /** |
| 471 | * This "helper class" implements the timer's task execution thread, which |
| 472 | * waits for tasks on the timer queue, executions them when they fire, |
| 473 | * reschedules repeating tasks, and removes cancelled tasks and spent |
| 474 | * non-repeating tasks from the queue. |
| 475 | */ |
| 476 | class TimerThread extends Thread { |
| 477 | /** |
| 478 | * This flag is set to false by the reaper to inform us that there |
| 479 | * are no more live references to our Timer object. Once this flag |
| 480 | * is true and there are no more tasks in our queue, there is no |
| 481 | * work left for us to do, so we terminate gracefully. Note that |
| 482 | * this field is protected by queue's monitor! |
| 483 | */ |
| 484 | boolean newTasksMayBeScheduled = true; |
| 485 | |
| 486 | /** |
| 487 | * Our Timer's queue. We store this reference in preference to |
| 488 | * a reference to the Timer so the reference graph remains acyclic. |
| 489 | * Otherwise, the Timer would never be garbage-collected and this |
| 490 | * thread would never go away. |
| 491 | */ |
| 492 | private TaskQueue queue; |
| 493 | |
| 494 | TimerThread(TaskQueue queue) { |
| 495 | this.queue = queue; |
| 496 | } |
| 497 | |
| 498 | public void run() { |
| 499 | try { |
| 500 | mainLoop(); |
| 501 | } finally { |
| 502 | // Someone killed this Thread, behave as if Timer cancelled |
| 503 | synchronized(queue) { |
| 504 | newTasksMayBeScheduled = false; |
| 505 | queue.clear(); // Eliminate obsolete references |
| 506 | } |
| 507 | } |
| 508 | } |
| 509 | |
| 510 | /** |
| 511 | * The main timer loop. (See class comment.) |
| 512 | */ |
| 513 | private void mainLoop() { |
| 514 | while (true) { |
| 515 | try { |
| 516 | TimerTask task; |
| 517 | boolean taskFired; |
| 518 | synchronized(queue) { |
| 519 | // Wait for queue to become non-empty |
| 520 | while (queue.isEmpty() && newTasksMayBeScheduled) |
| 521 | queue.wait(); |
| 522 | if (queue.isEmpty()) |
| 523 | break; // Queue is empty and will forever remain; die |
| 524 | |
| 525 | // Queue nonempty; look at first evt and do the right thing |
| 526 | long currentTime, executionTime; |
| 527 | task = queue.getMin(); |
| 528 | synchronized(task.lock) { |
| 529 | if (task.state == TimerTask.CANCELLED) { |
| 530 | queue.removeMin(); |
| 531 | continue; // No action required, poll queue again |
| 532 | } |
| 533 | currentTime = System.currentTimeMillis(); |
| 534 | executionTime = task.nextExecutionTime; |
| 535 | if (taskFired = (executionTime<=currentTime)) { |
| 536 | if (task.period == 0) { // Non-repeating, remove |
| 537 | queue.removeMin(); |
| 538 | task.state = TimerTask.EXECUTED; |
| 539 | } else { // Repeating task, reschedule |
| 540 | queue.rescheduleMin( |
| 541 | task.period<0 ? currentTime - task.period |
| 542 | : executionTime + task.period); |
| 543 | } |
| 544 | } |
| 545 | } |
| 546 | if (!taskFired) // Task hasn't yet fired; wait |
| 547 | queue.wait(executionTime - currentTime); |
| 548 | } |
| 549 | if (taskFired) // Task fired; run it, holding no locks |
| 550 | task.run(); |
| 551 | } catch(InterruptedException e) { |
| 552 | } |
| 553 | } |
| 554 | } |
| 555 | } |
| 556 | |
| 557 | /** |
| 558 | * This class represents a timer task queue: a priority queue of TimerTasks, |
| 559 | * ordered on nextExecutionTime. Each Timer object has one of these, which it |
| 560 | * shares with its TimerThread. Internally this class uses a heap, which |
| 561 | * offers log(n) performance for the add, removeMin and rescheduleMin |
| 562 | * operations, and constant time performance for the getMin operation. |
| 563 | */ |
| 564 | class TaskQueue { |
| 565 | /** |
| 566 | * Priority queue represented as a balanced binary heap: the two children |
| 567 | * of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is |
| 568 | * ordered on the nextExecutionTime field: The TimerTask with the lowest |
| 569 | * nextExecutionTime is in queue[1] (assuming the queue is nonempty). For |
| 570 | * each node n in the heap, and each descendant of n, d, |
| 571 | * n.nextExecutionTime <= d.nextExecutionTime. |
| 572 | */ |
| 573 | private TimerTask[] queue = new TimerTask[128]; |
| 574 | |
| 575 | /** |
| 576 | * The number of tasks in the priority queue. (The tasks are stored in |
| 577 | * queue[1] up to queue[size]). |
| 578 | */ |
| 579 | private int size = 0; |
| 580 | |
| 581 | /** |
| 582 | * Returns the number of tasks currently on the queue. |
| 583 | */ |
| 584 | int size() { |
| 585 | return size; |
| 586 | } |
| 587 | |
| 588 | /** |
| 589 | * Adds a new task to the priority queue. |
| 590 | */ |
| 591 | void add(TimerTask task) { |
| 592 | // Grow backing store if necessary |
| 593 | if (size + 1 == queue.length) |
| 594 | queue = Arrays.copyOf(queue, 2*queue.length); |
| 595 | |
| 596 | queue[++size] = task; |
| 597 | fixUp(size); |
| 598 | } |
| 599 | |
| 600 | /** |
| 601 | * Return the "head task" of the priority queue. (The head task is an |
| 602 | * task with the lowest nextExecutionTime.) |
| 603 | */ |
| 604 | TimerTask getMin() { |
| 605 | return queue[1]; |
| 606 | } |
| 607 | |
| 608 | /** |
| 609 | * Return the ith task in the priority queue, where i ranges from 1 (the |
| 610 | * head task, which is returned by getMin) to the number of tasks on the |
| 611 | * queue, inclusive. |
| 612 | */ |
| 613 | TimerTask get(int i) { |
| 614 | return queue[i]; |
| 615 | } |
| 616 | |
| 617 | /** |
| 618 | * Remove the head task from the priority queue. |
| 619 | */ |
| 620 | void removeMin() { |
| 621 | queue[1] = queue[size]; |
| 622 | queue[size--] = null; // Drop extra reference to prevent memory leak |
| 623 | fixDown(1); |
| 624 | } |
| 625 | |
| 626 | /** |
| 627 | * Removes the ith element from queue without regard for maintaining |
| 628 | * the heap invariant. Recall that queue is one-based, so |
| 629 | * 1 <= i <= size. |
| 630 | */ |
| 631 | void quickRemove(int i) { |
| 632 | assert i <= size; |
| 633 | |
| 634 | queue[i] = queue[size]; |
| 635 | queue[size--] = null; // Drop extra ref to prevent memory leak |
| 636 | } |
| 637 | |
| 638 | /** |
| 639 | * Sets the nextExecutionTime associated with the head task to the |
| 640 | * specified value, and adjusts priority queue accordingly. |
| 641 | */ |
| 642 | void rescheduleMin(long newTime) { |
| 643 | queue[1].nextExecutionTime = newTime; |
| 644 | fixDown(1); |
| 645 | } |
| 646 | |
| 647 | /** |
| 648 | * Returns true if the priority queue contains no elements. |
| 649 | */ |
| 650 | boolean isEmpty() { |
| 651 | return size==0; |
| 652 | } |
| 653 | |
| 654 | /** |
| 655 | * Removes all elements from the priority queue. |
| 656 | */ |
| 657 | void clear() { |
| 658 | // Null out task references to prevent memory leak |
| 659 | for (int i=1; i<=size; i++) |
| 660 | queue[i] = null; |
| 661 | |
| 662 | size = 0; |
| 663 | } |
| 664 | |
| 665 | /** |
| 666 | * Establishes the heap invariant (described above) assuming the heap |
| 667 | * satisfies the invariant except possibly for the leaf-node indexed by k |
| 668 | * (which may have a nextExecutionTime less than its parent's). |
| 669 | * |
| 670 | * This method functions by "promoting" queue[k] up the hierarchy |
| 671 | * (by swapping it with its parent) repeatedly until queue[k]'s |
| 672 | * nextExecutionTime is greater than or equal to that of its parent. |
| 673 | */ |
| 674 | private void fixUp(int k) { |
| 675 | while (k > 1) { |
| 676 | int j = k >> 1; |
| 677 | if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime) |
| 678 | break; |
| 679 | TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |
| 680 | k = j; |
| 681 | } |
| 682 | } |
| 683 | |
| 684 | /** |
| 685 | * Establishes the heap invariant (described above) in the subtree |
| 686 | * rooted at k, which is assumed to satisfy the heap invariant except |
| 687 | * possibly for node k itself (which may have a nextExecutionTime greater |
| 688 | * than its children's). |
| 689 | * |
| 690 | * This method functions by "demoting" queue[k] down the hierarchy |
| 691 | * (by swapping it with its smaller child) repeatedly until queue[k]'s |
| 692 | * nextExecutionTime is less than or equal to those of its children. |
| 693 | */ |
| 694 | private void fixDown(int k) { |
| 695 | int j; |
| 696 | while ((j = k << 1) <= size && j > 0) { |
| 697 | if (j < size && |
| 698 | queue[j].nextExecutionTime > queue[j+1].nextExecutionTime) |
| 699 | j++; // j indexes smallest kid |
| 700 | if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime) |
| 701 | break; |
| 702 | TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |
| 703 | k = j; |
| 704 | } |
| 705 | } |
| 706 | |
| 707 | /** |
| 708 | * Establishes the heap invariant (described above) in the entire tree, |
| 709 | * assuming nothing about the order of the elements prior to the call. |
| 710 | */ |
| 711 | void heapify() { |
| 712 | for (int i = size/2; i >= 1; i--) |
| 713 | fixDown(i); |
| 714 | } |
| 715 | } |