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 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
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. */
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
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.
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).
62 * @author Mark Wielaard (mark@klomp.org)
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.
74 private static final class TaskQueue
76 /** Default size of this queue */
77 private static final int DEFAULT_SIZE
= 32;
79 /** Whether to return null when there is nothing in the queue */
80 private boolean nullOnEmpty
;
83 * The heap containing all the scheduled TimerTasks
84 * sorted by the TimerTask.scheduled field.
85 * Null when the stop() method has been called.
87 private TimerTask heap
[];
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.
97 * Creates a TaskQueue of default size without any elements in it.
101 heap
= new TimerTask
[DEFAULT_SIZE
];
107 * Adds a TimerTask at the end of the heap.
108 * Grows the heap if necessary by doubling the heap in size.
110 private void add(TimerTask task
)
113 if (elements
== heap
.length
)
115 TimerTask new_heap
[] = new TimerTask
[heap
.length
* 2];
116 System
.arraycopy(heap
, 0, new_heap
, 0, heap
.length
);
119 heap
[elements
] = task
;
123 * Removes the last element from the heap.
124 * Shrinks the heap in half if
125 * elements+DEFAULT_SIZE/2 <= heap.length/4.
127 private void remove()
129 // clear the entry first
130 heap
[elements
] = null;
132 if (elements
+ DEFAULT_SIZE
/ 2 <= (heap
.length
/ 4))
134 TimerTask new_heap
[] = new TimerTask
[heap
.length
/ 2];
135 System
.arraycopy(heap
, 0, new_heap
, 0, elements
+ 1);
141 * Adds a task to the queue and puts it at the correct place
144 public synchronized void enqueue(TimerTask task
)
146 // Check if it is legal to add another element
149 throw new IllegalStateException
150 ("cannot enqueue when stop() has been called on queue");
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
)
160 heap
[child
] = heap
[parent
];
164 // This is the correct place for the new task
166 heap
[0] = null; // clear sentinel
167 // Maybe sched() is waiting for a new element
172 * Returns the top element of the queue.
173 * Can return null when no task is in the queue.
175 private TimerTask
top()
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.
192 public synchronized TimerTask
serve()
194 // The task to return
195 TimerTask task
= null;
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
))
209 // Do we have a task?
212 // The time to wait until the task should be served
213 long time
= task
.scheduled
- System
.currentTimeMillis();
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()
224 catch (InterruptedException _
)
231 // wait until a task is added
232 // or something else happens to the queue
237 catch (InterruptedException _
)
243 // reconstruct the heap
244 TimerTask lastTask
= heap
[elements
];
247 // drop lastTask at the beginning and move it down the heap
251 while (child
<= elements
)
253 if (child
< elements
)
255 if (heap
[child
].scheduled
> heap
[child
+ 1].scheduled
)
261 if (lastTask
.scheduled
<= heap
[child
].scheduled
)
262 break; // found the correct place (the parent) - done
264 heap
[parent
] = heap
[child
];
269 // this is the correct new place for the lastTask
270 heap
[parent
] = lastTask
;
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.
282 public synchronized void setNullOnEmpty(boolean nullOnEmpty
)
284 this.nullOnEmpty
= nullOnEmpty
;
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.
293 public synchronized void stop()
303 * The scheduler that executes all the tasks on a particular TaskQueue,
304 * reschedules any repeating tasks and that waits when no task has to be
305 * executed immediatly. Stops running when canceled or when the parent
306 * Timer has been finalized and no more tasks have to be executed.
308 private static final class Scheduler
implements Runnable
310 // The priority queue containing all the TimerTasks.
311 private TaskQueue queue
;
314 * Creates a new Scheduler that will schedule the tasks on the
317 public Scheduler(TaskQueue queue
)
325 while ((task
= queue
.serve()) != null)
327 // If this task has not been canceled
328 if (task
.scheduled
>= 0)
331 // Mark execution time
332 task
.lastExecutionTime
= task
.scheduled
;
337 // Last time this task is executed
346 catch (ThreadDeath death
)
348 // If an exception escapes, the Timer becomes invalid.
354 /* ignore all errors */
358 // Calculate next time and possibly re-enqueue.
359 if (task
.scheduled
>= 0)
363 task
.scheduled
+= task
.period
;
367 task
.scheduled
= task
.period
+ System
.currentTimeMillis();
374 catch (IllegalStateException ise
)
376 // Ignore. Apparently the Timer queue has been stopped.
383 // Number of Timers created.
384 // Used for creating nice Thread names.
385 private static int nr
;
387 // The queue that all the tasks are put in.
388 // Given to the scheduler
389 private TaskQueue queue
;
391 // The Scheduler that does all the real work
392 private Scheduler scheduler
;
394 // Used to run the scheduler.
395 // Also used to checked if the Thread is still running by calling
396 // thread.isAlive(). Sometimes a Thread is suddenly killed by the system
397 // (if it belonged to an Applet).
398 private Thread thread
;
400 // When cancelled we don't accept any more TimerTasks.
401 private boolean canceled
;
404 * Creates a new Timer with a non daemon Thread as Scheduler, with normal
405 * priority and a default name.
413 * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
414 * with normal priority and a default name.
416 public Timer(boolean daemon
)
418 this(daemon
, Thread
.NORM_PRIORITY
);
422 * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
423 * with the priority given and a default name.
425 private Timer(boolean daemon
, int priority
)
427 this(daemon
, priority
, "Timer-" + (++nr
));
431 * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
432 * with the priority and name given.E
434 private Timer(boolean daemon
, int priority
, String name
)
437 queue
= new TaskQueue();
438 scheduler
= new Scheduler(queue
);
439 thread
= new Thread(scheduler
, name
);
440 thread
.setDaemon(daemon
);
441 thread
.setPriority(priority
);
446 * Cancels the execution of the scheduler. If a task is executing it will
447 * normally finish execution, but no other tasks will be executed and no
448 * more tasks can be scheduled.
457 * Schedules the task at Time time, repeating every period
458 * milliseconds if period is positive and at a fixed rate if fixed is true.
460 * @exception IllegalArgumentException if time is negative
461 * @exception IllegalStateException if the task was already scheduled or
462 * canceled or this Timer is canceled or the scheduler thread has died
464 private void schedule(TimerTask task
, long time
, long period
, boolean fixed
)
467 throw new IllegalArgumentException("negative time");
469 if (task
.scheduled
== 0 && task
.lastExecutionTime
== -1)
471 task
.scheduled
= time
;
472 task
.period
= period
;
477 throw new IllegalStateException
478 ("task was already scheduled or canceled");
481 if (!this.canceled
&& this.thread
!= null)
487 throw new IllegalStateException
488 ("timer was canceled or scheduler thread has died");
492 private static void positiveDelay(long delay
)
496 throw new IllegalArgumentException("delay is negative");
500 private static void positivePeriod(long period
)
504 throw new IllegalArgumentException("period is negative");
509 * Schedules the task at the specified data for one time execution.
511 * @exception IllegalArgumentException if date.getTime() is negative
512 * @exception IllegalStateException if the task was already scheduled or
513 * canceled or this Timer is canceled or the scheduler thread has died
515 public void schedule(TimerTask task
, Date date
)
517 long time
= date
.getTime();
518 schedule(task
, time
, -1, false);
522 * Schedules the task at the specified date and reschedules the task every
523 * period milliseconds after the last execution of the task finishes until
524 * this timer or the task is canceled.
526 * @exception IllegalArgumentException if period or date.getTime() is
528 * @exception IllegalStateException if the task was already scheduled or
529 * canceled or this Timer is canceled or the scheduler thread has died
531 public void schedule(TimerTask task
, Date date
, long period
)
533 positivePeriod(period
);
534 long time
= date
.getTime();
535 schedule(task
, time
, period
, false);
539 * Schedules the task after the specified delay milliseconds for one time
542 * @exception IllegalArgumentException if delay or
543 * System.currentTimeMillis + delay is negative
544 * @exception IllegalStateException if the task was already scheduled or
545 * canceled or this Timer is canceled or the scheduler thread has died
547 public void schedule(TimerTask task
, long delay
)
549 positiveDelay(delay
);
550 long time
= System
.currentTimeMillis() + delay
;
551 schedule(task
, time
, -1, false);
555 * Schedules the task after the delay milliseconds and reschedules the
556 * task every period milliseconds after the last execution of the task
557 * finishes until this timer or the task is canceled.
559 * @exception IllegalArgumentException if delay or period is negative
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 schedule(TimerTask task
, long delay
, long period
)
565 positiveDelay(delay
);
566 positivePeriod(period
);
567 long time
= System
.currentTimeMillis() + delay
;
568 schedule(task
, time
, period
, false);
572 * Schedules the task at the specified date and reschedules the task at a
573 * fixed rate every period milliseconds until this timer or the task is
576 * @exception IllegalArgumentException if period or date.getTime() is
578 * @exception IllegalStateException if the task was already scheduled or
579 * canceled or this Timer is canceled or the scheduler thread has died
581 public void scheduleAtFixedRate(TimerTask task
, Date date
, long period
)
583 positivePeriod(period
);
584 long time
= date
.getTime();
585 schedule(task
, time
, period
, true);
589 * Schedules the task after the delay milliseconds and reschedules the task
590 * at a fixed rate every period milliseconds until this timer or the task
593 * @exception IllegalArgumentException if delay or
594 * System.currentTimeMillis + delay is negative
595 * @exception IllegalStateException if the task was already scheduled or
596 * canceled or this Timer is canceled or the scheduler thread has died
598 public void scheduleAtFixedRate(TimerTask task
, long delay
, long period
)
600 positiveDelay(delay
);
601 positivePeriod(period
);
602 long time
= System
.currentTimeMillis() + delay
;
603 schedule(task
, time
, period
, true);
607 * Tells the scheduler that the Timer task died
608 * so there will be no more new tasks scheduled.
610 protected void finalize() throws Throwable
612 queue
.setNullOnEmpty(true);