TimerThread

//******************************************************************************
//
// File:    TimerThread.java
// Package: edu.rit.util
// Unit:    Class edu.rit.util.TimerThread
//
// This Java source file is copyright (C) 2002-2004 by Alan Kaminsky. All rights
// reserved. For further information, contact the author, Alan Kaminsky, at
// ark@cs.rit.edu.
//
// This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
// software; you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// PJ 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 for more details.
//
// Linking this library statically or dynamically with other modules is making a
// combined work based on this library. Thus, the terms and conditions of the GNU
// General Public License cover the whole combination.
//
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent modules, and
// to copy and distribute the resulting executable under terms of your choice,
// provided that you also meet, for each linked independent module, the terms
// and conditions of the license of that module. An independent module is a module
// which is not derived from or based on this library. If you modify this library,
// you may extend this exception to your version of the library, but you are not
// obligated to do so. If you do not wish to do so, delete this exception
// statement from your version.
//
// A copy of the GNU General Public License is provided in the file gpl.txt. You
// may also obtain a copy of the GNU General Public License on the World Wide
// Web at http://www.gnu.org/licenses/gpl.html.
//
//******************************************************************************
package edu.rit.util;

import java.util.Iterator;
import java.util.Vector;

/**
 * Class TimerThread encapsulates a thread that does the timing for {@linkplain
 * Timer}s and performs {@linkplain TimerTask}s' actions when timeouts occur.
 * <P>
 * A timer is created by calling a timer thread's <code>createTimer()</code> method,
 * giving a timer task to associate with the timer. Multiple timers may be
 * created under the control of the same timer thread. The timer thread will
 * perform the actions of its timers' timer tasks one at a time at the proper
 * instants (by causing each timer to call its timer task's <code>action()</code>
 * method). Note that the timer tasks of a single timer thread are performed
 * sequentially, which may cause some timer tasks' actions to be delayed
 * depending on how long other timer tasks' actions take to execute. If
 * necessary, consider running separate timers in separate timer threads so the
 * timer tasks' actions run concurrently.
 * <P>
 * Class TimerThread does <I>not</I> offer real-time guarantees. It merely makes
 * a best-effort attempt to perform each timer task's actions as soon as
 * possible after the timeouts occur.
 * <P>
 * A TimerThread is just a {@linkplain java.lang.Thread Thread}. After
 * constructing a timer thread, you can mark it as a daemon thread if you want.
 * You must also call the timer thread's <code>start()</code> method, or no timeouts
 * will occur. To gracefully stop a timer thread, call the <code>shutdown()</code>
 * method.
 * <P>
 * To simplify writing programs with multiple objects that all use the same
 * timer thread, the static <code>TimerThread.getDefault()</code> method returns a
 * single shared instance of class TimerThread. The default timer thread is
 * marked as a daemon thread and is started automatically. The default timer
 * thread is not created until the first call to
 * <code>TimerThread.getDefault()</code>.
 * <P>
 * Classes {@linkplain Timer}, {@linkplain TimerTask}, and TimerThread provide
 * capabilities similar to classes java.util.Timer and java.util.TimerTask.
 * Unlike the latter, they also provide the ability to stop and restart a timer
 * and the ability to deal with race conditions in multithreaded programs.
 *
 * @author Alan Kaminsky
 * @version 18-Jun-2003
 */
public class TimerThread
        extends Thread {

// Hidden helper classes.
    /**
     * Class TimerThread.TimeoutInfo is a record used to keep track of a
     * timeout.
     *
     * @author Alan Kaminsky
     * @version 18-Sep-2002
     */
    private static class TimeoutInfo {
        // Instant at which the timeout will occur (milliseconds since midnight
        // 01-Jan-1970 UTC).

        public long myTimeout;

        // Timer to trigger.
        public Timer myTimer;

        public TimeoutInfo(long theTimeout,
                Timer theTimer) {
            myTimeout = theTimeout;
            myTimer = theTimer;
        }
    }

// Hidden data members.
    /**
     * Queue of timeout info records, organized as a heap in order of timeout.
     * Index 0 is unused. Indexes 1 .. mySize contain the heap. The queue's
     * length is increased by INCR when necessary to add a new record.
     */
    private static final int INCR = 4;
    private TimeoutInfo[] myQueue = new TimeoutInfo[INCR + 1];

    /**
     * Number of records in the queue.
     */
    private int mySize = 0;

    /**
     * True if this timer thread is running, false if it's shut down.
     */
    private boolean iamRunning = true;

// Hidden static data members.
    /**
     * The default timer thread.
     */
    private static TimerThread theDefaultTimerThread = null;

// Exported constructors.
    /**
     * Construct a new timer thread. After constructing it, you must call the
     * timer thread's <code>start()</code> method, or no timeouts will occur.
     */
    public TimerThread() {
        super();
    }

// Exported operations.
    /**
     * Get the default timer thread, a single shared instance of class
     * TimerThread. The default timer thread is marked as a daemon thread and is
     * started automatically. The default timer thread is not created until the
     * first call to <code>TimerThread.getDefault()</code>.
     *
     * @return Default timer thread.
     */
    public static synchronized TimerThread getDefault() {
        if (theDefaultTimerThread == null) {
            theDefaultTimerThread = new TimerThread();
            theDefaultTimerThread.setDaemon(true);
            theDefaultTimerThread.start();
        }
        return theDefaultTimerThread;
    }

    /**
     * Create a new timer associated with the given timer task and under the
     * control of this timer thread. When the timer is triggered, this timer
     * thread will cause the timer to call the given timer task's
     * <code>action()</code> method.
     *
     * @param theTimerTask Timer task.
     * @exception NullPointerException (unchecked exception) Thrown if
     * <code>theTimerTask</code> is null.
     * @return a {@link edu.rit.util.Timer} object.
     */
    public Timer createTimer(TimerTask theTimerTask) {
        return new Timer(this, theTimerTask);
    }

    /**
     * Shut down this timer thread.
     */
    public void shutdown() {
        synchronized (this) {
            iamRunning = false;
            notifyAll();
        }
    }

    /**
     * Perform this timer thread's processing. (Never call the <code>run()</code>
     * method yourself!)
     *
     * @exception IllegalStateException (unchecked exception) Thrown if some
     * thread other than this timer thread called the <code>run()</code> method.
     */
    @SuppressWarnings("unchecked")
    public void run() {
        // Only this timer thread itself can call the run() method.
        if (Thread.currentThread() != this) {
            throw new IllegalStateException("Wrong thread called the run() method");
        }

        try {
            while (iamRunning) {
                long now = System.currentTimeMillis();
                Vector<TimeoutInfo> theTriggeredTimeouts;

                synchronized (this) {
                    // If timeout queue is empty, wait until notified.
                    if (mySize == 0) {
                        wait();
                        now = System.currentTimeMillis();
                    } // If timeout queue is not empty and first timeout is in the
                    // future, wait until timeout or until notified.
                    else {
                        long waitTime = myQueue[1].myTimeout - now;
                        if (waitTime > 0L) {
                            wait(waitTime);
                            now = System.currentTimeMillis();
                        }
                    }

                    // Pull all timeouts that have occurred out of the timeout
                    // queue into a separate list.
                    theTriggeredTimeouts = new Vector<>();
                    while (mySize > 0 && myQueue[1].myTimeout <= now) {
                        theTriggeredTimeouts.add(myQueue[1]);
                        myQueue[1] = myQueue[mySize];
                        myQueue[mySize] = null;
                        --mySize;
                        siftDown(mySize);
                    }
                }

                // Perform the action of each triggered timeout. Do this outside
                // the synchronized block, or a deadlock may happen if a timer
                // is restarted.
                Iterator<TimeoutInfo> iter = theTriggeredTimeouts.iterator();
                while (iter.hasNext()) {
                    iter.next().myTimer.trigger(now);
                }
            }
        } catch (InterruptedException exc) {
            System.err.println("TimerThread interrupted");
            exc.printStackTrace(System.err);
        }
    }

// Hidden operations.
    /**
     * Schedule a timer.
     *
     * @param theTimeout Timeout instant.
     * @param theTimer Timer.
     */
    synchronized void schedule(long theTimeout,
            Timer theTimer) {
        // Increase queue allocation if necessary.
        if (mySize == myQueue.length - 1) {
            TimeoutInfo[] newQueue = new TimeoutInfo[myQueue.length + INCR];
            System.arraycopy(myQueue, 1, newQueue, 1, mySize);
            myQueue = newQueue;
        }

        // Add a new timeout info record to the queue.
        ++mySize;
        myQueue[mySize] = new TimeoutInfo(theTimeout, theTimer);
        siftUp(mySize);

        // Wake up the timer thread.
        notifyAll();
    }

    /**
     * Sift up the last element in the heap. Precondition: HEAP(1,n-1) and n
     * &gt; 0. Postcondition: HEAP(1,n).
     */
    private void siftUp(int n) {
        int i = n;
        int p;
        TimeoutInfo temp;
        for (;;) {
            // Invariant: HEAP(1,n) except perhaps between i and its parent.
            if (i == 1) {
                break;
            }
            p = i / 2;
            if (myQueue[p].myTimeout <= myQueue[i].myTimeout) {
                break;
            }
            temp = myQueue[p];
            myQueue[p] = myQueue[i];
            myQueue[i] = temp;
            i = p;
        }
    }

    /**
     * Sift down the first element in the heap. Precondition: HEAP(2,n) and n
     * &gt;= 0. Postcondition: HEAP(1,n).
     */
    private void siftDown(int n) {
        int i = 1;
        int c;
        TimeoutInfo temp;
        for (;;) {
            // Invariant: HEAP(1,n) except perhaps between i and its 0, 1, or 2
            // children.
            c = 2 * i;
            if (c > n) {
                break;
            }
            // c is the left child of i.
            if (c + 1 <= n) {
                // c+1 is the right child of i.
                if (myQueue[c + 1].myTimeout < myQueue[c].myTimeout) {
                    c = c + 1;
                }
            }
            // c is the least child of i.
            if (myQueue[i].myTimeout <= myQueue[c].myTimeout) {
                break;
            }
            temp = myQueue[c];
            myQueue[c] = myQueue[i];
            myQueue[i] = temp;
            i = c;
        }
    }

// Unit test main program.
//	/**
//	 * Helper class for unit test main program.
//	 */
//	private static class Message
//		implements TimerTask
//		{
//		private String myMessage;
//
//		public Message
//			(String theMessage)
//			{
//			myMessage = theMessage;
//			}
//
//		public void action
//			(Timer theTimer)
//			{
//			System.out.println (myMessage);
//			}
//		}
//
//	/**
//	 * Unit test main program.
//	 */
//	public static void main
//		(String[] args)
//		{
//		try
//			{
//			TimerThread theTimerThread = new TimerThread();
//			theTimerThread.start();
//
//			Timer timer1 =
//				theTimerThread.createTimer
//					(new Message ("Timer 1 triggered"));
//
//			Timer timer2 =
//				theTimerThread.createTimer
//					(new Message ("Timer 2 triggered"));
//
//			Timer timer3 =
//				theTimerThread.createTimer
//					(new Message ("Timer 3 triggered"));
//
//			timer1.start (1000L, 1000L);
//			timer2.start (5000L, 5000L);
//			timer3.start (10000L);
//			}
//		catch (Throwable exc)
//			{
//			System.err.println ("edu.rit.util.TimerThread: Uncaught exception");
//			exc.printStackTrace (System.err);
//			}
//		}
}