rt/emul/compact/src/main/java/java/util/Timer.java
author Jaroslav Tulach <jaroslav.tulach@apidesign.org>
Tue, 17 Jan 2017 07:04:06 +0100
changeset 1985 cd1cc103a03c
parent 1407 32e050a07754
permissions -rw-r--r--
Implementation of ClassValue for bck2brwsr
     1 /*
     2  * Copyright (c) 1999, 2008, Oracle and/or its affiliates. All rights reserved.
     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     4  *
     5  * This code is free software; you can redistribute it and/or modify it
     6  * under the terms of the GNU General Public License version 2 only, as
     7  * published by the Free Software Foundation.  Oracle designates this
     8  * particular file as subject to the "Classpath" exception as provided
     9  * by Oracle in the LICENSE file that accompanied this code.
    10  *
    11  * This code is distributed in the hope that it will be useful, but WITHOUT
    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    14  * version 2 for more details (a copy is included in the LICENSE file that
    15  * accompanied this code).
    16  *
    17  * You should have received a copy of the GNU General Public License version
    18  * 2 along with this work; if not, write to the Free Software Foundation,
    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
    20  *
    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
    22  * or visit www.oracle.com if you need additional information or have any
    23  * questions.
    24  */
    25 
    26 package java.util;
    27 import java.util.Date;
    28 import java.util.concurrent.atomic.AtomicInteger;
    29 import org.apidesign.bck2brwsr.core.JavaScriptBody;
    30 
    31 /**
    32  * A facility for threads to schedule tasks for future execution in a
    33  * background thread.  Tasks may be scheduled for one-time execution, or for
    34  * repeated execution at regular intervals.
    35  *
    36  * <p>Corresponding to each <tt>Timer</tt> object is a single background
    37  * thread that is used to execute all of the timer's tasks, sequentially.
    38  * Timer tasks should complete quickly.  If a timer task takes excessive time
    39  * to complete, it "hogs" the timer's task execution thread.  This can, in
    40  * turn, delay the execution of subsequent tasks, which may "bunch up" and
    41  * execute in rapid succession when (and if) the offending task finally
    42  * completes.
    43  *
    44  * <p>After the last live reference to a <tt>Timer</tt> object goes away
    45  * <i>and</i> all outstanding tasks have completed execution, the timer's task
    46  * execution thread terminates gracefully (and becomes subject to garbage
    47  * collection).  However, this can take arbitrarily long to occur.  By
    48  * default, the task execution thread does not run as a <i>daemon thread</i>,
    49  * so it is capable of keeping an application from terminating.  If a caller
    50  * wants to terminate a timer's task execution thread rapidly, the caller
    51  * should invoke the timer's <tt>cancel</tt> method.
    52  *
    53  * <p>If the timer's task execution thread terminates unexpectedly, for
    54  * example, because its <tt>stop</tt> method is invoked, any further
    55  * attempt to schedule a task on the timer will result in an
    56  * <tt>IllegalStateException</tt>, as if the timer's <tt>cancel</tt>
    57  * method had been invoked.
    58  *
    59  * <p>This class is thread-safe: multiple threads can share a single
    60  * <tt>Timer</tt> object without the need for external synchronization.
    61  *
    62  * <p>This class does <i>not</i> offer real-time guarantees: it schedules
    63  * tasks using the <tt>Object.wait(long)</tt> method.
    64  *
    65  * <p>Java 5.0 introduced the {@code java.util.concurrent} package and
    66  * one of the concurrency utilities therein is the {@link
    67  * java.util.concurrent.ScheduledThreadPoolExecutor
    68  * ScheduledThreadPoolExecutor} which is a thread pool for repeatedly
    69  * executing tasks at a given rate or delay.  It is effectively a more
    70  * versatile replacement for the {@code Timer}/{@code TimerTask}
    71  * combination, as it allows multiple service threads, accepts various
    72  * time units, and doesn't require subclassing {@code TimerTask} (just
    73  * implement {@code Runnable}).  Configuring {@code
    74  * ScheduledThreadPoolExecutor} with one thread makes it equivalent to
    75  * {@code Timer}.
    76  *
    77  * <p>Implementation note: This class scales to large numbers of concurrently
    78  * scheduled tasks (thousands should present no problem).  Internally,
    79  * it uses a binary heap to represent its task queue, so the cost to schedule
    80  * a task is O(log n), where n is the number of concurrently scheduled tasks.
    81  *
    82  * <p>Implementation note: All constructors start a timer thread.
    83  *
    84  * @author  Josh Bloch
    85  * @see     TimerTask
    86  * @see     Object#wait(long)
    87  * @since   1.3
    88  */
    89 
    90 public class Timer {
    91     /**
    92      * The timer task queue.  This data structure is shared with the timer
    93      * thread.  The timer produces tasks, via its various schedule calls,
    94      * and the timer thread consumes, executing timer tasks as appropriate,
    95      * and removing them from the queue when they're obsolete.
    96      */
    97     private final TaskQueue queue = new TaskQueue();
    98 
    99     /**
   100      * The timer thread.
   101      */
   102     private final TimerThread thread = new TimerThread(queue);
   103 
   104     /**
   105      * This object causes the timer's task execution thread to exit
   106      * gracefully when there are no live references to the Timer object and no
   107      * tasks in the timer queue.  It is used in preference to a finalizer on
   108      * Timer as such a finalizer would be susceptible to a subclass's
   109      * finalizer forgetting to call it.
   110      */
   111     private final Object threadReaper = new Object() {
   112         protected void finalize() throws Throwable {
   113             synchronized(queue) {
   114                 thread.newTasksMayBeScheduled = false;
   115                 thread.notifyQueue(1); // In case queue is empty.
   116             }
   117         }
   118     };
   119 
   120     /**
   121      * This ID is used to generate thread names.
   122      */
   123     private final static AtomicInteger nextSerialNumber = new AtomicInteger(0);
   124     private static int serialNumber() {
   125         return nextSerialNumber.getAndIncrement();
   126     }
   127 
   128     /**
   129      * Creates a new timer.  The associated thread does <i>not</i>
   130      * {@linkplain Thread#setDaemon run as a daemon}.
   131      */
   132     public Timer() {
   133         this("Timer-" + serialNumber());
   134     }
   135 
   136     /**
   137      * Creates a new timer whose associated thread may be specified to
   138      * {@linkplain Thread#setDaemon run as a daemon}.
   139      * A daemon thread is called for if the timer will be used to
   140      * schedule repeating "maintenance activities", which must be
   141      * performed as long as the application is running, but should not
   142      * prolong the lifetime of the application.
   143      *
   144      * @param isDaemon true if the associated thread should run as a daemon.
   145      */
   146     public Timer(boolean isDaemon) {
   147         this("Timer-" + serialNumber(), isDaemon);
   148     }
   149 
   150     /**
   151      * Creates a new timer whose associated thread has the specified name.
   152      * The associated thread does <i>not</i>
   153      * {@linkplain Thread#setDaemon run as a daemon}.
   154      *
   155      * @param name the name of the associated thread
   156      * @throws NullPointerException if {@code name} is null
   157      * @since 1.5
   158      */
   159     public Timer(String name) {
   160     }
   161 
   162     /**
   163      * Creates a new timer whose associated thread has the specified name,
   164      * and may be specified to
   165      * {@linkplain Thread#setDaemon run as a daemon}.
   166      *
   167      * @param name the name of the associated thread
   168      * @param isDaemon true if the associated thread should run as a daemon
   169      * @throws NullPointerException if {@code name} is null
   170      * @since 1.5
   171      */
   172     public Timer(String name, boolean isDaemon) {
   173     }
   174 
   175     /**
   176      * Schedules the specified task for execution after the specified delay.
   177      *
   178      * @param task  task to be scheduled.
   179      * @param delay delay in milliseconds before task is to be executed.
   180      * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
   181      *         <tt>delay + System.currentTimeMillis()</tt> is negative.
   182      * @throws IllegalStateException if task was already scheduled or
   183      *         cancelled, timer was cancelled, or timer thread terminated.
   184      * @throws NullPointerException if {@code task} is null
   185      */
   186     public void schedule(TimerTask task, long delay) {
   187         if (delay < 0)
   188             throw new IllegalArgumentException("Negative delay.");
   189         sched(task, System.currentTimeMillis()+delay, 0);
   190     }
   191 
   192     /**
   193      * Schedules the specified task for execution at the specified time.  If
   194      * the time is in the past, the task is scheduled for immediate execution.
   195      *
   196      * @param task task to be scheduled.
   197      * @param time time at which task is to be executed.
   198      * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
   199      * @throws IllegalStateException if task was already scheduled or
   200      *         cancelled, timer was cancelled, or timer thread terminated.
   201      * @throws NullPointerException if {@code task} or {@code time} is null
   202      */
   203     public void schedule(TimerTask task, Date time) {
   204         sched(task, time.getTime(), 0);
   205     }
   206 
   207     /**
   208      * Schedules the specified task for repeated <i>fixed-delay execution</i>,
   209      * beginning after the specified delay.  Subsequent executions take place
   210      * at approximately regular intervals separated by the specified period.
   211      *
   212      * <p>In fixed-delay execution, each execution is scheduled relative to
   213      * the actual execution time of the previous execution.  If an execution
   214      * is delayed for any reason (such as garbage collection or other
   215      * background activity), subsequent executions will be delayed as well.
   216      * In the long run, the frequency of execution will generally be slightly
   217      * lower than the reciprocal of the specified period (assuming the system
   218      * clock underlying <tt>Object.wait(long)</tt> is accurate).
   219      *
   220      * <p>Fixed-delay execution is appropriate for recurring activities
   221      * that require "smoothness."  In other words, it is appropriate for
   222      * activities where it is more important to keep the frequency accurate
   223      * in the short run than in the long run.  This includes most animation
   224      * tasks, such as blinking a cursor at regular intervals.  It also includes
   225      * tasks wherein regular activity is performed in response to human
   226      * input, such as automatically repeating a character as long as a key
   227      * is held down.
   228      *
   229      * @param task   task to be scheduled.
   230      * @param delay  delay in milliseconds before task is to be executed.
   231      * @param period time in milliseconds between successive task executions.
   232      * @throws IllegalArgumentException if {@code delay < 0}, or
   233      *         {@code delay + System.currentTimeMillis() < 0}, or
   234      *         {@code period <= 0}
   235      * @throws IllegalStateException if task was already scheduled or
   236      *         cancelled, timer was cancelled, or timer thread terminated.
   237      * @throws NullPointerException if {@code task} is null
   238      */
   239     public void schedule(TimerTask task, long delay, long period) {
   240         if (delay < 0)
   241             throw new IllegalArgumentException("Negative delay.");
   242         if (period <= 0)
   243             throw new IllegalArgumentException("Non-positive period.");
   244         sched(task, System.currentTimeMillis()+delay, -period);
   245     }
   246 
   247     /**
   248      * Schedules the specified task for repeated <i>fixed-delay execution</i>,
   249      * beginning at the specified time. Subsequent executions take place at
   250      * approximately regular intervals, separated by the specified period.
   251      *
   252      * <p>In fixed-delay execution, each execution is scheduled relative to
   253      * the actual execution time of the previous execution.  If an execution
   254      * is delayed for any reason (such as garbage collection or other
   255      * background activity), subsequent executions will be delayed as well.
   256      * In the long run, the frequency of execution will generally be slightly
   257      * lower than the reciprocal of the specified period (assuming the system
   258      * clock underlying <tt>Object.wait(long)</tt> is accurate).  As a
   259      * consequence of the above, if the scheduled first time is in the past,
   260      * it is scheduled for immediate execution.
   261      *
   262      * <p>Fixed-delay execution is appropriate for recurring activities
   263      * that require "smoothness."  In other words, it is appropriate for
   264      * activities where it is more important to keep the frequency accurate
   265      * in the short run than in the long run.  This includes most animation
   266      * tasks, such as blinking a cursor at regular intervals.  It also includes
   267      * tasks wherein regular activity is performed in response to human
   268      * input, such as automatically repeating a character as long as a key
   269      * is held down.
   270      *
   271      * @param task   task to be scheduled.
   272      * @param firstTime First time at which task is to be executed.
   273      * @param period time in milliseconds between successive task executions.
   274      * @throws IllegalArgumentException if {@code firstTime.getTime() < 0}, or
   275      *         {@code period <= 0}
   276      * @throws IllegalStateException if task was already scheduled or
   277      *         cancelled, timer was cancelled, or timer thread terminated.
   278      * @throws NullPointerException if {@code task} or {@code firstTime} is null
   279      */
   280     public void schedule(TimerTask task, Date firstTime, long period) {
   281         if (period <= 0)
   282             throw new IllegalArgumentException("Non-positive period.");
   283         sched(task, firstTime.getTime(), -period);
   284     }
   285 
   286     /**
   287      * Schedules the specified task for repeated <i>fixed-rate execution</i>,
   288      * beginning after the specified delay.  Subsequent executions take place
   289      * at approximately regular intervals, separated by the specified period.
   290      *
   291      * <p>In fixed-rate execution, each execution is scheduled relative to the
   292      * scheduled execution time of the initial execution.  If an execution is
   293      * delayed for any reason (such as garbage collection or other background
   294      * activity), two or more executions will occur in rapid succession to
   295      * "catch up."  In the long run, the frequency of execution will be
   296      * exactly the reciprocal of the specified period (assuming the system
   297      * clock underlying <tt>Object.wait(long)</tt> is accurate).
   298      *
   299      * <p>Fixed-rate execution is appropriate for recurring activities that
   300      * are sensitive to <i>absolute</i> time, such as ringing a chime every
   301      * hour on the hour, or running scheduled maintenance every day at a
   302      * particular time.  It is also appropriate for recurring activities
   303      * where the total time to perform a fixed number of executions is
   304      * important, such as a countdown timer that ticks once every second for
   305      * ten seconds.  Finally, fixed-rate execution is appropriate for
   306      * scheduling multiple repeating timer tasks that must remain synchronized
   307      * with respect to one another.
   308      *
   309      * @param task   task to be scheduled.
   310      * @param delay  delay in milliseconds before task is to be executed.
   311      * @param period time in milliseconds between successive task executions.
   312      * @throws IllegalArgumentException if {@code delay < 0}, or
   313      *         {@code delay + System.currentTimeMillis() < 0}, or
   314      *         {@code period <= 0}
   315      * @throws IllegalStateException if task was already scheduled or
   316      *         cancelled, timer was cancelled, or timer thread terminated.
   317      * @throws NullPointerException if {@code task} is null
   318      */
   319     public void scheduleAtFixedRate(TimerTask task, long delay, long period) {
   320         if (delay < 0)
   321             throw new IllegalArgumentException("Negative delay.");
   322         if (period <= 0)
   323             throw new IllegalArgumentException("Non-positive period.");
   324         sched(task, System.currentTimeMillis()+delay, period);
   325     }
   326 
   327     /**
   328      * Schedules the specified task for repeated <i>fixed-rate execution</i>,
   329      * beginning at the specified time. Subsequent executions take place at
   330      * approximately regular intervals, separated by the specified period.
   331      *
   332      * <p>In fixed-rate execution, each execution is scheduled relative to the
   333      * scheduled execution time of the initial execution.  If an execution is
   334      * delayed for any reason (such as garbage collection or other background
   335      * activity), two or more executions will occur in rapid succession to
   336      * "catch up."  In the long run, the frequency of execution will be
   337      * exactly the reciprocal of the specified period (assuming the system
   338      * clock underlying <tt>Object.wait(long)</tt> is accurate).  As a
   339      * consequence of the above, if the scheduled first time is in the past,
   340      * then any "missed" executions will be scheduled for immediate "catch up"
   341      * execution.
   342      *
   343      * <p>Fixed-rate execution is appropriate for recurring activities that
   344      * are sensitive to <i>absolute</i> time, such as ringing a chime every
   345      * hour on the hour, or running scheduled maintenance every day at a
   346      * particular time.  It is also appropriate for recurring activities
   347      * where the total time to perform a fixed number of executions is
   348      * important, such as a countdown timer that ticks once every second for
   349      * ten seconds.  Finally, fixed-rate execution is appropriate for
   350      * scheduling multiple repeating timer tasks that must remain synchronized
   351      * with respect to one another.
   352      *
   353      * @param task   task to be scheduled.
   354      * @param firstTime First time at which task is to be executed.
   355      * @param period time in milliseconds between successive task executions.
   356      * @throws IllegalArgumentException if {@code firstTime.getTime() < 0} or
   357      *         {@code period <= 0}
   358      * @throws IllegalStateException if task was already scheduled or
   359      *         cancelled, timer was cancelled, or timer thread terminated.
   360      * @throws NullPointerException if {@code task} or {@code firstTime} is null
   361      */
   362     public void scheduleAtFixedRate(TimerTask task, Date firstTime,
   363                                     long period) {
   364         if (period <= 0)
   365             throw new IllegalArgumentException("Non-positive period.");
   366         sched(task, firstTime.getTime(), period);
   367     }
   368 
   369     /**
   370      * Schedule the specified timer task for execution at the specified
   371      * time with the specified period, in milliseconds.  If period is
   372      * positive, the task is scheduled for repeated execution; if period is
   373      * zero, the task is scheduled for one-time execution. Time is specified
   374      * in Date.getTime() format.  This method checks timer state, task state,
   375      * and initial execution time, but not period.
   376      *
   377      * @throws IllegalArgumentException if <tt>time</tt> is negative.
   378      * @throws IllegalStateException if task was already scheduled or
   379      *         cancelled, timer was cancelled, or timer thread terminated.
   380      * @throws NullPointerException if {@code task} is null
   381      */
   382     private void sched(TimerTask task, long time, long period) {
   383         if (time < 0)
   384             throw new IllegalArgumentException("Illegal execution time.");
   385 
   386         // Constrain value of period sufficiently to prevent numeric
   387         // overflow while still being effectively infinitely large.
   388         if (Math.abs(period) > (Long.MAX_VALUE >> 1))
   389             period >>= 1;
   390 
   391         synchronized(queue) {
   392             if (!thread.newTasksMayBeScheduled)
   393                 throw new IllegalStateException("Timer already cancelled.");
   394 
   395             synchronized(task.lock) {
   396                 if (task.state != TimerTask.VIRGIN)
   397                     throw new IllegalStateException(
   398                         "Task already scheduled or cancelled");
   399                 task.nextExecutionTime = time;
   400                 task.period = period;
   401                 task.state = TimerTask.SCHEDULED;
   402             }
   403 
   404             queue.add(task);
   405             if (queue.getMin() == task)
   406                 thread.notifyQueue(1);
   407         }
   408     }
   409 
   410     /**
   411      * Terminates this timer, discarding any currently scheduled tasks.
   412      * Does not interfere with a currently executing task (if it exists).
   413      * Once a timer has been terminated, its execution thread terminates
   414      * gracefully, and no more tasks may be scheduled on it.
   415      *
   416      * <p>Note that calling this method from within the run method of a
   417      * timer task that was invoked by this timer absolutely guarantees that
   418      * the ongoing task execution is the last task execution that will ever
   419      * be performed by this timer.
   420      *
   421      * <p>This method may be called repeatedly; the second and subsequent
   422      * calls have no effect.
   423      */
   424     public void cancel() {
   425         synchronized(queue) {
   426             thread.newTasksMayBeScheduled = false;
   427             queue.clear();
   428             thread.notifyQueue(1);  // In case queue was already empty.
   429         }
   430     }
   431     
   432     /**
   433      * Removes all cancelled tasks from this timer's task queue.  <i>Calling
   434      * this method has no effect on the behavior of the timer</i>, but
   435      * eliminates the references to the cancelled tasks from the queue.
   436      * If there are no external references to these tasks, they become
   437      * eligible for garbage collection.
   438      *
   439      * <p>Most programs will have no need to call this method.
   440      * It is designed for use by the rare application that cancels a large
   441      * number of tasks.  Calling this method trades time for space: the
   442      * runtime of the method may be proportional to n + c log n, where n
   443      * is the number of tasks in the queue and c is the number of cancelled
   444      * tasks.
   445      *
   446      * <p>Note that it is permissible to call this method from within a
   447      * a task scheduled on this timer.
   448      *
   449      * @return the number of tasks removed from the queue.
   450      * @since 1.5
   451      */
   452      public int purge() {
   453          int result = 0;
   454 
   455          synchronized(queue) {
   456              for (int i = queue.size(); i > 0; i--) {
   457                  if (queue.get(i).state == TimerTask.CANCELLED) {
   458                      queue.quickRemove(i);
   459                      result++;
   460                  }
   461              }
   462 
   463              if (result != 0)
   464                  queue.heapify();
   465          }
   466 
   467          return result;
   468      }
   469 }
   470 
   471 /**
   472  * This "helper class" implements the timer's task execution thread, which
   473  * waits for tasks on the timer queue, executions them when they fire,
   474  * reschedules repeating tasks, and removes cancelled tasks and spent
   475  * non-repeating tasks from the queue.
   476  */
   477 class TimerThread implements Runnable {
   478     /**
   479      * This flag is set to false by the reaper to inform us that there
   480      * are no more live references to our Timer object.  Once this flag
   481      * is true and there are no more tasks in our queue, there is no
   482      * work left for us to do, so we terminate gracefully.  Note that
   483      * this field is protected by queue's monitor!
   484      */
   485     boolean newTasksMayBeScheduled = true;
   486 
   487     /**
   488      * Our Timer's queue.  We store this reference in preference to
   489      * a reference to the Timer so the reference graph remains acyclic.
   490      * Otherwise, the Timer would never be garbage-collected and this
   491      * thread would never go away.
   492      */
   493     private final TaskQueue queue;
   494     private Object prevTimeout;
   495 
   496     TimerThread(TaskQueue queue) {
   497         this.queue = queue;
   498     }
   499 
   500     void notifyQueue(int delay) {
   501         if (delay < 1) {
   502             delay = 1;
   503         }
   504         prevTimeout = setTimeout(delay, this, prevTimeout);
   505     }
   506     
   507     @JavaScriptBody(args = { "delay", "r", "prev" }, body = ""
   508 //        + "console.log('clear prev ' + prev);\n"
   509         + "if (prev) {\n"
   510         + "  window.clearTimeout(prev);\n"
   511         + "}\n"
   512 //        + "console.log('schedule in ' + delay);\n"
   513         + "return window.setTimeout(function() {\n"
   514 //        + "  console.log('running time');\n"
   515         + "  r.run__V();\n"
   516 //        + "  console.log('done running time');\n"
   517         + "}, delay);\n"
   518     )
   519     private static native Object setTimeout(int delay, Runnable r, Object prev);
   520 
   521 //    @JavaScriptBody(args = { "msg" }, body = "console.log(msg);")
   522     private static void log(String msg) {
   523     }
   524     
   525     @Override
   526     public void run() {
   527         try {
   528             mainLoop(1);
   529         } finally {
   530             synchronized (queue) {
   531                 if (!queue.isEmpty()) {
   532                     long next = queue.getMin().nextExecutionTime;
   533                     long now = System.currentTimeMillis();
   534                     int delta = (int) (next - now);
   535                     notifyQueue(delta);
   536                 }
   537             }
   538         }
   539 //        try {
   540 //            mainLoop(0);
   541 //        } finally {
   542 //            // Someone killed this Thread, behave as if Timer cancelled
   543 //            synchronized(queue) {
   544 //                newTasksMayBeScheduled = false;
   545 //                queue.clear();  // Eliminate obsolete references
   546 //            }
   547 //        }
   548     }
   549 
   550     /**
   551      * The main timer loop.  (See class comment.)
   552      */
   553     private void mainLoop(int inc) {
   554         for (int i = 0; i < 1; i += inc) {
   555             try {
   556                 TimerTask task;
   557                 boolean taskFired;
   558                 synchronized(queue) {
   559                     // Wait for queue to become non-empty
   560                     while (queue.isEmpty() && newTasksMayBeScheduled)
   561                         break;
   562                     if (queue.isEmpty())
   563                         break; // Queue is empty and will forever remain; die
   564 
   565                     // Queue nonempty; look at first evt and do the right thing
   566                     long currentTime, executionTime;
   567                     task = queue.getMin();
   568                     synchronized(task.lock) {
   569                         if (task.state == TimerTask.CANCELLED) {
   570                             queue.removeMin();
   571                             continue;  // No action required, poll queue again
   572                         }
   573                         currentTime = System.currentTimeMillis();
   574                         executionTime = task.nextExecutionTime;
   575                         if (taskFired = (executionTime<=currentTime)) {
   576                             if (task.period == 0) { // Non-repeating, remove
   577                                 queue.removeMin();
   578                                 task.state = TimerTask.EXECUTED;
   579                             } else { // Repeating task, reschedule
   580                                 queue.rescheduleMin(
   581                                   task.period<0 ? currentTime   - task.period
   582                                                 : executionTime + task.period);
   583                             }
   584                         }
   585                     }
   586                     if (!taskFired) {
   587                         // Task hasn't yet fired; wait
   588                         notifyQueue((int)(executionTime - currentTime));
   589                         return;
   590                     }
   591                 }
   592                 if (taskFired)  {
   593                     // Task fired; run it, holding no locks
   594                     log("Running " + task);
   595                     task.run();
   596                     log("Done running " + task);
   597                 }
   598             } catch(Exception e) {
   599                 e.printStackTrace();
   600             }
   601         }
   602     }
   603 }
   604 
   605 /**
   606  * This class represents a timer task queue: a priority queue of TimerTasks,
   607  * ordered on nextExecutionTime.  Each Timer object has one of these, which it
   608  * shares with its TimerThread.  Internally this class uses a heap, which
   609  * offers log(n) performance for the add, removeMin and rescheduleMin
   610  * operations, and constant time performance for the getMin operation.
   611  */
   612 class TaskQueue {
   613     /**
   614      * Priority queue represented as a balanced binary heap: the two children
   615      * of queue[n] are queue[2*n] and queue[2*n+1].  The priority queue is
   616      * ordered on the nextExecutionTime field: The TimerTask with the lowest
   617      * nextExecutionTime is in queue[1] (assuming the queue is nonempty).  For
   618      * each node n in the heap, and each descendant of n, d,
   619      * n.nextExecutionTime <= d.nextExecutionTime.
   620      */
   621     private TimerTask[] queue = new TimerTask[128];
   622 
   623     /**
   624      * The number of tasks in the priority queue.  (The tasks are stored in
   625      * queue[1] up to queue[size]).
   626      */
   627     private int size = 0;
   628 
   629     /**
   630      * Returns the number of tasks currently on the queue.
   631      */
   632     int size() {
   633         return size;
   634     }
   635 
   636     /**
   637      * Adds a new task to the priority queue.
   638      */
   639     void add(TimerTask task) {
   640         // Grow backing store if necessary
   641         if (size + 1 == queue.length)
   642             queue = Arrays.copyOf(queue, 2*queue.length);
   643 
   644         queue[++size] = task;
   645         fixUp(size);
   646     }
   647 
   648     /**
   649      * Return the "head task" of the priority queue.  (The head task is an
   650      * task with the lowest nextExecutionTime.)
   651      */
   652     TimerTask getMin() {
   653         return queue[1];
   654     }
   655 
   656     /**
   657      * Return the ith task in the priority queue, where i ranges from 1 (the
   658      * head task, which is returned by getMin) to the number of tasks on the
   659      * queue, inclusive.
   660      */
   661     TimerTask get(int i) {
   662         return queue[i];
   663     }
   664 
   665     /**
   666      * Remove the head task from the priority queue.
   667      */
   668     void removeMin() {
   669         queue[1] = queue[size];
   670         queue[size--] = null;  // Drop extra reference to prevent memory leak
   671         fixDown(1);
   672     }
   673 
   674     /**
   675      * Removes the ith element from queue without regard for maintaining
   676      * the heap invariant.  Recall that queue is one-based, so
   677      * 1 <= i <= size.
   678      */
   679     void quickRemove(int i) {
   680         assert i <= size;
   681 
   682         queue[i] = queue[size];
   683         queue[size--] = null;  // Drop extra ref to prevent memory leak
   684     }
   685 
   686     /**
   687      * Sets the nextExecutionTime associated with the head task to the
   688      * specified value, and adjusts priority queue accordingly.
   689      */
   690     void rescheduleMin(long newTime) {
   691         queue[1].nextExecutionTime = newTime;
   692         fixDown(1);
   693     }
   694 
   695     /**
   696      * Returns true if the priority queue contains no elements.
   697      */
   698     boolean isEmpty() {
   699         return size==0;
   700     }
   701 
   702     /**
   703      * Removes all elements from the priority queue.
   704      */
   705     void clear() {
   706         // Null out task references to prevent memory leak
   707         for (int i=1; i<=size; i++)
   708             queue[i] = null;
   709 
   710         size = 0;
   711     }
   712 
   713     /**
   714      * Establishes the heap invariant (described above) assuming the heap
   715      * satisfies the invariant except possibly for the leaf-node indexed by k
   716      * (which may have a nextExecutionTime less than its parent's).
   717      *
   718      * This method functions by "promoting" queue[k] up the hierarchy
   719      * (by swapping it with its parent) repeatedly until queue[k]'s
   720      * nextExecutionTime is greater than or equal to that of its parent.
   721      */
   722     private void fixUp(int k) {
   723         while (k > 1) {
   724             int j = k >> 1;
   725             if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
   726                 break;
   727             TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
   728             k = j;
   729         }
   730     }
   731 
   732     /**
   733      * Establishes the heap invariant (described above) in the subtree
   734      * rooted at k, which is assumed to satisfy the heap invariant except
   735      * possibly for node k itself (which may have a nextExecutionTime greater
   736      * than its children's).
   737      *
   738      * This method functions by "demoting" queue[k] down the hierarchy
   739      * (by swapping it with its smaller child) repeatedly until queue[k]'s
   740      * nextExecutionTime is less than or equal to those of its children.
   741      */
   742     private void fixDown(int k) {
   743         int j;
   744         while ((j = k << 1) <= size && j > 0) {
   745             if (j < size &&
   746                 queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
   747                 j++; // j indexes smallest kid
   748             if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
   749                 break;
   750             TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
   751             k = j;
   752         }
   753     }
   754 
   755     /**
   756      * Establishes the heap invariant (described above) in the entire tree,
   757      * assuming nothing about the order of the elements prior to the call.
   758      */
   759     void heapify() {
   760         for (int i = size/2; i >= 1; i--)
   761             fixDown(i);
   762     }
   763 }