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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 372: public Scheduler(TaskQueue queue) 373: { 374: this.queue = queue; 375: } 376: 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: 572: private static void positiveDelay(long delay) 573: { 574: if (delay < 0) 575: { 576: throw new IllegalArgumentException("delay is negative"); 577: } 578: } 579: 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 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: */ 700: public int purge() 701: { 702: return queue.purge(); 703: } 704: }