1 /* Timer.java -- Timer that runs TimerTasks at a later time. 2 Copyright (C) 2000, 2001, 2005 Free Software Foundation, Inc. 3 4 This file is part of GNU Classpath. 5 6 GNU Classpath is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2, or (at your option) 9 any later version. 10 11 GNU Classpath is distributed in the hope that it will be useful, but 12 WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GNU Classpath; see the file COPYING. If not, write to the 18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19 02110-1301 USA. 20 21 Linking this library statically or dynamically with other modules is 22 making a combined work based on this library. Thus, the terms and 23 conditions of the GNU General Public License cover the whole 24 combination. 25 26 As a special exception, the copyright holders of this library give you 27 permission to link this library with independent modules to produce an 28 executable, regardless of the license terms of these independent 29 modules, and to copy and distribute the resulting executable under 30 terms of your choice, provided that you also meet, for each linked 31 independent module, the terms and conditions of the license of that 32 module. An independent module is a module which is not derived from 33 or based on this library. If you modify this library, you may extend 34 this exception to your version of the library, but you are not 35 obligated to do so. If you do not wish to do so, delete this 36 exception statement from your version. */ 37 38 package java.util; 39 40 /** 41 * Timer that can run TimerTasks at a later time. 42 * TimerTasks can be scheduled for one time execution at some time in the 43 * future. They can be scheduled to be rescheduled at a time period after the 44 * task was last executed. Or they can be scheduled to be executed repeatedly 45 * at a fixed rate. 46 * <p> 47 * The normal scheduling will result in a more or less even delay in time 48 * between successive executions, but the executions could drift in time if 49 * the task (or other tasks) takes a long time to execute. Fixed delay 50 * scheduling guarantees more or less that the task will be executed at a 51 * specific time, but if there is ever a delay in execution then the period 52 * between successive executions will be shorter. The first method of 53 * repeated scheduling is preferred for repeated tasks in response to user 54 * interaction, the second method of repeated scheduling is preferred for tasks 55 * that act like alarms. 56 * <p> 57 * The Timer keeps a binary heap as a task priority queue which means that 58 * scheduling and serving of a task in a queue of n tasks costs O(log n). 59 * 60 * @see TimerTask 61 * @since 1.3 62 * @author Mark Wielaard (mark@klomp.org) 63 */ 64 public class Timer 65 { 66 /** 67 * Priority Task Queue. 68 * TimerTasks are kept in a binary heap. 69 * The scheduler calls sleep() on the queue when it has nothing to do or 70 * has to wait. A sleeping scheduler can be notified by calling interrupt() 71 * which is automatically called by the enqueue(), cancel() and 72 * timerFinalized() methods. 73 */ 74 private static final class TaskQueue 75 { 76 /** Default size of this queue */ 77 private static final int DEFAULT_SIZE = 32; 78 79 /** Whether to return null when there is nothing in the queue */ 80 private boolean nullOnEmpty; 81 82 /** 83 * The heap containing all the scheduled TimerTasks 84 * sorted by the TimerTask.scheduled field. 85 * Null when the stop() method has been called. 86 */ 87 private TimerTask heap[]; 88 89 /** 90 * The actual number of elements in the heap 91 * Can be less then heap.length. 92 * Note that heap[0] is used as a sentinel. 93 */ 94 private int elements; 95 96 /** 97 * Creates a TaskQueue of default size without any elements in it. 98 */ TaskQueue()99 public TaskQueue() 100 { 101 heap = new TimerTask[DEFAULT_SIZE]; 102 elements = 0; 103 nullOnEmpty = false; 104 } 105 106 /** 107 * Adds a TimerTask at the end of the heap. 108 * Grows the heap if necessary by doubling the heap in size. 109 */ add(TimerTask task)110 private void add(TimerTask task) 111 { 112 elements++; 113 if (elements == heap.length) 114 { 115 TimerTask new_heap[] = new TimerTask[heap.length * 2]; 116 System.arraycopy(heap, 0, new_heap, 0, heap.length); 117 heap = new_heap; 118 } 119 heap[elements] = task; 120 } 121 122 /** 123 * Removes the last element from the heap. 124 * Shrinks the heap in half if 125 * elements+DEFAULT_SIZE/2 <= heap.length/4. 126 */ remove()127 private void remove() 128 { 129 // clear the entry first 130 heap[elements] = null; 131 elements--; 132 if (elements + DEFAULT_SIZE / 2 <= (heap.length / 4)) 133 { 134 TimerTask new_heap[] = new TimerTask[heap.length / 2]; 135 System.arraycopy(heap, 0, new_heap, 0, elements + 1); 136 heap = new_heap; 137 } 138 } 139 140 /** 141 * Adds a task to the queue and puts it at the correct place 142 * in the heap. 143 */ enqueue(TimerTask task)144 public synchronized void enqueue(TimerTask task) 145 { 146 // Check if it is legal to add another element 147 if (heap == null) 148 { 149 throw new IllegalStateException 150 ("cannot enqueue when stop() has been called on queue"); 151 } 152 153 heap[0] = task; // sentinel 154 add(task); // put the new task at the end 155 // Now push the task up in the heap until it has reached its place 156 int child = elements; 157 int parent = child / 2; 158 while (heap[parent].scheduled > task.scheduled) 159 { 160 heap[child] = heap[parent]; 161 child = parent; 162 parent = child / 2; 163 } 164 // This is the correct place for the new task 165 heap[child] = task; 166 heap[0] = null; // clear sentinel 167 // Maybe sched() is waiting for a new element 168 this.notify(); 169 } 170 171 /** 172 * Returns the top element of the queue. 173 * Can return null when no task is in the queue. 174 */ top()175 private TimerTask top() 176 { 177 if (elements == 0) 178 { 179 return null; 180 } 181 else 182 { 183 return heap[1]; 184 } 185 } 186 187 /** 188 * Returns the top task in the Queue. 189 * Removes the element from the heap and reorders the heap first. 190 * Can return null when there is nothing in the queue. 191 */ serve()192 public synchronized TimerTask serve() 193 { 194 // The task to return 195 TimerTask task = null; 196 197 while (task == null) 198 { 199 // Get the next task 200 task = top(); 201 202 // return null when asked to stop 203 // or if asked to return null when the queue is empty 204 if ((heap == null) || (task == null && nullOnEmpty)) 205 { 206 return null; 207 } 208 209 // Do we have a task? 210 if (task != null) 211 { 212 // The time to wait until the task should be served 213 long time = task.scheduled - System.currentTimeMillis(); 214 if (time > 0) 215 { 216 // This task should not yet be served 217 // So wait until this task is ready 218 // or something else happens to the queue 219 task = null; // set to null to make sure we call top() 220 try 221 { 222 this.wait(time); 223 } 224 catch (InterruptedException _) 225 { 226 } 227 } 228 } 229 else 230 { 231 // wait until a task is added 232 // or something else happens to the queue 233 try 234 { 235 this.wait(); 236 } 237 catch (InterruptedException _) 238 { 239 } 240 } 241 } 242 243 // reconstruct the heap 244 TimerTask lastTask = heap[elements]; 245 remove(); 246 247 // drop lastTask at the beginning and move it down the heap 248 int parent = 1; 249 int child = 2; 250 heap[1] = lastTask; 251 while (child <= elements) 252 { 253 if (child < elements) 254 { 255 if (heap[child].scheduled > heap[child + 1].scheduled) 256 { 257 child++; 258 } 259 } 260 261 if (lastTask.scheduled <= heap[child].scheduled) 262 break; // found the correct place (the parent) - done 263 264 heap[parent] = heap[child]; 265 parent = child; 266 child = parent * 2; 267 } 268 269 // this is the correct new place for the lastTask 270 heap[parent] = lastTask; 271 272 // return the task 273 return task; 274 } 275 276 /** 277 * When nullOnEmpty is true the serve() method will return null when 278 * there are no tasks in the queue, otherwise it will wait until 279 * a new element is added to the queue. It is used to indicate to 280 * the scheduler that no new tasks will ever be added to the queue. 281 */ setNullOnEmpty(boolean nullOnEmpty)282 public synchronized void setNullOnEmpty(boolean nullOnEmpty) 283 { 284 this.nullOnEmpty = nullOnEmpty; 285 this.notify(); 286 } 287 288 /** 289 * When this method is called the current and all future calls to 290 * serve() will return null. It is used to indicate to the Scheduler 291 * that it should stop executing since no more tasks will come. 292 */ stop()293 public synchronized void stop() 294 { 295 this.heap = null; 296 this.elements = 0; 297 this.notify(); 298 } 299 300 /** 301 * Remove all canceled tasks from the queue. 302 */ purge()303 public synchronized int purge() 304 { 305 int removed = 0; 306 // Null out any elements that are canceled. Skip element 0 as 307 // it is the sentinel. 308 for (int i = elements; i > 0; --i) 309 { 310 if (heap[i].scheduled < 0) 311 { 312 ++removed; 313 314 // Remove an element by pushing the appropriate child 315 // into place, and then iterating to the bottom of the 316 // tree. 317 int index = i; 318 while (heap[index] != null) 319 { 320 int child = 2 * index; 321 if (child >= heap.length) 322 { 323 // Off end; we're done. 324 heap[index] = null; 325 break; 326 } 327 328 if (child + 1 >= heap.length || heap[child + 1] == null) 329 { 330 // Nothing -- we're done. 331 } 332 else if (heap[child] == null 333 || (heap[child].scheduled 334 > heap[child + 1].scheduled)) 335 ++child; 336 heap[index] = heap[child]; 337 index = child; 338 } 339 } 340 } 341 342 // Make a new heap if we shrank enough. 343 int newLen = heap.length; 344 while (elements - removed + DEFAULT_SIZE / 2 <= newLen / 4) 345 newLen /= 2; 346 if (newLen != heap.length) 347 { 348 TimerTask[] newHeap = new TimerTask[newLen]; 349 System.arraycopy(heap, 0, newHeap, 0, elements + 1); 350 heap = newHeap; 351 } 352 353 return removed; 354 } 355 } // TaskQueue 356 357 /** 358 * The scheduler that executes all the tasks on a particular TaskQueue, 359 * reschedules any repeating tasks and that waits when no task has to be 360 * executed immediately. Stops running when canceled or when the parent 361 * Timer has been finalized and no more tasks have to be executed. 362 */ 363 private static final class Scheduler implements Runnable 364 { 365 // The priority queue containing all the TimerTasks. 366 private TaskQueue queue; 367 368 /** 369 * Creates a new Scheduler that will schedule the tasks on the 370 * given TaskQueue. 371 */ Scheduler(TaskQueue queue)372 public Scheduler(TaskQueue queue) 373 { 374 this.queue = queue; 375 } 376 run()377 public void run() 378 { 379 TimerTask task; 380 while ((task = queue.serve()) != null) 381 { 382 // If this task has not been canceled 383 if (task.scheduled >= 0) 384 { 385 386 // Mark execution time 387 task.lastExecutionTime = task.scheduled; 388 389 // Repeatable task? 390 if (task.period < 0) 391 { 392 // Last time this task is executed 393 task.scheduled = -1; 394 } 395 396 // Run the task 397 try 398 { 399 task.run(); 400 } 401 catch (ThreadDeath death) 402 { 403 // If an exception escapes, the Timer becomes invalid. 404 queue.stop(); 405 throw death; 406 } 407 catch (Throwable t) 408 { 409 // If an exception escapes, the Timer becomes invalid. 410 queue.stop(); 411 } 412 } 413 414 // Calculate next time and possibly re-enqueue. 415 if (task.scheduled >= 0) 416 { 417 if (task.fixed) 418 { 419 task.scheduled += task.period; 420 } 421 else 422 { 423 task.scheduled = task.period + System.currentTimeMillis(); 424 } 425 426 try 427 { 428 queue.enqueue(task); 429 } 430 catch (IllegalStateException ise) 431 { 432 // Ignore. Apparently the Timer queue has been stopped. 433 } 434 } 435 } 436 } 437 } // Scheduler 438 439 // Number of Timers created. 440 // Used for creating nice Thread names. 441 private static int nr; 442 443 // The queue that all the tasks are put in. 444 // Given to the scheduler 445 private TaskQueue queue; 446 447 // The Scheduler that does all the real work 448 private Scheduler scheduler; 449 450 // Used to run the scheduler. 451 // Also used to checked if the Thread is still running by calling 452 // thread.isAlive(). Sometimes a Thread is suddenly killed by the system 453 // (if it belonged to an Applet). 454 private Thread thread; 455 456 // When cancelled we don't accept any more TimerTasks. 457 private boolean canceled; 458 459 /** 460 * Creates a new Timer with a non daemon Thread as Scheduler, with normal 461 * priority and a default name. 462 */ Timer()463 public Timer() 464 { 465 this(false); 466 } 467 468 /** 469 * Creates a new Timer with a daemon Thread as scheduler if daemon is true, 470 * with normal priority and a default name. 471 */ Timer(boolean daemon)472 public Timer(boolean daemon) 473 { 474 this(daemon, Thread.NORM_PRIORITY); 475 } 476 477 /** 478 * Create a new Timer whose Thread has the indicated name. It will have 479 * normal priority and will not be a daemon thread. 480 * @param name the name of the Thread 481 * @since 1.5 482 */ Timer(String name)483 public Timer(String name) 484 { 485 this(false, Thread.NORM_PRIORITY, name); 486 } 487 488 /** 489 * Create a new Timer whose Thread has the indicated name. It will have 490 * normal priority. The boolean argument controls whether or not it 491 * will be a daemon thread. 492 * @param name the name of the Thread 493 * @param daemon true if the Thread should be a daemon thread 494 * @since 1.5 495 */ Timer(String name, boolean daemon)496 public Timer(String name, boolean daemon) 497 { 498 this(daemon, Thread.NORM_PRIORITY, name); 499 } 500 501 /** 502 * Creates a new Timer with a daemon Thread as scheduler if daemon is true, 503 * with the priority given and a default name. 504 */ Timer(boolean daemon, int priority)505 private Timer(boolean daemon, int priority) 506 { 507 this(daemon, priority, "Timer-" + (++nr)); 508 } 509 510 /** 511 * Creates a new Timer with a daemon Thread as scheduler if daemon is true, 512 * with the priority and name given.E 513 */ Timer(boolean daemon, int priority, String name)514 private Timer(boolean daemon, int priority, String name) 515 { 516 canceled = false; 517 queue = new TaskQueue(); 518 scheduler = new Scheduler(queue); 519 thread = new Thread(scheduler, name); 520 thread.setDaemon(daemon); 521 thread.setPriority(priority); 522 thread.start(); 523 } 524 525 /** 526 * Cancels the execution of the scheduler. If a task is executing it will 527 * normally finish execution, but no other tasks will be executed and no 528 * more tasks can be scheduled. 529 */ cancel()530 public void cancel() 531 { 532 canceled = true; 533 queue.stop(); 534 } 535 536 /** 537 * Schedules the task at Time time, repeating every period 538 * milliseconds if period is positive and at a fixed rate if fixed is true. 539 * 540 * @exception IllegalArgumentException if time is negative 541 * @exception IllegalStateException if the task was already scheduled or 542 * canceled or this Timer is canceled or the scheduler thread has died 543 */ schedule(TimerTask task, long time, long period, boolean fixed)544 private void schedule(TimerTask task, long time, long period, boolean fixed) 545 { 546 if (time < 0) 547 throw new IllegalArgumentException("negative time"); 548 549 if (task.scheduled == 0 && task.lastExecutionTime == -1) 550 { 551 task.scheduled = time; 552 task.period = period; 553 task.fixed = fixed; 554 } 555 else 556 { 557 throw new IllegalStateException 558 ("task was already scheduled or canceled"); 559 } 560 561 if (!this.canceled && this.thread != null) 562 { 563 queue.enqueue(task); 564 } 565 else 566 { 567 throw new IllegalStateException 568 ("timer was canceled or scheduler thread has died"); 569 } 570 } 571 positiveDelay(long delay)572 private static void positiveDelay(long delay) 573 { 574 if (delay < 0) 575 { 576 throw new IllegalArgumentException("delay is negative"); 577 } 578 } 579 positivePeriod(long period)580 private static void positivePeriod(long period) 581 { 582 if (period < 0) 583 { 584 throw new IllegalArgumentException("period is negative"); 585 } 586 } 587 588 /** 589 * Schedules the task at the specified data for one time execution. 590 * 591 * @exception IllegalArgumentException if date.getTime() is negative 592 * @exception IllegalStateException if the task was already scheduled or 593 * canceled or this Timer is canceled or the scheduler thread has died 594 */ schedule(TimerTask task, Date date)595 public void schedule(TimerTask task, Date date) 596 { 597 long time = date.getTime(); 598 schedule(task, time, -1, false); 599 } 600 601 /** 602 * Schedules the task at the specified date and reschedules the task every 603 * period milliseconds after the last execution of the task finishes until 604 * this timer or the task is canceled. 605 * 606 * @exception IllegalArgumentException if period or date.getTime() is 607 * negative 608 * @exception IllegalStateException if the task was already scheduled or 609 * canceled or this Timer is canceled or the scheduler thread has died 610 */ schedule(TimerTask task, Date date, long period)611 public void schedule(TimerTask task, Date date, long period) 612 { 613 positivePeriod(period); 614 long time = date.getTime(); 615 schedule(task, time, period, false); 616 } 617 618 /** 619 * Schedules the task after the specified delay milliseconds for one time 620 * execution. 621 * 622 * @exception IllegalArgumentException if delay or 623 * System.currentTimeMillis + delay is negative 624 * @exception IllegalStateException if the task was already scheduled or 625 * canceled or this Timer is canceled or the scheduler thread has died 626 */ schedule(TimerTask task, long delay)627 public void schedule(TimerTask task, long delay) 628 { 629 positiveDelay(delay); 630 long time = System.currentTimeMillis() + delay; 631 schedule(task, time, -1, false); 632 } 633 634 /** 635 * Schedules the task after the delay milliseconds and reschedules the 636 * task every period milliseconds after the last execution of the task 637 * finishes until this timer or the task is canceled. 638 * 639 * @exception IllegalArgumentException if delay or period is negative 640 * @exception IllegalStateException if the task was already scheduled or 641 * canceled or this Timer is canceled or the scheduler thread has died 642 */ schedule(TimerTask task, long delay, long period)643 public void schedule(TimerTask task, long delay, long period) 644 { 645 positiveDelay(delay); 646 positivePeriod(period); 647 long time = System.currentTimeMillis() + delay; 648 schedule(task, time, period, false); 649 } 650 651 /** 652 * Schedules the task at the specified date and reschedules the task at a 653 * fixed rate every period milliseconds until this timer or the task is 654 * canceled. 655 * 656 * @exception IllegalArgumentException if period or date.getTime() is 657 * negative 658 * @exception IllegalStateException if the task was already scheduled or 659 * canceled or this Timer is canceled or the scheduler thread has died 660 */ scheduleAtFixedRate(TimerTask task, Date date, long period)661 public void scheduleAtFixedRate(TimerTask task, Date date, long period) 662 { 663 positivePeriod(period); 664 long time = date.getTime(); 665 schedule(task, time, period, true); 666 } 667 668 /** 669 * Schedules the task after the delay milliseconds and reschedules the task 670 * at a fixed rate every period milliseconds until this timer or the task 671 * is canceled. 672 * 673 * @exception IllegalArgumentException if delay or 674 * System.currentTimeMillis + delay is negative 675 * @exception IllegalStateException if the task was already scheduled or 676 * canceled or this Timer is canceled or the scheduler thread has died 677 */ scheduleAtFixedRate(TimerTask task, long delay, long period)678 public void scheduleAtFixedRate(TimerTask task, long delay, long period) 679 { 680 positiveDelay(delay); 681 positivePeriod(period); 682 long time = System.currentTimeMillis() + delay; 683 schedule(task, time, period, true); 684 } 685 686 /** 687 * Tells the scheduler that the Timer task died 688 * so there will be no more new tasks scheduled. 689 */ finalize()690 protected void finalize() throws Throwable 691 { 692 queue.setNullOnEmpty(true); 693 } 694 695 /** 696 * Removes all cancelled tasks from the queue. 697 * @return the number of tasks removed 698 * @since 1.5 699 */ purge()700 public int purge() 701 { 702 return queue.purge(); 703 } 704 } 705