| /* |
| * Copyright (c) 1999, 2021, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package java.util; |
| import dalvik.annotation.optimization.ReachabilitySensitive; |
| import java.util.Date; |
| import java.util.concurrent.atomic.AtomicInteger; |
| import java.lang.ref.Cleaner.Cleanable; |
| import jdk.internal.ref.CleanerFactory; |
| |
| /** |
| * A facility for threads to schedule tasks for future execution in a |
| * background thread. Tasks may be scheduled for one-time execution, or for |
| * repeated execution at regular intervals. |
| * |
| * <p>Corresponding to each {@code Timer} object is a single background |
| * thread that is used to execute all of the timer's tasks, sequentially. |
| * Timer tasks should complete quickly. If a timer task takes excessive time |
| * to complete, it "hogs" the timer's task execution thread. This can, in |
| * turn, delay the execution of subsequent tasks, which may "bunch up" and |
| * execute in rapid succession when (and if) the offending task finally |
| * completes. |
| * |
| * <p>After the last live reference to a {@code Timer} object goes away |
| * <i>and</i> all outstanding tasks have completed execution, the timer's task |
| * execution thread terminates gracefully (and becomes subject to garbage |
| * collection). However, this can take arbitrarily long to occur. By |
| * default, the task execution thread does not run as a <i>daemon thread</i>, |
| * so it is capable of keeping an application from terminating. If a caller |
| * wants to terminate a timer's task execution thread rapidly, the caller |
| * should invoke the timer's {@code cancel} method. |
| * |
| * <p>If the timer's task execution thread terminates unexpectedly, for |
| * example, because its {@code stop} method is invoked, any further |
| * attempt to schedule a task on the timer will result in an |
| * {@code IllegalStateException}, as if the timer's {@code cancel} |
| * method had been invoked. |
| * |
| * <p>This class is thread-safe: multiple threads can share a single |
| * {@code Timer} object without the need for external synchronization. |
| * |
| * <p>This class does <i>not</i> offer real-time guarantees: it schedules |
| * tasks using the {@code Object.wait(long)} method. |
| * |
| * <p>Java 5.0 introduced the {@code java.util.concurrent} package and |
| * one of the concurrency utilities therein is the {@link |
| * java.util.concurrent.ScheduledThreadPoolExecutor |
| * ScheduledThreadPoolExecutor} which is a thread pool for repeatedly |
| * executing tasks at a given rate or delay. It is effectively a more |
| * versatile replacement for the {@code Timer}/{@code TimerTask} |
| * combination, as it allows multiple service threads, accepts various |
| * time units, and doesn't require subclassing {@code TimerTask} (just |
| * implement {@code Runnable}). Configuring {@code |
| * ScheduledThreadPoolExecutor} with one thread makes it equivalent to |
| * {@code Timer}. |
| * |
| * <p>Implementation note: This class scales to large numbers of concurrently |
| * scheduled tasks (thousands should present no problem). Internally, |
| * it uses a binary heap to represent its task queue, so the cost to schedule |
| * a task is O(log n), where n is the number of concurrently scheduled tasks. |
| * |
| * <p>Implementation note: All constructors start a timer thread. |
| * |
| * @author Josh Bloch |
| * @see TimerTask |
| * @see Object#wait(long) |
| * @since 1.3 |
| */ |
| |
| public class Timer { |
| /** |
| * The timer task queue. This data structure is shared with the timer |
| * thread. The timer produces tasks, via its various schedule calls, |
| * and the timer thread consumes, executing timer tasks as appropriate, |
| * and removing them from the queue when they're obsolete. |
| */ |
| // Android-added: @ReachabilitySensitive |
| // Otherwise the finalizer may cancel the Timer in the middle of a |
| // sched() call. |
| @ReachabilitySensitive |
| private final TaskQueue queue = new TaskQueue(); |
| |
| /** |
| * The timer thread. |
| */ |
| // Android-added: @ReachabilitySensitive |
| @ReachabilitySensitive |
| private final TimerThread thread = new TimerThread(queue); |
| |
| /** |
| * An object of this class is registered with a Cleaner as the cleanup |
| * handler for this Timer object. This causes the execution thread to |
| * exit gracefully when there are no live references to the Timer object |
| * and no tasks in the timer queue. |
| */ |
| private static class ThreadReaper implements Runnable { |
| private final TaskQueue queue; |
| private final TimerThread thread; |
| |
| ThreadReaper(TaskQueue queue, TimerThread thread) { |
| this.queue = queue; |
| this.thread = thread; |
| } |
| |
| public void run() { |
| synchronized(queue) { |
| thread.newTasksMayBeScheduled = false; |
| queue.notify(); // In case queue is empty. |
| } |
| } |
| } |
| |
| private final Cleanable cleanup; |
| |
| /** |
| * This ID is used to generate thread names. |
| */ |
| private static final AtomicInteger nextSerialNumber = new AtomicInteger(); |
| private static int serialNumber() { |
| return nextSerialNumber.getAndIncrement(); |
| } |
| |
| /** |
| * Creates a new timer. The associated thread does <i>not</i> |
| * {@linkplain Thread#setDaemon run as a daemon}. |
| */ |
| public Timer() { |
| this("Timer-" + serialNumber()); |
| } |
| |
| /** |
| * Creates a new timer whose associated thread may be specified to |
| * {@linkplain Thread#setDaemon run as a daemon}. |
| * A daemon thread is called for if the timer will be used to |
| * schedule repeating "maintenance activities", which must be |
| * performed as long as the application is running, but should not |
| * prolong the lifetime of the application. |
| * |
| * @param isDaemon true if the associated thread should run as a daemon. |
| */ |
| public Timer(boolean isDaemon) { |
| this("Timer-" + serialNumber(), isDaemon); |
| } |
| |
| /** |
| * Creates a new timer whose associated thread has the specified name. |
| * The associated thread does <i>not</i> |
| * {@linkplain Thread#setDaemon run as a daemon}. |
| * |
| * @param name the name of the associated thread |
| * @throws NullPointerException if {@code name} is null |
| * @since 1.5 |
| */ |
| public Timer(String name) { |
| this(name, false); |
| } |
| |
| /** |
| * Creates a new timer whose associated thread has the specified name, |
| * and may be specified to |
| * {@linkplain Thread#setDaemon run as a daemon}. |
| * |
| * @param name the name of the associated thread |
| * @param isDaemon true if the associated thread should run as a daemon |
| * @throws NullPointerException if {@code name} is null |
| * @since 1.5 |
| */ |
| public Timer(String name, boolean isDaemon) { |
| var threadReaper = new ThreadReaper(queue, thread); |
| this.cleanup = CleanerFactory.cleaner().register(this, threadReaper); |
| thread.setName(name); |
| thread.setDaemon(isDaemon); |
| thread.start(); |
| } |
| |
| /** |
| * Schedules the specified task for execution after the specified delay. |
| * |
| * @param task task to be scheduled. |
| * @param delay delay in milliseconds before task is to be executed. |
| * @throws IllegalArgumentException if {@code delay} is negative, or |
| * {@code delay + System.currentTimeMillis()} is negative. |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} is null |
| */ |
| public void schedule(TimerTask task, long delay) { |
| if (delay < 0) |
| throw new IllegalArgumentException("Negative delay."); |
| sched(task, System.currentTimeMillis()+delay, 0); |
| } |
| |
| /** |
| * Schedules the specified task for execution at the specified time. If |
| * the time is in the past, the task is scheduled for immediate execution. |
| * |
| * @param task task to be scheduled. |
| * @param time time at which task is to be executed. |
| * @throws IllegalArgumentException if {@code time.getTime()} is negative. |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} or {@code time} is null |
| */ |
| public void schedule(TimerTask task, Date time) { |
| sched(task, time.getTime(), 0); |
| } |
| |
| /** |
| * Schedules the specified task for repeated <i>fixed-delay execution</i>, |
| * beginning after the specified delay. Subsequent executions take place |
| * at approximately regular intervals separated by the specified period. |
| * |
| * <p>In fixed-delay execution, each execution is scheduled relative to |
| * the actual execution time of the previous execution. If an execution |
| * is delayed for any reason (such as garbage collection or other |
| * background activity), subsequent executions will be delayed as well. |
| * In the long run, the frequency of execution will generally be slightly |
| * lower than the reciprocal of the specified period (assuming the system |
| * clock underlying {@code Object.wait(long)} is accurate). |
| * |
| * <p>Fixed-delay execution is appropriate for recurring activities |
| * that require "smoothness." In other words, it is appropriate for |
| * activities where it is more important to keep the frequency accurate |
| * in the short run than in the long run. This includes most animation |
| * tasks, such as blinking a cursor at regular intervals. It also includes |
| * tasks wherein regular activity is performed in response to human |
| * input, such as automatically repeating a character as long as a key |
| * is held down. |
| * |
| * @param task task to be scheduled. |
| * @param delay delay in milliseconds before task is to be executed. |
| * @param period time in milliseconds between successive task executions. |
| * @throws IllegalArgumentException if {@code delay < 0}, or |
| * {@code delay + System.currentTimeMillis() < 0}, or |
| * {@code period <= 0} |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} is null |
| */ |
| public void schedule(TimerTask task, long delay, long period) { |
| if (delay < 0) |
| throw new IllegalArgumentException("Negative delay."); |
| if (period <= 0) |
| throw new IllegalArgumentException("Non-positive period."); |
| sched(task, System.currentTimeMillis()+delay, -period); |
| } |
| |
| /** |
| * Schedules the specified task for repeated <i>fixed-delay execution</i>, |
| * beginning at the specified time. Subsequent executions take place at |
| * approximately regular intervals, separated by the specified period. |
| * |
| * <p>In fixed-delay execution, each execution is scheduled relative to |
| * the actual execution time of the previous execution. If an execution |
| * is delayed for any reason (such as garbage collection or other |
| * background activity), subsequent executions will be delayed as well. |
| * In the long run, the frequency of execution will generally be slightly |
| * lower than the reciprocal of the specified period (assuming the system |
| * clock underlying {@code Object.wait(long)} is accurate). As a |
| * consequence of the above, if the scheduled first time is in the past, |
| * it is scheduled for immediate execution. |
| * |
| * <p>Fixed-delay execution is appropriate for recurring activities |
| * that require "smoothness." In other words, it is appropriate for |
| * activities where it is more important to keep the frequency accurate |
| * in the short run than in the long run. This includes most animation |
| * tasks, such as blinking a cursor at regular intervals. It also includes |
| * tasks wherein regular activity is performed in response to human |
| * input, such as automatically repeating a character as long as a key |
| * is held down. |
| * |
| * @param task task to be scheduled. |
| * @param firstTime First time at which task is to be executed. |
| * @param period time in milliseconds between successive task executions. |
| * @throws IllegalArgumentException if {@code firstTime.getTime() < 0}, or |
| * {@code period <= 0} |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} or {@code firstTime} is null |
| */ |
| public void schedule(TimerTask task, Date firstTime, long period) { |
| if (period <= 0) |
| throw new IllegalArgumentException("Non-positive period."); |
| sched(task, firstTime.getTime(), -period); |
| } |
| |
| /** |
| * Schedules the specified task for repeated <i>fixed-rate execution</i>, |
| * beginning after the specified delay. Subsequent executions take place |
| * at approximately regular intervals, separated by the specified period. |
| * |
| * <p>In fixed-rate execution, each execution is scheduled relative to the |
| * scheduled execution time of the initial execution. If an execution is |
| * delayed for any reason (such as garbage collection or other background |
| * activity), two or more executions will occur in rapid succession to |
| * "catch up." In the long run, the frequency of execution will be |
| * exactly the reciprocal of the specified period (assuming the system |
| * clock underlying {@code Object.wait(long)} is accurate). |
| * |
| * <p>Fixed-rate execution is appropriate for recurring activities that |
| * are sensitive to <i>absolute</i> time, such as ringing a chime every |
| * hour on the hour, or running scheduled maintenance every day at a |
| * particular time. It is also appropriate for recurring activities |
| * where the total time to perform a fixed number of executions is |
| * important, such as a countdown timer that ticks once every second for |
| * ten seconds. Finally, fixed-rate execution is appropriate for |
| * scheduling multiple repeating timer tasks that must remain synchronized |
| * with respect to one another. |
| * |
| * @param task task to be scheduled. |
| * @param delay delay in milliseconds before task is to be executed. |
| * @param period time in milliseconds between successive task executions. |
| * @throws IllegalArgumentException if {@code delay < 0}, or |
| * {@code delay + System.currentTimeMillis() < 0}, or |
| * {@code period <= 0} |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} is null |
| */ |
| public void scheduleAtFixedRate(TimerTask task, long delay, long period) { |
| if (delay < 0) |
| throw new IllegalArgumentException("Negative delay."); |
| if (period <= 0) |
| throw new IllegalArgumentException("Non-positive period."); |
| sched(task, System.currentTimeMillis()+delay, period); |
| } |
| |
| /** |
| * Schedules the specified task for repeated <i>fixed-rate execution</i>, |
| * beginning at the specified time. Subsequent executions take place at |
| * approximately regular intervals, separated by the specified period. |
| * |
| * <p>In fixed-rate execution, each execution is scheduled relative to the |
| * scheduled execution time of the initial execution. If an execution is |
| * delayed for any reason (such as garbage collection or other background |
| * activity), two or more executions will occur in rapid succession to |
| * "catch up." In the long run, the frequency of execution will be |
| * exactly the reciprocal of the specified period (assuming the system |
| * clock underlying {@code Object.wait(long)} is accurate). As a |
| * consequence of the above, if the scheduled first time is in the past, |
| * then any "missed" executions will be scheduled for immediate "catch up" |
| * execution. |
| * |
| * <p>Fixed-rate execution is appropriate for recurring activities that |
| * are sensitive to <i>absolute</i> time, such as ringing a chime every |
| * hour on the hour, or running scheduled maintenance every day at a |
| * particular time. It is also appropriate for recurring activities |
| * where the total time to perform a fixed number of executions is |
| * important, such as a countdown timer that ticks once every second for |
| * ten seconds. Finally, fixed-rate execution is appropriate for |
| * scheduling multiple repeating timer tasks that must remain synchronized |
| * with respect to one another. |
| * |
| * @param task task to be scheduled. |
| * @param firstTime First time at which task is to be executed. |
| * @param period time in milliseconds between successive task executions. |
| * @throws IllegalArgumentException if {@code firstTime.getTime() < 0} or |
| * {@code period <= 0} |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} or {@code firstTime} is null |
| */ |
| public void scheduleAtFixedRate(TimerTask task, Date firstTime, |
| long period) { |
| if (period <= 0) |
| throw new IllegalArgumentException("Non-positive period."); |
| sched(task, firstTime.getTime(), period); |
| } |
| |
| /** |
| * Schedule the specified timer task for execution at the specified |
| * time with the specified period, in milliseconds. If period is |
| * positive, the task is scheduled for repeated execution; if period is |
| * zero, the task is scheduled for one-time execution. Time is specified |
| * in Date.getTime() format. This method checks timer state, task state, |
| * and initial execution time, but not period. |
| * |
| * @throws IllegalArgumentException if {@code time} is negative. |
| * @throws IllegalStateException if task was already scheduled or |
| * cancelled, timer was cancelled, or timer thread terminated. |
| * @throws NullPointerException if {@code task} is null |
| */ |
| private void sched(TimerTask task, long time, long period) { |
| if (time < 0) |
| throw new IllegalArgumentException("Illegal execution time."); |
| |
| // Constrain value of period sufficiently to prevent numeric |
| // overflow while still being effectively infinitely large. |
| if (Math.abs(period) > (Long.MAX_VALUE >> 1)) |
| period >>= 1; |
| |
| synchronized(queue) { |
| if (!thread.newTasksMayBeScheduled) |
| throw new IllegalStateException("Timer already cancelled."); |
| |
| synchronized(task.lock) { |
| if (task.state != TimerTask.VIRGIN) |
| throw new IllegalStateException( |
| "Task already scheduled or cancelled"); |
| task.nextExecutionTime = time; |
| task.period = period; |
| task.state = TimerTask.SCHEDULED; |
| } |
| |
| queue.add(task); |
| if (queue.getMin() == task) |
| queue.notify(); |
| } |
| } |
| |
| /** |
| * Terminates this timer, discarding any currently scheduled tasks. |
| * Does not interfere with a currently executing task (if it exists). |
| * Once a timer has been terminated, its execution thread terminates |
| * gracefully, and no more tasks may be scheduled on it. |
| * |
| * <p>Note that calling this method from within the run method of a |
| * timer task that was invoked by this timer absolutely guarantees that |
| * the ongoing task execution is the last task execution that will ever |
| * be performed by this timer. |
| * |
| * <p>This method may be called repeatedly; the second and subsequent |
| * calls have no effect. |
| */ |
| public void cancel() { |
| synchronized(queue) { |
| queue.clear(); |
| cleanup.clean(); |
| } |
| } |
| |
| /** |
| * Removes all cancelled tasks from this timer's task queue. <i>Calling |
| * this method has no effect on the behavior of the timer</i>, but |
| * eliminates the references to the cancelled tasks from the queue. |
| * If there are no external references to these tasks, they become |
| * eligible for garbage collection. |
| * |
| * <p>Most programs will have no need to call this method. |
| * It is designed for use by the rare application that cancels a large |
| * number of tasks. Calling this method trades time for space: the |
| * runtime of the method may be proportional to n + c log n, where n |
| * is the number of tasks in the queue and c is the number of cancelled |
| * tasks. |
| * |
| * <p>Note that it is permissible to call this method from within |
| * a task scheduled on this timer. |
| * |
| * @return the number of tasks removed from the queue. |
| * @since 1.5 |
| */ |
| public int purge() { |
| int result = 0; |
| |
| synchronized(queue) { |
| for (int i = queue.size(); i > 0; i--) { |
| if (queue.get(i).state == TimerTask.CANCELLED) { |
| queue.quickRemove(i); |
| result++; |
| } |
| } |
| |
| if (result != 0) |
| queue.heapify(); |
| } |
| |
| return result; |
| } |
| } |
| |
| /** |
| * This "helper class" implements the timer's task execution thread, which |
| * waits for tasks on the timer queue, executions them when they fire, |
| * reschedules repeating tasks, and removes cancelled tasks and spent |
| * non-repeating tasks from the queue. |
| */ |
| class TimerThread extends Thread { |
| /** |
| * This flag is set to false by the reaper to inform us that there |
| * are no more live references to our Timer object. Once this flag |
| * is true and there are no more tasks in our queue, there is no |
| * work left for us to do, so we terminate gracefully. Note that |
| * this field is protected by queue's monitor! |
| */ |
| boolean newTasksMayBeScheduled = true; |
| |
| /** |
| * Our Timer's queue. We store this reference in preference to |
| * a reference to the Timer so the reference graph remains acyclic. |
| * Otherwise, the Timer would never be garbage-collected and this |
| * thread would never go away. |
| */ |
| private TaskQueue queue; |
| |
| TimerThread(TaskQueue queue) { |
| this.queue = queue; |
| } |
| |
| public void run() { |
| try { |
| mainLoop(); |
| } finally { |
| // Someone killed this Thread, behave as if Timer cancelled |
| synchronized(queue) { |
| newTasksMayBeScheduled = false; |
| queue.clear(); // Eliminate obsolete references |
| } |
| } |
| } |
| |
| /** |
| * The main timer loop. (See class comment.) |
| */ |
| private void mainLoop() { |
| while (true) { |
| try { |
| TimerTask task; |
| boolean taskFired; |
| synchronized(queue) { |
| // Wait for queue to become non-empty |
| while (queue.isEmpty() && newTasksMayBeScheduled) |
| queue.wait(); |
| if (queue.isEmpty()) |
| break; // Queue is empty and will forever remain; die |
| |
| // Queue nonempty; look at first evt and do the right thing |
| long currentTime, executionTime; |
| task = queue.getMin(); |
| synchronized(task.lock) { |
| if (task.state == TimerTask.CANCELLED) { |
| queue.removeMin(); |
| continue; // No action required, poll queue again |
| } |
| currentTime = System.currentTimeMillis(); |
| executionTime = task.nextExecutionTime; |
| if (taskFired = (executionTime<=currentTime)) { |
| if (task.period == 0) { // Non-repeating, remove |
| queue.removeMin(); |
| task.state = TimerTask.EXECUTED; |
| } else { // Repeating task, reschedule |
| queue.rescheduleMin( |
| task.period<0 ? currentTime - task.period |
| : executionTime + task.period); |
| } |
| } |
| } |
| if (!taskFired) // Task hasn't yet fired; wait |
| queue.wait(executionTime - currentTime); |
| } |
| if (taskFired) // Task fired; run it, holding no locks |
| task.run(); |
| } catch(InterruptedException e) { |
| } |
| } |
| } |
| } |
| |
| /** |
| * This class represents a timer task queue: a priority queue of TimerTasks, |
| * ordered on nextExecutionTime. Each Timer object has one of these, which it |
| * shares with its TimerThread. Internally this class uses a heap, which |
| * offers log(n) performance for the add, removeMin and rescheduleMin |
| * operations, and constant time performance for the getMin operation. |
| */ |
| class TaskQueue { |
| /** |
| * Priority queue represented as a balanced binary heap: the two children |
| * of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is |
| * ordered on the nextExecutionTime field: The TimerTask with the lowest |
| * nextExecutionTime is in queue[1] (assuming the queue is nonempty). For |
| * each node n in the heap, and each descendant of n, d, |
| * n.nextExecutionTime <= d.nextExecutionTime. |
| */ |
| private TimerTask[] queue = new TimerTask[128]; |
| |
| /** |
| * The number of tasks in the priority queue. (The tasks are stored in |
| * queue[1] up to queue[size]). |
| */ |
| private int size = 0; |
| |
| /** |
| * Returns the number of tasks currently on the queue. |
| */ |
| int size() { |
| return size; |
| } |
| |
| /** |
| * Adds a new task to the priority queue. |
| */ |
| void add(TimerTask task) { |
| // Grow backing store if necessary |
| if (size + 1 == queue.length) |
| queue = Arrays.copyOf(queue, 2*queue.length); |
| |
| queue[++size] = task; |
| fixUp(size); |
| } |
| |
| /** |
| * Return the "head task" of the priority queue. (The head task is an |
| * task with the lowest nextExecutionTime.) |
| */ |
| TimerTask getMin() { |
| return queue[1]; |
| } |
| |
| /** |
| * Return the ith task in the priority queue, where i ranges from 1 (the |
| * head task, which is returned by getMin) to the number of tasks on the |
| * queue, inclusive. |
| */ |
| TimerTask get(int i) { |
| return queue[i]; |
| } |
| |
| /** |
| * Remove the head task from the priority queue. |
| */ |
| void removeMin() { |
| queue[1] = queue[size]; |
| queue[size--] = null; // Drop extra reference to prevent memory leak |
| fixDown(1); |
| } |
| |
| /** |
| * Removes the ith element from queue without regard for maintaining |
| * the heap invariant. Recall that queue is one-based, so |
| * 1 <= i <= size. |
| */ |
| void quickRemove(int i) { |
| assert i <= size; |
| |
| queue[i] = queue[size]; |
| queue[size--] = null; // Drop extra ref to prevent memory leak |
| } |
| |
| /** |
| * Sets the nextExecutionTime associated with the head task to the |
| * specified value, and adjusts priority queue accordingly. |
| */ |
| void rescheduleMin(long newTime) { |
| queue[1].nextExecutionTime = newTime; |
| fixDown(1); |
| } |
| |
| /** |
| * Returns true if the priority queue contains no elements. |
| */ |
| boolean isEmpty() { |
| return size==0; |
| } |
| |
| /** |
| * Removes all elements from the priority queue. |
| */ |
| void clear() { |
| // Null out task references to prevent memory leak |
| for (int i=1; i<=size; i++) |
| queue[i] = null; |
| |
| size = 0; |
| } |
| |
| /** |
| * Establishes the heap invariant (described above) assuming the heap |
| * satisfies the invariant except possibly for the leaf-node indexed by k |
| * (which may have a nextExecutionTime less than its parent's). |
| * |
| * This method functions by "promoting" queue[k] up the hierarchy |
| * (by swapping it with its parent) repeatedly until queue[k]'s |
| * nextExecutionTime is greater than or equal to that of its parent. |
| */ |
| private void fixUp(int k) { |
| while (k > 1) { |
| int j = k >> 1; |
| if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime) |
| break; |
| TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |
| k = j; |
| } |
| } |
| |
| /** |
| * Establishes the heap invariant (described above) in the subtree |
| * rooted at k, which is assumed to satisfy the heap invariant except |
| * possibly for node k itself (which may have a nextExecutionTime greater |
| * than its children's). |
| * |
| * This method functions by "demoting" queue[k] down the hierarchy |
| * (by swapping it with its smaller child) repeatedly until queue[k]'s |
| * nextExecutionTime is less than or equal to those of its children. |
| */ |
| private void fixDown(int k) { |
| int j; |
| while ((j = k << 1) <= size && j > 0) { |
| if (j < size && |
| queue[j].nextExecutionTime > queue[j+1].nextExecutionTime) |
| j++; // j indexes smallest kid |
| if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime) |
| break; |
| TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp; |
| k = j; |
| } |
| } |
| |
| /** |
| * Establishes the heap invariant (described above) in the entire tree, |
| * assuming nothing about the order of the elements prior to the call. |
| */ |
| void heapify() { |
| for (int i = size/2; i >= 1; i--) |
| fixDown(i); |
| } |
| } |
