summaryrefslogtreecommitdiff
path: root/java/util/Timer.java
blob: b145d2b7cc89deebbb22b9ede550a042d0e6cde7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
/* Timer.java -- Timer that runs TimerTasks at a later time.
   Copyright (C) 2000, 2001, 2005 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath 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 2, or (at your option)
any later version.

GNU Classpath 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.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

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. */

package java.util;

/**
 * Timer that can run TimerTasks at a later time.
 * TimerTasks can be scheduled for one time execution at some time in the
 * future. They can be scheduled to be rescheduled at a time period after the
 * task was last executed. Or they can be scheduled to be executed repeatedly
 * at a fixed rate.
 * <p>
 * The normal scheduling will result in a more or less even delay in time
 * between successive executions, but the executions could drift in time if
 * the task (or other tasks) takes a long time to execute. Fixed delay
 * scheduling guarantees more or less that the task will be executed at a
 * specific time, but if there is ever a delay in execution then the period
 * between successive executions will be shorter. The first method of
 * repeated scheduling is preferred for repeated tasks in response to user
 * interaction, the second method of repeated scheduling is preferred for tasks
 * that act like alarms.
 * <p>
 * The Timer keeps a binary heap as a task priority queue which means that
 * scheduling and serving of a task in a queue of n tasks costs O(log n).
 *
 * @see TimerTask
 * @since 1.3
 * @author Mark Wielaard (mark@klomp.org)
 */
public class Timer
{
  /**
   * Priority Task Queue.
   * TimerTasks are kept in a binary heap.
   * The scheduler calls sleep() on the queue when it has nothing to do or
   * has to wait. A sleeping scheduler can be notified by calling interrupt()
   * which is automatically called by the enqueue(), cancel() and
   * timerFinalized() methods.
   */
  private static final class TaskQueue
  {
    /** Default size of this queue */
    private static final int DEFAULT_SIZE = 32;

    /** Whether to return null when there is nothing in the queue */
    private boolean nullOnEmpty;

    /**
     * The heap containing all the scheduled TimerTasks
     * sorted by the TimerTask.scheduled field.
     * Null when the stop() method has been called.
     */
    private TimerTask heap[];

    /**
     * The actual number of elements in the heap
     * Can be less then heap.length.
     * Note that heap[0] is used as a sentinel.
     */
    private int elements;

    /**
     * Creates a TaskQueue of default size without any elements in it.
     */
    public TaskQueue()
    {
      heap = new TimerTask[DEFAULT_SIZE];
      elements = 0;
      nullOnEmpty = false;
    }

    /**
     * Adds a TimerTask at the end of the heap.
     * Grows the heap if necessary by doubling the heap in size.
     */
    private void add(TimerTask task)
    {
      elements++;
      if (elements == heap.length)
	{
	  TimerTask new_heap[] = new TimerTask[heap.length * 2];
	  System.arraycopy(heap, 0, new_heap, 0, heap.length);
	  heap = new_heap;
	}
      heap[elements] = task;
    }

    /**
     * Removes the last element from the heap.
     * Shrinks the heap in half if
     * elements+DEFAULT_SIZE/2 <= heap.length/4.
     */
    private void remove()
    {
      // clear the entry first
      heap[elements] = null;
      elements--;
      if (elements + DEFAULT_SIZE / 2 <= (heap.length / 4))
	{
	  TimerTask new_heap[] = new TimerTask[heap.length / 2];
	  System.arraycopy(heap, 0, new_heap, 0, elements + 1);
	  heap = new_heap;
	}
    }

    /**
     * Adds a task to the queue and puts it at the correct place
     * in the heap.
     */
    public synchronized void enqueue(TimerTask task)
    {
      // Check if it is legal to add another element
      if (heap == null)
	{
	  throw new IllegalStateException
	    ("cannot enqueue when stop() has been called on queue");
	}

      heap[0] = task;		// sentinel
      add(task);		// put the new task at the end
      // Now push the task up in the heap until it has reached its place
      int child = elements;
      int parent = child / 2;
      while (heap[parent].scheduled > task.scheduled)
	{
	  heap[child] = heap[parent];
	  child = parent;
	  parent = child / 2;
	}
      // This is the correct place for the new task
      heap[child] = task;
      heap[0] = null;		// clear sentinel
      // Maybe sched() is waiting for a new element
      this.notify();
    }

    /**
     * Returns the top element of the queue.
     * Can return null when no task is in the queue.
     */
    private TimerTask top()
    {
      if (elements == 0)
	{
	  return null;
	}
      else
	{
	  return heap[1];
	}
    }

    /**
     * Returns the top task in the Queue.
     * Removes the element from the heap and reorders the heap first.
     * Can return null when there is nothing in the queue.
     */
    public synchronized TimerTask serve()
    {
      // The task to return
      TimerTask task = null;

      while (task == null)
	{
	  // Get the next task
	  task = top();

	  // return null when asked to stop
	  // or if asked to return null when the queue is empty
	  if ((heap == null) || (task == null && nullOnEmpty))
	    {
	      return null;
	    }

	  // Do we have a task?
	  if (task != null)
	    {
	      // The time to wait until the task should be served
	      long time = task.scheduled - System.currentTimeMillis();
	      if (time > 0)
		{
		  // This task should not yet be served
		  // So wait until this task is ready
		  // or something else happens to the queue
		  task = null;	// set to null to make sure we call top()
		  try
		    {
		      this.wait(time);
		    }
		  catch (InterruptedException _)
		    {
		    }
		}
	    }
	  else
	    {
	      // wait until a task is added
	      // or something else happens to the queue
	      try
		{
		  this.wait();
		}
	      catch (InterruptedException _)
		{
		}
	    }
	}

      // reconstruct the heap
      TimerTask lastTask = heap[elements];
      remove();

      // drop lastTask at the beginning and move it down the heap
      int parent = 1;
      int child = 2;
      heap[1] = lastTask;
      while (child <= elements)
	{
	  if (child < elements)
	    {
	      if (heap[child].scheduled > heap[child + 1].scheduled)
		{
		  child++;
		}
	    }

	  if (lastTask.scheduled <= heap[child].scheduled)
	    break;		// found the correct place (the parent) - done

	  heap[parent] = heap[child];
	  parent = child;
	  child = parent * 2;
	}

      // this is the correct new place for the lastTask
      heap[parent] = lastTask;

      // return the task
      return task;
    }

    /**
     * When nullOnEmpty is true the serve() method will return null when
     * there are no tasks in the queue, otherwise it will wait until
     * a new element is added to the queue. It is used to indicate to
     * the scheduler that no new tasks will ever be added to the queue.
     */
    public synchronized void setNullOnEmpty(boolean nullOnEmpty)
    {
      this.nullOnEmpty = nullOnEmpty;
      this.notify();
    }

    /**
     * When this method is called the current and all future calls to
     * serve() will return null. It is used to indicate to the Scheduler
     * that it should stop executing since no more tasks will come.
     */
    public synchronized void stop()
    {
      this.heap = null;
      this.elements = 0;
      this.notify();
    }

    /**
     * Remove all canceled tasks from the queue.
     */
    public synchronized int purge()
    {
      int removed = 0;
      // Null out any elements that are canceled.  Skip element 0 as
      // it is the sentinel.
      for (int i = elements; i > 0; --i)
	{
	  if (heap[i].scheduled < 0)
	    {
	      ++removed;

	      // Remove an element by pushing the appropriate child
	      // into place, and then iterating to the bottom of the
	      // tree.
	      int index = i;
	      while (heap[index] != null)
		{
		  int child = 2 * index;
		  if (child >= heap.length)
		    {
		      // Off end; we're done.
		      heap[index] = null;
		      break;
		    }

		  if (child + 1 >= heap.length || heap[child + 1] == null)
		    {
		      // Nothing -- we're done.
		    }
		  else if (heap[child] == null
			   || (heap[child].scheduled
			       > heap[child + 1].scheduled))
		    ++child;
		  heap[index] = heap[child];
		  index = child;
		}
	    }
	}

      // Make a new heap if we shrank enough.
      int newLen = heap.length;
      while (elements - removed + DEFAULT_SIZE / 2 <= newLen / 4)
	newLen /= 2;
      if (newLen != heap.length)
	{
	  TimerTask[] newHeap = new TimerTask[newLen];
	  System.arraycopy(heap, 0, newHeap, 0, elements + 1);
	  heap = newHeap;
	}

      return removed;
    }
  }				// TaskQueue

  /**
   * The scheduler that executes all the tasks on a particular TaskQueue,
   * reschedules any repeating tasks and that waits when no task has to be
   * executed immediately. Stops running when canceled or when the parent
   * Timer has been finalized and no more tasks have to be executed.
   */
  private static final class Scheduler implements Runnable
  {
    // The priority queue containing all the TimerTasks.
    private TaskQueue queue;

    /**
     * Creates a new Scheduler that will schedule the tasks on the
     * given TaskQueue.
     */
    public Scheduler(TaskQueue queue)
    {
      this.queue = queue;
    }

    public void run()
    {
      TimerTask task;
      while ((task = queue.serve()) != null)
	{
	  // If this task has not been canceled
	  if (task.scheduled >= 0)
	    {

	      // Mark execution time
	      task.lastExecutionTime = task.scheduled;

	      // Repeatable task?
	      if (task.period < 0)
		{
		  // Last time this task is executed
		  task.scheduled = -1;
		}

	      // Run the task
	      try
		{
		  task.run();
		}
              catch (ThreadDeath death)
                {
                  // If an exception escapes, the Timer becomes invalid.
                  queue.stop();
                  throw death;
                }
	      catch (Throwable t)
		{
		  // If an exception escapes, the Timer becomes invalid.
                  queue.stop();
		}
	    }

	  // Calculate next time and possibly re-enqueue.
	  if (task.scheduled >= 0)
	    {
	      if (task.fixed)
		{
		  task.scheduled += task.period;
		}
	      else
		{
		  task.scheduled = task.period + System.currentTimeMillis();
		}

	      try
	        {
	          queue.enqueue(task);
		}
	      catch (IllegalStateException ise)
	        {
		  // Ignore. Apparently the Timer queue has been stopped.
		}
	    }
	}
    }
  }				// Scheduler

  // Number of Timers created.
  // Used for creating nice Thread names.
  private static int nr;

  // The queue that all the tasks are put in.
  // Given to the scheduler
  private TaskQueue queue;

  // The Scheduler that does all the real work
  private Scheduler scheduler;

  // Used to run the scheduler.
  // Also used to checked if the Thread is still running by calling
  // thread.isAlive(). Sometimes a Thread is suddenly killed by the system
  // (if it belonged to an Applet).
  private Thread thread;

  // When cancelled we don't accept any more TimerTasks.
  private boolean canceled;

  /**
   * Creates a new Timer with a non daemon Thread as Scheduler, with normal
   * priority and a default name.
   */
  public Timer()
  {
    this(false);
  }

  /**
   * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
   * with normal priority and a default name.
   */
  public Timer(boolean daemon)
  {
    this(daemon, Thread.NORM_PRIORITY);
  }

  /** @since 1.5 */
  public Timer(String name)
  {
    this(false, Thread.NORM_PRIORITY, name);
  }

  /** @since 1.5 */
  public Timer(String name, boolean daemon)
  {
    this(daemon, Thread.NORM_PRIORITY, name);
  }

  /**
   * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
   * with the priority given and a default name.
   */
  private Timer(boolean daemon, int priority)
  {
    this(daemon, priority, "Timer-" + (++nr));
  }

  /**
   * Creates a new Timer with a daemon Thread as scheduler if daemon is true,
   * with the priority and name given.E
   */
  private Timer(boolean daemon, int priority, String name)
  {
    canceled = false;
    queue = new TaskQueue();
    scheduler = new Scheduler(queue);
    thread = new Thread(scheduler, name);
    thread.setDaemon(daemon);
    thread.setPriority(priority);
    thread.start();
  }

  /**
   * Cancels the execution of the scheduler. If a task is executing it will
   * normally finish execution, but no other tasks will be executed and no
   * more tasks can be scheduled.
   */
  public void cancel()
  {
    canceled = true;
    queue.stop();
  }

  /**
   * Schedules the task at Time time, repeating every period
   * milliseconds if period is positive and at a fixed rate if fixed is true.
   *
   * @exception IllegalArgumentException if time is negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  private void schedule(TimerTask task, long time, long period, boolean fixed)
  {
    if (time < 0)
      throw new IllegalArgumentException("negative time");

    if (task.scheduled == 0 && task.lastExecutionTime == -1)
      {
	task.scheduled = time;
	task.period = period;
	task.fixed = fixed;
      }
    else
      {
	throw new IllegalStateException
	  ("task was already scheduled or canceled");
      }

    if (!this.canceled && this.thread != null)
      {
	queue.enqueue(task);
      }
    else
      {
	throw new IllegalStateException
	  ("timer was canceled or scheduler thread has died");
      }
  }

  private static void positiveDelay(long delay)
  {
    if (delay < 0)
      {
	throw new IllegalArgumentException("delay is negative");
      }
  }

  private static void positivePeriod(long period)
  {
    if (period < 0)
      {
	throw new IllegalArgumentException("period is negative");
      }
  }

  /**
   * Schedules the task at the specified data for one time execution.
   *
   * @exception IllegalArgumentException if date.getTime() is negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  public void schedule(TimerTask task, Date date)
  {
    long time = date.getTime();
    schedule(task, time, -1, false);
  }

  /**
   * Schedules the task at the specified date and reschedules the task every
   * period milliseconds after the last execution of the task finishes until
   * this timer or the task is canceled.
   *
   * @exception IllegalArgumentException if period or date.getTime() is
   * negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  public void schedule(TimerTask task, Date date, long period)
  {
    positivePeriod(period);
    long time = date.getTime();
    schedule(task, time, period, false);
  }

  /**
   * Schedules the task after the specified delay milliseconds for one time
   * execution.
   *
   * @exception IllegalArgumentException if delay or
   * System.currentTimeMillis + delay is negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  public void schedule(TimerTask task, long delay)
  {
    positiveDelay(delay);
    long time = System.currentTimeMillis() + delay;
    schedule(task, time, -1, false);
  }

  /**
   * Schedules the task after the delay milliseconds and reschedules the
   * task every period milliseconds after the last execution of the task
   * finishes until this timer or the task is canceled.
   *
   * @exception IllegalArgumentException if delay or period is negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  public void schedule(TimerTask task, long delay, long period)
  {
    positiveDelay(delay);
    positivePeriod(period);
    long time = System.currentTimeMillis() + delay;
    schedule(task, time, period, false);
  }

  /**
   * Schedules the task at the specified date and reschedules the task at a
   * fixed rate every period milliseconds until this timer or the task is
   * canceled.
   *
   * @exception IllegalArgumentException if period or date.getTime() is
   * negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  public void scheduleAtFixedRate(TimerTask task, Date date, long period)
  {
    positivePeriod(period);
    long time = date.getTime();
    schedule(task, time, period, true);
  }

  /**
   * Schedules the task after the delay milliseconds and reschedules the task
   * at a fixed rate every period milliseconds until this timer or the task
   * is canceled.
   *
   * @exception IllegalArgumentException if delay or
   * System.currentTimeMillis + delay is negative
   * @exception IllegalStateException if the task was already scheduled or
   * canceled or this Timer is canceled or the scheduler thread has died
   */
  public void scheduleAtFixedRate(TimerTask task, long delay, long period)
  {
    positiveDelay(delay);
    positivePeriod(period);
    long time = System.currentTimeMillis() + delay;
    schedule(task, time, period, true);
  }

  /**
   * Tells the scheduler that the Timer task died
   * so there will be no more new tasks scheduled.
   */
  protected void finalize() throws Throwable
  {
    queue.setNullOnEmpty(true);
  }

  /** @since 1.5 */
  public int purge()
  {
    return queue.purge();
  }
}