OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import 'dart:_internal' hide Symbol; | 5 import 'dart:_internal' hide Symbol; |
6 | 6 |
7 // Timer heap implemented as a array-based binary heap[0]. | 7 // Timer heap implemented as a array-based binary heap[0]. |
8 // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n)) | 8 // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n)) |
9 // `add`. | 9 // `add`. |
10 // | 10 // |
11 // To ensure the timers are ordered by insertion time, the _Timer class has a | 11 // To ensure the timers are ordered by insertion time, the _Timer class has a |
12 // `_id` field set when added to the heap. | 12 // `_id` field set when added to the heap. |
13 // | 13 // |
14 // [0] http://en.wikipedia.org/wiki/Binary_heap | 14 // [0] http://en.wikipedia.org/wiki/Binary_heap |
15 class _TimerHeap { | 15 class _TimerHeap { |
16 List<_Timer> _list; | 16 List<_Timer> _list; |
17 int _used = 0; | 17 int _used = 0; |
18 | 18 |
19 _TimerHeap([int initSize = 7]) | 19 _TimerHeap([int initSize = 7]) : _list = new List<_Timer>(initSize); |
20 : _list = new List<_Timer>(initSize); | |
21 | 20 |
22 bool get isEmpty => _used == 0; | 21 bool get isEmpty => _used == 0; |
23 | 22 |
24 _Timer get first => _list[0]; | 23 _Timer get first => _list[0]; |
25 | 24 |
26 bool isFirst(_Timer timer) => timer._indexOrNext == 0; | 25 bool isFirst(_Timer timer) => timer._indexOrNext == 0; |
27 | 26 |
28 void add(_Timer timer) { | 27 void add(_Timer timer) { |
29 if (_used == _list.length) { | 28 if (_used == _list.length) { |
30 _resize(); | 29 _resize(); |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
133 // ids are recycled after ID_MASK enqueues or when the timer queue is empty. | 132 // ids are recycled after ID_MASK enqueues or when the timer queue is empty. |
134 static const _ID_MASK = 0x1fffffff; | 133 static const _ID_MASK = 0x1fffffff; |
135 static int _idCount = 0; | 134 static int _idCount = 0; |
136 | 135 |
137 static RawReceivePort _receivePort; | 136 static RawReceivePort _receivePort; |
138 static SendPort _sendPort; | 137 static SendPort _sendPort; |
139 static int _scheduledWakeupTime; | 138 static int _scheduledWakeupTime; |
140 | 139 |
141 static bool _handlingCallbacks = false; | 140 static bool _handlingCallbacks = false; |
142 | 141 |
143 Function _callback; // Closure to call when timer fires. null if canceled. | 142 Function _callback; // Closure to call when timer fires. null if canceled. |
144 int _wakeupTime; // Expiration time. | 143 int _wakeupTime; // Expiration time. |
145 final int _milliSeconds; // Duration specified at creation. | 144 final int _milliSeconds; // Duration specified at creation. |
146 final bool _repeating; // Indicates periodic timers. | 145 final bool _repeating; // Indicates periodic timers. |
147 var _indexOrNext; // Index if part of the TimerHeap, link otherwise. | 146 var _indexOrNext; // Index if part of the TimerHeap, link otherwise. |
148 int _id; // Incrementing id to enable sorting of timers with same expiry. | 147 int _id; // Incrementing id to enable sorting of timers with same expiry. |
149 | |
150 | 148 |
151 // Get the next available id. We accept collisions and reordering when the | 149 // Get the next available id. We accept collisions and reordering when the |
152 // _idCount overflows and the timers expire at the same millisecond. | 150 // _idCount overflows and the timers expire at the same millisecond. |
153 static int _nextId() { | 151 static int _nextId() { |
154 var result = _idCount; | 152 var result = _idCount; |
155 _idCount = (_idCount + 1) & _ID_MASK; | 153 _idCount = (_idCount + 1) & _ID_MASK; |
156 return result; | 154 return result; |
157 } | 155 } |
158 | 156 |
| 157 _Timer._internal( |
| 158 this._callback, this._wakeupTime, this._milliSeconds, this._repeating) |
| 159 : _id = _nextId(); |
159 | 160 |
160 _Timer._internal(this._callback, | 161 static Timer _createTimer( |
161 this._wakeupTime, | 162 void callback(Timer timer), int milliSeconds, bool repeating) { |
162 this._milliSeconds, | |
163 this._repeating) : _id = _nextId(); | |
164 | |
165 | |
166 static Timer _createTimer(void callback(Timer timer), | |
167 int milliSeconds, | |
168 bool repeating) { | |
169 // Negative timeouts are treated as if 0 timeout. | 163 // Negative timeouts are treated as if 0 timeout. |
170 if (milliSeconds < 0) { | 164 if (milliSeconds < 0) { |
171 milliSeconds = 0; | 165 milliSeconds = 0; |
172 } | 166 } |
173 // Add one because DateTime.now() is assumed to round down | 167 // Add one because DateTime.now() is assumed to round down |
174 // to nearest millisecond, not up, so that time + duration is before | 168 // to nearest millisecond, not up, so that time + duration is before |
175 // duration milliseconds from now. Using microsecond timers like | 169 // duration milliseconds from now. Using microsecond timers like |
176 // Stopwatch allows detecting that the timer fires early. | 170 // Stopwatch allows detecting that the timer fires early. |
177 int now = VMLibraryHooks.timerMillisecondClock(); | 171 int now = VMLibraryHooks.timerMillisecondClock(); |
178 int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); | 172 int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); |
179 | 173 |
180 _Timer timer = new _Timer._internal(callback, | 174 _Timer timer = |
181 wakeupTime, | 175 new _Timer._internal(callback, wakeupTime, milliSeconds, repeating); |
182 milliSeconds, | |
183 repeating); | |
184 // Enqueue this newly created timer in the appropriate structure and | 176 // Enqueue this newly created timer in the appropriate structure and |
185 // notify if necessary. | 177 // notify if necessary. |
186 timer._enqueue(); | 178 timer._enqueue(); |
187 return timer; | 179 return timer; |
188 } | 180 } |
189 | 181 |
190 | |
191 factory _Timer(int milliSeconds, void callback(Timer timer)) { | 182 factory _Timer(int milliSeconds, void callback(Timer timer)) { |
192 return _createTimer(callback, milliSeconds, false); | 183 return _createTimer(callback, milliSeconds, false); |
193 } | 184 } |
194 | 185 |
195 | |
196 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { | 186 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { |
197 return _createTimer(callback, milliSeconds, true); | 187 return _createTimer(callback, milliSeconds, true); |
198 } | 188 } |
199 | 189 |
200 | |
201 bool get _isInHeap => _indexOrNext is int; | 190 bool get _isInHeap => _indexOrNext is int; |
202 | 191 |
203 | |
204 int _compareTo(_Timer other) { | 192 int _compareTo(_Timer other) { |
205 int c = _wakeupTime - other._wakeupTime; | 193 int c = _wakeupTime - other._wakeupTime; |
206 if (c != 0) return c; | 194 if (c != 0) return c; |
207 return _id - other._id; | 195 return _id - other._id; |
208 } | 196 } |
209 | 197 |
210 | |
211 bool get isActive => _callback != null; | 198 bool get isActive => _callback != null; |
212 | 199 |
213 | |
214 // Cancels a set timer. The timer is removed from the timer heap if it is a | 200 // Cancels a set timer. The timer is removed from the timer heap if it is a |
215 // non-zero timer. Zero timers are kept in the list as they need to consume | 201 // non-zero timer. Zero timers are kept in the list as they need to consume |
216 // the corresponding pending message. | 202 // the corresponding pending message. |
217 void cancel() { | 203 void cancel() { |
218 _callback = null; | 204 _callback = null; |
219 // Only heap timers are really removed. Zero timers need to consume their | 205 // Only heap timers are really removed. Zero timers need to consume their |
220 // corresponding wakeup message so they are left in the queue. | 206 // corresponding wakeup message so they are left in the queue. |
221 if (!_isInHeap) return; | 207 if (!_isInHeap) return; |
222 bool update = _heap.isFirst(this); | 208 bool update = _heap.isFirst(this); |
223 _heap.remove(this); | 209 _heap.remove(this); |
224 if (update) { | 210 if (update) { |
225 _notifyEventHandler(); | 211 _notifyEventHandler(); |
226 } | 212 } |
227 } | 213 } |
228 | 214 |
229 | |
230 void _advanceWakeupTime() { | 215 void _advanceWakeupTime() { |
231 // Recalculate the next wakeup time. For repeating timers with a 0 timeout | 216 // Recalculate the next wakeup time. For repeating timers with a 0 timeout |
232 // the next wakeup time is now. | 217 // the next wakeup time is now. |
233 _id = _nextId(); | 218 _id = _nextId(); |
234 if (_milliSeconds > 0) { | 219 if (_milliSeconds > 0) { |
235 _wakeupTime += _milliSeconds; | 220 _wakeupTime += _milliSeconds; |
236 } else { | 221 } else { |
237 _wakeupTime = VMLibraryHooks.timerMillisecondClock(); | 222 _wakeupTime = VMLibraryHooks.timerMillisecondClock(); |
238 } | 223 } |
239 } | 224 } |
240 | 225 |
241 | |
242 // Adds a timer to the heap or timer list. Timers with the same wakeup time | 226 // Adds a timer to the heap or timer list. Timers with the same wakeup time |
243 // are enqueued in order and notified in FIFO order. | 227 // are enqueued in order and notified in FIFO order. |
244 void _enqueue() { | 228 void _enqueue() { |
245 if (_milliSeconds == 0) { | 229 if (_milliSeconds == 0) { |
246 if (_firstZeroTimer == null) { | 230 if (_firstZeroTimer == null) { |
247 _lastZeroTimer = this; | 231 _lastZeroTimer = this; |
248 _firstZeroTimer = this; | 232 _firstZeroTimer = this; |
249 } else { | 233 } else { |
250 _lastZeroTimer._indexOrNext = this; | 234 _lastZeroTimer._indexOrNext = this; |
251 _lastZeroTimer = this; | 235 _lastZeroTimer = this; |
252 } | 236 } |
253 // Every zero timer gets its own event. | 237 // Every zero timer gets its own event. |
254 _notifyZeroHandler(); | 238 _notifyZeroHandler(); |
255 } else { | 239 } else { |
256 _heap.add(this); | 240 _heap.add(this); |
257 if (_heap.isFirst(this)) { | 241 if (_heap.isFirst(this)) { |
258 _notifyEventHandler(); | 242 _notifyEventHandler(); |
259 } | 243 } |
260 } | 244 } |
261 } | 245 } |
262 | 246 |
263 | |
264 // Enqeue one message for each zero timer. To be able to distinguish from | 247 // Enqeue one message for each zero timer. To be able to distinguish from |
265 // EventHandler messages we send a _ZERO_EVENT instead of a _TIMEOUT_EVENT. | 248 // EventHandler messages we send a _ZERO_EVENT instead of a _TIMEOUT_EVENT. |
266 static void _notifyZeroHandler() { | 249 static void _notifyZeroHandler() { |
267 if (_sendPort == null) { | 250 if (_sendPort == null) { |
268 _createTimerHandler(); | 251 _createTimerHandler(); |
269 } | 252 } |
270 _sendPort.send(_ZERO_EVENT); | 253 _sendPort.send(_ZERO_EVENT); |
271 } | 254 } |
272 | 255 |
273 | |
274 // Handle the notification of a zero timer. Make sure to also execute non-zero | 256 // Handle the notification of a zero timer. Make sure to also execute non-zero |
275 // timers with a lower expiration time. | 257 // timers with a lower expiration time. |
276 static List _queueFromZeroEvent() { | 258 static List _queueFromZeroEvent() { |
277 var pendingTimers = new List(); | 259 var pendingTimers = new List(); |
278 assert(_firstZeroTimer != null); | 260 assert(_firstZeroTimer != null); |
279 // Collect pending timers from the timer heap that have an expiration prior | 261 // Collect pending timers from the timer heap that have an expiration prior |
280 // to the currently notified zero timer. | 262 // to the currently notified zero timer. |
281 var timer; | 263 var timer; |
282 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { | 264 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { |
283 timer = _heap.removeFirst(); | 265 timer = _heap.removeFirst(); |
284 pendingTimers.add(timer); | 266 pendingTimers.add(timer); |
285 } | 267 } |
286 // Append the first zero timer to the pending timers. | 268 // Append the first zero timer to the pending timers. |
287 timer = _firstZeroTimer; | 269 timer = _firstZeroTimer; |
288 _firstZeroTimer = timer._indexOrNext; | 270 _firstZeroTimer = timer._indexOrNext; |
289 timer._indexOrNext = null; | 271 timer._indexOrNext = null; |
290 pendingTimers.add(timer); | 272 pendingTimers.add(timer); |
291 return pendingTimers; | 273 return pendingTimers; |
292 } | 274 } |
293 | 275 |
294 | |
295 static void _notifyEventHandler() { | 276 static void _notifyEventHandler() { |
296 if (_handlingCallbacks) { | 277 if (_handlingCallbacks) { |
297 // While we are already handling callbacks we will not notify the event | 278 // While we are already handling callbacks we will not notify the event |
298 // handler. _handleTimeout will call _notifyEventHandler once all pending | 279 // handler. _handleTimeout will call _notifyEventHandler once all pending |
299 // timers are processed. | 280 // timers are processed. |
300 return; | 281 return; |
301 } | 282 } |
302 | 283 |
303 // If there are no pending timers. Close down the receive port. | 284 // If there are no pending timers. Close down the receive port. |
304 if ((_firstZeroTimer == null) && _heap.isEmpty) { | 285 if ((_firstZeroTimer == null) && _heap.isEmpty) { |
(...skipping 12 matching lines...) Expand all Loading... |
317 | 298 |
318 // Only send a message if the requested wakeup time differs from the | 299 // Only send a message if the requested wakeup time differs from the |
319 // already scheduled wakeup time. | 300 // already scheduled wakeup time. |
320 var wakeupTime = _heap.first._wakeupTime; | 301 var wakeupTime = _heap.first._wakeupTime; |
321 if ((_scheduledWakeupTime == null) || | 302 if ((_scheduledWakeupTime == null) || |
322 (wakeupTime != _scheduledWakeupTime)) { | 303 (wakeupTime != _scheduledWakeupTime)) { |
323 _scheduleWakeup(wakeupTime); | 304 _scheduleWakeup(wakeupTime); |
324 } | 305 } |
325 } | 306 } |
326 | 307 |
327 | |
328 static List _queueFromTimeoutEvent() { | 308 static List _queueFromTimeoutEvent() { |
329 var pendingTimers = new List(); | 309 var pendingTimers = new List(); |
330 if (_firstZeroTimer != null) { | 310 if (_firstZeroTimer != null) { |
331 // Collect pending timers from the timer heap that have an expiration | 311 // Collect pending timers from the timer heap that have an expiration |
332 // prior to the next zero timer. | 312 // prior to the next zero timer. |
333 // By definition the first zero timer has been scheduled before the | 313 // By definition the first zero timer has been scheduled before the |
334 // current time, meaning all timers which are "less than" the first zero | 314 // current time, meaning all timers which are "less than" the first zero |
335 // timer are expired. The first zero timer will be dispatched when its | 315 // timer are expired. The first zero timer will be dispatched when its |
336 // corresponding message is delivered. | 316 // corresponding message is delivered. |
337 var timer; | 317 var timer; |
338 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { | 318 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { |
339 timer = _heap.removeFirst(); | 319 timer = _heap.removeFirst(); |
340 pendingTimers.add(timer); | 320 pendingTimers.add(timer); |
341 } | 321 } |
342 } else { | 322 } else { |
343 // Collect pending timers from the timer heap which have expired at this | 323 // Collect pending timers from the timer heap which have expired at this |
344 // time. | 324 // time. |
345 var currentTime = VMLibraryHooks.timerMillisecondClock(); | 325 var currentTime = VMLibraryHooks.timerMillisecondClock(); |
346 var timer; | 326 var timer; |
347 while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) { | 327 while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) { |
348 timer = _heap.removeFirst(); | 328 timer = _heap.removeFirst(); |
349 pendingTimers.add(timer); | 329 pendingTimers.add(timer); |
350 } | 330 } |
351 } | 331 } |
352 return pendingTimers; | 332 return pendingTimers; |
353 } | 333 } |
354 | 334 |
355 | |
356 static void _runTimers(List pendingTimers) { | 335 static void _runTimers(List pendingTimers) { |
357 // If there are no pending timers currently reset the id space before we | 336 // If there are no pending timers currently reset the id space before we |
358 // have a chance to enqueue new timers. | 337 // have a chance to enqueue new timers. |
359 if (_heap.isEmpty && (_firstZeroTimer == null)) { | 338 if (_heap.isEmpty && (_firstZeroTimer == null)) { |
360 _idCount = 0; | 339 _idCount = 0; |
361 } | 340 } |
362 | 341 |
363 // Fast exit if no pending timers. | 342 // Fast exit if no pending timers. |
364 if (pendingTimers.length == 0) { | 343 if (pendingTimers.length == 0) { |
365 return; | 344 return; |
(...skipping 29 matching lines...) Expand all Loading... |
395 if (immediateCallback != null) { | 374 if (immediateCallback != null) { |
396 immediateCallback(); | 375 immediateCallback(); |
397 } | 376 } |
398 } | 377 } |
399 } | 378 } |
400 } finally { | 379 } finally { |
401 _handlingCallbacks = false; | 380 _handlingCallbacks = false; |
402 } | 381 } |
403 } | 382 } |
404 | 383 |
405 | |
406 static void _handleMessage(msg) { | 384 static void _handleMessage(msg) { |
407 var pendingTimers; | 385 var pendingTimers; |
408 if (msg == _ZERO_EVENT) { | 386 if (msg == _ZERO_EVENT) { |
409 pendingTimers = _queueFromZeroEvent(); | 387 pendingTimers = _queueFromZeroEvent(); |
410 assert(pendingTimers.length > 0); | 388 assert(pendingTimers.length > 0); |
411 } else { | 389 } else { |
412 assert(msg == _TIMEOUT_EVENT); | 390 assert(msg == _TIMEOUT_EVENT); |
413 _scheduledWakeupTime = null; // Consumed the last scheduled wakeup now. | 391 _scheduledWakeupTime = null; // Consumed the last scheduled wakeup now. |
414 pendingTimers = _queueFromTimeoutEvent(); | 392 pendingTimers = _queueFromTimeoutEvent(); |
415 } | 393 } |
416 _runTimers(pendingTimers); | 394 _runTimers(pendingTimers); |
417 // Notify the event handler or shutdown the port if no more pending | 395 // Notify the event handler or shutdown the port if no more pending |
418 // timers are present. | 396 // timers are present. |
419 _notifyEventHandler(); | 397 _notifyEventHandler(); |
420 } | 398 } |
421 | 399 |
422 | |
423 // Tell the event handler to wake this isolate at a specific time. | 400 // Tell the event handler to wake this isolate at a specific time. |
424 static void _scheduleWakeup(int wakeupTime) { | 401 static void _scheduleWakeup(int wakeupTime) { |
425 if (_sendPort == null) { | 402 if (_sendPort == null) { |
426 _createTimerHandler(); | 403 _createTimerHandler(); |
427 } | 404 } |
428 VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime); | 405 VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime); |
429 _scheduledWakeupTime = wakeupTime; | 406 _scheduledWakeupTime = wakeupTime; |
430 } | 407 } |
431 | 408 |
432 | |
433 // Cancel pending wakeups in the event handler. | 409 // Cancel pending wakeups in the event handler. |
434 static void _cancelWakeup() { | 410 static void _cancelWakeup() { |
435 assert(_sendPort != null); | 411 assert(_sendPort != null); |
436 VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER); | 412 VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER); |
437 _scheduledWakeupTime = null; | 413 _scheduledWakeupTime = null; |
438 } | 414 } |
439 | 415 |
440 | |
441 // Create a receive port and register a message handler for the timer | 416 // Create a receive port and register a message handler for the timer |
442 // events. | 417 // events. |
443 static void _createTimerHandler() { | 418 static void _createTimerHandler() { |
444 assert(_receivePort == null); | 419 assert(_receivePort == null); |
445 assert(_sendPort == null); | 420 assert(_sendPort == null); |
446 _receivePort = new RawReceivePort(_handleMessage); | 421 _receivePort = new RawReceivePort(_handleMessage); |
447 _sendPort = _receivePort.sendPort; | 422 _sendPort = _receivePort.sendPort; |
448 _scheduledWakeupTime = null; | 423 _scheduledWakeupTime = null; |
449 } | 424 } |
450 | 425 |
451 | |
452 static void _shutdownTimerHandler() { | 426 static void _shutdownTimerHandler() { |
453 _receivePort.close(); | 427 _receivePort.close(); |
454 _receivePort = null; | 428 _receivePort = null; |
455 _sendPort = null; | 429 _sendPort = null; |
456 _scheduledWakeupTime = null; | 430 _scheduledWakeupTime = null; |
457 } | 431 } |
458 | 432 |
459 | |
460 // The Timer factory registered with the dart:async library by the embedder. | 433 // The Timer factory registered with the dart:async library by the embedder. |
461 static Timer _factory(int milliSeconds, | 434 static Timer _factory( |
462 void callback(Timer timer), | 435 int milliSeconds, void callback(Timer timer), bool repeating) { |
463 bool repeating) { | |
464 if (repeating) { | 436 if (repeating) { |
465 return new _Timer.periodic(milliSeconds, callback); | 437 return new _Timer.periodic(milliSeconds, callback); |
466 } | 438 } |
467 return new _Timer(milliSeconds, callback); | 439 return new _Timer(milliSeconds, callback); |
468 } | 440 } |
469 } | 441 } |
470 | 442 |
471 | |
472 _setupHooks() { | 443 _setupHooks() { |
473 VMLibraryHooks.timerFactory = _Timer._factory; | 444 VMLibraryHooks.timerFactory = _Timer._factory; |
474 } | 445 } |
OLD | NEW |