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