Source code: iiuf/util/Timer.java
1 package iiuf.util;
2
3 import java.util.Random;
4 import java.io.Serializable;
5
6 /**
7 The timer class. This class implements timer tasks that can be run at
8 a specified time. This class stores tasks in an efficient tree
9 representation which keeps the insert and remove costs almost constant
10 even for a large (> 10000) number of tasks.
11
12 (c) 1999, 2000, 2001, IIUF, DIUF<p>
13
14 @author $Author: ohitz $
15 @version $Revision: 1.1 $
16 */
17 public class Timer
18 implements
19 Runnable,
20 Serializable
21 {
22 /** @serial The initial delay. */
23 public long milliseconds;
24 /** @serial The absolute time when this timer will be triggerd. */
25 public long absolute = Long.MAX_VALUE;
26 /** The link to the next timer. */
27 transient protected Timer next;
28 /** Set to <code>true</code> as soon as the <code>run</code> method
29 starts executing. reset by <code>reschedule</code> or
30 <code>schedule</code>.
31 */
32 transient protected boolean execute;
33 /** @serial If <code>true</code>, the timer's <code>run</code>
34 method will be run
35 in a separate thread. */
36 protected boolean thread;
37 /** The task to run by this timer, or <code>null</code> if no task. */
38 transient private Runnable timer_task;
39 /** If <code>true</code>, the timer's <code>run</code> will not be called.
40 This variable is set to false by <code>TimerTree.insert()</code> and set by <code>TimerTree.remove()</code>. */
41 transient boolean dontRun;
42
43 protected Timer() {this(false);}
44
45 protected Timer(boolean thread_) {
46 thread = thread_;
47 }
48
49 /**
50 Creates a new timer task.
51
52 @param timer_task_ The timer task to run.
53 @param thread Run the task as a thread if true, run by timer
54 thread if false.
55 */
56 public Timer(Runnable timer_task_, boolean thread) {
57 this(thread);
58 timer_task = timer_task_;
59 }
60
61 /**
62 Schedules this objects <code>run</code> method to be executed in
63 <code>milliseconds_</code> from now.
64
65 @param milliseconds_ Milliseconds from now until the the <code>run</code>
66 method is executed.
67
68 @return This timer.
69 */
70 public Timer schedule(long milliseconds_) {
71 execute = false;
72 TimerTree.remove(this);
73 milliseconds = milliseconds_;
74 absolute = System.currentTimeMillis() + milliseconds;
75 TimerTree.insert(this);
76 return this;
77 }
78
79 /**
80 Cancels this timer. Cancel only ensures that the <code>run</code> method is
81 not executed after <code>cancel</code> returns. But the <code>run</code>
82 method may be excuted during the execution of <code>cancel</code>.
83
84 @return This timer.
85 */
86 public Timer cancel() {
87 TimerTree.remove(this);
88 return this;
89 }
90
91 /**
92 Re-schedules this objects <code>run</code> method to be executed in
93 <code>milliseconds_</code> after the <code>schedule</code> call from the
94 last execution of the <code>run</code> method. Use this call for fixed
95 frequency tasks instead of using <code>schedule</code> in order
96 to avoid drift.
97
98 @return This timer.
99 */
100 public Timer reschedule() {
101 TimerTree.remove(this);
102 absolute += milliseconds;
103 execute = false;
104 TimerTree.insert(this);
105 return this;
106 }
107
108 public String toString() {
109 return
110 "(ms:" + milliseconds +
111 ":abs:" + absolute +
112 ":exe:" + execute +
113 (next == null ? "" : ":next:" + next) +
114 ")";
115 }
116
117 public void run() {
118 if(timer_task != null)
119 timer_task.run();
120 }
121
122 //
123 // T E S T S T U F F
124 //
125
126 private static Random random = new Random();
127 private static int rnd(int range) {
128 int result = random.nextInt();
129 result = result < 0 ? -result : result;
130 return result % range;
131 }
132
133 private static void countdown(int sec) {
134 for(int i = sec; sec >= 0; sec--) {
135 System.out.print("\b\b\b\b\b\b\b\b\b" + sec + " ");
136 System.out.flush();
137 try{Thread.sleep(1000);}
138 catch(Exception e) {}
139 }
140 }
141
142 /** Test program. */
143 public static void main(String[] argv) {
144 int test = Integer.parseInt(argv[0]);
145 switch(test) {
146 case 0:
147 System.out.println("Single task, in 5 seconds.");
148 new TestTimer("Hello!", false).schedule(5000);
149 countdown(5);
150 break;
151 case 1:
152 System.out.println("Single task, every 5 seconds.");
153 new TestTimer("Hello!", true).schedule(5000);
154 break;
155 case 2:
156 System.out.println("Two task, in 5 seconds.");
157 TestTimer t0 = new TestTimer("Hello 0!", false);
158 TestTimer t1 = new TestTimer("Hello 1!", false);
159
160 t0.schedule(5000);
161 t1.milliseconds = t0.milliseconds;
162 t1.absolute = t0.absolute;
163
164 TimerTree.insert(t1);
165 System.out.println(TimerTree.root);
166
167 countdown(5);
168 break;
169 case 3: {
170 System.out.println("Random timers");
171 Timer[] t = new Timer[10000];
172 for(;;) {
173 int idx = rnd(t.length);
174 int time = rnd(5000) + 100;
175 boolean reschedule = rnd(2) == 1;
176 if(t[idx] != null)
177 t[idx].cancel();
178 t[idx] = new TestTimer("[" + idx + "]Hello(" + time + ", " +
179 reschedule + ")", reschedule);
180 System.out.println("Scheduling new task...");
181 t[idx].schedule(time);
182 try{
183 Thread.sleep(250);
184 if(System.in.available() > 0) {
185 System.out.println(TimerTree.root);
186 System.exit(0);
187 }
188 }
189 catch(Exception e) {}
190 }
191 }
192 case 4: {
193 System.out.println("Random timers fill");
194 Timer[] t = new Timer[Integer.parseInt(argv[1])];
195 for(int i = 0; i < t.length; i++) {
196 int time = rnd(5000);
197 t[i] = new TestTimer("[" + i + "]Hello(" + time + ")", false);
198 t[i].schedule(time);
199 }
200 countdown(15);
201 System.out.println();
202 long now = System.currentTimeMillis();
203 for(int i = 0; i < t.length; i++)
204 System.out.println("[" + i + "]" + t[i] + (now - t[i].absolute));
205 System.out.println(TimerTree.root);
206 System.exit(0);
207 break;
208 }
209 }
210 }
211 }
212
213 class TestTimer
214 extends
215 Timer {
216
217 static long min = Long.MAX_VALUE;
218 static long max = Long.MIN_VALUE;
219 static long sum;
220 static long count;
221 transient String message;
222 transient boolean reschedule;
223
224 TestTimer(String message_, boolean reschedule_) {
225 message = message_;
226 reschedule = reschedule_;
227 }
228
229 public void run() {
230 long error = System.currentTimeMillis() - absolute;
231 if(error < min) min = error;
232 if(error > max) max = error;
233 sum += error;
234 count++;
235 System.out.println(message + "[" +
236 min + "," +
237 error + "," +
238 max + "," +
239 (sum / count) + "]");
240 if(reschedule)
241 reschedule();
242 }
243 }
244
245 final class TimerTree {
246 static final Object LOCK = TimerTree.class;
247 static final boolean DEBUG = false;
248 static final int CHILDS = 256;
249 static final int ILLEGAL = 1000;
250 static long start = System.currentTimeMillis();
251 static TimerTree root;
252 static TimerThread timer_thread = new TimerThread();
253 static int baseshift;
254 int shift;
255 int min;
256 int max;
257 TimerTree[] childs;
258 Timer[] timers;
259
260 static Timer min() {
261 synchronized(LOCK) {
262 return root._min();
263 }
264 }
265
266 static void insert(Timer timer) {
267 if(DEBUG) System.out.println("insert(" + timer + ")");
268 timer.dontRun = false;
269 long ltime = timer.absolute - start;
270 long stime = ltime >> baseshift;
271 synchronized(LOCK) {
272 while(stime > 0) {
273 baseshift += 8;
274 stime = ltime >> baseshift;
275 if(root != null)
276 root = new TimerTree(baseshift, root);
277 }
278 if(root == null) root = new TimerTree(baseshift);
279 root.insert(ltime, timer);
280 }
281 timer_thread.check();
282 if(DEBUG) System.out.println(root);
283 }
284
285 static void remove(Timer timer) {
286 if(DEBUG) System.out.println("remove(" + timer + ")");
287 synchronized(LOCK) {
288 if(root != null) {
289 root.remove(timer.absolute - start, timer);
290 timer.next = null;
291 }
292 }
293 timer.dontRun = true;
294 if(DEBUG) System.out.println(root);
295 }
296
297 private Timer _min() {
298 if(min == ILLEGAL) return null;
299 return shift > 0 ? childs[min]._min() : timers[min];
300 }
301
302 private TimerTree(int shift_) {
303 shift = shift_ - 8;
304 min = ILLEGAL;
305 max = -1;
306 if(shift > 0)
307 childs = new TimerTree[CHILDS];
308 else
309 timers = new Timer[CHILDS];
310 }
311
312 private TimerTree(int shift_, TimerTree old) {
313 shift = shift_ - 8;
314 childs = new TimerTree[CHILDS];
315 if(old.min != ILLEGAL) {
316 childs[0] = old;
317 min = max = 0;
318 }
319 else {
320 min = ILLEGAL;
321 max = -1;
322 }
323 }
324
325 private TimerTree(int shift_, long time, Timer timer) {
326 shift = shift_ - 8;
327 min = max = (int)((time >> shift) & 0x0FF);
328 if(shift > 0) {
329 childs = new TimerTree[CHILDS];
330 childs[min] = new TimerTree(shift, time, timer);
331 }
332 else {
333 timers = new Timer[CHILDS];
334 timers[min] = timer;
335 }
336 }
337
338 private void insert(long time, Timer timer) {
339 int idx = (int)(( time >> shift) & 0x0FF);
340 if(idx < min) min = idx;
341 if(idx > max) max = idx;
342 if(shift > 0) {
343 if(childs[idx] == null)
344 childs[idx] = new TimerTree(shift, time, timer);
345 else
346 childs[idx].insert(time, timer);
347 }
348 else {
349 timer.next = timers[idx];
350 timers[idx] = timer;
351 }
352 }
353
354 private boolean remove(long time, Timer timer) {
355 int idx = (int)((time >> shift) & 0x0FF);
356 if(shift > 0) {
357 if(childs[idx] != null &&
358 childs[idx].remove(time, timer)) {
359 childs[idx] = null;
360 for(int i = min; i <= max; i++)
361 if(childs[i] != null) {
362 min = i;
363 return false;
364 }
365 min = ILLEGAL;
366 max = -1;
367 return true;
368 }
369 return false;
370 }
371 else {
372 Timer last = null;
373 for(Timer t = timers[idx]; t != null; t = t.next) {
374 if(t == timer)
375 if(last == null)
376 timers[idx] = t.next;
377 else
378 last.next = t.next;
379 last = t;
380 }
381 for(int i = min; i <= max; i++)
382 if(timers[i] != null) {
383 min = i;
384 return false;
385 }
386 min = ILLEGAL;
387 max = -1;
388 return true;
389 }
390 }
391
392 private String prefix() {
393 String result = "";
394 for(int i = 0; i < (64 - shift) / 8; i++)
395 result += " ";
396 return result;
397 }
398
399 public String toString() {
400 String result = prefix() + "shift:" + shift +
401 ":min:" + min + ":max:" + max + "\n";
402 if(childs != null)
403 for(int i = 0; i < childs.length; i++)
404 if(childs[i] != null)
405 result += prefix() + "childs[" + i + "]\n" + childs[i];
406 if(timers != null)
407 for(int i = 0; i < timers.length; i++)
408 if(timers[i] != null)
409 result += prefix() + "timers[" + i + "]:" + timers[i] + "\n";
410 return result;
411 }
412 }
413
414 final class TimerThread
415 extends
416 Thread
417 {
418 private boolean notified;
419
420 TimerThread() {
421 setName("TimerThread");
422 setPriority(Thread.MAX_PRIORITY);
423 start();
424 }
425
426 synchronized void check() {
427 notified = true;
428 notify();
429 }
430
431 public void run() {
432 synchronized(this) {
433 while(TimerTree.root == null) {
434 try{wait();}
435 catch(InterruptedException e) {
436 Util.printStackTrace(e);
437 }
438 }
439 }
440 for(;;) {
441 long now = System.currentTimeMillis();
442 Timer t = TimerTree.min();
443 if(t != null) {
444 if(now >= t.absolute) {
445 if(t.dontRun) {
446 TimerTree.remove(t);
447 continue;
448 }
449 t.execute = true;
450 TimerTree.remove(t);
451 if(t.thread)
452 new Thread(t).start();
453 else
454 t.run();
455 continue;
456 }
457 else {
458 long delta = t.absolute - now;
459 if(delta > 10) {
460 synchronized(this) {
461 if(notified) {
462 notified = false;
463 continue;
464 }
465 try{wait(delta);}
466 catch(InterruptedException e) {
467 Util.printStackTrace(e);
468 }
469 }
470 }
471 }
472 } else {
473 synchronized(this) {
474 if(notified) {
475 notified = false;
476 continue;
477 }
478 try{wait();}
479 catch(InterruptedException e) {
480 Util.printStackTrace(e);
481 }
482 }
483 }
484 }
485 }
486 }
487 /*
488 $Log: Timer.java,v $
489 Revision 1.1 2002/07/11 12:00:11 ohitz
490 Initial checkin
491
492 Revision 1.8 2001/04/30 07:33:17 schubige
493 added webcom to cvstree
494
495 Revision 1.7 2001/04/11 14:17:03 schubige
496 adapted tinja stuff for semantic checks
497
498 Revision 1.6 2001/02/23 17:23:11 schubige
499 Added loop source to soundium and fxed some bugs along
500
501 Revision 1.5 2001/02/02 18:04:35 schubige
502 rpc client working for udp & tcp
503
504 Revision 1.4 2001/01/04 16:28:42 schubige
505 Header update for 2001 and DIUF
506
507 Revision 1.3 2000/08/17 16:22:15 schubige
508 Swing cleanup & TreeView added
509
510 Revision 1.2 1999/09/03 15:50:08 schubige
511 Changed to new header & log conventions.
512
513 */