1 /* Timer.java -- Timer that runs TimerTasks at a later time.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
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)
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.
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., 59 Temple Place, Suite 330, Boston, MA
21 As a special exception, if you link this library with other files to
22 produce an executable, this library does not by itself cause the
23 resulting executable to be covered by the GNU General Public License.
24 This exception does not however invalidate any other reasons why the
25 executable file might be covered by the GNU General Public License. */
30 * Timer that can run TimerTasks at a later time.
31 * TimerTasks can be scheduled for one time execution at some time in the
32 * future. They can be scheduled to be rescheduled at a time period after the
33 * task was last executed. Or they can be scheduled to be executed repeatedly
36 * The normal scheduling will result in a more or less even delay in time
37 * between successive executions, but the executions could drift in time if
38 * the task (or other tasks) takes a long time to execute. Fixed delay
39 * scheduling guarantees more or less that the task will be executed at a
40 * specific time, but if there is ever a delay in execution then the period
41 * between successive executions will be shorter. The first method of
42 * repeated scheduling is preferred for repeated tasks in response to user
43 * interaction, the second method of repeated scheduling is preferred for tasks
44 * that act like alarms.
46 * The Timer keeps a binary heap as a task priority queue which means that
47 * scheduling and serving of a task in a queue of n tasks costs O(log n).
51 * @author Mark Wielaard (mark@klomp.org)
56 * Priority Task Queue.
57 * TimerTasks are kept in a binary heap.
58 * The scheduler calls sleep() on the queue when it has nothing to do or
59 * has to wait. A sleeping scheduler can be notified by calling interrupt()
60 * which is automatically called by the enqueue(), cancel() and
61 * timerFinalized() methods.
63 private static final class TaskQueue
65 /** Default size of this queue */
66 private final int DEFAULT_SIZE = 32;
68 /** Whether to return null when there is nothing in the queue */
69 private boolean nullOnEmpty;
72 * The heap containing all the scheduled TimerTasks
73 * sorted by the TimerTask.scheduled field.
74 * Null when the stop() method has been called.
76 private TimerTask heap[];
79 * The actual number of elements in the heap
80 * Can be less then heap.length.
81 * Note that heap[0] is used as a sentinel.
86 * Creates a TaskQueue of default size without any elements in it.
90 heap = new TimerTask[DEFAULT_SIZE];
96 * Adds a TimerTask at the end of the heap.
97 * Grows the heap if necessary by doubling the heap in size.
99 private void add(TimerTask task)
102 if (elements == heap.length)
104 TimerTask new_heap[] = new TimerTask[heap.length * 2];
105 System.arraycopy(heap, 0, new_heap, 0, heap.length);
108 heap[elements] = task;
112 * Removes the last element from the heap.
113 * Shrinks the heap in half if
114 * elements+DEFAULT_SIZE/2 <= heap.length/4.
116 private void remove()
118 // clear the entry first
119 heap[elements] = null;
121 if (elements + DEFAULT_SIZE / 2 <= (heap.length / 4))
123 TimerTask new_heap[] = new TimerTask[heap.length / 2];
124 System.arraycopy(heap, 0, new_heap, 0, elements + 1);
130 * Adds a task to the queue and puts it at the correct place
133 public synchronized void enqueue(TimerTask task)
135 // Check if it is legal to add another element
138 throw new IllegalStateException
139 ("cannot enqueue when stop() has been called on queue");
142 heap[0] = task; // sentinel
143 add(task); // put the new task at the end
144 // Now push the task up in the heap until it has reached its place
145 int child = elements;
146 int parent = child / 2;
147 while (heap[parent].scheduled > task.scheduled)
149 heap[child] = heap[parent];
153 // This is the correct place for the new task
155 heap[0] = null; // clear sentinel
156 // Maybe sched() is waiting for a new element
161 * Returns the top element of the queue.
162 * Can return null when no task is in the queue.
164 private TimerTask top()
177 * Returns the top task in the Queue.
178 * Removes the element from the heap and reorders the heap first.
179 * Can return null when there is nothing in the queue.
181 public synchronized TimerTask serve()
183 // The task to return
184 TimerTask task = null;
191 // return null when asked to stop
192 // or if asked to return null when the queue is empty
193 if ((heap == null) || (task == null && nullOnEmpty))
198 // Do we have a task?
201 // The time to wait until the task should be served
202 long time = task.scheduled - System.currentTimeMillis();
205 // This task should not yet be served
206 // So wait until this task is ready
207 // or something else happens to the queue
208 task = null; // set to null to make sure we call top()
213 catch (InterruptedException _)
220 // wait until a task is added
221 // or something else happens to the queue
226 catch (InterruptedException _)
232 // reconstruct the heap
233 TimerTask lastTask = heap[elements];
236 // drop lastTask at the beginning and move it down the heap
240 while (child <= elements)
242 if (child < elements)
244 if (heap[child].scheduled > heap[child + 1].scheduled)
250 if (lastTask.scheduled <= heap[child].scheduled)
251 break; // found the correct place (the parent) - done
253 heap[parent] = heap[child];
258 // this is the correct new place for the lastTask
259 heap[parent] = lastTask;
266 * When nullOnEmpty is true the serve() method will return null when
267 * there are no tasks in the queue, otherwise it will wait until
268 * a new element is added to the queue. It is used to indicate to
269 * the scheduler that no new tasks will ever be added to the queue.
271 public synchronized void setNullOnEmpty(boolean nullOnEmpty)
273 this.nullOnEmpty = nullOnEmpty;
278 * When this method is called the current and all future calls to
279 * serve() will return null. It is used to indicate to the Scheduler
280 * that it should stop executing since no more tasks will come.
282 public synchronized void stop()
291 * The scheduler that executes all the tasks on a particular TaskQueue,
292 * reschedules any repeating tasks and that waits when no task has to be
293 * executed immediatly. Stops running when canceled or when the parent
294 * Timer has been finalized and no more tasks have to be executed.
296 private static final class Scheduler implements Runnable
298 // The priority queue containing all the TimerTasks.
299 private TaskQueue queue;
302 * Creates a new Scheduler that will schedule the tasks on the
305 public Scheduler(TaskQueue queue)
313 while ((task = queue.serve()) != null)
315 // If this task has not been canceled
316 if (task.scheduled >= 0)
319 // Mark execution time
320 task.lastExecutionTime = task.scheduled;
325 // Last time this task is executed
336 /* ignore all errors */
340 // Calculate next time and possibly re-enqueue.
341 if (task.scheduled >= 0)
345 task.scheduled += task.period;
349 task.scheduled = task.period + System.currentTimeMillis();
356 catch (IllegalStateException ise)
358 // Ignore. Apparently the Timer queue has been stopped.
365 // Number of Timers created.
366 // Used for creating nice Thread names.
367 private static int nr = 0;
369 // The queue that all the tasks are put in.
370 // Given to the scheduler
371 private TaskQueue queue;
373 // The Scheduler that does all the real work
374 private Scheduler scheduler;
376 // Used to run the scheduler.
377 // Also used to checked if the Thread is still running by calling
378 // thread.isAlive(). Sometimes a Thread is suddenly killed by the system
379 // (if it belonged to an Applet).
380 private Thread thread;
382 // When cancelled we don't accept any more TimerTasks.
383 private boolean canceled;
386 * Creates a new Timer with a non daemon Thread as Scheduler, with normal
387 * priority and a default name.
395 * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
396 * with normal priority and a default name.
398 public Timer(boolean daemon)
400 this(daemon, Thread.NORM_PRIORITY);
404 * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
405 * with the priority given and a default name.
407 private Timer(boolean daemon, int priority)
409 this(daemon, priority, "Timer-" + (++nr));
413 * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
414 * with the priority and name given.E
416 private Timer(boolean daemon, int priority, String name)
419 queue = new TaskQueue();
420 scheduler = new Scheduler(queue);
421 thread = new Thread(scheduler, name);
422 thread.setDaemon(daemon);
423 thread.setPriority(priority);
428 * Cancels the execution of the scheduler. If a task is executing it will
429 * normally finish execution, but no other tasks will be executed and no
430 * more tasks can be scheduled.
439 * Schedules the task at Time time, repeating every period
440 * milliseconds if period is positive and at a fixed rate if fixed is true.
442 * @exception IllegalArgumentException if time is negative
443 * @exception IllegalStateException if the task was already scheduled or
444 * canceled or this Timer is canceled or the scheduler thread has died
446 private void schedule(TimerTask task, long time, long period, boolean fixed)
449 throw new IllegalArgumentException("negative time");
451 if (task.scheduled == 0 && task.lastExecutionTime == -1)
453 task.scheduled = time;
454 task.period = period;
459 throw new IllegalStateException
460 ("task was already scheduled or canceled");
463 if (!this.canceled && this.thread != null)
469 throw new IllegalStateException
470 ("timer was canceled or scheduler thread has died");
474 private static void positiveDelay(long delay)
478 throw new IllegalArgumentException("delay is negative");
482 private static void positivePeriod(long period)
486 throw new IllegalArgumentException("period is negative");
491 * Schedules the task at the specified data for one time execution.
493 * @exception IllegalArgumentException if date.getTime() is negative
494 * @exception IllegalStateException if the task was already scheduled or
495 * canceled or this Timer is canceled or the scheduler thread has died
497 public void schedule(TimerTask task, Date date)
499 long time = date.getTime();
500 schedule(task, time, -1, false);
504 * Schedules the task at the specified date and reschedules the task every
505 * period milliseconds after the last execution of the task finishes until
506 * this timer or the task is canceled.
508 * @exception IllegalArgumentException if period or date.getTime() is
510 * @exception IllegalStateException if the task was already scheduled or
511 * canceled or this Timer is canceled or the scheduler thread has died
513 public void schedule(TimerTask task, Date date, long period)
515 positivePeriod(period);
516 long time = date.getTime();
517 schedule(task, time, period, false);
521 * Schedules the task after the specified delay milliseconds for one time
524 * @exception IllegalArgumentException if delay or
525 * System.currentTimeMillis + delay is negative
526 * @exception IllegalStateException if the task was already scheduled or
527 * canceled or this Timer is canceled or the scheduler thread has died
529 public void schedule(TimerTask task, long delay)
531 positiveDelay(delay);
532 long time = System.currentTimeMillis() + delay;
533 schedule(task, time, -1, false);
537 * Schedules the task after the delay milliseconds and reschedules the
538 * task every period milliseconds after the last execution of the task
539 * finishes until this timer or the task is canceled.
541 * @exception IllegalArgumentException if delay or period is negative
542 * @exception IllegalStateException if the task was already scheduled or
543 * canceled or this Timer is canceled or the scheduler thread has died
545 public void schedule(TimerTask task, long delay, long period)
547 positiveDelay(delay);
548 positivePeriod(period);
549 long time = System.currentTimeMillis() + delay;
550 schedule(task, time, period, false);
554 * Schedules the task at the specified date and reschedules the task at a
555 * fixed rate every period milliseconds until this timer or the task is
558 * @exception IllegalArgumentException if period or date.getTime() is
560 * @exception IllegalStateException if the task was already scheduled or
561 * canceled or this Timer is canceled or the scheduler thread has died
563 public void scheduleAtFixedRate(TimerTask task, Date date, long period)
565 positivePeriod(period);
566 long time = date.getTime();
567 schedule(task, time, period, true);
571 * Schedules the task after the delay milliseconds and reschedules the task
572 * at a fixed rate every period milliseconds until this timer or the task
575 * @exception IllegalArgumentException if delay or
576 * System.currentTimeMillis + delay is negative
577 * @exception IllegalStateException if the task was already scheduled or
578 * canceled or this Timer is canceled or the scheduler thread has died
580 public void scheduleAtFixedRate(TimerTask task, long delay, long period)
582 positiveDelay(delay);
583 positivePeriod(period);
584 long time = System.currentTimeMillis() + delay;
585 schedule(task, time, period, true);
589 * Tells the scheduler that the Timer task died
590 * so there will be no more new tasks scheduled.
592 protected void finalize()
594 queue.setNullOnEmpty(true);