libjava/java/util/Timer.java

   1 /* Timer.java -- Timer that runs TimerTasks at a later time.
   2    Copyright (C) 2000, 2001 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., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 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 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   }                             // TaskQueue
 301
 302   /**
 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.
 307    */
 308   private static final class Scheduler implements Runnable
 309   {
 310     // The priority queue containing all the TimerTasks.
 311     private TaskQueue queue;
 312
 313     /**
 314      * Creates a new Scheduler that will schedule the tasks on the
 315      * given TaskQueue.
 316      */
 317     public Scheduler(TaskQueue queue)
 318     {
 319       this.queue = queue;
 320     }
 321
 322     public void run()
 323     {
 324       TimerTask task;
 325       while ((task = queue.serve()) != null)
 326         {
 327           // If this task has not been canceled
 328           if (task.scheduled >= 0)
 329             {
 330
 331               // Mark execution time
 332               task.lastExecutionTime = task.scheduled;
 333
 334               // Repeatable task?
 335               if (task.period < 0)
 336                 {
 337                   // Last time this task is executed
 338                   task.scheduled = -1;
 339                 }
 340
 341               // Run the task
 342               try
 343                 {
 344                   task.run();
 345                 }
 346               catch (Throwable t)
 347                 {
 348                   /* ignore all errors */
 349                 }
 350             }
 351
 352           // Calculate next time and possibly re-enqueue.
 353           if (task.scheduled >= 0)
 354             {
 355               if (task.fixed)
 356                 {
 357                   task.scheduled += task.period;
 358                 }
 359               else
 360                 {
 361                   task.scheduled = task.period + System.currentTimeMillis();
 362                 }
 363
 364               try
 365                 {
 366                   queue.enqueue(task);
 367                 }
 368               catch (IllegalStateException ise)
 369                 {
 370                   // Ignore. Apparently the Timer queue has been stopped.
 371                 }
 372             }
 373         }
 374     }
 375   }                             // Scheduler
 376
 377   // Number of Timers created.
 378   // Used for creating nice Thread names.
 379   private static int nr = 0;
 380
 381   // The queue that all the tasks are put in.
 382   // Given to the scheduler
 383   private TaskQueue queue;
 384
 385   // The Scheduler that does all the real work
 386   private Scheduler scheduler;
 387
 388   // Used to run the scheduler.
 389   // Also used to checked if the Thread is still running by calling
 390   // thread.isAlive(). Sometimes a Thread is suddenly killed by the system
 391   // (if it belonged to an Applet).
 392   private Thread thread;
 393
 394   // When cancelled we don't accept any more TimerTasks.
 395   private boolean canceled;
 396
 397   /**
 398    * Creates a new Timer with a non daemon Thread as Scheduler, with normal
 399    * priority and a default name.
 400    */
 401   public Timer()
 402   {
 403     this(false);
 404   }
 405
 406   /**
 407    * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
 408    * with normal priority and a default name.
 409    */
 410   public Timer(boolean daemon)
 411   {
 412     this(daemon, Thread.NORM_PRIORITY);
 413   }
 414
 415   /**
 416    * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
 417    * with the priority given and a default name.
 418    */
 419   private Timer(boolean daemon, int priority)
 420   {
 421     this(daemon, priority, "Timer-" + (++nr));
 422   }
 423
 424   /**
 425    * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
 426    * with the priority and name given.E
 427    */
 428   private Timer(boolean daemon, int priority, String name)
 429   {
 430     canceled = false;
 431     queue = new TaskQueue();
 432     scheduler = new Scheduler(queue);
 433     thread = new Thread(scheduler, name);
 434     thread.setDaemon(daemon);
 435     thread.setPriority(priority);
 436     thread.start();
 437   }
 438
 439   /**
 440    * Cancels the execution of the scheduler. If a task is executing it will
 441    * normally finish execution, but no other tasks will be executed and no
 442    * more tasks can be scheduled.
 443    */
 444   public void cancel()
 445   {
 446     canceled = true;
 447     queue.stop();
 448   }
 449
 450   /**
 451    * Schedules the task at Time time, repeating every period
 452    * milliseconds if period is positive and at a fixed rate if fixed is true.
 453    *
 454    * @exception IllegalArgumentException if time is negative
 455    * @exception IllegalStateException if the task was already scheduled or
 456    * canceled or this Timer is canceled or the scheduler thread has died
 457    */
 458   private void schedule(TimerTask task, long time, long period, boolean fixed)
 459   {
 460     if (time < 0)
 461       throw new IllegalArgumentException("negative time");
 462
 463     if (task.scheduled == 0 && task.lastExecutionTime == -1)
 464       {
 465         task.scheduled = time;
 466         task.period = period;
 467         task.fixed = fixed;
 468       }
 469     else
 470       {
 471         throw new IllegalStateException
 472           ("task was already scheduled or canceled");
 473       }
 474
 475     if (!this.canceled && this.thread != null)
 476       {
 477         queue.enqueue(task);
 478       }
 479     else
 480       {
 481         throw new IllegalStateException
 482           ("timer was canceled or scheduler thread has died");
 483       }
 484   }
 485
 486   private static void positiveDelay(long delay)
 487   {
 488     if (delay < 0)
 489       {
 490         throw new IllegalArgumentException("delay is negative");
 491       }
 492   }
 493
 494   private static void positivePeriod(long period)
 495   {
 496     if (period < 0)
 497       {
 498         throw new IllegalArgumentException("period is negative");
 499       }
 500   }
 501
 502   /**
 503    * Schedules the task at the specified data for one time execution.
 504    *
 505    * @exception IllegalArgumentException if date.getTime() is negative
 506    * @exception IllegalStateException if the task was already scheduled or
 507    * canceled or this Timer is canceled or the scheduler thread has died
 508    */
 509   public void schedule(TimerTask task, Date date)
 510   {
 511     long time = date.getTime();
 512     schedule(task, time, -1, false);
 513   }
 514
 515   /**
 516    * Schedules the task at the specified date and reschedules the task every
 517    * period milliseconds after the last execution of the task finishes until
 518    * this timer or the task is canceled.
 519    *
 520    * @exception IllegalArgumentException if period or date.getTime() is
 521    * negative
 522    * @exception IllegalStateException if the task was already scheduled or
 523    * canceled or this Timer is canceled or the scheduler thread has died
 524    */
 525   public void schedule(TimerTask task, Date date, long period)
 526   {
 527     positivePeriod(period);
 528     long time = date.getTime();
 529     schedule(task, time, period, false);
 530   }
 531
 532   /**
 533    * Schedules the task after the specified delay milliseconds for one time
 534    * execution.
 535    *
 536    * @exception IllegalArgumentException if delay or
 537    * System.currentTimeMillis + delay is negative
 538    * @exception IllegalStateException if the task was already scheduled or
 539    * canceled or this Timer is canceled or the scheduler thread has died
 540    */
 541   public void schedule(TimerTask task, long delay)
 542   {
 543     positiveDelay(delay);
 544     long time = System.currentTimeMillis() + delay;
 545     schedule(task, time, -1, false);
 546   }
 547
 548   /**
 549    * Schedules the task after the delay milliseconds and reschedules the
 550    * task every period milliseconds after the last execution of the task
 551    * finishes until this timer or the task is canceled.
 552    *
 553    * @exception IllegalArgumentException if delay or period is negative
 554    * @exception IllegalStateException if the task was already scheduled or
 555    * canceled or this Timer is canceled or the scheduler thread has died
 556    */
 557   public void schedule(TimerTask task, long delay, long period)
 558   {
 559     positiveDelay(delay);
 560     positivePeriod(period);
 561     long time = System.currentTimeMillis() + delay;
 562     schedule(task, time, period, false);
 563   }
 564
 565   /**
 566    * Schedules the task at the specified date and reschedules the task at a
 567    * fixed rate every period milliseconds until this timer or the task is
 568    * canceled.
 569    *
 570    * @exception IllegalArgumentException if period or date.getTime() is
 571    * negative
 572    * @exception IllegalStateException if the task was already scheduled or
 573    * canceled or this Timer is canceled or the scheduler thread has died
 574    */
 575   public void scheduleAtFixedRate(TimerTask task, Date date, long period)
 576   {
 577     positivePeriod(period);
 578     long time = date.getTime();
 579     schedule(task, time, period, true);
 580   }
 581
 582   /**
 583    * Schedules the task after the delay milliseconds and reschedules the task
 584    * at a fixed rate every period milliseconds until this timer or the task
 585    * is canceled.
 586    *
 587    * @exception IllegalArgumentException if delay or
 588    * System.currentTimeMillis + delay is negative
 589    * @exception IllegalStateException if the task was already scheduled or
 590    * canceled or this Timer is canceled or the scheduler thread has died
 591    */
 592   public void scheduleAtFixedRate(TimerTask task, long delay, long period)
 593   {
 594     positiveDelay(delay);
 595     positivePeriod(period);
 596     long time = System.currentTimeMillis() + delay;
 597     schedule(task, time, period, true);
 598   }
 599
 600   /**
 601    * Tells the scheduler that the Timer task died
 602    * so there will be no more new tasks scheduled.
 603    */
 604   protected void finalize() throws Throwable
 605   {
 606     queue.setNullOnEmpty(true);
 607   }
 608 }