001    /* Timer.java -- Timer that runs TimerTasks at a later time.
002       Copyright (C) 2000, 2001, 2005 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package java.util;
039    
040    /**
041     * Timer that can run TimerTasks at a later time.
042     * TimerTasks can be scheduled for one time execution at some time in the
043     * future. They can be scheduled to be rescheduled at a time period after the
044     * task was last executed. Or they can be scheduled to be executed repeatedly
045     * at a fixed rate.
046     * <p>
047     * The normal scheduling will result in a more or less even delay in time
048     * between successive executions, but the executions could drift in time if
049     * the task (or other tasks) takes a long time to execute. Fixed delay
050     * scheduling guarantees more or less that the task will be executed at a
051     * specific time, but if there is ever a delay in execution then the period
052     * between successive executions will be shorter. The first method of
053     * repeated scheduling is preferred for repeated tasks in response to user
054     * interaction, the second method of repeated scheduling is preferred for tasks
055     * that act like alarms.
056     * <p>
057     * The Timer keeps a binary heap as a task priority queue which means that
058     * scheduling and serving of a task in a queue of n tasks costs O(log n).
059     *
060     * @see TimerTask
061     * @since 1.3
062     * @author Mark Wielaard (mark@klomp.org)
063     */
064    public class Timer
065    {
066      /**
067       * Priority Task Queue.
068       * TimerTasks are kept in a binary heap.
069       * The scheduler calls sleep() on the queue when it has nothing to do or
070       * has to wait. A sleeping scheduler can be notified by calling interrupt()
071       * which is automatically called by the enqueue(), cancel() and
072       * timerFinalized() methods.
073       */
074      private static final class TaskQueue
075      {
076        /** Default size of this queue */
077        private static final int DEFAULT_SIZE = 32;
078    
079        /** Whether to return null when there is nothing in the queue */
080        private boolean nullOnEmpty;
081    
082        /**
083         * The heap containing all the scheduled TimerTasks
084         * sorted by the TimerTask.scheduled field.
085         * Null when the stop() method has been called.
086         */
087        private TimerTask heap[];
088    
089        /**
090         * The actual number of elements in the heap
091         * Can be less then heap.length.
092         * Note that heap[0] is used as a sentinel.
093         */
094        private int elements;
095    
096        /**
097         * Creates a TaskQueue of default size without any elements in it.
098         */
099        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    }